How to calculate move while avoiding deep copy

When you develop your game object-oriented, this might be a good application for the flyweight pattern.

In this context, a flyweight would be an object which acts as a copy of the gamestate, but actually references the original gamestate it was created from while also having one or more modifications to it.

To create a flyweight, you need

1. a reference to either a gamestate or another flyweight which is the base of this flyweight (the "parent")
2. the change or changes you want to make to that parent

When a value is read from a flyweight, it first checks if the value which is read is the or one of the changes. When that's the case, it returns the changed value. When this isn't the case, it delegates the read to the parent.

The advantage of this pattern is that the creation of a new copy is very cheap. The complexity in both memory and runtime only depends on the size of the changes. However, access is slightly less efficient and will get less and less efficient the more flyweights you nest into each other to represent multiple changes which build onto each other. However, in a typical game AI these reference chains shouldn't be very deep.

You may want to try to optimize it, copying data should be relatively lightweight.

Some things you can do:

• Allocate enough memory for the copy beforehand, instead of allocating for every single object. Each allocation call is expensive and you should be able to reduce it to a single one. This is probably the biggest bottle neck in your case.
• Reduce the size of the single objects.
  • Split the definition of objects (e.g. stuff that doesn't change after the object was created) and the object itself, this should make it possible to reduce the size of the single object by a lot.
• Mem-copy large blocks of data, rather than calling copy constructors for each one. Much easier to run in parallel and you shouldn't run into any cache misses that way.

While there have been several answers focusing on the question you asked I think you're barking up the wrong tree here.

If the cost of copying is bogging you down you have a lot of game objects and thus the tree you are describing will grow very fast. I doubt you are going to get enough depth to the tree to be of much value here.

Exhaustive trees are only an option in games where the choices are simple. After all, even chess has a tree that is beyond computation.

Instead of replicating state in each new node you could just keep state differences between a node and its parent in the tree. By traversing the tree from the root node to a node at depth n you can calculate the new state at n.

It would be useful to know which language you're using, as memory management changes a lot. Some general ideas:

• When searching, you don't have to generate the whole search space up front. If you're using something like alpha-beta prune or any heuristic so you early out branches of the tree, then you can copy the nodes only as you need them, and save a lot of sections that will never get explored.
• An alternative to copying is to keep a single copy of the objects, apply the action to see the results, then undo the action, before evaluating the next node. Rinse and repeat. This is much cheaper memory-wise, but requires you to be able to undo all the actions to do the search.
• In general, I'd recommend having a simplified representation of the objects, for AI reasoning purposes. This is different from the Flyweight pattern suggested by Philipp. You may need to recreate the transformations that the actions apply to the objects and distill it to the minimum (so for instance, you don't update animation states if the AI doesn't care about it).
• Finally, standard optimization advice applies. Profile, see what's expensive to copy, then make it cheap :)