A Layman's Chess Engine

Abstract

In 1997, IBM’s Deep Blue computer beat World Chess Champion Gary Kasparov in a six- game match. Since then, chess engines have increased in power, with top engines having an Elo rating over 3400 (a human hasn’t reached 2900). Even with these advances, chess is by no means a solved problem, and playing at a high level requires immense computational power and efficient algorithms. Chess engines are built to quantify the goodness of chess positions and to efficiently search for moves that lead to beneficial positions. With estimates of the number of legal positions in a game ranging from 1045-10120 (compared to an estimated 1082 atoms in the observable universe [1]), exhaustive searches cannot be performed, so an efficient algorithm is necessary. In this thesis, I built a chess engine, Layman. It is playable via a graphical user interface and will operate primarily via an evaluation function and a search algorithm. The evaluation function takes several game parameters into account, the search method uses alpha-beta pruning and principle variations to enhance minimax searching, and I estimate the playing strength of Layman. Finally, I discuss the relevance of chess engines to tracking algorithms in particle physics.