Jeśli otrzyma się nieskończoną moc obliczeniową, czy istnieje algorytm, który doskonale gra w szachy?

29

Czy istnieje taki algorytm, w którym przy nieskończonej mocy obliczeniowej komputer mógłby grać w szachy idealnie, aby nigdy nie przegrał?

Jeśli tak, to gdzie mogę znaleźć pseudo kod?

chess-algorithms

— Jonasz
źródło

8

Co rozumiesz przez idealne szachy?

— Herb Wolfe,

5

@HerbWolfe Zakładam, że ma na myśli, że nigdy nie wykonuje ruchu, który pozwala przeciwnikowi zmusić go do przegranej i rezygnuje, jeśli tylko każdy możliwy ruch pozwala przeciwnikowi zmusić go do przegrania.

— David Schwartz,

5

@DavidSchwartz - „idealnych szachów” oczywiście nie można zdefiniować. Ani też „nieskończona moc przetwarzania”. Czy to oznacza „wykonuje wszystkie sekwencje instrukcji w czasie 0”? „Czy dostępna jest nieskończona liczba procesorów”? FWIW - moja definicja „idealnych szachów” brzmi „nigdy nie przegrywa”.

— Bob Jarvis - Przywróć Monikę

24

Tak, to się nazywa brutalna siła. Dzięki nieskończonej mocy obliczeniowej nie musisz przycinać wersji alfa-beta, chociaż możesz również potrzebować dość dużej ilości miejsca do przechowywania drzewa wyszukiwania.

— Michael

4

Pojęcie „algorytmu” i pojęcie nieskończonej mocy obliczeniowej tak naprawdę się nie mieszają. Teoria algorytmów i obliczalności opiera się na założeniu osiągnięcia wyniku w skończonej liczbie kroków. Jeśli masz nieograniczoną liczbę kroków, różnica między tym, co jest obliczalne, a tym, co nie jest, znika.

— Michael Kay,

62

Czy istnieje algorytm? Tak. Zgodnie z Twierdzeniem Zermelo istnieją trzy możliwości skończonej deterministycznej gry dla dwóch graczy o doskonałej informacji, takiej jak szachy: albo pierwszy gracz ma strategię wygraną, albo drugi gracz ma strategię wygraną, albo którykolwiek z graczy może wymusić remis. Nie wiemy (jeszcze), co to jest dla szachów. (Z drugiej strony warcaby zostały rozwiązane : każdy gracz może wymusić remis.)

Pod względem koncepcyjnym algorytm jest dość prosty: zbuduj pełne drzewo gry , przeanalizuj węzły liści (pozycje końcowe gry) i albo dokonaj zwycięskiego początkowego ruchu, zrezygnuj lub zaoferuj remis.

Problem tkwi w szczegółach: istnieje około 10 ⁴³ możliwych pozycji i jeszcze większa liczba ruchów (większość pozycji można osiągnąć na więcej niż jeden sposób). Naprawdę potrzebujesz swojego nieskończenie potężnego komputera, aby skorzystać z tego, ponieważ komputer, który może skorzystać z tego algorytmu, albo nie może zmieścić się w znanym wszechświecie, albo nie zakończy obliczeń, dopóki jakiś czas się nie skończy.

— znak
źródło

13

@Wildcard Nie, nic nie zakłada: zawiera tylko wszystkie możliwe legalne gry w szachy i wybierze wszystkie te, w których gracz nie przegrywa.

— gented

11

@gented, miałem na myśli etap „rezygnacji” algorytmu. To wcale nie jest konieczny krok.

— Wildcard,

38

Zasada trzech powtórzeń ogranicza przestrzeń poszukiwań, więc komputer nie musi być nieskończenie potężny, a jedynie astronomiczny.

— Hoa Long Tam,

9

Dla porównania porównaj dolną granicę liczby możliwych gier ( 10 ^ 120 ) z liczbą atomów w obserwowalnym wszechświecie (rzędu 10 ^ 80 ). Najprostszy algorytm musiałby znaleźć wszystkie te gry i przechowywać ich dane. Przechowywanie jednej gry na atom wymagałoby 10 ^ 40 razy więcej atomów niż szacujemy w obserwowalnym wszechświecie.

— Engineer Toast,

6

Ta odpowiedź jest świetna do samego końca, gdy mówisz o „nieskończenie potężnym komputerze”. To nie to, co masz na myśli, i że fraza nie należy w pytaniu ani dyskusji.

— Don Hatch,

25

Zobacz https://en.wikipedia.org/wiki/Endgame_tablebase .

Przy nieskończonej mocy komputera można zbudować taki stół dla pozycji wyjściowej i rozwiązać szachy .

W praktyce tylko pozycje z maksymalnie siedmioma „ludźmi” (pionkami i pionkami, licząc królów) zostały rozwiązane przy użyciu obecnych superkomputerów, więc jesteśmy bardzo daleko od rozwiązywania szachów. Złożoność problemu rośnie wykładniczo wraz z liczbą elementów.

— itub
źródło

9

Na marginesie, jeśli faktycznie stworzyłeś taki stół, bez względu na to, w czym zapisałeś informacje, ważyłby około 10 ^ 43 razy więcej niż obserwowalny wszechświat; biorąc pod uwagę, że w obserwowalnym wszechświecie istnieje ~ 10 ^ 123 możliwych pozycji szachowych i tylko ~ 10 ^ 80 barionów.

— Shufflepants,

6

@Shufflepants, którzy powiedzieli, że przechowuję go za pomocą barionów?

— Michael

3

@Christoph Zakładając ochronę informacji i zakładając, że posiadasz detektor i superkomputer z nieskończoną mocą przetwarzania, możesz powoli w ciągu czegoś w rodzaju lat googolplex odczytać podstawę stołu jako promieniowanie jastrzębie.

— Shufflepants,

3

@Shufflepants Pamiętaj, że faktyczna strategia wygranej może wymagać znacznie mniej miejsca niż pełna podstawa stołu. Na przykład Nim ma zwycięską strategię, którą można łatwo opisać, nie ma potrzeby budowania ogromnej tabeli wszystkich możliwych stanów.

— Federico Poloni,

1

To rozwiązanie, jak stwierdzono, nie jest wykonalne. Masa takiej tabeli utworzyłaby czarną dziurę i niemożliwe byłoby wyodrębnienie z niej danych.

— emory

19

Jeśli naprawdę masz nieskończoną moc obliczeniową, taki algorytm byłby naprawdę trywialny do napisania. Ponieważ szachy mają skończoną liczbę możliwych stanów, możesz teoretycznie po prostu je wszystkie iterować, aż znajdziesz ścieżkę doskonałej gry. Byłoby to okropnie nieefektywne, ale jeśli masz nieskończoną moc przetwarzania, nie miałoby to znaczenia.

— vsz
źródło

To nieprawda. Powiedział, że masz nieskończoną moc przetwarzania, ale nie powiedział nic o nieskończonej przestrzeni.

— ubadub

@ubadub: Nie potrzebowalibyśmy nieskończonej przestrzeni. Długość gry jest ograniczona ze względu na zasadę 50 ruchów, a regułę można utworzyć, aby posortować wszystkie możliwe ruchy z pozycji. Ponieważ można je sortować, mogą być przechowywane jako liczby całkowite. To cała pamięć wymagana do przejścia całego drzewa. A jeśli masz nieskończony czas, możesz chodzić po drzewie tak często, jak chcesz, więc nie musisz przechowywać każdej możliwej gry w szachy.

— vsz

Długość gry jest ograniczona, ale jest bardzo duża; jak ktoś zauważył, jeśli stworzyłeś tabelę do przechowywania wszystkich takich gier, „bez względu na to, na czym zapisałeś informacje, ważyłby około 10 ^ 43 razy więcej niż obserwowalny wszechświat; biorąc pod uwagę, że ~ 10 ^ 123 jest możliwe pozycje w szachach i tylko ~ 10 ^ 80 barionów we obserwowalnym wszechświecie

— ubadub

2

@ubadub: To prawda, ale nie mówiłem o „stole do przechowywania wszystkich takich gier”. Istnieje wiele algorytmów związanych z drzewem, które nie muszą utrzymywać w pamięci wszystkich węzłów całego drzewa.

— vsz

@ vsz good point

— ubadub

13

Aby bezpośrednio odpowiedzieć na pytanie: tak, istnieje taki algorytm. Nazywa się to minimax. (Podstawy tabel gry końcowej są generowane przy użyciu tego algorytmu (wstecz!), Ale wystarczy zwykły stary prosty algorytm minimax). Ten algorytm może doskonale grać w dowolną grę z zerową sumą dla dwóch graczy. Znajdź pseudokod tutaj:

https://en.wikipedia.org/wiki/Minimax

zauważ, że warianty tego algorytmu są używane przez współczesne komputerowe programy szachowe.

— chessprogrammer
źródło

4

Istnieje nie tylko algorytm do gry w szachy idealne, ale można również napisać krótki program, który (przy nieskończonych zasobach) doskonale zagra w każdą deterministyczną grę dla dwóch graczy o doskonałej wiedzy o ograniczonym czasie trwania .

Silnik gry nie musi nawet znać zasad gry, w którą gra. Wszystko czego potrzebuje to nieprzejrzyste przedstawienie „stanu gry” i funkcji, które (a) w dowolnym stanie gry, zapewniają listę legalnych następnych stanów gry i (b) w danym stanie gry decydują, czy jest to wygrana dla gracza 1 , wygrana dla gracza 2, remis lub nie jest to stan końcowy.

Biorąc pod uwagę te funkcje, prosty algorytm rekurencyjny „rozwiązuje” grę.

Nawiązano do tego w poprzednich odpowiedziach chessprogrammer (minimax) i Acccumulation (który udostępnia wersję programu w pythonie).

Napisałem taki program ponad 20 lat temu. Przetestowałem to, grając w kółko i krzyżyk (kółko i krzyżyk, jeśli jesteś Amerykaninem). Rzeczywiście grał w idealną grę.

Oczywiście szybko spadnie to na każdy wyobrażalny komputer w każdej poważnej grze. Ponieważ jest rekurencyjny, skutecznie buduje całe drzewo gry na stosie, więc dostaniesz „przepełnienie stosu” (gra słów bardzo przeznaczona), zanim zbliżysz się do analizy 10 ^ 123 stanów szachów, o których mowa w innych odpowiedziach. Ale fajnie jest wiedzieć, że w zasadzie ten mały program wykona zadanie.

Dla mnie mówi to również coś interesującego o AI: jakkolwiek, jak myślisz, „inteligencję” przejawia Deep Blue lub Go Zero, a nawet człowiek grający w Chess or Go, istnieje poczucie, że te gry mają trywialne, dokładnie obliczalne optymalne rozwiązania. Wyzwanie polega na tym, jak uzyskać dobre, choć nie optymalne rozwiązanie w rozsądnym czasie.

— Gareth
źródło

Twój algorytm działa tylko w przypadku gier dla dwóch graczy o doskonałej wiedzy. Przewróci się w przypadku gier z ukrytymi informacjami, takich jak Stratego , ponieważ każda implementacja funkcji (a) narusza zasady gry. Nie udaje się to również w grach o potencjalnie nieskończonym czasie trwania: na przykład porzuć zasadę 50 ruchów z szachów i nie można powiedzieć, że dwóch królów ścigających się wokół planszy nie jest stanem do wygrania. Wszystko, co może powiedzieć, to to, że nie jest to stan końcowy.

— Mark

Ważne punkty Zmienię swoją odpowiedź.

— gareth

3

Dla uproszczenia zignoruję możliwości losowania lub nieskończone sekwencje ruchów. Po zrozumieniu algorytmu nie jest szczególnie trudne rozszerzenie go na te przypadki.

Po pierwsze, niektóre definicje:

Każdy ruch, który wygrywa grę dla gracza, który go wykona, jest ruchem wygrywającym.
Każdy ruch, który przegrywa grę dla gracza, który go wykonał, jest ruchem przegrywającym.
Każdy ruch, który pozostawia drugiemu graczowi co najmniej jeden ruch wygrywający, jest również ruchem przegrywającym. (Ponieważ przeciwnik może wykonać ten ruch i wymusić stratę.)
Każdy ruch, który pozostawia drugiemu graczowi tylko ruchy tracące, jest również ruchem wygrywającym. (Bez względu na to, jaki ruch wykona twój przeciwnik, wygrasz.)
Idealna strategia oznacza zawsze wykonywanie zwycięskich ruchów, jeśli takie pozostały, i rezygnację, gdy pozostały tylko przegrane ruchy.

Teraz napisanie idealnej strategii jest banalne. Wystarczy rozbić wszystkie możliwe sekwencje ruchów i zidentyfikować ruchy wygrywające / przegrywające. Ignorując impas, ostatecznie rozpozna każdy ruch jako ruch wygrywający lub przegrywający.

Teraz strategia jest trywialna. Spójrz na wszystkie możliwe ruchy. Jeśli pozostaną jakiekolwiek ruchy wygrywające, weź jeden i wygraj. Jeśli pozostaną tylko przegrane ruchy, zrezygnuj, ponieważ przeciwnik może zmusić cię do przegrania.

Dostosowanie strategii w celu uwzględnienia możliwości impasu nie jest trudne.

Aktualizacja : na wszelki wypadek, gdy nie jest jasne, w jaki sposób identyfikuje każdy ruch jako ruch bardziej wygrywający lub przegrywający, rozważ:

Każdy ruch, który kończy się zwycięstwem, jest zwycięskim ruchem.
Każdy ruch, który kończy się stratą, jest ruchem przegrywającym.
Każdy ruch, w wyniku którego przeciwnik ma tylko ruchy wygrywające lub przegrywające, jest ruchem wygrywającym lub przegrywającym.
Sprawdź nliczbę ruchów w najdłuższej możliwej grze w szachy. (Na razie ignorujemy sekwencje niezwiązane, choć ich włączenie nie jest trudne).
Nie ma ruchów z nwcześniejszymi ruchami, które musimy rozważyć.
Każdy ruch z n-1poprzednimi ruchami jest ruchem wygrywającym lub przegrywającym, ponieważ nruchy kończą najdłuższą grę.
Zatem po każdym ruchu na głębokości n-2następuje tylko ruch wygrywający lub ruch przegrywający, a zatem sam ruch wygrywający lub ruch przegrywający.
I tak wróć do pierwszego ruchu.

— David Schwartz
źródło

1

Twoje definicje ruchów wygrywających i przegrywających nie są wystarczająco wyczerpujące. Na przykład pierwszy ruch nie wygrywa gry (# 1), ani nie pozostawia przeciwnikowi tylko ruchów tracących (# 4), więc nie jest to „ruch wygrywający”. Nie przegrywa też gry (# 2), ani nie pozostawia przeciwnikowi żadnego zwycięskiego ruchu (# 3), więc nie jest to ruch przegrany. Twoja strategia wymaga, aby każdy ruch był zdefiniowany jako „ruch wygrywający” lub „ruch przegrywający”, co po prostu nie jest tak, jak to zdefiniowałeś.

— Nuclear Wang,

2

@NuclearWang Definiuje każdy ruch jako ruch wygrywający lub przegrywający. Jak myślisz, jaka jest trzecia alternatywa? Wizualizuj drzewo wszystkich możliwych gier w szachy (i pamiętaj, że na razie wykluczamy krawaty lub nieskończone sekwencje). Każdy łańcuch kończy się wygraną lub przegraną. To przenika przez drzewo, identyfikując ostatecznie każdy ruch jako ruch wygrywający lub przegrywający.

— David Schwartz,

13

@NuclearWang albo pierwszy ruch jest zwycięskim ruchem dla jednego gracza, albo szachy to (jak kółko i krzyżyk) gra losowana z idealną grą. Nie wiemy, które, ponieważ nikt nigdy nie miał mocy obliczeniowej, aby uruchomić ten algorytm do końca, i nikt nie znalazł bardziej bezpośredniego dowodu.

— hobbs

8

W szachach nie ma przypadkowości ani ukrytych informacji, co nie pozostawia miejsca na „może”. Każda pozycja jest wygrywana, przegrywana lub losowana (nawet jeśli nie udało nam się ich zidentyfikować ). Wyjaśnienie to pomija opcję „wylosowaną” dla uproszczenia, ale w większości wynosi 1) pozycja jest losowana, jeśli jest losowana zgodnie z zasadami, i 2) pozycja jest losowana, jeśli nie ma ruchów wygrywających, ale ma co najmniej jeden ruch, który pozostawia przeciwnikowi bez zwycięskich ruchów.

— hobbs

2

@DavidSchwartz: O ile ktoś nie traci pozycji, każdy ruch, który nie jest idealny, jest zły. W pozycji przegranej na ogół nie byłoby pojedynczego „idealnego” ruchu [z wyjątkiem sytuacji przymusowego ruchu], ponieważ każdy legalny ruch może mieć pewne prawdopodobieństwo bycia jedynym ruchem wygrywającym lub ciągnącym w pewnych możliwych (prawdopodobnie wysoce wymyślnych) okolicznościach. Rezygnacja wydawałaby się jednak jednoznacznym najgorszym „posunięciem”. Załóżmy, że gra została udowodniona jako wygrana dla Białych za pomocą d4. Czy chcesz grać programu szachowego, który odpowiedział na 1. d4z ...resigns?

— supercat,

2

Załóżmy, że masz trzy funkcje: win_state, get_player, i next_states. Dane wejściowe win_stateto stan gry, a wartość wyjściowa to -1, jeśli biały jest w matowym, 0, jeśli to remis, 1, jeśli czarny jest w matowym, i Noneinaczej. Dane wejściowe get_playerto stan gry, a wynik wynosi -1, jeśli jest tura czarnych i 1, jeśli jest tura białych. Dane wejściowe dla next_statesto lista możliwych następnych stanów gry, które mogą wynikać z legalnego ruchu. Następnie poniższa funkcja, gdy zostanie podany stan gry i gracz, powinna powiedzieć ci, w jaki stan gry przejść, aby ten gracz wygrał.

def best_state(game_state,player)
  def best_result(game_state):
     if win_state(game_state):
        return(win_state)
     else:
         player = get_player(game_state)
         return max([best_result(move)*player for move in next_states(game_state)])*player
  cur_best_move = next_states(games_state)[0]
  cur_best_outcome = -1
  for state in next_states(game_state):
     if best_result(state)*player > cur_best_outcome:
           cur_best_outcome = best_result(state)*player
           cur_best_move = state
return(best_move)

— Akumulacja
źródło

0

Użyj tabeli przeglądowej

Tak. To łatwe. Nie potrzebujesz nawet nieskończonej mocy obliczeniowej. Wszystko czego potrzebujesz to stół przeglądowy, który zawiera, dla każdej możliwej pozycji na planszy, najlepszy ruch do gry na tej pozycji. Oto pseudo-kod:

def play-move(my-color, board-position):
    return table-of-best-moves[my-color, board-position]

Haczyk

Jedynym haczykiem jest to, że ten stół przeglądowy musiałby być bardzo, bardzo duży - być może większy niż galaktyka Drogi Mlecznej - i jego budowa zajęłaby dużo czasu - być może dłuższy niż obecny wiek wszechświata, chyba że istnieje pewną nieodkrytą regularność w szachach, która sprawia, że jest to o wiele prostsze niż obecnie. Ale jeśli masz tę tabelę przeglądową, podprogram, aby za każdym razem wybrać idealny ruch, może być zaimplementowany w zaledwie jednej instrukcji procesora.

Ponadto, biorąc pod uwagę naszą obecną wiedzę o szachach, nie ma sposobu, aby upewnić się, że idealna gra gwarantuje, że nie przegrasz. Na przykład, jeśli idealna gra gwarantuje wygraną dla Białych, wtedy Czarne przegrają, nawet jeśli Czarne zagrają idealnie.

— Ben Kovitz
źródło