Program that plays a strategy board game

Software	Java or C++ or Smalltalk or another object oriented language with good GUI facilities, alternatively a functional language or maybe Prolog, or an expert systems shell
Covers	Problem representation, search algorithms, evaluation methods
Skills Required	Programming, understanding some strategy game, some interest in artificial intelligence
Challenge	Conceptual ?? Technical ?? Programming ????

Brief Description

A lot of interesting artificial intelligence research has been done on games. Board games like draughts and chess have been major drivers of the development of search techniques. And programs for playing board games have been commercially successful as toys.

Your challenge is to develop a program for playing a two-player strategy board game, if possible well. Draughts and chess have played an important role in the development of AI. Othello is a popular choice. Backgammon presents rather different challenges: it's a demanding game of skill involving chance and hence a grasp of likely and unlikely events; the branching factor is too large for deep searches. Chinese Chequers and Nine Men's Morris would be interesting choices; as would one of the various hexagonal chess games. Go is probably too hard to get anywhere with. (AI researchers have built programs capable of giving the world champion a good game in chess, draughts, backgammon and othello. Professional standard Go was regarded as impossible for the foreseeable future, but has now been cracked with very advanced machine learning techniques.)

This involves devising an appropriate representation for a game of draughts/whatever in your chosen language, implementing search algorithms to explore future states of the game, and implementing metrics for evaluating the value of a given state of the game. It should have a simple interface, and be capable of being driven by code (such as a separate graphic interface, or a shell that pits two game playing programs against each other).

For any game, the success the project will depend most of all on coming up with a good way to represent game states and moves, and then a good way to represent rules for choosing moves. Describing game states and moves is easy for Othello, a bit harder for draughts, and more challenging (but doable, if you're clever) for Chinese Chequers.

Extensions

Build a system that learns to play the game well.

Build a good graphic interface for the game playing program.

Back to