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

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?

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.

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.

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.

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.

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.

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:

1. Każdy ruch, który wygrywa grę dla gracza, który go wykona, jest ruchem wygrywającym.

2. Każdy ruch, który przegrywa grę dla gracza, który go wykonał, jest ruchem przegrywającym.

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

4. 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.)

5. 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ż:

1. Każdy ruch, który kończy się zwycięstwem, jest zwycięskim ruchem.
2. Każdy ruch, który kończy się stratą, jest ruchem przegrywającym.
3. Każdy ruch, w wyniku którego przeciwnik ma tylko ruchy wygrywające lub przegrywające, jest ruchem wygrywającym lub przegrywającym.
4. 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).
5. Nie ma ruchów z nwcześniejszymi ruchami, które musimy rozważyć.
6. Każdy ruch z n-1poprzednimi ruchami jest ruchem wygrywającym lub przegrywającym, ponieważ nruchy kończą najdłuższą grę.
7. 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.
8. I tak wróć do pierwszego ruchu.

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)

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.