java - 列出所有游戏

Question

关注一个问题here OP 有兴趣列出所有独特的 2x2 游戏。这里的游戏是博弈论游戏，其中有两个玩家和两个策略。因此，有四种可能的结果(见图)。这些结果伴随着每个玩家的“ yield ”。 yield “对”是每个玩家从某些策略组合中获得的两个 yield 。 yield 以整数形式给出，不能超过 4。

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

                  P2
            Right   Left

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

此处的 yield 取值 [ (2,2),(3,4) | (1,1),(4,3) ].

现在，显然许多其他游戏(即独特的 yield 矩阵)也是可能的。如果每个玩家的 yield 由 1,2,3,4 给出(我们可以用 4!=24 种方式排列)，那么 24*24 场比赛是可能的。 OP 有兴趣列出所有这些游戏。

这里是微妙的部分:如果可以通过以下方式从另一个获得一个，则两个唯一的支付矩阵仍然可以代表游戏

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

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

iii) 交换玩家(即交换 yield 对和 沿第一条对角线镜像矩阵)

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

我有兴趣更改代码，以便程序列出可能 yield 不同的所有独特游戏:即玩家 1 的 (1,2,3,3) 和 (1,2) ,3,4) 对于玩家 2。在这里，会有 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++
             }
          }
       }
    }

---

我尝试将“assert 1 <= a && a <= 4”更改为“assert 1 <= a && a <= 3”，然后在代码中将 4 更改为 3。这似乎不起作用。

不过我不确定“int hashCode() {return (a-1) * 4 + (b-1)”或“(q.tl.a == 4) {} else if (q.tr.a == 4) {"确实如此，因此不确定如何更改它。

除此之外，我怀疑翻转和交换可以保持原样，因为这应该会产生一个程序来识别独特的游戏，无论特定的 yield 集是什么(即是否是 1、2、3、4或 1、2、3、3)。

---

我已经手工计算了不同 yield 集的独特游戏数量，可能会有引用意义。

Answer 1

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

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