0

我需要帮助从游戏奥赛罗的可能动作中制作树，稍后我将使用 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但显然，我不知道如何使用它们。这就是这两个类的样子。

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

提前致谢。

4

1 回答 1

0

你需要你的递归函数来返回一个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

您的findMoveForAIandAlphaBeta函数将不再获得boardandplayer作为参数，它们也不会调用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)
# ...
于 2021-05-23T09:44:54.000 回答