adamstelmaszczyk/gtsa

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

gtsa's Issues

MTD-f

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

Null move heuristic

Better testing framework

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

Consistent usage of const

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

Transposition table

Improve handling time limits in Minimax

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.

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)

Virtual visits

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

Zobrist hashing

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

RAVE (Rapid Action Value Estimation)

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

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

Null-move heuristic

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

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.

Iterative deepening

Killer heuristic

Unit tests

Tests coverage

To see if maybe some critical code was left untested.

Check out www.coveralls.io.

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.

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.

good!

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.

History heuristic

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