AdamStelmaszczyk / gtsa / 481

88%

Build Type

push

travis-ci-com

Committed by Adam Stelmaszczyk

Commit Message

Fix the UCT maximization

This fixes a severe bug that was making MCTS + UCT much weaker.

Root player move was corractly taken as:

max(ratio + UCT)

However, for the opponent wrong move was taken:

min(ratio - UCT)

I thought it was doing:

min(- ratio - UCT)

which would be correct.

I also simplified by always taking the max ratio (ratio = score / visits). Negamax trick.
Score is always stored with the respect to the player_to_move.

So e.g. root player has ratio = 0.7. However on opponent turn
we also want to take max, so want to have ratio 0.3 (for the same state).
To do this I pass "player" argument to the get_uct function,
to get UCT with respect to that player.

It passes all the unit tests, it also wins with Minimax(0.1)
when given 10s (does ~70-90k simulations). When given 1s (~7k simulations)
it loses. In 0.1s Minimax looks at ~80k positions, so MCTS is much slower.
There is probably a lot of optimization space in MCTS, e.g. unordered_set.

Run Details

18 of 18 new or added lines in 1 file covered. (100.0%)

761 of 851 relevant lines covered (89.42%)

268268.76 hits per line