Jakie algorytmy i heurystyka są popularne w szachach komputerowych?

18

Szachy komputerowe eksplodowały w ciągu ostatnich dwudziestu lat, kiedy ustanowiono mistrzostwa świata w komputerach, a wielu projektantów komputerów szachowych zaczęło osiągać znaczne zyski. Niektóre programy ukrywają swój kod źródłowy, ale wiele z nich ma charakter open source, w szczególności Fruit, który stanowił podstawę rodziny silników szachowych.

Jakie są przykłady heurystyki lub algorytmów używanych przez komputery szachowe i które odniosły największy sukces lub są najbardziej popularne?

Andrew Latham
źródło
2
To nie jest właściwe miejsce na to pytanie i zostało już zadane w definicji projektu: przedyskutuj.area51.stackexchange.com/questions/5056/...
Charles Menguy

Odpowiedzi:

7

Algorytmy wykorzystywane głównie polegają na przeszukiwaniu przestrzeni stanów. Problem polega na tym, że możliwe pozycje, które kawałek może zająć w następnym ruchu, są bardzo duże. Ale to jest skończone. Jest to w zasadzie problem z wyszukiwaniem. Istnieje ważna pozycja, którą może zająć kawałek. To jest znany stan początkowy i znany stan końcowy. Nie ma w tym prawdopodobieństwa, jak problem z rzuceniem monetą.
Typowym algorytmem jest stosowanie brutalnej siły i obliczanie ruchów dla ustalonej liczby ruchów. W takich przypadkach można stosować MiniMax. Przycinanie alfa-beta jest również dobrze znanym algorytmem. Przeważnie przestrzenie wyszukiwania są reprezentowane przy użyciu struktury danych opartej na drzewie.
Program komputerowy również intensywnie wykorzystuje bazy danych zawierające ruchy, otwory, pozycje w końcowej fazie gry itp.


źródło
1
Pytanie dotyczy heurystyki . Celem heurystyki jest unikanie kosztów brutalnej kalkulacji wszystkich legalnych ruchów. Odpowiedź na brutalne podejście niestety nie jest na ten temat.
Jaxter