_{chess.com pls don't sue us, it's for fun}

Index

• Instalacja i update
  • Unix
  • Windows
• Jak zagrać?
  • Online
  • pip package
  • Lokalnie
• Testujesz?
• Jak to działa?
• Minimax
• Różnice depth w algorytmie minimax
• Terminologia
• Selfplay
  • Zasada działania
  • Problemy

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ę.

Terminologia

Przyjrzyjmy się zdjęciu tego drzewka:

_źródło

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ównemu 3 i jest ich 8.

• 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

1. Biały wykonuje obliczony ruch ze startowego FEN stringa.
2. Czarny pobiera zmieniony FEN i na jego podstawie oblicza swój ruch.
3. Punkty 1 oraz 2 zapętlają się dopóki wartość game.is_game_over() jest True.

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.