Using Overlapping Turns To Mitigate Delay: A Discussion of Pipeline Parallelism in Cooperative Games


Last week, we reviewed Astro Knights: it’s a cooperative deck-builder (see our review here). The main hook of Astro Knights is that you don’t have to shuffle your cards when your deck runs out, you just flip the discard pile over! That’s great! No shuffling! One of the other hooks, related to this, is that you have some choice over the order the cards go into the discard pile at the end of your turn. It’s really cool that you have some agency over the order cards might go into your discard, but it’s actually fairy limited. When you buy a new card, it immediately goes to the discard. When weapon cards go off, they immediately go into the discard. The only choice you generally have is over some of your Power cards. In playing, that choice didn’t make “that much of a difference” because the only cards you could could re-order were very limited. We loved this idea of reordering, but it didn’t seem that efficacious in practice.

Potential House Rule for Astro Knights and Aeon’s End


We were going to propose a house rule for Astro Knights about the reordering last week, but it lead us down quite a twisted path: we need to discuss it before we formally propose it.

The proposed House Rule is called Full Reordering:

In Astro Knights or Aeon’s End, any card that would go into the discard pile this turn can be re-ordered in any way the players want at the end of their turn. Those re-ordered cards then go to the top of discard.

Thus, any card that was bought, played, or discarded (weapons in particular) on that turn can be re-ordered as desired into the top of the discard.  So, if you buy a card, it doesn’t immediately go into your discard: it only goes at the end of the turn after you have re-ordered all your cards for that turn!

For ease of maintenance, the player can keep a separate pool of cards discarded/played/bought for that turn (representing cards to be discarded that turn) and re-order them at the very end of their turn.  When they are done re-ordering all the pooled discards, the pooled discards will go into the main discard.

It seems like Full Reordering should have been the rule all along in both Astro Knights and Aeon’s End.  Why wasn’t it? Let’s look into this a little.

Analysis Paralysis 


The main reason the proposed House Rule of Full Reordering is problematic is probably time: if you give the players a chance to re-order 5, 6 ,7 or more cards, then amount of re-orders the user will consider grows quickly … by a factorial!  Thus, with 5 cards to re-order, there are 5! = 60 permutations, 6 cards has 6! = 360 permutations, 7 cards has 7! = 5040 permutations, and factorial grows very fast (approximately exponentially if you believe Stirling’s Approximation)!   And, unfortunately, many players will take all the time they can to find the optimal solution, this increasing the amount of time a player takes on their turn (slowing down the game substantially).

If you “just allow” re-ordering of just a few cards (as per the current ruleset), there are typically only 1 to 4 cards to re-order, which are much are much smaller numbers: 1! = 1, 2! = 2, 3! = 6, 4! = 24.  I suspect the real reason the re-order rule by default is so limited is to avoid analysis paralysis: there are simply too may permutations of the discards if the player is allowed to consider all possible permutations. 

Potential Savior


There is still a potential way that the proposed House Rule of Full Reordering could work: What if we allow the next player to start his turn while the previous player simultaneously re-orders their discards?  This would mean the “re-order discard” step and “start of next turn” would be happening simultaneously!  Simultaneous play is something we are seeing a lot of current modern games: Ares Expedition, Sidekick Saga, Seven Wonders, Race for the Galaxy are just a few modern games where the game has embraced simultaneous play to move play forward.  One of the reasons that Terraforming Mars has fallen off the radar in my group is that Ares Expedition does everything that Terraforming Mars does, but in one quarter the time!  Most of this time reduction is because players are playing/building simultaneously instead of waiting for full completion of the previous player turn.  See our reviews of Ares Expedition and Ares Expedition: Crisis for more discussion.

I would argue that many people already play Astro Knights simultaneously: 

Player 1: “Hey, you done yet re-ordering your cards?” 

Player 2: “Almost, why don’t you just start your turn?” 

As you become more and more familiar with a game, it becomes second nature to exploit the opportunities for simultaneous execution.  Take a look at our blog entry about Arkham Horror and concurrency in our post of Concurrency in Board Games. In Arkham Horror, we start taking advantage of the turn structure to introduce some simultaneous play (concurrency) to move the game along.

Pipeline Parallelism

Let’s take a brief detour into the world of computer architecture: we’ll see a useful metaphor which will inform our discussion of simultaneous play.


Probably the most used textbook in Computer Organization is Hennessy and Patterson’s Computer Organization and Design.  A major topic of this textbook is pipelining: this is a technique modern CPUs use to achieve major performance gains.

The idea of pipelining is simple: break up a task into multiple stages, and execute as many stages in parallel (simultaneously) as you can.  Another similar analogy to the pipeline is the assembly line.


Above is the simplified stage breakup of the MIPS 5-stage pipeline.  Let’s say it takes 5 cycles to execute a single CPU instruction: 1 cycle per stage.  Like the assembly line, there is one worker per stage doing just one job: the first worker can only do Instruction Fetch (IF), the second worker can only do Instruction Decode (ID) and so on.  To finish a task, all 5 stages must be completed in order.

By overlapping the execution of the stages, we can achieve some parallelism and speed up the execution.  See above as it takes 9 cycles to execute 5 tasks (instructions)!  Without the overlapping, it would take 5*5 = 25 cycles to execute the same 5 tasks!

To take that idea further: Without pipelining, 100 instructions would take 500 cycles to execute, as each instruction takes 5 cycles. With pipelining, 100 instructions take 104 cycles to execute, as we can execute the 5 pipeline stages simultaneously, overlapping some of the stages! That’s basically a 5x speedup!

In real life, there are issues as you can’t always necessarily overlap stages.  As long as the stages can be executed independently, (like finishing a turn and starting a next turn), this pipeline parallelism works great!

The problem are the hazards.



Without getting too much into complexities, hazards happen when things interfere with simultaneous execution.  The entire discussion of hazards can be quite deep (Read-After-Write Hazards, Write-After-Write Hazards, timing issues, etc).  For our purposes, the hazards just “get in the way” of simultaneous play.  You’ll notice in the branch chart above that pure overlapping is not happening due to hazards/issues!  That’s the real world!

If you are interested in the idea of simultaneous actions or pipeline parallelism, the ideas found in the Hennessy and Patterson book can be informative: What are the type of hazards that can prevent simultaneous actions?  What are some of the workarounds? The discussion is very technical and focused on modern CPUs, but the ideas it presents are very relevant in other forms of pipeline parallelism.

Back Of The Envelope Timings

In our case for Astro Knights: it takes too long to re-order a large number of cards!  Even if we overlap “the end of a turn” and “the start of a turn“, the player re-ordering may still be re-ordering even AFTER the next player has played!  At some point, the re-ordering will interfere (become a hazard) with a player’s turn! “Uh, I can’t start my turn until I finished re-ordering…”

Let’s say it takes 3 minutes to play a full turn in Astro Knights. And it takes 1 second to consider each permutation.  For 5 cards, that’s 5! = 120 permutations or 2 minutes: that’s not a problem! The re-ordering will finish before the next player’s turn finishes. What about 6 cards?  That’s 6! = 720 or 7 minutes!   What about 7 cards?  That 7! or 5040 seconds or 84 minutes or 1.4 hours!!! 

This overlapping turns mechanism can only work for us if we can somehow keep the re-ordering step short enough.

Opportunity Cost


But Rich“, I can hear you saying, “My friends and I don’t has that much Analysis Paralysis!  We could re-order our cards in under 3 minutes! No problem!”  

Even if that were true, there is another cost: interaction!  When re-ordering your cards, the player’s head is down, focused on the re-order task, which means they are NOT engaged with their fellow players!  In other words, all the cooperation we like in Aeon’s End and Astro Knights is thrown out the window because each player is spending too much time on re-ordering their cards.

There is an opportunity cost: we lose the the opportunity to cooperate and interact when re-ordering.



So, is our proposed House Rule (Full Reordering) even viable?  The number of permutations of cards to re-order is the first real big problem!  The overlapping turns can solve some of that problem, but even then, the simultaneous play is only a partial solution, as you lose some of the interaction/cooperation we like in Astro Knights and Aeon’s End.

Decide for yourself: if you think your group can overlap turns, quickly re-order their discards, and still interact effectively, then maybe Full Reordering is a viable House Rule.  I personally think Full Reordering is probably too fragile a house rule because the effects of any slight analysis paralysis will be devastating.

So maybe that’s why the re-ordering the discard in Astro Knights and Aeon’s End is so limited!


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s