如何在黑白棋 (Reversi) 游戏中实现由可能的动作制成的树

Question

我需要帮助根据黑白棋游戏中的可能走法制作树，稍后我将在其上使用 MiniMax 算法。游戏以 Player vs 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)

所以，我的想法是，在标记的地方，我为 AI 在那个时刻的每一个可能的移动做树，然后在它上面做 MiniMax 并获得最好的移动。问题是，我不知道如何制作树。我有 class TreeNode 和 class Tree 但显然，我不知道如何使用它们。这就是那 2 类的样子。

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

您需要将递归函数 return 设为 TreeNode 实例，而不是 Tree 实例。顶级调用将 return 根节点，然后应将其分配给单个 Tree 实例的 root 属性。

我还建议创建一个 Edge class，这样您就可以存储有关在父棋盘中下过的棋子的信息，以便到达子棋盘。

如果我理解正确，你想将 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)
# ...

如何在黑白棋 (Reversi) 游戏中实现由可能的动作制成的树

How to implement tree made from possible moves in game Othello (Reversi)

python

algorithm

tree

recursion

othello