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

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?

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