すべてのゲームを表示する

Question

質問の後にhere OPはすべての一意の2x2ゲームをリストすることに興味があります。ゲームはここに2人のプレーヤーと2つの戦略があるゲーム理論ゲームです。したがって、4つの可能な結果があります（図参照）。これらの結果には、各プレイヤーのための「報酬」が付いています。ペイオフ「ペア」は、戦略のいくつかの組み合わせから各プレイヤーに対して2つのペイオフです。ペイオフ整数で与えられ、例えば4

を超えることができない、（それぞれペイオフ対が括弧内に書かれているとし、P1及びP2示すプレーヤ1及び2）2x2のゲームの次の例を考えてみます。

    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はこれらすべてのゲームをリストすることに興味がありました。

ここで微妙な部分が来る：1（つまりプレイヤーAの戦略を再ラベル付け）

II）の交換行

I）の列を交換することによって、他のから入手できるのであれば、2つの固有のペイオフ行列が、それにもかかわらず、ゲームを表すことができますすなわちペイオフのペアを交換し は最初の対角線に沿って行列）

OPをミラーリング（

III）の選手を交換し（つまり、プレイヤーBの戦略を再ラベル付け）それぞれの報酬が（1,2,3,4）になる可能性のある78のゲームすべてが正しくリストされている以下のコードを掲載しました。

私は、プログラムが全てのユニークなのゲームをリストアップするようにコードを変更したいと考えています。プレイヤー1の場合は（1,2,3,3）、 ）ここでは、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 <は& & < = 4 =主張" "1 <は=主張& & < = 3" とし、3に4代を変更さらにコードの下に。これはうまくいかないようです。

しかし、 "int hashCode（）{return（a-1）* 4 +（b-1）"または "（q.tl.a == 4）の場合{ } else if（q.tr.a == 4）{"しているので、これをどのように変更するか分かりません。

私は、特定のペイオフセットが何であるかにかかわらずユニークなゲームを識別するための手順を生成する必要があるので、フリップと交換はそのままであると考えています（1,2,3、 4または1,2,3,3）。

---

異なるペイオフセットのユニークゲームの数を手作業で計算しました。これは参考になる可能性があります。

Answer 1

Iは、同様の状況がオセロ/リバーシためのAIを行う、冗長処理を除去することができる限り小さくなるように状態空間を望んでいました。 私が使った手法は、ゲームをメタ状態の集合として、あるいはあなたの場合にはメタアウトカムとして表現することでした。各メタは等価なすべての並べ替えから成り立っています。メタインスタンスのキーとなる方向または反射を決定する正規化スキームを使用して、同等の置換をリストして識別する。次に、新しいインスタンスを表すかどうかを比較する前に、すべての新しい順列を変換して正規化します。

行と列のスワップが同じであると見なされる場合、ソート順の向きが左上隅に最小値を、右上に次の最も小さい隣接値コーナー。これにより、4つのフリップポジション（アイデンティティ、hフリップ、v-vlip、hv-flip）がすべて1つの表現に正規化されます。