Towards Solving Othello (challenging)

Title

Towards Solving Othello (challenging)

Topic

A number of games have been solved: Checkers, Nine-men’s morris,
Connect-Four, Awari.

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.

Disclaimer:
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?

 

Company/Organization
LIACS intern

Student Profile
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

Time frame
Negotiable

Scientific Challenge
This is one of the major open challenges of AI and HPC.
Successful research will likely results in one or possibly more important publications.

Advisor
Walter Kosters
Aske Plaat

Information: aske.plaat at gmail.com

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s