Classical Checkers

João Carlos Correia

Key information

Authors:

João Carlos Correia (João Carlos Correia Guerra)

Supervisors:

Maria Inês Camarate de Campos Lynce de Faria (Inês Lynce)

Published in

11/03/2011

Abstract

For the last 60 years, games have been an important research subject in the field of Artificial Intelligence. For some time the focus was mainly on creating strong computer Chess programs. With the rise of master-level game-playing programs the trend changed. Now, the focus is on determining which games can effectively be solved and on solving them. The recent breakthrough with Monte-Carlo Tree Search (MCTS) techniques in complex games, such as Go and Amazons, also led the research away from alpha-beta. However, MCTS has not yet beaten alpha-beta in more simple games, such as Checkers and Chess. In this dissertation, we describe a computer program created to play the game of Classical Checkers, Turska, and, for the first time, we estimate and analyse the complexity of Classical Checkers. Additionally, some experiments were made with the program. The results are analysed in order to better understand how each one of the studied search algorithms and techniques behave in the domain under study, and how they can be improved. Given that the enhancements that take advantage of transpositions were the ones that accounted for more savings, we tried to improve them. We did so by trying to improve the information stored in the transposition table and how it was managed. The program was evaluated by playing some matches against another Classical Checkers computer program. In short, the results indicate that Turska's evaluation function needs further work. This is re-stated in the future work, along with other research suggestions.