Reversi

Reversi is a project developed during the 1st year of our Computing Master in Bordeaux (FR). The aim of the project was to create the best AI possible for the Reversi/Othello game.

At the end of the development, all the AI of the Master Promotion were facing each other and we finished 2nd. We used classic AI, and tried to find the best heuristic possible with a AlphaBeta algorithm. Our heuristic takes the following factors: Corners, Mobility, Parity and Stability. All these factors are known for a long time, we were inspired by a study from the University of Washington. Please check it to have more information about the heuristic. The coefficient applied in the heuristic calculation evolve during the game. We had a limited time per move so we also had to find a way to play quickly. So we added a few features : The start of the game is already settled with an Opening Book, that we adapted to a 10x10 grid. We also implemented shortcuts, to play obvious shots quickly (taking a corner or blocking the opponent). Our AlphaBeta algorithm is only going to depth 3 at the beginning, but can increase depending on the state of the game. There is also a multi-threading system, to increase the calculation capacity.

Our project also embeds several "Evaluators" that uses different heuristics with different factors, that can be tested thanks to a benchmark program that we developed. It allows to compare different heuristics or strategies, on an sample of games, home and away.