Artificial Intelligence and Combinatorial Game Theory

Combinatorial Game Theory (CGT) is a branch of applied mathematics and computer science that studies turned-based, perfect-information games, such as chess and checkers.

During the Summer of 2011 at DigiPen I independently studied the mathematical theory of CGT, including surreal numbers and game temperatures. My professor's favorite game (and now my own) is The Game of the Amazons (usually simply called Amazons), and was the game we used whenever we needed an applied demonstration.

At the same time, I was enrolled in CS380, the school's applied artificial intelligence (AI) class. (I had already completed CS381, theoretical AI and logic.) There we studied usual game AI techniques, such as A* and state machines.

Both classes required a final project, which I decided to combine into one. My mathematics professor was interested in applying game theory to a computer-based Amazons player. Similarly, my AI professor wanted an applied artificial intelligence demonstration, accompanied by text. The result was a large article surveying various CGT AI techniques and my own implementation of an Amazons AI, simply named "Brain".

Brain can be downloaded in ZIP form. It contains both the full source code and Windows executable. The code is written in standard C++ with mild C++11 use, and may be compiled on any standards-conforming C++ compiler partially supporting C++11, including GCC on Linux.

The AI successfully plays Amazons at intermediate level, and can solve a 4x4 board in less than one second (that is, it can figure out a forced win from the starting position). Brain is highly configurable, at both run-time and compile-time. At run-time, game settings like time limits may be modified; at compile-time, implementation settings like board represenatation and search methods may be selected.

The article can be downloaded in PDF form, or viewed below: