IMO, program multi-threaded games is not that hard, but the problem is where and how to divide the game into parts. It will gain no performance boost if we divid the game in a wrong way.
The single threaded process is probably like this, Game State -> AI actions -> Physics -> Graphics and loop. If we cut them into pipeline stages, we probably gain nothing. We still have the same amount of delay in the game.
It has to be reodered to something like this
Game State -> AI actions thread and Physics thread -> Graphics. Each stage is dependen by the previouse stage result. By doing this, we only shorten the delay from 4 to 3 times of the longest stage. Multi-threaded utilization is only max at two in second stage.
In order to truly tab the power of multi-threaded envirnment, we have to shorten the stage as well. This is where the hardest part, especially with physics.
Where to optimize, IMO explotion is always a power monster, optimize that is first priority.