Implementing monte-carlo tree search in a tile based game with units

Question

I have this simple risk-like game I would like to develop an AI for. Players move their Units on the map and a simple fight resolution is done. There is a time constraint of 100ms for each round, the AI has complete information and fight resolution is deterministic but units move simultaneously each round.

As far as I understand the monte carlo approach, I need to copy the state of a current round and generate a tree with new game states, play it out randomly or do an evaluation.

Currently my zones keeps a list each unit and they're moved around by storing orders. They're kept in a dictionary for each turn and are applied at the end of the round. Deep copying this takes around 3ms and I guess is too slow to use effectively considering the time constraint. I was wondering if I could use this order-system to generate the tree faster by applying and undoing them, but I can't yet wrap my head around how I would do it.

This is my current class design:

How can I effectively add MCTS for this kind of game?

Answer 1

In my experience with AI planning, copying the state was indeed very slow and your suggested idea (maintaining a single copy of the state and undoing the actions when you go "up the tree") worked much better. But that really depends on the size of your state and language you use: in C++ you could probably use custom allocators to fit the whole state into a continuous block of memory which would be copied extremely quickly with memcpy. Copying into preallocated memory/objects also helps a lot.

If copying state is slow even with preallocation, the simplest solution would probably be to add a OrderUndo interface and every Order implementation would have a createUndo() method to produce the undo instance. The implementations of OrderUndo would then preserve a minimal subset of the game state (different orders result in different modification of state, hence the polymorphism) and they would have an apply() method that would restore the particular part of state.

Upon search, you simply execute orders and put undo's on a stack and when traversing back apply the undo's on top of the stack.

For speed you should also preallocate memory / create an object pool for the undo objects (memory allocation tends to be veeeery slow regardless of language). So the createUndo method would have a signature similar to createUndo(UndoPool pool).

Answer 2

The simplest method is to implement a "copy" primitive. Copy the game at the root of the search and run forward using the existing machinery. Repeat.