列出所有游戏

Question

在这里提出一个问题OP有兴趣列出所有独特的2x2游戏.这里的游戏是游戏理论游戏,其中有两个玩家和两个策略.因此,有四种可能的结果(见图).这些结果伴随着每个球员的"回报".支付'对'是来自某些策略组合的每个玩家的两个回报.支付以整数给出,不能超过4.

例如,考虑以下2x2游戏的示例(支付对写在括号中,P1和P2分别表示玩家1和2):

                  P2
            Right   Left

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

这里的收益取值[(2,2),(3,4)| (1,1),(4,3)].

现在,显然许多其他游戏(即独特的支付矩阵)是可能的.如果每个玩家的收益是1,2,3,4(我们可以在4种方式中排除!= 24种方式),则可以进行24*24场比赛.OP有兴趣列出所有这些游戏.

这里有一个微妙的部分:两个独特的支付矩阵可能代表游戏,如果一个可以从另一个获得

i)交换列(即重新标记玩家A的策略)

ii)交换行(即重新标记玩家B的策略)

iii)交换玩家(即交换支付对并沿第一对角线镜像矩阵)

OP发布了以下代码,正确列出了所有78种可能的游戏,其中每种游戏的收益可以是(1,2,3,4).

我有兴趣更改代码,以便程序列出所有可能的收益不同的独特游戏:即玩家1的(1,2,3,3)和玩家2的(1,2,3,4). ,会有4!/ 2!置换方式(1,2,3,3),因此更少的游戏.

    #!/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++
             }
          }
       }
    }

---

我试图将"断言1 <= a && a <= 4"改为"断言1 <= a && a <= 3",然后在代码中将4更改为3.这似乎不起作用.

然而,我不确定"int hashCode(){return(a-1)*4 +(b-1)"或"if(q.tl.a == 4){} else if(q.tr. a == 4){"但确实如何改变这一点.

除此之外,我怀疑翻转和交换可以保持原样,因为无论特定的支付集是什么(即是1,2,3,4或1, 2,3,3).

---

我已经手动计算了不同支付集的独特游戏数量,可供参考.

Answer 1

我也遇到过类似的情况，为黑白棋制作人工智能，并希望状态空间尽可能小以消除冗余处理。我使用的技术是将游戏表示为一组元状态，或者在您的情况下，表示元结果，其中每个元由所有等效的排列组成。列出和识别等效排列涉及提出一个规范化方案，该方案确定哪个方向或反射是元实例的关键。然后，所有新的排列都会被转换以对它们进行标准化，然后进行比较以查看它们是否代表新的实例。

在您的情况下，如果交换行和列都被认为是等效的，您可能会考虑这样的情况：排序顺序的方向将最小值放在左上角，将下一个最小相邻值放在右上角。这将所有 4 个翻转位置（identity、h-flip、v-vlip、hv-flip）标准化为单个表示。