Answers.Body: <p>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 <a href="http://www.ideanest.com/vegos/MonteCarloGo.pdf" rel="nofollow noreferrer">original paper</a> 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. </p>
  
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-05-21T21:38:52.953Z
Answers.Text: Good point about Go vs. m,n,k-games.
Answers.UserDisplayName: DukeZhou
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-05-21T22:54:45.757Z
Answers.Text: 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.
Answers.UserDisplayName: allo
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-05-22T01:51:40.737Z
Answers.Text: @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: https://en.wikipedia.org/wiki/Rules_of_Go#Concise_statement, and any number of existing implementations you could use as a starting point.
Answers.UserDisplayName: John Doucette
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-05-21T21:00:04.693Z
Answers.LastActivityDate: 2019-05-21T21:00:04.693Z
Answers.UserDisplayName: John Doucette
Answers.Body: <p>I now currently use:</p>
  
  <ul>
  <li><a href="https://en.wikipedia.org/wiki/Connect_Four" rel="nofollow noreferrer">Connect four</a> / a <a href="https://en.wikipedia.org/wiki/M,n,k-game" rel="nofollow noreferrer">m,n,k-game</a></li>
  <li><a href="https://boardgamegeek.com/boardgame/1875/isolation" rel="nofollow noreferrer">Isolation</a> with 6x8 board</li>
  </ul>
  
  <p>I currently have, but may remove:</p>
  
  <ul>
  <li>Iterated prisoners dilemma (hard to interpret and I am not sure if MCTS is really the right choice)</li>
  </ul>
  
  <p>I may add sometime:</p>
  
  <ul>
  <li><a href="https://en.wikipedia.org/wiki/Tic-tac-toe" rel="nofollow noreferrer">Tic-tac-toe</a> as very simple verification</li>
  <li><a href="https://en.wikipedia.org/wiki/Dots_and_Boxes" rel="nofollow noreferrer">Dots and Boxes</a> (looks like it could be an interesting planning problem)</li>
  </ul>
  
  <p>Other good ideas:</p>
  
  <ul>
  <li><a href="https://en.wikipedia.org/wiki/Rules_of_Go#Concise_statement" rel="nofollow noreferrer">Go with simplified rules</a> (thanks John Doucette)</li>
  </ul>
  
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-06-12T08:41:02.370Z
Answers.LastActivityDate: 2019-06-12T08:41:02.370Z
Answers.UserDisplayName: allo
Body: <p>What is a simple turn-based game, that can be used to validate a Monte-Carlo Tree Search code and it's parameters?</p>
  
  <p>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.</p>
  
  <p>I built a <em>connect-four game</em> in which to MCTS-AI play against each other and an <em>iterated prisoners dilemma</em> 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.</p>
  
  <p>Another alternative would be a <em>tic-tac-toe</em> 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.</p>
  
  <p>In addition, expanding a full game tree does not tell you if any states before the full expansion are following the best MCTS strategy.</p>
  
  <hr>
  
  <p><em>Example:</em>
  You can alternate in the expand step of player 1's tree between <em>optimize for player 1</em> and <em>optimize for player 2</em>, 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.</p>
  
  <p>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.</p>
  
  <hr>
  
  <p>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?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-05-21T15:27:35.827Z
Comments.Text: 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
Comments.UserDisplayName: Miguel Saraiva
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-05-21T17:59:59.423Z
Comments.Text: 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.
Comments.UserDisplayName: allo
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-05-21T18:10:08.987Z
Comments.Text: What do you mean by "Depending on the game, you should alternate in the expand step" ? alternate between what?
Comments.UserDisplayName: Miguel Saraiva
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-05-21T18:21:22.547Z
Comments.Text: I added it to the question. I think you should alternate between optimizing for player 1 and optimizing for player 2, because you must assume that player 2 will optimize for himself. But this is only one example. When you actually implement it in a more general setting, you find a lot of details that aren't all that clear as in the pseudo code and the simple example code bases. So I am looking for good games that can be used to verify that the implementation finds the best possible solution.
Comments.UserDisplayName: allo
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-05-21T18:25:49.567Z
Comments.Text: Why would you alternate? when you simulate a game, starting at the selected state in selection phase (or one of the children), you will end up with either A or B winning and you update the nodes that belong to the winner with +1 wins, and all the nodes on the path with +1 simulations. I know this wasn't your question, but I was just trying to make sense from the rest.
Comments.UserDisplayName: Miguel Saraiva
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-05-21T18:57:40.563Z
Comments.Text: @MiguelSaraiva When I expand a move of player 1, the children of the next state are moves of player 2. As I must assume, that player 2 chooses the best move for himself, I should not expand the best move for player 1, but the best move for player 2. I use two different trees, as one player could build a whole different tree, e.g., using another constant in the UCT function. DukeZhou: I am looking for any good test cases. I want to be able to verify as much correctness as possible. Just "wins 80% of the games" is no good benchmark if you do not know if it should be 90% or not.
Comments.UserDisplayName: allo
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-05-21T20:37:10.550Z
Comments.Text: 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.)*
Comments.UserDisplayName: DukeZhou
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-05-21T20:57:57.447Z
Comments.Text: I think I will add [Isolation](https://en.wikipedia.org/wiki/Isolation_(board_game)) as well. But really checking the moves is more an heuristic in most games, as in "why doesn't the AI see, that it must prevent the next move of the opponent", but it is harder to be sure if the AI must have seen the problem three moves ago.
Comments.UserDisplayName: allo
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-05-22T07:24:11.953Z
Comments.Text: 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.
Comments.UserDisplayName: Dennis Soemers
Tags: <monte-carlo-tree-search>
Title: What is a simple game for validation of MCTS?
UserDisplayName: allo
ThreadText: # What is a simple game for validation of MCTS?
  
  (Asked by: username_0 on 2019-05-21)
  
  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?
  
  **Tags:** monte-carlo-tree-search
  
  > **Comments:**
  > **username_1**: 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  
  > **username_0**: 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.  
  > **username_1**: What do you mean by "Depending on the game, you should alternate in the expand step" ? alternate between what?  
  > **username_0**: I added it to the question. I think you should alternate between optimizing for player 1 and optimizing for player 2, because you must assume that player 2 will optimize for himself. But this is only one example. When you actually implement it in a more general setting, you find a lot of details that aren't all that clear as in the pseudo code and the simple example code bases. So I am looking for good games that can be used to verify that the implementation finds the best possible solution.  
  > **username_1**: Why would you alternate? when you simulate a game, starting at the selected state in selection phase (or one of the children), you will end up with either A or B winning and you update the nodes that belong to the winner with +1 wins, and all the nodes on the path with +1 simulations. I know this wasn't your question, but I was just trying to make sense from the rest.  
  > **username_0**: @username_1 When I expand a move of player 1, the children of the next state are moves of player 2. As I must assume, that player 2 chooses the best move for himself, I should not expand the best move for player 1, but the best move for player 2. I use two different trees, as one player could build a whole different tree, e.g., using another constant in the UCT function. username_2: I am looking for any good test cases. I want to be able to verify as much correctness as possible. Just "wins 80% of the games" is no good benchmark if you do not know if it should be 90% or not.  
  > **username_2**: 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.)*  
  > **username_0**: I think I will add [Isolation](https://en.wikipedia.org/wiki/Isolation_(board_game)) as well. But really checking the moves is more an heuristic in most games, as in "why doesn't the AI see, that it must prevent the next move of the opponent", but it is harder to be sure if the AI must have seen the problem three moves ago.  
  > **username_3**: 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.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_4 on 2019-05-21. Score: 4
  
  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](http://www.ideanest.com/vegos/MonteCarloGo.pdf) 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.
  
  > **Comments:**
  > **username_2**: Good point about Go vs. m,n,k-games.  
  > **username_0**: 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.  
  > **username_4**: @username_0 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: https://en.wikipedia.org/wiki/Rules_of_Go#Concise_statement, and any number of existing implementations you could use as a starting point.  
  
  ---
  
  ### Answer by username_0 on 2019-06-12. Score: 1
  
  I now currently use:
  
  * [Connect four](https://en.wikipedia.org/wiki/Connect_Four) / a [m,n,k-game](https://en.wikipedia.org/wiki/M,n,k-game)
  * [Isolation](https://boardgamegeek.com/boardgame/1875/isolation) with 6x8 board
  
  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:
  
  * [Tic-tac-toe](https://en.wikipedia.org/wiki/Tic-tac-toe) as very simple verification
  * [Dots and Boxes](https://en.wikipedia.org/wiki/Dots_and_Boxes) (looks like it could be an interesting planning problem)
  
  Other good ideas:
  
  * [Go with simplified rules](https://en.wikipedia.org/wiki/Rules_of_Go#Concise_statement) (thanks username_4 username_4)
  
  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.
  
  
  ---
  
  