Chess-Playing Algorithms with Deep Neural Network Heuristics

Nedávno vyvinutý algoritmus AlphaGo pro hraní hry Go, porazil světového mistra v této hře. Tohoto úspěchu bylo dosaženo pomocí heuristických funkcích založených na hlubokých konvolučních neuronových sítí s využitím algoritmu Monte Carlo Tree Search. V šachách bylo dosaženo výborných výsledků s využitím hluboké neuronové sítě, která porovnávala šachové pozice s přesností 98 % a byla integrována do algoritmu Alpha-Beta prořezávání. Tato práce se zaměřila na replikaci těchto výsledků a na experimentální porovnání algoritmů Alpha-Beta prořezávání a Monte Carlo Tree Search ve hře šachy. Zmíněné výsledky se zcela nepodařilo zreplikovat. Naučená sít dosáhla při porovnání jen na přesnost 93,9 %. Proto, aby porovnání algoritmů mělo vypovídající hodnotu, byla také použita neuronová sít z šachového programu Giraffe, která ohodnocuje šachové pozice. Na základě provedených experimentů nedosáhl algoritmus Monte Carlo tree search i přes použité heuristiky na úroveň algoritmu Alpha-Beta prořezávání. Algoritmus Alpha-Beta prořezávání dosáhl s využitím heuristik na úroveň přibližně kolem 1900 Elo podle žebříčku CCRL 40/40.AlphaGo, a recently developed algorithm to play the game Go, has defeated a human world champion in the game. This success has been achieved with heuristic functions based on deep convolutional neural networks used with Monte Carlo Tree Search algorithm. In chess, there were excellent results with deep neural networks, that compared chess positions with 98% accuracy and were integrated into Alpha-Beta prunning algorithm. This thesis focused on replication of these results, and on experimental comparison of algorithms Alpha-Beta prunning and Monte Carlo Tree Search in chess. The mentioned results were not fully replicated. The trained network achieved only 93.9% accuracy of comparison. In order to reasonably compare the algorithms, a neural network from chess engine Girraffe, that evaluated chess positions, was used. Based on the performed experiments, the Monte Carlo tree search algorithm could not achieve the level of the Alpha-Beta prunning algorithm despite the heuristics used. The Alpha-Beta pruning algorithm with use of heurisitcs achieved level around 1900 Elo according to the CCRL 40/40 ladder