时间戳

首页 > 解决方案 > 这个极小极大实现有什么问题？

python - 这个极小极大实现有什么问题？

问题描述

我一直在尝试为一个简单的井字游戏实现一个极小值，但是当它运行时，我无法让它给出正确的结果。该函数假定 AI 正在扮演“O”，而玩家正在扮演“X”。

import itertools

class Board:
    def __init__(self):
        self.grid = {}

    def get_symbol(self, move):
        return self.grid.get(move)

    def set_symbol(self, move, symbol):
        self.grid[move] = symbol

    def clear_symbol(self, move):
        self.grid.pop(move)

    def has_winner(self):
        return self.is_winner('X') or self.is_winner('O')

    def is_winner(self, symbol):
        wins = [[(0, 0), (1, 0), (2, 0)],
                [(0, 1), (1, 1), (2, 1)],
                [(0, 2), (1, 2), (2, 2)],
                [(0, 0), (0, 1), (0, 2)],
                [(1, 0), (1, 1), (1, 2)],
                [(2, 0), (2, 1), (2, 2)],
                [(0, 0), (1, 1), (2, 2)],
                [(0, 2), (1, 1), (2, 0)]]
        for win in wins:
            if all(self.get_symbol(e) == symbol for e in win):
                return True
        return False

    def is_full(self):
        return all(self.get_symbol(tuple(e)) is not None for e in itertools.product(range(3), repeat=2))

    def get_moves(self):
        return [move for move in itertools.product(range(3), repeat=2) if move not in self.grid.keys()]

    def get_heuristic(self):
        if self.is_winner('X'):
            return -1
        if self.is_winner('O'):
            return 1
        return 0

def get_enemy(symbol):
    if symbol == 'O':
        return 'X'
    return 'O'

def is_terminal(board):
    return board.has_winner() or board.is_full()

def minimax(board, depth, piece):
    if depth == 0 or is_terminal(board):
        return board.get_heuristic()

    if piece == 'O':
        value = float('-inf')
        for move in board.get_moves():
            board.set_symbol(move, piece)
            value = max(value, minimax(board, depth-1, get_enemy(piece)))
            board.clear_symbol(move)
        return value
    else:
        value = float('inf')
        for move in board.get_moves():
            board.set_symbol(move, piece)
            value = min(value, minimax(board, depth-1, get_enemy(piece)))
            board.clear_symbol(move)
        return value

def main():
    board = Board()
    board.set_symbol((0, 0), 'X')
    board.set_symbol((0, 1), 'O')
    board.set_symbol((1, 0), 'X')

    moves = board.get_moves()
    scores = []
    for move in moves:
        board.set_symbol(move, 'O')
        scores.append(minimax(board, 100, 'O'))
        board.clear_symbol(move)

    m = max(scores)
    for i, e in enumerate(moves):
        if scores[i] == m:
            print(e)


if __name__ == '__main__':
    main()

这应该打印 '(2, 0)'，因为任何其他位置都会导致 'X' 在下一轮获胜，但是它会根据传递给 minimax 的深度来打印 6 个可能结果的各种子集。我尝试使用“X”和“O”作为 minimax 函数的片段的初始参数，但都没有给出正确的结果。出了什么问题？

标签： pythonrecursiontic-tac-toeminimax

解决方案

我相信错误出在您的 Minimax 函数中。您在函数的参数中调用了该片段，但是您为 themaximizingPlayer和minimizingPlayer递归调用了该片段（对于 theO和该X片段的含义）。

这是我认为至少解决了一个问题的更新功能：

def minimax(board, depth, piece):
    if depth == 0 or is_terminal(board):
        return board.get_heuristic() #else return a value for the board

    if piece == 'O':
        value = float('-inf')
        for move in board.get_moves():
            board.set_symbol(move, 'X') #'X'. Drop an X piece and see where they score their highest move so that O can maximize it
            value = max(value, minimax(board, depth-1, get_enemy(piece)))
            board.clear_symbol(move)
        return value
    else:
        value = float('inf')
        for move in board.get_moves():
            board.set_symbol(move, 'O') #'O' Drop an O piece and see where they score their highest move so that X can minimize it
            value = min(value, minimax(board, depth-1, get_enemy(piece)))
            board.clear_symbol(move)
        return value

推荐阅读