Algorytmy minimax i alfa-beta cięć w zastosowaniu do programów szachowych

Abstract

Zasadniczym celem pracy było przedstawienie algorytmu mini-max, który jest podstawowym algorytmem pozwalającym każdemu programowi szachowemu opracować strategie grania, a także algorytmu alfa-beta cięć z jego udoskonaleniami. Praca ta składa się z trzech części. W pierwszej części został przedstawiony ponad pół wieczny okres dorobku metod programowania rozwoju najpierw maszyn a potem programów do gry w szachy. W drugim rozdziale został przedstawiony algorytm minimax wraz z jego rozwinięciem – algorytm alfa-beta cięć. Algorytm minimax jest podstawowym algorytmem wykorzystywanym w mechanizmie programowania gier logicznych, jest on stosowany do oszacowania wartości danej pozycji. Jego zadaniem jest znalezienie najbardziej trafnego posunięcia, które przyniesie zwycięstwo, a porażkę przeciwnikowi. W kolejnym rozdziale zostały omówione różnorodne metody udoskonalenia algorytmu alfa-beta, takie jak: przeszukiwanie minimalnego okna, PVS, MTD(f), przeszukiwanie w przód, mechanizmy kolejności ruchów (heurystyki: ruchów morderców (killer moves), historii i w oparciu o pusty ruch), iteracyjne pogłębianie, tablice transpozycji, ProbCut i MultiProbCut. Autor niniejszej pracy zakłada, że czytelnik posiada postawy algorytmów i minimalną wiedzę szachową. Z algorytmu mini-max z cięciami alfa-beta wynika, że przeglądanie wszystkich gałęzi drzewa nie jest konieczne. Algorytm ten daje taki sam rezultat jak bez cięć, ale jest o wiele bardziej wydajny. Zazwyczaj podwaja ilość półruchów, które mogą być przeszukane w danym czasie. Udoskonalenia takie jak heurystyki kolejności ruchów, iteracyjne pogłębianie, Pro-bCut i Multi-ProbCut a także użycie tablic transpozycji powoduje, że każdy program gra inaczej i znacznie szybciej. Metody te są skomplikowane, ale właściwa ich implementacji i współgranie decyduje o sile grania programu.