Baumstruktur für expectiminimax Algorithmus

Question

So habe ich nicht viel formelle Informatik Ausbildung, so entschuldige ich mich im Voraus, wenn das eine dumme Frage ist.

Ich schreibe gerade ein Würfel Poker Spiel in Python. Die Regeln lauten nicht wie the game found in The Witcher 2, sondern basieren auf einem alten mobilen Würfel Poker Spiel, das vor einiger Zeit aus dem App Store genommen wurde.

Die Regeln sind wie folgt:

• Der Spieler und die KI rollen zunächst 5 poker dice je.
• Der Spieler und die KI wählen aus, an welchen Würfeln sie sich festhalten und rollen den Rest, um die Ergebnisse einander zu zeigen.
• Der obige Schritt wird wiederholt.

• Wer eine höhere Hand in der Rangliste (siehe unten) hat, gewinnt, wobei die absolut hohe Karte als Tie-Break fungiert.

  1. Five of a Kind
  2. Vier einer Art
  3. Gerade
  4. Full House
  5. Drilling
  6. Zwei Paar
  7. Ein Paar
  8. High Card

Der entsprechende Code ist unten:

class Tree(object): 
    '''Generic tree node''' 
    def __init__(self, children=None, value=None, type=None): 
     self.children = [] 
     self.value = value 
     self.type = type # either 'player', 'ai', or 'chance' 
     if children is not None: 
      for child in children: 
       self.add_child(child) 

    def add_child(self, node): 
     assert isinstance(node, Tree) 
     self.children.append(node) 

    def is_terminal(self): 
     return len(self.children) == 0 


def expectiminimax(node): 
    '''Adapted from Wikipedia's pseudocode''' 
    MAX_INT = 1e20 
    if node.is_terminal(): 
     return node.value 
    if node.type == 'player': 
     q = MAX_INT 
     for child in node.children: 
      q = min(q, expectiminimax(child)) 
    elif node.type == 'ai': 
     q = -MAX_INT 
     for child in node.children: 
      q = max(q, expectiminimax(child)) 
    elif node.type == 'chance': 
     q = 0 
     for child in node.children: 
      # All children are equally probable 
      q += len(node.children)**-1 * expectiminimax(child) 
    return q 


def ai_choose(ai_hand, player_hand): 
    ''' 
    Given an AI hand and a player hand, choose which cards to hold onto 
    for best outcome. 
    ''' 
    def construct_tree(ai_hand, player_hand): 
     ''' 
     Construct a 5-layer (?) tree for use with expectiminimax. 
         Δ    MAX 
        / \ 
        O ... O    CHANCE - Possible AI moves 
       /\ /\ 
       ∇ .. ∇ ∇ .. ∇   MIN - Possible card dice rolls 
      / \ ........ 
      O ... O ...........  CHANCE - Possible player moves 
     /\ /\ ............ 
      ▢ .. ▢ ▢ .. ▢ ............. END - Possible card dice rolls 
     ''' 
     tree_structure = ['ai', 'chance', 'player', 'chance', 'ai'] 
     tree = Tree(type=tree_structure[0]) 
     for subset in powerset(ai_hand.hand): 
      tree.add_child(Tree(value=subset)) 
    # ... 

Was möchte ich fragen, ist dies: ist diese Schichtstruktur korrekt? Oder sollten die Ebenen min, max und chance neu angeordnet werden? Andere allgemeine Kommentare sind ebenfalls willkommen.

Answer 1

Soweit ich sehen kann, ist die Schichtung korrekt. Ich habe vor einiger Zeit etwas Ähnliches gemacht und ich denke, Sie können es ohne die Baumstruktur implementieren, es sollte machbar sein und ist wahrscheinlich sauberer, da Sie keinen Zufallstyp brauchen.