Towards Solving Othello (challenging)
A number of games have been solved: Checkers, Nine-men’s morris,
The 10-log of their estimated state space complexity is 21, 10, 14, 12. For 8 by 8 Othello this number is 28. The quest to solving checkers (North-amercian draughts on an 8×8 board) is described in a 2007 article in the journal Science by Schaeffer et al. It took a massive effort of High Performance Computing and Artificial Intelligence search techniques. Human ambition and scientific curiosity lead us naturally to the next game: Othello. 4×4 Othello and 6×6 are solved, it is a win for the second player. For 8×8 Othello it is suspected that the game theoretical outcome is a draw. (Dis-)proving this draw will take a very large effort in High Performance Computing, given the large state space of 10 to the power of 28 states. The minimax proof will consist of a proof-tree of 10 to the power of 14 states. (Your first step is, of course, calculating how many bits storing an Othello position takes.)
This Master’s thesis topic consists of two phases: In the first, realistic phase, you will do preliminary calculations and algorithmic development to find out what is needed to solve the game. In the second, unrealistic phase, you will solve the game.
In all honesty it should be stressed that it is unrealistic to believe that you will solve the game of Othello as part of a Master’s thesis project. That would mean you are very very lucky, and very very very bright. Please be realistic. 10 to the power of 28 is really large. You have been warned. But it is nice to have a challenging goal, right?
CS student with Artificial Intelligence AND High Performance Computing affinity who would like to work towards solving the game, and will beable to stand the disappointment if the actual solving is not achieved
This is one of the major open challenges of AI and HPC.
Successful research will likely results in one or possibly more important publications.
Information: aske.plaat at gmail.com