FP proponents have claimed that concurrency is easy because their paradigm avoids mutable state. I don't get it.

Imagine we're creating a multiplayer dungeon crawl (a roguelike) using FP where we emphasize pure functions and immutable data structures. We generate a dungeon composed of rooms, corridors, heroes, monsters and loot. Our world is effectively an object graph of structures and their relationships. As things change our representation of the world is amended to reflect those changes. Our hero kills a rat, picks up a shortsword, etc. 

To me the world (current reality) carries this idea of state and I'm missing how FP overcomes this. As our hero takes action, functions amend the state of the world. It appears to be every decision (AI or human) needs to be based on the state of the world as it is in the present. Where would we allow for concurrency? We can't have multiple processes concurrently ammending the state of the world lest one process base its outcomes on some expired state. It feels to me that all control should occur within a single control loop so that we're always processing the present state represented by our current object graph of the world.

Clearly there are situations perfectly suited for concurrency (i.e. When processing isolated tasks whose states are independent of one another).

I'm failing to see how concurrency is useful in my example and that may be the issue. I may be misrepresenting the claim somehow. 

Can someone better represent this claim?
['https://softwareengineering.stackexchange.com/questions/195718', 'https://softwareengineering.stackexchange.com', 'https://softwareengineering.stackexchange.com/users/88091/']
I'll try to hint on the answer. This is *not* an answer, only an introductory illustration. @jk's answer points to the real thing, zippers.

Imagine you have an immutable tree structure. You want to alter one node by inserting a child. As a result, you get a whole new tree.

But most of the new tree is exactly the same as old tree. [A clever implementation](http://en.wikipedia.org/wiki/Persistent_data_structure#Trees) would reuse most of the tree fragments, routing pointers around the altered node:

![From Wikipedia](https://i.imgur.com/U5FOpOE.png)

[Okasaki's book](http://rads.stackoverflow.com/amzn/click/0521663504) is full of examples like this.

So I suppose you could reasonably alter small parts of your game world each move (pick up a coin), and only actually change small parts of your world data structure (the cell where the coin was picked up). Parts that only belong to past states will be garbage-collected in time.

This probably takes some consideration in designing the data game world structure in an appropriate way. Unfortunately, I'm no expert in these matters. Definitely it must be something else than a NxM matrix one would use as a mutable data structure. Probably it should consist of smaller pieces (corridors? individual cells?) that point to each other, as tree nodes do.
[9000's answer](https://softwareengineering.stackexchange.com/a/195730/31260) is half the answer, persistent data structures allow you to reuse unchanged parts. 

You may already be thinking however "hey what if I want to change the root of the tree?" as it stands with the example given that now means changing all the nodes. This is where [Zippers](http://en.wikipedia.org/wiki/Zipper_%28data_structure%29) come to the rescue. They allow element at a focus to be changed in O(1), and the focus can be moved anywhere in the structure.

The other point with zippers is that a [Zipper exists for pretty much any data type you want](http://en.wikibooks.org/wiki/Haskell/Zippers#Differentiation_of_data_types)