FP proponents have claimed that concurrency is easy because their
paradigm avoids mutable state. I don't get it.
I wanted to pitch in about this general question as someone who is a functional neophyte but has been up to my eyeballs in side effects over the years and would like to mitigate them, for all kinds of reasons, including easier (or specifically "safer, less error-prone") concurrency. When I glance over at my functional peers and what they're doing, the grass seems a bit greener and smells nicer, at least in this regard.
That said, about your specific example, if your problem is serial in nature and B cannot be executed until A is finished, conceptually you can't run A and B in parallel no matter what. You have to find a way to break the order dependency like in your answer based on making parallel moves using old game state, or use a data structure which allows parts of it to be independently modified to eliminate the order dependency as proposed in the other answers, or something of this sort. But there are definitely a share of conceptual design problems like this where you can't necessarily just multithread everything so easily because things are immutable. Some things are just going to be serial in nature until you find some smart way to break the order dependency, if that's even possible.
That said, there are many cases where we fail to parallelize programs that involve side effects in places that could potentially significantly improve performance simply because of the possibility that it might not be thread-safe. One of the cases where eliminating the mutable state (or more specifically, external side effects) helps a lot as I see it is that it turns "may or may not be thread-safe" into "definitely thread-safe".
To make that statement a bit more concrete, consider that I give you a task to implement a sorting function in C which accepts a comparator and uses that to sort an array of elements. It's meant to be quite generalized but I'll give you an easy assumption that it will be used against inputs of such a scale (millions of elements or more) that it will doubtlessly be beneficial to always use a multithreaded implementation. Can you multithread your sorting function?
The problem is that you cannot because the comparators your sorting function calls may cause side effects unless you know how they are implemented (or at the very least documented) for all possible cases which is kind of impossible without degeneralizing the function. A comparator could do something disgusting like modify a global variable inside in a non-atomic way. 99.9999% of comparators may not do this, but we still can't multithread this generalized function simply because of the 0.00001% of cases that might cause side effects. As a result you might have to offer both a single-threaded and multithreaded sort function and pass the responsibility to the programmers using it to decide which one to use based on thread safety. And people might still use the single-threaded version and miss opportunities to multithread because they might also be unsure whether the comparator is thread-safe, or whether it will always remain as such in the future.
There's a whole lot of brainpower that can be involved in just rationalizing about the thread safety of things without throwing locks everywhere which can go away if we just had hard guarantees that functions won't cause side effects for now and the future. And there's fear: practical fear, because anyone who has had to debug a race condition a few too many times would probably be hesitant about multithreading anything that they can't be 110% sure is thread-safe and will remain as such. Even for the most paranoid (of which I am probably at least borderline), the pure function provides that sense of relief and confidence that we can safely call it in parallel.
And that's one of the main cases where I see it as so beneficial if you can get a hard guarantee that such functions are thread-safe which you get with pure functional languages. The other is that functional languages often promote creating functions free of side effects in the first place. For example, they might provide you with persistent data structures where it's reasonably quite efficient to input a massive data structure and then output a brand new one with only a small part of it changed from the original without touching the original. Those working without such data structures might want to modify them directly and lose some thread safety along the way.
That said, I disagree with one part with all due respect to my functional friends (who I think are super cool):
[...] because their paradigm avoids mutable state.
It's not necessarily immutability that makes concurrency so practical as I see it. It's functions that avoid causing side effects. If a function inputs an array to sort, copies it, and then mutates the copy to sort its contents and outputs the copy, it's still just as thread-safe as one working with some immutable array type even if you're passing the same input array to it from multiple threads. So I think there's still a place for mutable types in creating very concurrency-friendly code, so to speak, though there are a lot of additional benefits to immutable types, including persistent data structures which I use not so much for their immutable properties but to eliminate the expense of having to deep copy everything in order to create functions free of side effects.
And there's often overhead to making functions free of side effects in the form of shuffling and copying some additional data, maybe an extra level of indirection, and possibly some GC on parts of a persistent data structure, but I look at one my buddies who has a 32-core machine and I'm thinking the exchange is probably worth it if we can more confidently do more things in parallel.