无限递归调用minimax算法

Question

我最近实现了 4X4 井字游戏 的代码，该游戏使用极小极大算法。但是，我的 minimax 函数正在递归地调用自己无限否。的次数。

初始棋盘 (4X4) tic tac toe ->

board = np.array([['_','_','_', '_'],['_','_','_', '_'],['_','_','_', '_'],['_','_','_', '_']])

电脑转码 ->

import math
from utility import *

def minimax(board, spotsLeft, maximizing):
    bestIdx = (0,0)
    p1 = 'X'
    p2 = 'O'
    res, stat = checkGameOver(board, spotsLeft)
    if res==True:
        if stat == 'X': return 17-spotsLeft, bestIdx
        elif stat == 'O': return -17+spotsLeft, bestIdx
        else: return 0, bestIdx
    
    if maximizing:
        # return max score
        bestMove = -math.inf
        for i in range(4):
            for j in range(4):
                if board[i][j] == '_':
                    board[i][j] = p1
                    score, idx = minimax(board, spotsLeft-1, False)
                    print(score, idx)
                    board[i][j] = '_'
                    if bestMove<score:
                        bestMove = score
                        bestIdx = (i,j)
        return bestMove, bestIdx
    else:
        # return min score
        bestMove = math.inf
        for i in range(4):
            for j in range(4):
                if board[i][j] == '_':
                    board[i][j] = p2
                    score, idx = minimax(board, spotsLeft-1, True)
                    print(score, idx)
                    board[i][j] = '_'
                    if bestMove>score:
                        bestMove = score
                        bestIdx = (i,j)
        return bestMove, bestIdx
    

def ai(board):
    spotsLeft = 16
    p1 = 'X'    # Computer
    p2 = 'O'    # Player
    turn = p1
    while True:
        res, stat = checkGameOver(board, spotsLeft)
        if res==False:
            if turn == p1:
                # AI
                boardCopy = board[:]
                score, idx = minimax(boardCopy, spotsLeft, True)
                board[idx[0]][idx[1]] = turn
                turn = p2
                spotsLeft-=1
            else:
                # Human
                inp = int(input(f"Your turn: "))
                i, j = spotToIdx(inp)
                if board[i][j]=='_':
                    board[i][j] = turn
                    turn = p1
                    spotsLeft-=1
        else: return stat
        printBoard(board)

在上面的代码中 spotsLeft是船上的空位， checkGameOver returns“X”（如果玩家 X 获胜），returns“O”（如果玩家 O 获胜）& returns“T”（如果游戏平局）

checkGameOver 函数 ->

def checkWin(board):
    # Check Row
    for i in board:
        if len(set(i)) == 1 and i[0]!='_':
            return i[0]
        
    # Check Column
    for i in range(4):
        if (board[0][i] == board[1][i] == board[2][i] == board[3][i]) and board[0][i]!='_':
            return board[0][i]
    
    # Check Diagonals
    if (board[0][0]==board[1][1]==board[2][2]==board[3][3]) and board[0][0]!='_':
            return board[0][0]
    if (board[0][3]==board[1][2]==board[2][1]==board[3][0]) and board[0][3]!='_':
        return board[0][3]
    
    # No One Won Yet
    return -1
    

def checkGameOver(board, spotsLeft):
    # t -> Game Tied
    # x -> Player X won
    # o -> Player O won
    
    # if tied - all spots filled
    if spotsLeft == 0:
        return True, 'T'
    
    # if any player won the game
    result = checkWin(board)
    if result!=-1:
        return True, result
    
    return False, -1

Answer 1

我认为你的代码很好，并且在做你想让它做的事情。这个问题很可能是由于问题的复杂性，对于较低维度的井字游戏，它可以正常工作。

让我们首先简化并查看 2x2 的情况。在第一轮中，您从 ai 函数中调用 minimax，该函数将在第一层调用自身 4 次。在下一级，这些调用中的每一个也会调用 minimax，但比上一级少一次。把它作为一个列表：

0 级（ai 函数）：1 次调用 minimax
1 级：4 次调用
级别 2：4x3 次调用（上述 4 次调用中的每一次调用 3 次新调用）
3 级：4x3x2 调用
4 级：4x3x2x1 调用

现在使用 n-factorial 表示法 n!，我们可以计算调用总数为：

4!/4! + 4!/(4-1)! + 4!/(4-2)! + 4!/(4-3)! + 4!/(4-4!)

这是 n!/(n-k)! 对于 k 在 0 之间的总和 和 n（包括在内），n 开始您电路板上的单元数。这里的结果是 65 次调用 minimax 用于 2x2 板。

放入python代码：

def factorial(n):
    if n > 1: return n*factorial(n-1)
    else: return 1

def tictactoeComplexity(gridsize):
    return sum([factorial(gridsize)/factorial(gridsize-k) for k in range(gridsize+1)])

print(tictactoeComplexity(2*2)) # result is 65

现在让我们检查 3*3 板：

print(tictactoeComplexity(3*3)) # result is 986,410

从 2x2 到 3x3，我们从大约 100 增加到大约 1,000,000。你可以猜出 4x4 板的结果：

print(tictactoeComplexity(4*4)) # result is 56,874,039,553,217

所以你的程序会按照你的要求去做，但你要求的很多。

Answer 2

正如珍妮所解释的那样，搜索树太大了。即使您会改进数据结构和 move-mechanics 以提高它们的效率并减少内存占用，要在可接受的时间内完成此搜索仍然是一个挑战。

一般来说，您会采取以下措施来减少搜索树：

停在某个搜索深度（例如 4），然后对电路板执行静态评估。这种评估将是一种启发式的。例如，它将为 3-in-a-row 提供高价值，并有可用的免费单元格来完成它以获胜。它还会给未被对手阻挡的线上的一对带来重要价值，...等等
使用 alpha-beta 修剪以避免在搜索树的早期阶段搜索永远不会导致更好选择的分支。
使用杀手招式：在某个对手的招式之后发现好的招式，也可能被证明是对另一个对手招式的回应。并尝试第一个可能与 alpha-beta 修剪结合使用效果很好。
记忆已评估的位置（通过交换移动），并将位置镜像到等效位置以减小该字典的大小。

但老实说，4x4 井字游戏很无聊：平局很容易，而且需要很差的棋手才能把比赛拱手相让。例如，两个玩家都不能做出糟糕的 first 着法。无论他们在第一步中如何下棋，如果下法正确，仍将是平局。

所以...我建议只使用启发式评估函数，根本不进行搜索。或者，执行浅层 minimax，并在该固定深度使用这种启发式评估。但即使仅用评估函数替换 minimax 算法也能很好地工作。

改变什么

要实现该想法，请执行以下操作：

将AI部分替换为：

     if turn == p1:
         # AI -- a heuristic based approach
         bestScore = -math.inf
         bestMove = None
         for i in range(4):
             for j in range(4):
                 if board[i][j] == '_':
                     board[i][j] = turn
                     score = evaluate(board, turn)
                     if score > bestScore:
                         bestScore = score
                         bestMove = (i, j)
                     board[i][j] = '_'
         i, j = bestMove
         board[i][j] = turn
         turn = p2
         spotsLeft-=1

这会调用 evaluate，它会给出一个数字分数，对于给定的玩家（参数）来说，分数越高越好。

添加evaluate的定义：

# winning lines
lines = [
    [(i, j) for i in range(4)] for j in range(4)
] + [
    [(j, i) for i in range(4)] for j in range(4)
] + [
    [(i, i) for i in range(4)],
    [(3-i, i) for i in range(4)]
]

def evaluate(board, player):
    score = 0
    for line in lines:
        discs = [board[i][j] for i, j in line]
        # The more discs in one line the better
        value = [1000, 10, 6, 1, 0][sum(ch == "_" for ch in discs)]
        if "X" in discs:
            if not "O" in discs: # X could still win in this line
                score += value
        elif "O" in discs: # O could still win in this line
            score -= value
    # Change the sign depending on which player has just played
    return score if player == "X" else -score

就是这样！您可以选择使用 evaluate 函数来简化 checkWin 函数：

def checkWin(board):
    score = evaluate(board, "X")
    if abs(score) > 500:  # Take into account there could be some reduction
        return "X" if score > 0 else "O"
    # No One Won Yet
    return -1

通过此实现，您不再需要 minimax 函数，但您可能希望保留它并限制搜索深度。当达到该深度时，调用 evaluate，...等。我仍然发现上面的实现很好。你赢不了比赛。

无限递归调用minimax算法

Infinite recursive call minimax algorithm

python

recursion

artificial-intelligence

tic-tac-toe

minimax

改变什么