Niedawno rozmawiałem z osobą niekodującą na temat możliwości komputerów szachowych. Nie jestem dobrze zorientowany w teorii, ale myślę, że wiem wystarczająco.
Twierdziłem, że nie może istnieć deterministyczna maszyna Turinga, która zawsze wygrywała lub znajdowała się w impasie w szachach. Myślę, że nawet jeśli przeszukasz całą przestrzeń wszystkich kombinacji ruchów gracza 1/2, pojedynczy ruch, na który komputer decyduje na każdym kroku, opiera się na heurystyce. Opierając się na heurystyce, niekoniecznie pokonuje WSZYSTKIE ruchy, które może wykonać przeciwnik.
Wręcz przeciwnie, mój przyjaciel pomyślał, że komputer zawsze wygrywa lub remisuje, jeśli nigdy nie wykonałby „błędnego” ruchu (jak to zdefiniujesz?). Jednak będąc programistą, który zajął się CS, wiem, że nawet twoje dobre wybory - biorąc pod uwagę mądrego przeciwnika - mogą w końcu zmusić cię do „błędnych” posunięć. Nawet jeśli wiesz wszystko, następnym krokiem jest chciwość w dopasowaniu heurystyki.
Większość komputerów szachowych próbuje dopasować ewentualną grę końcową do gry w toku, co jest zasadniczo dynamicznym śledzeniem programowania. Ponownie, omawianej gry końcowej można jednak uniknąć.
Edycja: Hmm ... wygląda na to, że potarłem tu kilka piór. Dobre.
Myśląc o tym ponownie, wydaje się, że nie ma teoretycznego problemu z rozwiązywaniem skończonej gry, takiej jak szachy. Twierdzę, że szachy są nieco bardziej skomplikowane niż warcaby, ponieważ wygrana niekoniecznie jest wynikiem numerycznego wyczerpania figur, ale mata. Moje pierwotne stwierdzenie jest prawdopodobnie błędne, ale z drugiej strony wydaje mi się, że wskazałem na coś, co nie zostało jeszcze zadowalająco udowodnione (formalnie).
Wydaje mi się, że mój eksperyment myślowy polegał na tym, że za każdym razem, gdy brana jest gałąź w drzewie, algorytm (lub zapamiętane ścieżki) musi znaleźć ścieżkę do partnera (bez matowania) dla każdej możliwej gałęzi na ruchach przeciwnika. Po dyskusji kupię, że mając więcej pamięci, niż możemy sobie wymarzyć, wszystkie te ścieżki można znaleźć.