Czy szachy to rozwiązana gra?

Szachy to gra o sumie zerowej i ograniczonych decyzjach. Liczba możliwych ruchów w danym punkcie i liczba możliwych stanów planszy są skończone.

Kółko i krzyżyk, jest jednym z najłatwiejszych przykładów rozwiązanej gry. Nie pamiętam, ile lat minęło, odkąd ostatnio przegrałem mecz w kółko i krzyżyk. Czy istnieje jakaś „optymalna strategia” dla szachów?

Czy jest jakaś strategia, która zagwarantuje, że gracz odniesie zwycięstwo lub, w najgorszym przypadku, remis?

Jeśli tak, proszę rzucić na to trochę światła.

Z uwagi na twoją obserwację, że drzewo możliwych ścieżek do gry w szachy jest skończone, szachy są rzeczywiście możliwe do rozwiązania w dokładnie tym samym sensie, co kółko i krzyżyk. Istnieją więc optymalne strategie dla szachów; nikt jednak nie ma pojęcia, czym one są. Podczas gdy kółko i krzyżyk jest rozwiązywany dzięki dość niewielkiej przestrzeni możliwych gier, szachy nie są jeszcze prawie rozwiązane, ponieważ ich przestrzeń możliwych gier znacznie przewyższa to, co można by rozwiązać dzięki obecnej technologii komputerowej.

Jak zauważono w innej odpowiedzi, podstawy tabeli końcowej wykazują optymalną grę dla wszystkich pozycji z ograniczoną liczbą elementów. Więc w tych ustawieniach mamy rozwiązania, które są tak jednoznaczne i konkretne, jak te dla kółko i krzyżyk. Należy jednak pamiętać, że chociaż można łatwo nauczyć / zapamiętać optymalną strategię gry w kółko i krzyżyk i szybko stać się doskonałym samodzielnym graczem w kółko i krzyżyk , ilość informacji za, powiedzmy, 7-częściowymi podstawami Łomonosowa , wynosi 140 terabajtów. Nie ma zwięzłego opisu optymalnej 7-osobowej strategii, której można się nauczyć / zapamiętać, a następnie grać doskonale bez pomocy.

Gry w szachy mogą być skończone, ale liczba możliwych gier jest poza wyobrażeniem.

Nie jest znana sekwencja ruchów, która gwarantowałaby wygraną lub remis.

Szachy nie zostały rozwiązane i nie będzie to możliwe w ciągu następnych dziesięcioleci (z wyjątkiem absurdalnego postępu komputerowego obejmującego obliczenia kwantowe lub tak drastycznych zmian).

Możesz obliczyć w głowie dla pierwszego ruchu: biały ma 20 opcji, a czarny ma 20 odpowiedzi; mamy już 400 możliwych pozycji. Liczba ta rośnie absurdalnie szybko, liczba możliwych pozycji dla gry z 80 ruchami jest niewyobrażalnie duża.

Ponadto, gdyby rozwiązano szachy, turnieje szachowe i mistrzostwa byłyby w zasadzie ćwiczeniami w zapamiętywaniu, czyniąc je bezcelowymi. (EDYCJA: jest to raczej zawyżone, patrz komentarze.)

Obecnie szachy są rozwiązywane dla dowolnej pozycji z sześćsiedem sztuk (w tym królów). Najnowsze szacunki, o których słyszałem7-mężczyznPodstawy 8-osobowe były gdzieś w latach dwudziestych XX wieku i oczywiście czas potrzebny na dodatkowy kawałek rośnie wykładniczo. Nie spodziewam się, że szachy w moim życiu będą prawie rozwiązane (ponownie, z wyjątkiem naprawdę wyjątkowych osiągnięć w dziedzinie komputerów). (Podziękowania za poprawki dla Tony'ego Ennisa.)

Inną kwestią jest to, że gra w szachy jest skończona, ale tylko z zasadą 75 ruchów (gra jest losowana, jeśli nie ma żadnych chwytów lub ruchów pionkiem dla 75 ruchów). Wcześniej zasada ta polegała na losowaniu przez kolejne trzykrotne powtórzenie pozycji, tak zwana „reguła niemiecka”, pozwalająca na nieskończoną liczbę gier, jak pokazuje Max Euwe .

Wiemy, że istnieje optymalna strategia, ponieważ gdy w grze jest skończona liczba graczy i skończona liczba strategii dla każdego gracza, można pokazać, że istnieje równowaga Nasha (więc grasz swoją optymalną reakcją na optymalną grę drugiego gracza odpowiedź i viceversa).

Chodzi o to, że nawet jeśli wiemy, że taka strategia istnieje, nie wiemy dokładnie, która to strategia ze względu na ograniczenia obliczeniowe.

Oto odpowiedź, którą pierwotnie napisałem na /cstheory/6563/what-is-the-computational-complexity-of-solving-chess/38102#38102 .

Idealny szachista zawsze wymusi wygraną, gdy może wymusić wygraną i wymusi remis, gdy wymusi remis. Oczywiście w dowolnym momencie, jeśli mogą wymusić zwycięstwo, mogą również zmusić remis. Również, gdy jeden gracz nie może wymusić wygranej, drugi gracz może wymusić remis. Szachy bez reguły 50 ruchów lub 3-krotnego powtórzenia mogą nie być tak trudne do rozwiązania, jak myślisz. Można wykazać, że dodanie zasady 3-krotnego powtórzenia nie ma znaczenia, czy gracz może wymusić wygraną czy remis. Liczba możliwych sposobów, w jakie może przejść gra po n ruchach, rośnie wykładniczo wraz z n. Z drugiej strony liczba stanów, które mogą wystąpić po n ruchach, nie rośnie wykładniczo, ponieważ nie może przekroczyć całkowitej liczby możliwych stanów, które mogą wystąpić w legalnej grze. Wedłughttps://en.wikipedia.org/wiki/Game_complexity , istnieje około 10 ^ 47 stanów, które mogą wystąpić w legalnej grze w szachy.

Szachy można rozwiązać w następujący sposób: weź zestaw stanów, które możemy udowodnić, zawiera wszystkie stany, które mogą wystąpić w legalnej grze w szachy bez reguły 3-krotnego powtórzenia lub reguły 50 ruchów. Dwa różne stany mogą mieć taki sam układ pionków szachowych i różnić się, czyja to kolej, czy masz prawo do schwytania en passant i czy dany król lub wieża ma prawo do ponownego zamku. Następnie weź wszystkie stany, w których minimalna liczba ruchów białych może zmusić wygraną do 1, która musi wystąpić w turze białych. Następnie weź wszystkie stany, w których minimalna liczba ruchów, w których biały może wygrać, wynosi 2, co oznacza, że ​​jest tura czarnych i bez względu na to, jaki ruch mogą wykonać, biały może wymusić wygraną w 1 ruchu. Następnie weź wszystkie stany, w których minimalna liczba ruchów białych może zmusić wygraną do 3, co oznacza, że ​​biały ma ruch, który zapewni mu wymuszoną wygraną w 2 ruchach, ale nie może wymusić wygranej w 1 ruchu. Następnie weź wszystkie stany, w których minimalna liczba ruchów, w których biały może zmusić wygraną, wynosi 4, co oznacza, że ​​jest tura czarnego i bez względu na to, jaki ruch wykonają, biały może zmusić wygraną w 3 ruchach, ale biały nie może obecnie wymusić wygranej w 2 ruchy. Gdy dojdziemy do liczby takiej, że nie ma stanów, w których minimalna liczba ruchów białych może zmusić wygraną do takiej liczby, już znaleźliśmy wszystkie stany, w których biały może zmusić wygraną. Możemy znaleźć wszystkie stany, w których czarny może wymusić zwycięstwo w podobny sposób. Wszystkie pozostałe stany to te, w których obaj gracze mogą wymusić remis. co oznacza, że ​​jest tura czarnych i bez względu na to, jaki ruch wykonają, biały może wymusić zwycięstwo w 3 ruchach, ale biały nie może obecnie zmusić wygranej w 2 ruchach. Gdy dojdziemy do liczby takiej, że nie ma stanów, w których minimalna liczba ruchów białych może zmusić wygraną do takiej liczby, już znaleźliśmy wszystkie stany, w których biały może zmusić wygraną. Możemy znaleźć wszystkie stany, w których czarny może wymusić zwycięstwo w podobny sposób. Wszystkie pozostałe stany to te, w których obaj gracze mogą wymusić remis. co oznacza, że ​​jest tura czarnych i bez względu na to, jaki ruch wykonają, biały może wymusić zwycięstwo w 3 ruchach, ale biały nie może obecnie zmusić wygranej w 2 ruchach. Gdy dojdziemy do liczby takiej, że nie ma stanów, w których minimalna liczba ruchów białych może zmusić wygraną do takiej liczby, już znaleźliśmy wszystkie stany, w których biały może zmusić wygraną. Możemy znaleźć wszystkie stany, w których czarny może wymusić zwycięstwo w podobny sposób. Wszystkie pozostałe stany to te, w których obaj gracze mogą wymusić remis. Możemy znaleźć wszystkie stany, w których czarny może wymusić zwycięstwo w podobny sposób. Wszystkie pozostałe stany to te, w których obaj gracze mogą wymusić remis. Możemy znaleźć wszystkie stany, w których czarny może wymusić zwycięstwo w podobny sposób. Wszystkie pozostałe stany to te, w których obaj gracze mogą wymusić remis.

Ponieważ istnieje około 10 ^ 47 stanów, które mogą wystąpić w legalnej grze w szachy, użycie brutalnej siły zajęłoby nam zbudowanie komputera, który doskonale gra w szachy bez względu na to, jak gra przeciwnik. Uważam, że nie zostało udowodnione, że nie ma dużo krótszego algorytmu, który mógłby ci powiedzieć, jak grać doskonale, bez względu na to, jak gra przeciwnik. Na przykład może tylko niewielka część stanów, które mogą wystąpić w legalnej grze, może wystąpić w grze, w której grasz tak, jak algorytm każe ci grać, aby algorytm działał, mimo że mówi ci tylko, jak grać doskonale we wszystkich stanach, w których może wystąpić, gdy zawsze postępujesz zgodnie z tym algorytmem od początku gry, ale nie we wszystkich stanach, które mogą wystąpić w legalnej grze. Może oprócz tego ten algorytm jest złożonym algorytmem, który dla każdego stanu, który może wystąpić w grze, w której zawsze go śledziłeś, wykonuje o wiele mniej kroków, aby obliczyć optymalny ruch, niż liczba stanów, które mogą wystąpić w grze, w której zawsze go śledziłeś. Wedłughttp://onlinelibrary.wiley.com/doi/10.1002/sres.2171/abstract, laboratoria uczenia ewolucyjnego planują rozwiązywać złożone problemy. Może kiedyś wymyślą złożoną strategię perfekcyjnej gry w szachy. Być może nawet jeśli algorytm jest bardzo krótki i wymaga bardzo niewielu kroków, aby obliczyć optymalny ruch w dowolnym stanie, który może wystąpić w grze, w której zawsze postępujesz zgodnie z tym algorytmem, nie oznacza to, że człowiek nie jest w stanie nauczyć się doskonale grać w szachy. Może człowiek mógłby ciągle wymyślać rzeczy i zachowywać to, co wymyślili, wykombinować więcej rzeczy z tego, co wcześniej wymyślili i zachować je jakąś złożoną metodą,

Prawdopodobnie jeszcze łatwiej jest graczowi mieć strategię, która zapewnia, że ​​jeśli jego przeciwnik gra idealnie, on również będzie grał idealnie. Podejrzewam, że obaj gracze mają przymusowe losowanie od początku gry. Prawdopodobnie łatwiej jest mieć strategię, która wymusza remis, niż strategię, która gwarantuje, że jeśli twój przeciwnik da ci wymuszoną wygraną, nie przegrasz. Strategia, która wymusza remis, jest także strategią, która zapewnia, że ​​jeśli twój przeciwnik gra idealnie, będziesz grać idealnie. Jeśli grają idealnie, nie zapewnią ci wygranej wymuszonej, więc nie stracisz wygranej wymuszonej po tym, jak ci ją dadzą.

W 1949 roku naukowiec Shannon oszacował, że rozwiązanie szachów za pomocą komputera 1 MHz zajmie 10–90 lat. Od tego czasu technologia zasilania i pamięci masowej uległa znacznej poprawie (zwanej także prawem Moore'a), gdzie moc komputera i pojemność pamięci podwajają się każdego roku. Biorąc to pod uwagę, opracowanie komputera zajęłoby około 300 lat, które byłoby 10–90 razy mocniejsze niż maszyna Shannona 1 MHz. Nie ma żadnych przewidywalnych ograniczeń w rozwoju komputerów. Na przykład procesor Intel 4004 został wykonany przy użyciu technologii fotolitografii 10 mikrometrów, podczas gdy obecne modele i9 są wykonane w technologii 14 nm. Kiedy rdzenie stają się coraz potężniejsze i mniejsze, łatwo jest wypchnąć więcej rdzeni o tej samej wielkości fizycznej niż w poprzednich latach o połowę jako potężnych przodków. W fotolitografii właśnie weszliśmy w kategorię długości fal ultrafioletowych poniżej 10 nm, ale istnieją długości fali, takie jak promienie gamma, których długość fali wynosi 1 pikometr (czyli o 10.000 więcej mniej). Atom wodoru ma wielkość 0,1 nm, ale tj. Kwarki są około 200 razy mniejsze niż 1 pikometr (czyli 0,43 x 10 ^ −15 mm,https://www.theguardian.com/science/life-and-physics/2016/apr/07/how-big-is-a-quark )

Nie

nie możemy powiedzieć, kto powinien wygrać, czy remis

istnieje zbyt wiele kombinacji ruchów, aby nawet spróbować obliczyć odpowiedź przy użyciu obecnej technologii, wypróbowując wszystkie możliwe ruchy i widząc wyniki

wtedy musielibyśmy przycinać wstecz, aby zobaczyć, jaka byłaby odpowiedź i gdyby była wyjątkowa

i gdybyśmy mogli, gra nie byłaby dłużej zabawą

Na początku XX wieku popularne było przekonanie, że szachy zostaną wkrótce rozwiązane (zwane „losową śmiercią szachów”). Mistrz świata J.-R. Capablanca zwykle w to wierzyła. Mecze Capablanca-Alekhine (prawie wszystkie w Queen's Gambit Decpled) również potwierdziły to przekonanie. Patrz na przykład: https://en.wikipedia.org/wiki/Capablanca_chess .

Rewolucja współczesnych otworów (King's Indian itp.), A następnie rewolucja sztucznej inteligencji dostarczyły intuicyjnych dowodów, że rozwiązywanie szachów nie jest takie proste. Rzeczywiście, dzisiaj gry arcymistrzowskie są często analizowane za pomocą programu, co ujawnia linie, które gracze (nawet najlepsi) nadzorowali podczas gry.

To powiedziawszy, „absolutna moc obliczeniowa” może rzeczywiście rozwiązać szachy w sensie teorii obliczeń.

Ludzki umysł jest znacznie bardziej złożony niż gra w kółko i krzyżyk. Możesz więc znaleźć dobrą strategię gry w taką grę.

Szachy są dość różne. Szachy to gra heurystyczna.

nie możesz postawić żołnierza przed generałem. Umysł generała jest znacznie bardziej złożony niż umysł żołnierza pod względem wojskowym. To tylko analogia.

Najważniejsza jest złożoność.

Musisz być bardziej złożony niż szachy. Jest to niemożliwe, ale musisz spróbować, musisz spróbować. Możesz to osiągnąć na kilku poziomach. W grę wchodzi wiele czynników. Wysiłki są ważne, ale wielu z nas robi wielkie wysiłki, osiągając słabe wyniki. Ale są ludzie, którzy niewiele się starali i osiągali doskonałe wyniki.

Natura jest niesprawiedliwa.

Ale jeśli nauczysz się szachów w wieku pięciu lat, Twoje szanse będą większe niż w przypadku gry w wieku dziesięciu lat.

Oczywiście, jeśli byłeś dzieckiem przez wiele godzin przed telewizorem, zmarnowałeś swoją inteligencję.

Na koniec przepraszam za mój angielski.

2000-3000 Elos więcej do perfekcji, aby obecne najlepsze silniki mogły przynajmniej podwoić swoją siłę. Szachy są w rzeczywistości bliżej niemowlęctwa niż późniejszych etapów. Na przykład obecne najlepsze silniki odgadłyby tylko jeden z 5 najlepszych ruchów otwierających. Przed nami jeszcze długa droga.