adamstelmaszczyk / gtsa

Game Tree Search Algorithms - C++ library for AI bot programming

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.

• Go - game rules, code example.

Implemented algorithms

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

Both handle sequential, multiplayer games:

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}},
}

gtsa's Issues

std namespace

Your gtsa header is

using namespace std;

I think you should remove it, because if I use your header the standard namespaces could clash with my own implementations (or someone might not notice it uses the wrong library)

Zobrist hashing

Maybe Zobrist hashing will be faster than current implementation with boost::hash_combine.

good!

History heuristic

Alpha-Beta Search Enhancements in Practice
https://chessprogramming.wikispaces.com/History+Heuristic
https://chessprogramming.wikispaces.com/Move+Ordering

Null move heuristic

Tests coverage

To see if maybe some critical code was left untested.

Check out www.coveralls.io.

Improve handling time limits in Minimax

input() doesn't work in Python 2

Now on user input used in Human it will raise run-time exception in Python 2.

Have to look for input() which works in Python 2 and 3.

Transposition table in MCTS

This needs more research as it's not clear to me how to add a TT to MCTS, what it will store etc.

Consistent usage of const

Figure out where const should be used and apply such rule consistently.

MCTS can be probably much faster

Right now MCTS does lots of memory allocations. If it used continuous, pre-allocated memory, caching would be better, which will probably significantly boost the overall performance.

ETC (Enhanced Transposition Cutoff)

According to https://webdocs.cs.ualberta.ca/~jonathan/PREVIOUS/Courses/657/Notes/4.DAGs.pdf, roughly 25% reduction in the number of nodes examined.

Details in Exploiting Graph Properties of Game Trees.

Unit tests

Iterative deepening

Mistype in get_uct method

gtsa/cpp/gtsa.hpp

Line 166 in d1f65da

ratio = (visits - score) / score;

Seems like there must be (visits - score) / visits for opponent

Virtual visits

According to Methods of MCTS and the game Arimaa adding 5 virtual visits to the newly expanded nodes improved MCTS.

Better testing framework

To be able to change 1 parameter, run X tests, and decide whether the new version is better.

Killer heuristic

Null-move heuristic

Experiments with the Null-Move Heuristic
https://en.wikipedia.org/wiki/Null-move_heuristic
http://chessprogramming.wikispaces.com/Null+Move+Pruning

Transposition table

Mirror library in C++

Currently only Python library is available. In parallel to it, mirror library will be available, in C++.

Python was chosen because of the speed and ease of development and prototyping. New features and upgrades will be always implemented and tested there first.

However, Python is unfortunately much slower than compiled C++. So, to gain probably like 10-100x speed up there will be a mirror library, a port from Python to C++. Performance is important, 100x speed up means 100x more simulations (within the time limit which always exists during competitions).

The libraries will be both in the same repository. There will be two root directories - python and cpp.

MTD-f

This paper claims that MTD-f is 5-10% faster than than alpha-beta.

RAVE (Rapid Action Value Estimation)

Monte-Carlo Tree Search and Rapid Action Value Estimation in Computer Go.