[Fyron]

First off, note that cores never wait for other cores; cores are always running, always processing instructions. The kernel task scheduler puts various processes and threads on each core dynamically, as needed for optimal load-balancing.

Abandoning the garbage sequential movement mode solves the concurrency issue nicely. If all game modes featured simultaneous movement, each AI can think at the same time, since all they are doing is giving orders. They can even do all their thinking while the human player is playing his turn... Turn resolution can still benefit somewhat from multithreading, since you could process the movement of all of an empire's ships in one thread. Have each one process one day worth of movement and wait for combat resolutions.

With 20 threads and 4 cores (a full game), the kernel task scheduler would typically have 5 of the threads process on each core (though it could really be any distribution, depending on how long each AI thread takes to finish). Each AI thread would process one day of movement, then go to sleep. After all such AI threads are sleeping, all pending combats would then be assigned their own threads, and executed in parallel. Once they are all done, the main game thread just has to wake up each of the AI threads.