Spis treści:
- 1 Piękno szachów
- 2 Trudność gry? Szachy są tak naprawdę dla każdego
- 3 Szachy komputerowe
- 4 Program Stockfish i ranking szachowy Elo
- 5 Rozwiązywanie szachów, czyli chess solving, i czy to w ogóle możliwe
- 6 Algorytm szachowy - jak to działa?
- 7 Superkomputery i szachy
- 8 Szachy i sztuczna inteligencja, czyli deep learning
- 9 Czy człowiek dorówna komputerowi?
Filadelfia w USA, stan Pensylwania, rok 1997. Świat z niedowierzaniem patrzy, jak arcymistrz Garry Kasparov, prawdopodobnie najlepszy szachista w historii, po pierwszych zwycięstwach przegrywa kolejne mecze z komputerem IBM Deep Blue. Rozpoczyna się era silników szachowych, która na zawsze zmienia obraz tej wspaniałej gry.
Na początek rozróżnienie – trudno zdefiniować mądrość. Powszechnie postrzegana jest jako umiejętność podejmowania uzasadnionych decyzji życiowych na podstawie posiadanej wiedzy i doświadczenia. Wcale nie łatwiej jest z inteligencją – według wielu “być inteligentnym” to pustosłowie, inni poszukują bezpiecznych definicji w rozróżnieniu rodzajów inteligencji. Jeżeli mamy się dziś zajmować inteligencją, to zdecydowanie w ujęciu matematyczno-logicznym. To właśnie na takiej biegłości opiera się gra wszechczasów, którą są szachy. Gra zresztą nieobca wielu programistom.
Jason Statham, cytat z fikcyjnej książki "Fundamentals of Chess 1883", kadr z filmu Revolver (2005)
Minimax (czasami minmax), czyli metoda minimalizowania maksymalnych możliwych strat albo alternatywnie maksymalizacja minimalnego zysku (maximin), to jedna z podwalin przewidywania w szachach i punkt wyjścia do konstruowania coraz to lepszych algorytmów grających. Wywodzi się to z teorii gry o sumie zerowej i obejmuje dwie “organizacje” ruchów: zarówno tę, w której gracze wykonują ruchy naprzemiennie, jak i tę, gdzie ruchy wykonuje się jednocześnie. Przyjrzyjmy się dzisiaj temu, jak z podejmowaniem decyzji w obliczu niepewności radzą sobie ludzie, a jak komputery. Ile “inteligencji” jako ich twórcy zdołaliśmy im dotychczas przekazać?
Piękno szachów
Cały świat słyszał o szachach. Są jak Coca-Cola. Według informacji z 2020 roku na portalu chess.com w szachy gra regularnie ponad 600 milionów dorosłych. Liczba porównywalna do regularnych użytkowników portalu Facebook. Według The Encyclopedia of Chess Variants z 2007 roku istnieje ponad 2000 wariantów gry. Usłyszeliśmy kiedyś, że gry takie jak szachy, poker czy brydż różni od nowoczesnych gier planszowych, karcianych czy bitewniaków ważna sprawa – ta druga grupa to nie są gry, w które będziecie grali przez następne 50 lat swojego życia. Coś w tym jest.
Szachy to rekreacyjna i konkurencyjna gra planszowa rozgrywana pomiędzy dwoma graczami. Czasami nazywana jest szachami zachodnimi lub międzynarodowymi, aby odróżnić ją od pokrewnych gier, takich jak xiangqi. Obecnie rozgrywana forma szachów pojawiła się w południowej Europie w drugiej połowie XV wieku po wyewoluowaniu z podobnych, znacznie starszych gier pochodzenia indyjskiego i perskiego. Obecnie szachy są jedną z najpopularniejszych gier na świecie, w którą grają miliony – w domach, w klubach, online, korespondencyjnie i na turniejach.
To przede wszystkim abstrakcyjna gra strategiczna, która nie zawiera żadnych ukrytych informacji. Nie ma tu elementu zagadki, nie ma elementu szczęścia albo pecha, czyli losowości – są tylko czyste umiejętności logicznego myślenia. Na początku każdy z graczy, czyli jeden kontrolujący białe, a drugi czarne figury, kontroluje szesnaście bierek. To figury i piony: jeden król, jedna królowa (hetman), dwie wieże, dwa gońce (laufer, feudał, biskup), dwa skoczki (koń, rycerz) i osiem pionów. Jest tu też pewne piękne przesłanie: pion, który przemaszeruje całą szachownicę i osiągnie ostatnią linię, staje się hetmanem/królową lub dowolną, wybraną przez gracza figurą.
Celem gry jest zaszachowanie i w konsekwencji zamatowanie króla przeciwnika. Mat to sytuacja, w której król jest natychmiast atakowany (król jest w “szachu”) i nie ma sposobu, aby usunąć go z atakowanego pola w następnym ruchu. Istnieje również kilka sposobów na zakończenie gry remisem. To właśnie te chłodno przewidywalne cechy sprawiają, że szachy są idealną przestrzenią do testowania algorytmiki.
Trudność gry? Szachy są tak naprawdę dla każdego
Być może powinniśmy powiedzieć raczej: złożoność gry. Trudny do pokonania może okazać się przeciwnik, ponieważ zasady gry w szachy wcale trudne do pojęcia nie są. Istnieje jednak znaczne rozróżnienie pomiędzy znaniem reguł rządzących grą w szachy, a graniem w szachy po prostu… dobrze. Tak jak w grze z elementem losowym i strategicznym pokerzysta Texas Hold’em oblicza prawdopodobieństwo na to, czy na stole pojawi się brakująca do układu karta, tak szachista nie jest w stanie rozpatrzyć wszystkich możliwych wariantów partii szachowej od jej początku do końca. Ale próbować powinien.
Poniżej możliwa ilość kontynuacji ruchów, która da nam pogląd na wielkości, na jakich tu operujemy:
♞♞♞ po 3 posunięciach (ostatnie posunięcie białych)
♞♞♞♞ po 4 posunięciach (ostatnie posunięcie czarnych)
♞♞♞♞♞ po 5 posunięciach (ostatnie posunięcie białych)
♞♞♞♞♞♞ po 6 posunięciach (ostatnie posunięcie czarnych)
♞♞♞♞♞♞♞ po 7 posunięciach (ostatnie posunięcie białych)
♞♞♞♞♞♞♞♞ po 8 posunięciach (ostatnie posunięcie czarnych)
8902
197 281
4 865 609
119 060 324
3 195 901 860
84 998 978 956
Przyprawia o zawrót głowy, prawda? Po tym jak każdy z graczy poruszył się 5 razy, istnieje 69 352 859 712 417 możliwych gier, które mogły (mogłyby?) zostać rozegrane. Biorąc pod uwagę obliczenia amerykańskiego matematyka Claude’a Shannona, to jeśli przeanalizuje się szachy pod kątem liczby “sensownych” partii, które można rozegrać (nie licząc niedorzecznych, ewidentnie przegrywających grę ruchów, np. ruchu królową, która zostaje zbita za piona bez rekompensaty), wynik jest bliski ok. 10^40 partiom. Szacunek ten opiera się na możliwości wyboru około trzech sensownych ruchów i długości gry wynoszącej 80 ruchów. Cóż, ponad 1000 gier i miliardowe wartości z powyższego zestawienia – resztę liczenia pozostawiamy Wam.
Szachy komputerowe
Szachy komputerowe obejmują zarówno sprzęt, czyli specjalne przeznaczone do nich komputery, jak i szachowe boty – oprogramowanie umożliwiające grę. Szachy komputerowe dają graczom możliwość ćwiczenia nawet przy braku ludzkich przeciwników, a także zapewniają możliwość analizy, rozrywki i treningu. Jest też w graniu z komputerem coś uspokajającego – niektórzy wolą to od gry z ludzkim przeciwnikiem, przed którym można się zwyczajnie zbłaźnić. Oczywiście nie powinno to nikogo hamować, ale też nie należy dawać początkującym “fory” – w końcu komputer nikomu jej nie daje.
Pierwsze maszyny z lat 50. z ery komputerów lampowych grały tak słabo, że mógł pokonać je nawet początkujący, a silniki szachowe z drugiej połowy lat 90. to już naprawdę wyspecjalizowany sprzęt, czego dowodzi przywołany w nagłówku artykułu mecz Kasparova z IBM Deep Blue. Aplikacje do gry w szachy komputerowe, które grają na poziomie mistrza szachowego lub wyższym, są dostępne na sprzęcie od superkomputerów po smartfony. Dostępne są również samodzielne maszyny do gry w szachy. Stockfish, GNU Chess, Fruit i inne wolne aplikacje open source są dostępne na różne platformy. Spójrzmy na nasz ulubiony – Stockfisha.
Program Stockfish i ranking szachowy Elo
Stockfish to darmowy silnik szachowy o otwartym kodzie źródłowym dostępny na różne platformy stacjonarne i mobilne. Oprócz jego ojców wkład w możliwości silnika ma także szeroka społeczność programistów open-source. Stockfish pozostaje na pierwszym miejscu lub w pobliżu szczytu większości list rankingowych podobnego oprogramowania. Zgodnie uważa się, że jest najsilniejszym silnikiem szachowym CPU. Wygrał nieoficjalne mistrzostwa świata w szachach komputerowych w sezonach 6 (2014), 9 (2016), 11 (2018), 12 (2018), 13 (2018), 14 (2019), 16 (2019), 18 (2020), 19 (2020) i 20 (2021), w pozostałych zdobył wicemistrzostwo.
Stockfish może używać do 512 wątków CPU w systemach wieloprocesorowych, implementuje zaawansowane wyszukiwanie alfa-beta i wykorzystuje tablice bitowe. W porównaniu z innymi silnikami charakteryzuje się jeszcze lepszą głębokością przeszukiwania częściowo dzięki bardziej agresywnej grze. Ciekawostka: obsługuje też mocno losowy wariant Chess960.
Czy naprawdę Stockfish jest aż tak dobry? Spójrzmy na to tak: najpierw potrzebujemy rankingu Elo. Nie ma on nic wspólnego z młodzieżowym przywitaniem, ale na start “Elo”, czyli na początek, nowicjusz nie jest rankingowany. Ranking Elo gracza jest reprezentowany przez liczbę, która może się zmieniać w zależności od wyniku ocenianych gier. Po każdej grze gracz wygrywający odbiera punkty graczowi przegrywającemu. Różnica pomiędzy ratingami zwycięzcy i przegranego określa całkowitą liczbę punktów zdobytych lub straconych po meczu. Jeśli wygra gracz z wyższą oceną, wtedy tylko kilka punktów ratingowych zostanie odebranych graczowi z niższą oceną.
Jeśli niżej sklasyfikowany gracz wygra, zostanie przeniesionych wiele punktów ratingowych. Niżej sklasyfikowany gracz zyskuje również nieco punktów od wyżej sklasyfikowanego gracza w przypadku remisu. Oznacza to, że ten system ratingowy jest samonaprawiający się. Gracze, których ratingi są zbyt niskie lub zbyt wysokie, powinni w dłuższej perspektywie radzić sobie lepiej lub gorzej niż przewiduje system ratingowy, a tym samym zyskiwać lub tracić punkty ratingowe, aż te zaczną odzwierciedlać ich prawdziwą siłę w grze. I tak dalej, i tak dalej. Ranking przeszedł wiele przemian i jest tylko klasyfikacją porównawczą dla puli, w której został ustalony, ale to nadal najlepszy, oficjalny i powszechnie stosowany sposób oceny szachistów.
Spójrzmy teraz na zestawienie pierwszych ośmiu miejsc, którą podaje Międzynarodowa Federacja Szachowa FIDE.
Najlepsi zawodnicy wariantu Standard wg FIDE, stan z kwietnia 2021 roku
- Magnus Carlsen, Norwegia – Elo 2847
- Fabiano Caruana, USA – Elo 2820
- Liren Ding, Chiny – Elo 2791
- Ian Nepomniachtchi, Rosja – Elo 2789
- Levon Aronian, Armenia – Elo 2781
- Alexander Grischuk, Rosja – Elo 2777
- Anish Giri, Holandia – Elo 2776
- Shakhriyar Mamedyarov, Azerbejdżan – Elo 2770
Garri Kasparov wróżył Carlsenowi osiągnięcie rankingu 2900, gdyby tylko ten “zaczął pracować na poważnie”. Teraz, znając sposób klasyfikacji rankingu Elo z poprzedniego akapitu… Stockfish posiada ranking 3516, o kilkaset punktów wyższy, niż obecny arcymistrz światowy i prawdopodobnie najlepszy gracz w historii.
Inne najlepsze programy szachowe, które w ostatnich latach znacząco rozwinęły swoje możliwości obliczeniowe, to:
- Komodo (Elo +3400)
- Houdini 6 (Elo +3400)
- Fire 7.1 (Elo +3300)
- Deep Shredder (Elo +3200)
Obecnie wielu profesjonalnych szachistów spędza dużo czasu na pracy z komputerem. Uznaje się, że każdy ambitny gracz powinien spróbować zagrać z silnym silnikiem szachowym choćby z tego względu, że pozwalają one na rozpoczęcie gry z dowolnie wybranej pozycji, praktycznie nieskończoną (życia nie starczy) naukę najlepszych wariantów posunięć i zapobiegnięcie stagnacji, jeżeli nie mamy zbyt wielu partnerów do gry. Z drugiej strony do tego samego może doprowadzić lenistwo i nadużywanie takich narzędzi. Jeżeli wierzyć ogólnym opiniom płynącym ze środowiska, rośnie liczba szachistów amatorów, którzy nie myślą samodzielnie o danej pozycji szachowej, lecz w pierwszej kolejności zwracają uwagę na opiniowanie maszyny. Czyż wśród programistów i koderów nie jest to podobnie zgubny nawyk?
Rozwiązywanie szachów, czyli chess solving, i czy to w ogóle możliwe
Zastanówmy się: skoro istnieje wiele gier, które są rozwiązywalne i zostały rozwiązane, czy istnieje matematyczne rozwiązanie dla szachów? Cóż, matematycznie jest to z pewnością możliwe. Przykładem rozwiązanej gry jest kółko i krzyżyk, w której istnieje sprawdzony sposób na wygraną, jeśli gra się jako pierwszy, lub remis za każdym razem, niezależnie od tego, czy gra się jako pierwszy, czy jako drugi.
Czy przy zastosowaniu tej samej logiki możliwe byłoby wykonanie pewnej sekwencji ruchów w szachach, która gwarantowałaby wygraną lub remis? Chociaż szachy są o wiele bardziej skomplikowane niż stawianie kółek i krzyżyków patykiem na piaszczystej drodze, a liczba możliwych gier i wyników jest wręcz niezrozumiale ogromna, to wciąż gra jest skończona. Co ciekawe, w turnieju FIDE World Chess Solving Championships w klasyfikacji drużynowej prym od roku 2009 wiodą drużyny z Polski – aż miło patrzeć!
Uczestnicy muszą rozwiązać serię różnego rodzaju zadań szachowych w określonym czasie. Punkty przyznawane są za poprawne rozwiązania w jak najkrótszym czasie. Czy zbliża nas to do całkowitego rozwiązania szachów – chyba nie, ale ćwiczenie znakomite.
Algorytm szachowy - jak to działa?
Dlaczego te programy są takie mądre? Albo, jak kto woli: inteligentne? Albo wreszcie: czemu tacy z nich niesamowici rachmistrzowie? Komputerowe aplikacje szachowe, niezależnie od sposobu implementacji, wykorzystują inny paradygmat wyboru ruchów niż ludzie. Używają heurystycznych metod do budowania, przeszukiwania i oceniania drzew reprezentujących sekwencje ruchów z bieżącej pozycji i próbują wykonać najlepszy wariant podczas gry. Czy to możliwe, aby wybrać ten jeden, najlepszy, niezależnie od tego, jak prawdopodobnie zareaguje przeciwnik? Wygląda na to, że tak – jednym z codziennych ćwiczeń dla szachistów proponowanych w popularnej, darmowej aplikacji Lichess jest zadanie wyboru najlepszego ruchu z predefiniowanej pozycji bierek. Takie drzewa decyzyjne są naprawdę duże. Mają od tysięcy do milionów węzłów.
Szybkość obliczeniowa współczesnych komputerów, zdolnych do przetwarzania dziesiątek tysięcy do setek tysięcy węzłów lub więcej na sekundę, w połączeniu z heurystyką rozszerzania i redukcji, która zawęża drzewo do najbardziej istotnych węzłów, czyni takie podejście… cóż, naprawdę efektywnym w spuszczaniu manta nawet najbardziej wprawionym szachistom.
Superkomputery i szachy
W połowie ubiegłego roku japońskie Fujitsu ujawniło Fugaku – najszybszy superkomputer świata do celów badawczych. Jego wydajność to aż 415,5 petaflopsów (PFLOPS) . System operacyjny wykorzystuje zarówno Linux, jak i lekkie jądro McKernel. W pierwszej wersji z czerwca 2020 roku do pracy wykorzystywał 158,976 węzłów A64FX, z czasem tę liczbę jeszcze zwiększono. Niezwykle fascynujące byłoby z pewnością wykorzystanie Fugaku do szachowych symulacji. Deep Blue, który pokonał Kasparova w 1996 i ponownie w późniejszych latach, był w stanie osiągnąć 11,38 gigaflopów (GFLOPS). Gigaflop jest równy 10^9 FLOPS lub 1 miliardowi FLOPS. W istocie, w mniej niż 30 lat, Deep Blue był około 81 666 razy potężniejszy niż Apollo 11 AGC, komputer NASA wspierający misję lądowania na Księżycu Apollo 11 w 1969 roku.
Rozwój technologii związanych z półprzewodnikami powoduje wykładniczy wzrost mocy obliczeniowej kolejnych generacji komputerów. W roku 2020, czyli 23 lata od powstania Deep Blue i 51 lat od lądowania Apollo 11, historia zgłasza do tego wyścigu smartfon iPhone. 13 października 2020 roku firma Apple Inc. wypuściła najnowszą linię iPhone’ów nazwaną iPhone 12. Według firmy nowy Neural Engine jest w stanie 11 trylionów operacji na sekundę (TFLOPS). Czyni go to 967 razy wydajniejszym niż Deep Blue i ponad 890 milionów razy bardziej wydajniejszym niż Apollo 11 AGC.
Szachy i sztuczna inteligencja, czyli deep learning
Nie mniej do zaoferowania szachom mają technologie sztucznej inteligencji Deep Learning. Skoro szachy są grą skończoną – wróćmy do tej tezy – to oznacza to, że gdybyśmy mieli wystarczająco dużą moc obliczeniową, to moglibyśmy rozwiązać szachy. Każda pozycja w szachach jest albo wygraną dla białych, albo wygraną dla czarnych, albo wymuszonym remisem dla obu graczy. Można to oznaczyć funkcją z użyciem reguł rekursywnych.
Każda sztuczna inteligencja szachowa zaczyna od funkcji, która jest połączona z przeszukiwaniem pozycji w dół drzewa gry. Wszystkie AI szachowe skupiają się na inteligentnych algorytmach wyszukiwania, ale jako że liczba pozycji eksploduje wykładniczo w dół drzewa wyszukiwania, to w praktyce nie można przejść głębiej niż, powiedzmy, 5-10 pozycji do kilkunastu pozycji do przodu.
Czy człowiek dorówna komputerowi?
A na ile taka komparatystyka ma w ogóle sens? Trudno odpowiedzieć na tak postawione pytanie przez pryzmat percepcji i wyobraźni przeciętnego człowieka. Nawet największy geniusz nie jest w stanie wyobrazić sobie wszystkiego – tak jak i niczego, bo próżnia to już coś. A rzędy wielkości w szachach to dla zdolności obliczeniowych naszych mózgów jak wszystko. Być może owe problemy należy pozostawić filozofii i jej działom takim jak ontologia.
Zawsze fajnie spojrzeć na historię i zobaczyć, jak daleko zaszliśmy w świecie komputerów. Będziemy i już właściwie jesteśmy świadkami tego, jak rodząca się technologia, która wylądowała na Księżycu, stanie się w przyszłości technologią, która wyląduje na Marsie i jeszcze dalej. Co więcej, technologie GSM, które pozwalają na utrzymywanie kontaktu z przyjaciółmi i rodziną, są o wiele potężniejsze niż się powszechnie wydaje. Dosłownie mamy już osobiste superkomputery w kieszeni.
Co dalej z szachami, które przywędrowały do nas w zamierzchłych czasach z dalekich Indii? Wciąż nie ma technologii i mocy obliczeniowej, która potrafiłaby zamknąć złożoność i piękno tej niesamowitej, starej gry w zamkniętej puli czynności i opisać je w wyobrażalnych liczbach. Arcymistrz Magnus Carlsen dryfuje w kierunku modellingu na światowych wybiegach, Kasparova na scenie już nie ma.
Szachy w czasie pandemii i na kanwie popularności serialu Gambit Królowej zdają się mieć jednak przed sobą kolejny renesans. Poza tym: czy umiejętności strategicznego planowania kiedykolwiek wyszły z mody?
2 Responses
Przy obecnych szybkościach komputerów gra w szachy stała się grą zamkniętą – program szachowy potrafi w określnym czasie przewidzieć wszystkie możliwe ruchy przeciwnika. I przez to jest nie tyle lepszy ale szybszy od mistrza szachowego., bo tak jak napisano – programy tworzy człowiek i wprowadza dane partii szachowych rozegranych przez najlepszych. W czasch małego Atari wygrywałem w szachy z tym komuterem na najniższym poziomie trudności – odpowiedź komputera natychmiastowa. Pozim wyżej już nie dałem rady.
To nieprawda, stockfish liczy warianty ale nie jest w stanie policzyć ich wszystkich, nawet nie zbliża się do tego. Gdy Stockfish został zdeklasowany przez AlphaZero rozegrali 100 partii 27 zakończyło sie remisem a 73 wygrał AlphaZero! Co jest bardzo interesujące w tamtym meczu mieli ograniczony czas na ruch tj 2sekundy. Stockfish obliczał ok 70mln ruchów na sekundę a AlphaZero jedynie ok 50tys a mimo to AlphaZero nie dało szans Stockfishowi.