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?