Monday, December 7, 2009

Different Game Sums

Previously there had been some discussion about different methods for summing games. Normally, given two games G1 = {L1 | R1} and G2 = {L2 | R2}, we use the disjunctive sum to describe making one move:

G1 + G2 =
{ { L + G2 : L \in L1} U { G1 + L: L \in L2} |
{R + G2: R \in R1} U {G1 + R: R \in R2} }

Informally, a player may choose one of the subgames, and make one of the moves available to them normally on that summand.

Lots of the discussion of last month concerned "where to apply misereness" to a game. I was trying to apply it to the game objects themselves, while it is usually applied to the play of a game instead. Paul Ottaway stepped in and said this was okay while evaluating games using the short disjunctive sum. When taking the short disjunctive sum, a player does not need to choose a subgame on which they have a move, but if none legal move exists, they immediately lose.

This is not as immediately obvious to define in the above set-notation, so let's give it a try:
(Warning: Attempted Ascii Brackets ahead! Update: Ascii Brackets removed!)

Short Disjunctive: (Update: fixed spacing issue. Did I get it right, though?)
G1 + G2 = { Left | Right } where
if either L1 = null or L2 = null, Left = { L + G2 : L \in L1} U { G1 + L: L \in L2} U { | 0}
otherwise, Left = { L + G2 : L \in L1} U { G1 + L: L \in L2}
if either R1= null or R2=null, Right = {R + G2: R \in R1} U {G1 + R: R \in R2} U {0 | }
otherwise, Right = {R + G2: R \in R1} U {G1 + R: R \in R2}

(Did I do that right?)

Alternatively, one may want to consider the sum where each player chooses to make a move on each of the available game boards. This is called the conjunctive sum of games:

G1 + G2 = { { l1 + l2 | r1 + r2} : l1 \in L1, l2 \in L2, r1 \in R1, r2 \in R2}

This may seem simpler, but after getting used to the disjunctive sum, it likely seems much more complicated from a gamester's point of view. Perhaps we will cover these sums more in the future!

Are there sums I missed? Please let me know!


  1. Thanks for the nods to my research in your past couple posts.

    I'm not sure if the definition you've given for the short disjunctive sum is quite correct (though perhaps I'm simply misunderstanding the ascii brackets).

    It looks like you're saying that if one of the summands has an empty set of options then we can consider it to be {|0} which in normal play is equal to -1. This is clearly not always going to be true but I'm not sure how to fix it using this style of definition.

    To get around this in my work was to define special placeholders which can be treated like games and represent overriding moves (again, following winning ways). These objects become idempotents in the group of games under a short sum.

    On another note - there is also something known as a sequential join of games which is a sum G1+G2 where both players must play in G1 until a player has no moves. At that point, G1 is discarded and play continues in G2.

    The interesting thing about such sums is that you need to know how to play each component in both normal and misere versions. If you have G1+G2 for example and G2 is a P position in normal play, then you need to *lose* G1 so that your opponent must play first in G2. Therefore, we need to play G1 as if it was misere.

  2. Oh wow! This didn't post at all like I tried to have it come out. I forget that html doesn't do spaces like I want it to...

    Let me attempt to fix this...