Significant amount of the operations are read-only operations (attempts to insert an already present game state), so we must ensure that they are physically read-only in our implementation. A common way to achieve this is the lockfree reader pattern.
The idea of the pattern is to make a data structure consistent and available for reading all the time, regardless of the way of implementation of mutating operations. I.e. mutating operations can be synchronized with each other by means of mutexes, however each mutation operation must have a linearization point with regard to readers, after which the operation take all effects and is completely visible for all readers. This does mean that mutation operations under a mutex still must be implemented with concurrency in mind.
Here is an essence of the pattern by example of a concurrent singly-linked list (C++0x concurrency primitives are used):
The fact that there is no concurrent remove operations greatly simplifies the implementation. If there are concurrent remove operations, then some form of PDR (Partial copy-on-write Deferred Reclamation) must be employed in order to ensure that readers can read/traverse a data structure regardless of concurrently removing nodes.
Move on to Lockfree Insert Operation