5
$\begingroup$

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?

Improve this question
$\endgroup$
9
  • $\begingroup$ AS you said, if the game is simple enough, MCTS will search the whole tree easily. So you can try tic-tac-toe with a low number of iterations $\endgroup$
    – Miguel Saraiva
    Commented May 21, 2019 at 15:27
  • $\begingroup$ I can use tic-tac-toe to construct a tree, but it does not easily reveal if all properties in the tree are correct. Example: Depending on the game, you should alternate in the expand step, if UCT is based on the expected score for player 1 or player 2, even when building the tree for player 1. If you do not do this, the strategy will be worse when using an incomplete tree. When using a fully expanded tree you won't notice the difference. To catch all such details, it would be best to have a game with a clear winning strategy even when the tree is not fully expanded. $\endgroup$
    – allo
    Commented May 21, 2019 at 17:59
  • $\begingroup$ What do you mean by "Depending on the game, you should alternate in the expand step" ? alternate between what? $\endgroup$
    – Miguel Saraiva
    Commented May 21, 2019 at 18:10
  • 1
    $\begingroup$ I think you're on the right track using a simple m,n,k-game. Possibly expand the board dimensions to the maximum size that is tractable on your equipment, then restrict the MCTS searches to simulate intractability, and compare the MCTS results to perfect play with an exhausted game tree? (Problem with truly intractable models like Go is you can never know for certain what constitutes perfect play, only that one player has played more optimally if they win.) $\endgroup$
    – DukeZhou
    Commented May 21, 2019 at 20:37
  • 1
    $\begingroup$ Tic-Tac-Toe generally actually is my first test case when I write a new MCTS implementation / add something to an existing one. This test case may not catch every single bug, but it can already catch a lot of bugs, and you'll be sure there won't be any "False Positives": if your agent does not immediately play perfectly, you'll know for sure there's a bug somewhere. In many other games, you do not have as much certainty; it may play imperfectly even when the implementation is correct. $\endgroup$
    – Dennis Soemers ♦
    Commented May 22, 2019 at 7:24

2 Answers 2

Reset to default
4
$\begingroup$

A good choice might be smaller-scale games of Go, like a 9x9 board. This was the original application domain MCTS was designed for, and the original paper by Brugmann from 1993 details parameters that should lead to an agent that can play above beginner level in what is today a minuscule amount of computational time, in a scaled-down 9x9 grid.

Go is a good choice for a benchmark because most learning algorithms fail at it pretty badly. The fact that MCTS worked here was a major breakthrough at the time, and helped cement it as a technique for game playing. If your algorithm is not working properly, it is therefore unlikely that it can learn to play Go at the level described in Brugmann's paper.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Good point about Go vs. m,n,k-games. $\endgroup$
    – DukeZhou
    Commented May 21, 2019 at 21:38
  • $\begingroup$ Go is of course the application for mcts. But I think implementing its rules is quite a bit of code as well and I try to find a minimal game as example program and validation for some more generic framework I am working on. In the end I want to apply the framework to other problems, but before doing so I want to be sure that it works correctly. But your answer is still a good suggestion and in the long term adding a simple Go implementation can help other people to compare the results to other implementations. $\endgroup$
    – allo
    Commented May 21, 2019 at 22:54
  • 1
    $\begingroup$ @allo Probably to handle all the edge cases in Go might be a bit involved, but the core gameplay is actually very simple (that's part of why AI researchers were frustrated by its difficulty). There's a good 9-rule summary here: en.wikipedia.org/wiki/Rules_of_Go#Concise_statement, and any number of existing implementations you could use as a starting point. $\endgroup$
    – John Doucette
    Commented May 22, 2019 at 1:51
1
$\begingroup$

I now currently use:

I currently have, but may remove:

  • Iterated prisoners dilemma (hard to interpret and I am not sure if MCTS is really the right choice)

I may add sometime:

Other good ideas:

I did not try all ideas, as I just want to verify my framework, that should be used on other problems (that are harder to verify). You can still keep adding answers with good ideas, that may be a good reference for others that want to test their implementations.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .