सभी खेलों को सूचीबद्ध करना

Question

एक प्रश्न के बाद here ओपी सभी अद्वितीय 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 गेम संभव हैं। ओपी इन सभी खेलों को सूचीबद्ध करने में रुचि रखते थे।

यहाँ सूक्ष्म हिस्सा आता है: दो अनूठे अदायगी मैट्रिक्स फिर भी खेल का प्रतिनिधित्व कर सकते अगर एक (यानी relabel प्लेयर एक की रणनीतियों)

ii) का आदान प्रदान पंक्तियों

i) कॉलम आदान-प्रदान करके दूसरे से प्राप्त किया जा सकता (यानी प्लेयर बी की रणनीतियों relabel)

iii) खिलाड़ियों एक्सचेंज (यानी अदायगी जोड़े का आदान प्रदान और पहले विकर्ण साथ मैट्रिक्स)

ओपी मिरर निम्नलिखित कोड पोस्ट किया गया है जो सभी 78 संभव गेमों को सही ढंग से सूचीबद्ध करता है जिसमें प्रत्येक के लिए भुगतान (1,2,3,4) हो सकता है।

मुझे कोड बदलने में दिलचस्पी है ताकि प्रोग्राम सभी अद्वितीय गेम सूचीबद्ध करता है जहां संभावित भुगतान अलग-अलग होते हैं: यानी (1,2,3,3) खिलाड़ी 1 और (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++ 
      } 
      } 
     } 
    } 

---

मैं बदल रहा है का प्रयास किया है "का दावा है 1 < = एक & & एक < = 4" से "पर जोर 1 < = एक & & एक < = 3" और फिर 4 की बदलते एक से 3 कोड में आगे नीचे। यह काम नहीं लग रहा है।

मैं हालांकि यकीन नहीं है क्या "पूर्णांक hashCode() {वापसी (एक -1) * 4 + (ख -1)" या अगर "(q.tl.a == 4) { } else अगर (q.tr.a == 4) {"करता है और इसलिए यह सुनिश्चित नहीं करता कि इसे कैसे बदला जाए।

इसके अलावा, मुझे संदेह है कि फ्लिप और एक्सचेंज वे जिस तरह से बने रह सकते हैं, क्योंकि इससे अद्वितीय गेम की पहचान करने की प्रक्रिया उत्पन्न होनी चाहिए चाहे कोई भी विशिष्ट भुगतान सेट (यानी यह 1,2,3 है, 4 या 1,2,3,3)।

---

मैंने हाथ से विभिन्न पेऑफ सेट के लिए अद्वितीय गेम की संख्या की गणना की है जो संदर्भ के लिए उपयोगी हो सकती है।

Answer 1

मैं एक ऐसी ही स्थिति ओथेलो/रिवर्सी के लिए एक ऐ रही है, और चाहने राज्य अंतरिक्ष अनावश्यक प्रसंस्करण दूर करने के लिए संभव के रूप में छोटे होना ही था। मैं जिस तकनीक का उपयोग करता था वह मेटा-स्टेटस के सेट के रूप में, या आपके मामले में, मेटा-परिणाम के रूप में गेम का प्रतिनिधित्व करना था, जहां प्रत्येक मेटा में सभी क्रमिक क्रम होते हैं जो समकक्ष होते हैं। एक सामान्यीकरण योजना के साथ आने वाले समकक्ष क्रमिकताओं को सूचीबद्ध और पहचानना जो निर्धारित करता है कि मेटा उदाहरण के लिए कौन सा अभिविन्यास या प्रतिबिंब कुंजी है। फिर सभी नए क्रमिकताओं को यह देखने के लिए संशोधित करने के लिए बदल दिया जाता है कि वे एक नए उदाहरण का प्रतिनिधित्व करते हैं या नहीं।

आपके मामले में, यदि पंक्तियों और कॉलमों को स्वैपिंग समकक्ष समझा जाता है, तो आप उस मामले पर विचार कर सकते हैं जहां सॉर्ट किए गए क्रम का अभिविन्यास शीर्ष-बाएं कोने में सबसे छोटा मान रखता है और अगले दाएं कोने में सबसे छोटा निकट मूल्य कोने। यह सभी 4 फ्लिप पदों (पहचान, एच-फ्लिप, वी-वीएलआईपी, एचवी-फ्लिप) को एक एकल प्रतिनिधित्व में सामान्यीकृत करता है।