Skip to main content

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

Linux OSX Windows 10 Python PyPI

Index


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:

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:

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

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

KoksSzachy-0.8.52.tar.gz (250.7 kB view hashes)

Uploaded Source

Built Distribution

KoksSzachy-0.8.52-py3-none-any.whl (257.8 kB view hashes)

Uploaded Python 3

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page