无限递归调用minimax算法

Question

我最近实现了一个4X4井字游戏的代码，这是使用极大极小算法。然而，我的极大极小函数无限次地递归调用自己。

初始板 （4X4） 井字 -

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)

在上面的代码中的斑点左是船上的空位置，检查游戏结束返回“X”（如果玩家X获胜），返回“O”（如果玩家O获胜）

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

正如珍妮所解释的那样，搜索树太大了。即使你会对数据结构和移动机制进行改进，使它们更高效，减少内存占用，在可接受的时间内完成搜索仍然是一个挑战。

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

>

在某个搜索深度（如4）处停止，然后对电路板进行静态评估。此评估将是一种启发式评估。例如，它将为一个三人行提供一个高价值，并提供一个可用的空闲单元来完成它，从而获得胜利。这也会给一对在没有被对手阻挡的线上的一对球员带来重要的价值……等等。

使用alpha-beta修剪来避免在分支中搜索，这些分支在搜索树的早期阶段永远不会导致更好的选择。

使用杀手招式：在对手的某个招式之后被发现是好的招式，也可能是对对手的另一个招式的回应。首先尝试一下，与阿尔法-贝塔修剪相结合可能效果很好。

记忆已经评估过的位置(通过交换移动)，并将位置镜像到等价的位置以减少字典的大小。

但说实话，4x4井字游戏相当无聊:打平局非常容易，而且一名玩家将游戏交给另一名玩家需要非常低劣的动作。举例来说，两个玩家都不能先走一步。不管他们第一步怎么走，只要走得正确，这仍然是一场平局。

所以。。。我建议只使用启发式评估html" target="_blank">函数，根本不使用搜索。或者，执行浅最小值，并在该固定深度使用此类启发式评估。但是，即使仅用评估函数替换最小最大值算法也非常有效。

要实现这一想法，请按以下步骤进行:

>

将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

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

添加< code>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

就是这样！您可以选择使用< code>evaluate函数来简化< code>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 函数，但您可能希望保留它，并限制搜索深度。当达到该深度时，调用以评估，...等。我仍然发现上面的实现运行良好。你无法赢得一场比赛。

Answer 2

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

让我们首先简化并看一个2x2的案例。第一次，您从ai函数调用minimax，它将在第一级调用自身4次。在下一级，这些调用中的每一个都将调用minimax，但比上一级少一次。要将其作为列表：

• 级别0（ai函数）：1次调用最小值
• 1级：4次通话
• 2级：4x3呼叫（以上4个呼叫各打3个新呼叫）
• 3级：4x3x2呼叫
• 4级：4x3x2x1呼叫

现在使用 n 阶乘表示法作为 n！，我们可以将调用总数计算为：

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

也就是n的总和！/(n-k)！对于0到n之间的k(包括0和n)，n表示棋盘上的单元数。这里的结果是对2x2板的65次调用< code>minimax。

放入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

所以你的html" target="_blank">程序做了你要求它做的事情，但是你要求得太多了。