expectiminimax算法的樹結構

Question

所以我沒有太多正式的計算機科學教育，所以我提前道歉，如果這是一個愚蠢的問題。

我目前正在用Python編寫一個骰子撲克遊戲。規則是而不是像the game found in The Witcher 2，而是基於一箇舊的移動骰子撲克遊戲，從前不久從App Store中取消。

的規則如下：

• 的播放器和AI最初滾動每次5 poker dice。
• 玩家和AI選擇哪個骰子保持並滾動其餘骰子，將結果展示給對方。
• 重複上述步驟。

• 誰在排名上位居第二（見下文），誰將贏得勝利，而絕對高牌則成爲決勝局。

  1. 的一類
  2. 直
  3. 滿屋
  4. 三同
  5. 兩對
  6. 一對
  7. 高卡
  的類
  8. 四五

相關的代碼如下：

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)) 
    # ... 

我要問的是：是該層結構是否正確？或者應該重新排列min，max和chance層？其他一般性意見也是受歡迎的。

Answer 1

據我所見，分層是正確的。我前段時間做了類似的事情，我認爲你可以在沒有樹數據結構的情況下實現它，它應該是可行的，並且可能更清潔，因爲你不需要機會類型。