Lubisz grać w szachy? Podobał ci się chess.com lub lichess? W takim razie pokochasz KoksSzachy! <3
Project description
chess.com pls don't sue us, it's for fun
Index
- Instalacja i update
- Jak zagrać?
- Testujesz?
- Jak to działa?
- Minimax
- Różnice depth w algorytmie minimax
- Terminologia
- Selfplay
Instalacja i update
Do zainstalowania KoksSzachów wymagany jest pobrany Python 3.7
lub nowszy oraz pip
odpowiadjący wersji Pythona, czyli pythonowy package manager.
Unix
$ pip3 install koksszachy --upgrade
Windows
$ pip install koksszachy --upgrade
Jak zagrać?
Online
Wystarczy otworzyć nową kartę w przeglądarce i udać się pod adres koks-szachy.herokuapp.com
pip package
$ koksszachy -p
# lub
$ koksszachy --play
Lokalnie
cd koksszachy
./play.py
PROTIP: Jeśli debugujesz, to ci się przyda.
$ DEBUG=1 ./play.py
Testujesz?
$ python3 -m pytest -v
Jak to działa?
Silnik KoksSzachów działa na bardzo prostej zasadzie:
-
Pobranie pozycji chessboard.js za pomocą wpisywania w url FEN stringów.
-
Rekreacja pozycji w bibliotece python-chess, która umożliwia stworzenie listy możliwych ruchów i wiele innych, które przydadzą się w algorytmie Minimax.
-
Ewaluacja materiału. Działa ona na podstawie zliczania wartości wszystkich bierek na planszy. Wartości te są przedstawione w słowniku
values
. -
Ewaluacja pozycji odtworzonej przez wspomnianą wcześniej bibliotekę przy pomocy FEN stringa. Jest ona robiona na podstawie słownika
positions
.-
Jak to działa? To bardzo proste - w słowniku dla każdej figury istnieje odpowiadający jej dwuwymiarowy array z liczbami całkowitymi. Array odpowiada prawdziwym rozmiarom szachownicy czyli 8x8. Weźmy dla przykładu array poświęcony gońcowi. Specjalnie zaznaczona została notacja szachowa dla ułatwienia wizualizacji.
chess.BISHOP: [ -20,-10,-10,-10,-10,-10,-10,-20, -10, 0, 0, 0, 0, 0, 0,-10, -10, 0, 5, 10, 10, 5, 0,-10, -10, 5, 5, 10, 10, 5, 5,-10, -10, 0, 10, 10, 10, 10, 0,-10, -10, 10, 10, 10, 10, 10, 10,-10, -10, 5, 0, 0, 0, 0, 5,-10, -20,-10,-10,-10,-10,-10,-10,-20 ],
Wartości pochodzą z tego artykułu
Łatwo zauważyć, że każdy z narożników szachownicy ma bardzo niskie wartości. To dlatego, że goniec stając na nich traci możliwość poruszania się po dwóch przekątnych tylko do jednej.
Zagłębiając się w wartości tej czy innych figur można dostrzec wiele innych wariantów.Arraye są przedstawione z perspektywy pierwszej osoby.
-
-
Gdy białe - gracz, wykonają ruch, czarne - czyli komputer analizują pozycje i materiał zapisując obecną wartość ogólną. Po tym procesie uruchamiany jest algorytm Minimax, który analizuje przyszłe i możliwe posunięcia przeciwnika po wykonanym ruchu. W ten sposób algorytm ocenia, który ruch jest dla niego najlepszy. To na ile posunięć do przodu liczy jest kontrolowane przez zmienną
depth
. -
Obliczone ruchy są zapisywane w odpowiedniej kolejności.
-
Komputer wybiera pierwszy ruch z listy i go wykonuje.
-
Wszystko działa dopóki są możliwe ruchy. Nie działa to na podstawie pętli.
Minimax
Ty, jako gracz, grasz białymi figurami. Minimax jest wywoływany przez gracza maksymalizującego wynik, w tym przypadku są to czarne figury, czyli komputer. Scenariusz, w którym grasz maksymalizujący wygrywa ma przypisaną warość nieskończoną. Idąc tym schematem przegrana dla gracza maksymalizującego ma wartość ujemnej nieskończoności.
Minimax w KoksSzachach jest zooptymlizowany poprzez alpha-beta pruning oraz iterative deepening.
Ciekawe artykuły i źródła na temat tych algorytmów:
- https://www.youtube.com/watch?v=dQw4w9WgXcQ
- https://pl.wikipedia.org/wiki/Algorytm_min-max
- https://www.cs.cornell.edu/courses/cs312/2002sp/lectures/rec21.htm
- https://www.cs.tau.ac.il/~wolf/papers/deepchess.pdf
- https://en.wikipedia.org/wiki/Evaluation_function#In_chess
- https://www.chessprogramming.org/Simplified_Evaluation_Function
- https://www.youtube.com/watch?v=JnXKZYFmGOg
- https://www.freecodecamp.org/news/simple-chess-ai-step-by-step-1d55a9266977/
- https://towardsdatascience.com/how-a-chess-playing-computer-thinks-about-its-next-move-8f028bd0e7b1
- https://andreasstckl.medium.com/writing-a-chess-program-in-one-day-30daff4610ec
- https://pl.wikipedia.org/wiki/Algorytm_alfa-beta
- https://www.chessprogramming.org/Iterative_Deepening
- https://www.youtube.com/watch?v=STjW3eH0Cik
- https://www.chessprogramming.org/Branching_Factor
- https://www.flyingmachinestudios.com/programming/minimax/
- https://athena.ecs.csus.edu/~gordonvs/papers/trappy.pdf
Różnice depth w algorytmie minimax
Przeprowadziłem prosty eksperyment polegający na mierzeniu różnic czasowych i eksploracyjnych pomiędzy wartościami depth.
Najniższą możliwą wartością depth jest 1
. Zakładając, że mierzymy wszystkie wartości dla klasycznego i każdemu znango ruchu e4
, wartość zmiennej leaves_explored
, czyli jednym słowem możliwe rozwinięcia dla danej sytuacji, wynosi 20
rozwinięć.
I jeśli rzeczywiście popatrzymy na szachownicę, ta wartość się jak najbardziej zgadza.
Jeśli porównamy wartości depth od 1-8
to zobaczymy prawdziwe różnice.
Chciałem tutaj dać piękny wykres matplotliba, ale nie udało mi się.
Depth | Leaves | Czas(s) |
---|---|---|
1 | 20 | 0.004 |
2 | 102 | 0.014 |
3 | 1233 | 0.086 |
4 | 22884 | 1.563 |
5 | 197047 | 13.232 |
6 | 768488 | 51.222 |
7 | 12713930 | 886.259 |
8 | 78510963 | 5392.2 |
Terminologia
Przyjrzyjmy się zdjęciu tego drzewka:
W tym przypadku wartość depth
będzie wynosiła 3
, ponieważ drzewko zagłębia się na 3 poziomy.
Node
, to są punkty na drzewku, w KoksSzachach jest to legalny ruch. Istnieją dwa pojęcia na tą wartość:
-
leaf nodes
,terminal nodes
Są to punkty, w których drzewko się kończy. W tym przypadku są to wszytkie punkty na samym dole przy
depth
równemu3
i jest ich8
. -
root node
Na drzewku zawsze istnieje taki jeden punkt. W przypadku szachów jest to pozycja, w której obecnie jesteśmy. Od niego rozchodzi się całe drzewko.
-
internal nodes
,non-leaf nodes
Są to wszystkie punkty na drzewku, nie licząc
leaf nodes
. Jak sama nazwa mowi są to punkty "wewnętrzne".
W algorytmie minimax istnieje takie pojęcie jak branching factor
. Jest to średnia ilość dzieci każdego z punktów na danej głębokości. Na naszym przykładowym drzewku jest to 2
. Ponieważ każdy punkt ma przypisane 2 inne punkty. Oczywiście branching factor
w szachach nie jest stały i się zmienia zależnie od pozycji oraz tego czy ucinamy pewne rozwinięcia z alpha-beta. Średnio wynosi on od 31 do 35. Branching factor
można obliczyć w taki sposób:
The average branching factor can be quickly calculated as the number of non-root nodes (the size of the tree, minus one; or the number of edges) divided by the number of non-leaf nodes (the number of nodes with children).
Zatem w przypadku przykładowego drzewka możemy tą formułę:
>> # (len(tree)-1)/leaves
>> (15-1)/7
2.0
Selfplay
Przez selfplay mam na myśli komputer grający z komputerem. Będą to dwa oddzielne, lub jeden ten sam proces KoksSzachów
.
Zasada działania
- Biały wykonuje obliczony ruch ze startowego FEN stringa.
- Czarny pobiera zmieniony FEN i na jego podstawie oblicza swój ruch.
- Punkty 1 oraz 2 zapętlają się dopóki wartość
game.is_game_over()
jestTrue
.
Problemy
- Czy gra ma się zaczynać gdy strona się załaduje, czy po kliknięciu przycisku?
- Wydaje mi się, że można zrobić to na początku w formie tylko "terminalowej", a potem spróbować popchnąć to tak, żeby obejmowała to biblioteka
chessboard.js
.
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
File details
Details for the file KoksSzachy-0.8.52.tar.gz
.
File metadata
- Download URL: KoksSzachy-0.8.52.tar.gz
- Upload date:
- Size: 250.7 kB
- Tags: Source
- Uploaded using Trusted Publishing? No
- Uploaded via: twine/3.1.1 pkginfo/1.4.2 requests/2.22.0 setuptools/45.2.0 requests-toolbelt/0.8.0 tqdm/4.30.0 CPython/3.8.5
File hashes
Algorithm | Hash digest | |
---|---|---|
SHA256 | ebd25335e082276b8fb16ea60fb297e140f176d84074fe8d5a1179cf18638876 |
|
MD5 | d906fcd57bfed81a38b383b8eaba1729 |
|
BLAKE2b-256 | cc504a1719e02b094463ffa4cdc5130c46d77258e58504ab28aa904f50b57084 |
File details
Details for the file KoksSzachy-0.8.52-py3-none-any.whl
.
File metadata
- Download URL: KoksSzachy-0.8.52-py3-none-any.whl
- Upload date:
- Size: 257.8 kB
- Tags: Python 3
- Uploaded using Trusted Publishing? No
- Uploaded via: twine/3.1.1 pkginfo/1.4.2 requests/2.22.0 setuptools/45.2.0 requests-toolbelt/0.8.0 tqdm/4.30.0 CPython/3.8.5
File hashes
Algorithm | Hash digest | |
---|---|---|
SHA256 | d434c453172df21e2f480790d38f6d4dab18c4644a47f3c614d12a8cb205c361 |
|
MD5 | e51fec2a518f5407040ce4973908c5c2 |
|
BLAKE2b-256 | 74708b31bc78dd9f28ded792a7028016a9f82397ed048999a18644cb1fadb9bd |