I recently started trying to implement a monte carlo tree search based algorithm for playing cops and robber.

The game is based on the cops and robber game and is played on an arbitrary graph (not multigraph). There are n cops and one robber. The cops try to catch the robber by moving all at once per round on the graph (only being able to move to other vertices that are connected to the current vertex on the graph). The robber also moves once each turn (first the cops move, then the robber). For initialization the cops pick a vertex for each cop to start and then the robber picks a vertex. The cops and the robber know the position of the other party when moving (so no restricted information).

Edit: There is a bound on the number of rounds played so the game cannot go on forever

Now to my actual question: When trying to apply the monte carlo tree search I stumbled across the following problem:

I am encoding the possible game states into tuples with the positions of the cops and the robber and the current party who's turn it is. These game states are themselves stored in a directed graph data structure (the gamestate graph) with vertices indicating possible next game states.

Now it turns out that the resulting gamestate graph is (in most of the cases) not actually a tree. Or rather not actually circle free. Which is a problem for monte carlo tree search if I understand it correctly.

I stumbled upon this while implementing the selection of the monte carlo method. While selecting the next node (in the gamestate graph) to expand, if one gets into such a circle in the gamestate graph, the selection may never stop.

So my questions are:

  • Is there a way to mitigate this problem?
  • Is there a way to implement the monte carlo tree search on games that may have recurring gamestates?

1 Answer 1


When your game allows recurring gamestates, your game can potentially run for infinity, which is not a problem just for MCS, but for the game itself. Hence you need to modify the game rules, not MCS.

A simple solution for this to make the turn number part of the gamestate, introduce an upper limit for the number of turns allowed for the game, and define happens when the limit is reached (player 1 wins, player 2 wins, or draw).

Another solution is to completely forbid to enter a previous state (as in Go), or to only allow the repetition of a previous state for a fixed number of times (like in Chess).

  • Thank you for your answer. That is definetly an issue. I actually already have a limited round number (and forgot to write that), however that doesn't solve the problem I described in my issue. In the gamestate graph the current round number is not saved. Trying to encode the round number into the nodes of the gamestate graph would also increase the number of nodes drastically and as such would not be feasable. As such I am instead asking how the selection of the gamestate to expand could work with said framework. Jul 18 at 11:32
  • @RaoulLuqué: sorry, but I don't understand how you run the simulation step of MCTS when you don't know the turn number for a gamestate. A random playout needs to make Limit - Current turn number turns, I guess? BTW, there are memory efficient techniques to store nodes which only differ by their round number, if that is your concern.
    – Doc Brown
    Jul 18 at 13:07
  • Okay, maybe I am understanding something wrong here or just not very educated on the matter. Lets say the monte carlo engine is playing as robber: Then in the class of the robber there would be an attribute tracking the current round number. With the help of this attribute I can simulate a played out game from whichever node of the gamestate graph I wish. I am definetly interested in the memory efficient techniques of storing nodes which only differ by their round numbers. That would be a way of mitigating the problem with the selection. Jul 18 at 14:01
  • @RaoulLuqué: the current round number should be an attribute of the game state, not of the robber, and it is independent from the side the engine takes. But I guess when using MCTS, the round number does not have to be stored explicitly, since it can be implicitly reconstructed from the MC tree (it is equal to the node's depth, or half of it if you only count the robber's moves as a turn). Still the round number is available implicitly, which means selection and simulation don't run into an endless loop, even if there are a lot of nodes with the same game state (=locations of cops and robber)
    – Doc Brown
    Jul 18 at 15:01
  • ... Regarding memory efficient techniques: use an immutable data structure for the game state. then you can reference the same state from several different nodes without getting unwanted side effects.
    – Doc Brown
    Jul 18 at 15:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.