如何实现由游戏奥赛罗（黑白棋）中可能的动作组成的树[关闭]

Question

我正在尝试为黑白棋游戏制作一棵可能的走法树，稍后我将在其中使用极小极大算法。游戏以玩家 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 am trying to make a 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)

另外，这就是我初始化板的方式：

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

在我在代码中标记的地方，我试图为人工智能在那一刻的每个可能的移动创建一棵树，然后对其进行极小极大并获得最佳可能的移动。

我有

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

这就是我尝试制作树的方法：

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

但是现在这会创建许多

Tree

实例，而我需要一棵树和许多节点。我如何用这种递归方法解决这个问题？

Answer 1

您需要递归函数返回

TreeNode

实例，而不是

Tree

实例。然后，顶层调用将返回根节点，然后应将其分配给单个

root

实例的

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