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.

<p><a href="https://github.com/AdamStelmaszczyk/gtsa/blob/master/cpp/examples/tic_tac_toe.md"><img src="https://github.com/AdamStelmaszczyk/gtsa/blob/master/cpp/examples/tic_tac_toe.gif"/></a></p>

• Isola - game rules, code example.

<p><a href="https://github.com/AdamStelmaszczyk/gtsa/blob/master/cpp/examples/isola.md"><img src="https://github.com/AdamStelmaszczyk/gtsa/blob/master/cpp/examples/isola.gif"/></a></p>

• Connect Four - game rules, code example.

<p><a href="https://github.com/AdamStelmaszczyk/gtsa/blob/master/cpp/examples/connect_four.md"><img src="https://github.com/AdamStelmaszczyk/gtsa/blob/master/cpp/examples/connect_four.gif"/></a></p>

• Go - game rules, code example.

<p><a href="https://github.com/AdamStelmaszczyk/gtsa/blob/master/cpp/examples/go.md"><img src="https://github.com/AdamStelmaszczyk/gtsa/blob/master/cpp/examples/go.gif"/></a></p>

Implemented algorithms

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

Both handle sequential, multiplayer games:

<img src="https://github.com/AdamStelmaszczyk/gtsa/blob/master/cpp/examples/isola_four.gif"/></a></p>

MCTS also handles simultaneous games using SUCT.

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 as many games as needed to determine which Isola bot is better.

For all the commands check Makefile file.

Dependencies

• To build and run unit tests, g++ 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++ libboost-all-dev valgrind imagemagick.

Priorities of the library

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

Would like to help?

Suggestions welcome on Issues. Pull requests too.

If you use code or ideas from this repository, please cite it as follows:

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