Monte Carlo Tree Search with Cops and Robber Game

Question

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?

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).