Listing all the Games

Question

Following a question here OP is interested in listing all unique 2x2 games. Games here are game theory games in which there with two players and two strategies each. Hence, there are four possible outcomes (see diagram). These outcomes comes with 'payoffs' for each players. Payoff 'pairs' are two payoffs for each player from some combinations of strategies. Payoffs are given in integers and cannot exceed 4.

For instance, consider the following example of a 2x2 game (with a payoff pair is written in the brackets, and P1 and P2 denote player 1 and 2 respectively):

                  P2
            Right   Left

       Up   (2,2)   (3,4)
   P1         
       Down (1,1)   (4,3)

The payoffs here take the values [ (2,2),(3,4) | (1,1),(4,3) ].

Now, clearly many other games (i.e. unique payoff matrices) are possible. If payoffs for each players is given by 1,2,3,4 (which we can permute in 4!=24 ways) then 24*24 games are possible. OP was interested with listing all these games.

Here comes the subtle part: two unique payoff matrices may nevertheless represent games if one can be obtained from the other by

i) exchanging columns (i.e. relabel Player A's strategies)

ii) exchanging rows (i.e. relabel Player B's strategies)

iii) Exchange the players (i.e. exchanging the payoff pairs and mirroring the matrix along the first diagonal)

OP posted the following code that correctly lists all 78 possible games in which the payoffs for each can be (1,2,3,4).

I am interested in changing the code so that the program lists all unique games where the possible payoffs are different: i.e. (1,2,3,3) for player 1 and (1,2,3,4) for player 2. Here, there would be 4!/2! ways of permuting (1,2,3,3) and therefore fewer games.

    #!/usr/bin/groovy

    // Payoff Tuple (a,b) found in game matrix position.
    // The Tuple is immutable, if we need to change it, we create a new one.
    // "equals()" checks for equality against another Tuple instance.
    // "hashCode()" is needed for insertion/retrievel of a Tuple instance into/from
    // a "Map" (in this case, the hashCode() actually a one-to-one mapping to the integers.)

    class Tuple {

       final int a,b

       Tuple(int a,int b) {
          assert 1 <= a && a <= 4
          assert 1 <= b && b <= 4
          this.a = a
          this.b = b
       }

    #!/usr/bin/groovy

    // Payoff Tuple (a,b) found in game matrix position.
    // The Tuple is immutable, if we need to change it, we create a new one.
    // "equals()" checks for equality against another Tuple instance.
    // "hashCode()" is needed for insertion/retrievel of a Tuple instance into/from
    // a "Map" (in this case, the hashCode() actually a one-to-one mapping to the integers.)

    class Tuple {

       final int a,b

       Tuple(int a,int b) {
          assert 1 <= a && a <= 4
          assert 1 <= b && b <= 4
          this.a = a
          this.b = b
       }

       boolean equals(def o) {
          if (!(o && o instanceof Tuple)) {
             return false
          }
          return a == o.a && b == o.b
       }

       int hashCode() {
          return (a-1) * 4 + (b-1)
       }

       String toString() {
          return "($a,$b)"
       }

       Tuple flip() {
          return new Tuple(b,a)
       }
    }

    // "GameMatrix" is an immutable structure of 2 x 2 Tuples:
    // top left, top right, bottom left, bottom right
    // "equals()" checks for equality against another GameMatrix instance.
    // "hashCode()" is needed for insertion/retrievel of a GameMatrix instance into/from
    // a "Map" (in this case, the hashCode() actually a one-to-one mapping to the integers)

    class GameMatrix {

       final Tuple tl, tr, bl, br

       GameMatrix(Tuple tl,tr,bl,br) {
          assert tl && tr && bl && br
          this.tl = tl; this.tr = tr
          this.bl = bl; this.br = br
       }

       GameMatrix colExchange() {
          return new GameMatrix(tr,tl,br,bl)
       }

       GameMatrix rowExchange() {
          return new GameMatrix(bl,br,tl,tr)
       }

       GameMatrix playerExchange() {
          return new GameMatrix(tl.flip(),bl.flip(),tr.flip(),br.flip())
       }

       GameMatrix mirror() {
          // columnEchange followed by rowExchange
          return new GameMatrix(br,bl,tr,tl)
       }

       String toString() {
          return "[ ${tl},${tr} | ${bl},${br} ]"
       }

       boolean equals(def o) {
          if (!(o && o instanceof GameMatrix)) {
             return false
          }
          return tl == o.tl && tr == o.tr && bl == o.bl && br == o.br
       }

       int hashCode() {
          return (( tl.hashCode() * 16 + tr.hashCode() ) * 16 + bl.hashCode() ) * 16 + br.hashCode()     
       }

    }

    // Check whether a GameMatrix can be mapped to a member of the "canonicals", the set of 
    // equivalence class representatives, using a reduced set of transformations. Technically,
    // "canonicals" is a "Map" because we want to not only ask the membership question, but 
    // also obtain the canonical member, which is easily done using a Map. 
    // The method returns the array [ canonical member, string describing the operation chain ]
    // if found, [ null, null ] otherwise.

    static dupCheck(GameMatrix gm, Map canonicals) {
       // Applying only one of rowExchange, colExchange, mirror will
       // never generate a member of "canonicals" as all of these have player A payoff 4
       // at topleft, and so does gm
       def q     = gm.playerExchange()
       def chain = "player"
       if (q.tl.a == 4) {
       }
       else if (q.tr.a == 4) {
          q = q.colExchange(); chain = "column ∘ ${chain}"
       }
       else if (q.bl.a == 4) {
          q = q.rowExchange(); chain = "row ∘ ${chain}"
       }
       else if (q.br.a == 4) {
          q = q.mirror(); chain = "mirror ∘ ${chain}"
       }
       else {
          assert false : "Can't happen"
       }
       assert q.tl.a == 4
       return (canonicals[q]) ? [ canonicals[q], chain ] : [ null, null ]
    }

    // Main enumerates all the possible Game Matrixes and builds the
    // set of equivalence class representatives, "canonicals".
    // We only bother to generate Game Matrixes of the form
    // [ (4,_) , (_,_) | (_,_) , (_,_) ]
    // as any other Game Matrix can be trivially transformed into the
    // above form using row, column and player exchange.

    static main(String[] argv) {
       def canonicals = [:]
       def i = 1
       [3,2,1].permutations { payoffs_playerA ->
          [4,3,2,1].permutations { payoffs_playerB ->
             def gm = new GameMatrix(
                           new Tuple(4,                  payoffs_playerB[0]),
                           new Tuple(payoffs_playerA[0], payoffs_playerB[1]),
                           new Tuple(payoffs_playerA[1], payoffs_playerB[2]),
                           new Tuple(payoffs_playerA[2], payoffs_playerB[3])
                      )
             def ( c, chain ) = dupCheck(gm,canonicals)
             if (c) {
                System.out << "${gm} equivalent to ${c} via ${chain}\n"
             }
             else {
                System.out << "${gm} accepted as canonical entry ${i}\n"
                canonicals[gm] = gm
                i++
             }
          }
       }
    }

---

I have attempted changing the "assert 1 <= a && a <= 4" to "assert 1 <= a && a <= 3" and then changing the 4's to a 3 further down in the code. This does not seem to work.

I am not sure however what the "int hashCode() {return (a-1) * 4 + (b-1)" or if "(q.tl.a == 4) { } else if (q.tr.a == 4) {" does and therefore not sure how to change this.

Apart from this, I suspect that the flips and exchanges can remain the way they are, since this should produce a procedure for identifying unique games no matter what the specific payoff set is (i.e. whether it's 1,2,3,4 or 1,2,3,3).

---

I have calculated the number of unique games for different payoff sets by hand which may be useful for reference.

Answer 1

I had a similar situation making an AI for Othello/Reversi, and wanting the state-space to be as small as possible to remove redundant processing. The technique I used was to represent the game as a set of meta-states, or in your case, meta-outcomes, where each meta consists of all the permutations which are equivalent. Listing and identifying equivalent permutations involved coming up with a normalization scheme which determines which orientation or reflection is the key for the meta instance. Then all new permutations are transformed to normalize them before comparing to see if they represented a new instance.

In your case, if swapping rows and columns are both considered equivalent, you might consider the case where the orientation of sorted order puts the smallest value in the top-left corner and the next smallest adjacent value in the top-right corner. This normalizes all 4 flip positions (identity, h-flip, v-vlip, hv-flip) into a single representation.