What is a simple turn-based game, that can be used to validate a Monte-Carlo Tree Search code and it's parameters?
Before applying it to problems where I do not have a possiblity to validate its moves for correctness, I would like to implement a test case, that makes sure that it behaves as expected, especially when there are some ambiguities between different implementations and papers.
I built a connect-four game in which to MCTS-AI play against each other and an iterated prisoners dilemma implementation, in which a MCTS-AI plays against common strategies like Tit-for-Tat, but I am still not sure if there is a real good interpretation if the MCTS-AI finds the best strategy.
Another alternative would be a tic-tac-toe game, but MCTS will exhaust the whole search space within little steps, so it is hard to tell how the implementation will perform on other problems.
In addition, expanding a full game tree does not tell you if any states before the full expansion are following the best MCTS strategy.
Example: You can alternate in the expand step of player 1's tree between optimize for player 1 and optimize for player 2, assuming that player 2 will not play the best move for player 1, but the best move for himself. Not doing so would result in an optimistic game tree, that may work in some cases, but probably is not the best choice for many games, while it would be useful for cooperative games.
When the game tree is fully expanded, you can find the best move, even when the order of the expand steps was not optimal, so using a game that can be fully expanded is no good test to validate the in-between steps.
Is there a simple to implement game, that can be used for validation, in which you can reliably check for each move, if the AI did find the expected move?