Timeline for Monte Carlo Tree Search with Cops and Robber Game
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 18, 2023 at 15:41 | comment | added | Raoul Luqué | Let us continue this discussion in chat. | |
| Jul 18, 2023 at 15:41 | comment | added | Raoul Luqué | I don't quite understand how one would construct a MC tree in this case: I would proceed as follows: Start with a start node (empty gamestate). Start select next gamestate and emulate a game from there and evaluate etc.. Repeat until time is over. However: one may look at possible next gamestates of a gamestate that is already in the gamestate graph. When adding an edge between two nodes in the gamestate graph, said graph is not a tree anymore. In my mind, the gamestate graph for the cops and robber game is more of a circle/(almost) complete graph | |
| Jul 18, 2023 at 15:05 | comment | added | Doc Brown | ... 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. | |
| Jul 18, 2023 at 15:01 | comment | added | Doc Brown | @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) | |
| Jul 18, 2023 at 14:01 | comment | added | Raoul Luqué | 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, 2023 at 13:07 | comment | added | Doc Brown |
@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.
|
|
| Jul 18, 2023 at 11:32 | comment | added | Raoul Luqué | 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, 2023 at 9:57 | history | edited | Doc Brown | CC BY-SA 4.0 |
added 315 characters in body
|
| Jul 18, 2023 at 9:50 | history | answered | Doc Brown | CC BY-SA 4.0 |