如何在游戏Othello (Reversi)中实现从可能的移动中生成的树

Question

我需要帮助，从可能的移动在游戏奥赛罗树，我将在以后使用MiniMax算法。游戏是在玩家和AI模式下进行的，我总是"1“在船上，AI总是"2”在船上。这就是我目前为AI获得最佳移动的功能：

def findMoveForAI(board, player, depth, start):
    best_score_for_move = -float('inf')
    play_x = play_y = -1
    moves = validMoves(board, player)
    if not moves:
        return (play_x , play_y)
    for x, y in moves:
        # this is where I would like to make tree
        (temp, total_fillped) = PlayMove(copy.deepcopy(board), x, y, player)
        move_eval = AlphaBeta(temp, player, depth, -999999999999, 999999999999, True, start)
        if move_eval > best_score_for_move  :
            best_score_for_move = move_eval 
            play_x = x; play_y= y
    return (play_x , play_y)

所以，我的想法是，在标记的地方，我为人工智能在那一刻的每一个可能的移动做树，然后在上面做MiniMax，得到最好的移动。问题是我不知道怎么做树。我有class TreeNode和class Tree，但很显然，我不知道如何使用它们。这是这两个类的样子。

class TreeNode(object):

    def __init__(self, data):
        self.parent = None
        self.children = []
        self.data = data

    def is_root(self):
        return self.parent is None

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

    def add_child(self, x):
        x.parent = self
        self.children.append(x)

class Tree(object):
    def __init__(self):
        self.root = None

而且，如果需要的话，我也是这样初始化板的。

board = [['.' for x in range(8)] for y in range(8)]

我真的很感激任何帮助，因为我觉得应该用递归来完成，但这并不是我最强大的一面。

这就是我试过的：

def makeTree(tree, board, player, depth):
    if depth > 0:
        new_player = change_player(player)
        possible_moves = validMoves(board, new_player)
        for x, y in possible_moves:
            new_board = PlayMove(copy.deepcopy(board), x, y, new_player)[0]
            child_tree = makeTree(tree, new_board, new_player, depth - 1)
            tree.add_child(child_tree)
    return tree

提前谢谢。

Answer 1

您需要使用递归函数来返回TreeNode实例，而不是Tree实例。然后，顶层调用将返回根节点，然后应该将其分配给单个Tree实例的Tree属性。

我还建议创建一个Edge类，这样您就可以存储有关在父板中播放的移动的信息，以便到达子板。

如果我理解正确的话，您想要将minimax/alphabeta算法与实际的游戏规则分开，首先创建状态树(特定于游戏)，然后将其提供给一个通用的minimax/alphabeta算法，该算法可以不了解游戏规则，只需关注树中的信息。

下面是一个实现的想法：

class Tree:
    def __init__(self):
        self.root = None

class TreeNode:

    def __init__(self, board, player, value=None):
        self.parent = None
        self.children = []
        self.board = board
        self.player = player
        self.value = value  # Initially only provided for leaf nodes

    def is_root(self):
        return self.parent is None

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

    def add_edge(self, edge):
        edge.child.parent = self
        self.children.append(edge)

    def to_list(self):  # to ease debugging...
        return [self.board, [edge.child.to_list() for edge in self.children]]

class Edge:
    def __init__(self, x, y, child):
        self.x = x
        self.y = y
        self.child = child

    
def makeTree(board, player, depth):

    def makeNode(board, player, depth):
        if depth == 0:  # Create a leaf with a heuristic value
            return TreeNode(board, player, heuristic(board, player))
        
        node = TreeNode(board, player)
        new_player = change_player(player)
        possible_moves = validMoves(board, new_player)
        for x, y in possible_moves:
            new_board = PlayMove(copy.deepcopy(board), x, y, new_player)[0]
            node.add_edge(Edge(x, y, makeNode(new_board, new_player, depth - 1)))
        return node

    tree = Tree()
    tree.root = makeNode(board, player, depth)
    return tree

您的findMoveForAI和AlphaBeta函数将不再以board和player作为参数，也不会调用PlayMove。相反，他们只会穿过这棵树。findMoveForAI将把树实例作为参数，而AlphaBeta将获得一个节点作为参数。根据存储在树叶中的值，这些值在执行时会在树上冒泡。

所以findMoveForAI看起来可能是这样：

def findMoveForAI(tree):
    best_score_for_move = -float('inf')
    play_x = play_y = -1
    for x, y, child in tree.root.children:
        move_eval = AlphaBeta(child, depth, -999999999999, 999999999999)
        if move_eval > best_score_for_move:
            best_score_for_move = move_eval 
            play_x = x
            play_y = y
    return (play_x , play_y)

驱动程序代码将包含以下两个步骤：

DEPTH = 3
# ...
tree = makeTree(board, player, DEPTH) 
best_move = findMoveForAI(tree)
# ...