Game Tree Search Algorithms

C++ library for AI bot programming.

Usage

1. Specify game rules by subclassing State and Move.
2. Choose AI algorithm (Minimax, MonteCarloTreeSearch), play by yourself (Human) or against external program (Executable).
3. Read the game state, pass it to the algorithm and output the move. For local, statistically significant tests, use Tester.

Game examples

• Tic Tac Toe - game rules, code example.

• Isola - game rules, code example.

• Connect Four - game rules, code example.

Implemented algorithms

• NegaScout with iterative deepening and transposition table.
• Monte Carlo tree search with UCT.

Make commands

Execute below commands in the cpp directory.

• make builds everything.
• make test runs unit tests.
• make valgrind runs valgrind's memory leak tests.
• make play_isola plays a game of Isola between two bots.

For all the commands check Makefile file.

Dependencies

• To build and run unit tests, g++-4.8 and libboost-all-dev packages are needed.
• To run valgrind, valgrind package is needed.
• To make GIFs, imagemagick package is needed.

You can install all of them with sudo apt-get install g++-4.8 libboost-all-dev valgrind imagemagick.

Priorities of the library

1. Correctness.
2. Compliance with environment typical for competitions. One file submission, compiled with one invocation of g++.
3. Performance.

Would like to help?

Suggestions welcome on Issues. Pull requests too.

I'm transferring 50$ to anybody who reports an actual bug.

To cite this repository:

@misc{stelmaszczyk2015gtsa,
    author = {Stelmaszczyk, Adam},
    title = "{Game Tree Search Algorithms}",
    year = {2015},
    publisher = {GitHub},
    journal = {GitHub repository},
    howpublished = {\url{https://github.com/AdamStelmaszczyk/gtsa}},
}