我最近实现了一个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
我认为你的代码很好，并且做你想做的事情。该问题很可能是由于问题的复杂性，对于较低维度的井字游戏，它可以正常工作。
让我们首先简化并看一个2x2的案例。第一次，您从ai函数调用minimax，它将在第一级调用自身4次。在下一级，这些调用中的每一个都将调用minimax，但比上一级少一次。要将其作为列表：
ai函数）：1次调用最小值现在使用 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
所以你的程序做了你要求它做的事情，但是你要求得太多了。
正如珍妮所解释的那样，搜索树太大了。即使你会对数据结构和移动机制进行改进，使它们更高效，减少内存占用，在可接受的时间内完成搜索仍然是一个挑战。
一般来说，您会采取以下措施来减少搜索树：
>
在某个搜索深度（如4）处停止，然后对电路板进行静态评估。此评估将是一种启发式评估。例如，它将为一个三人行提供一个高价值，并提供一个可用的空闲单元来完成它，从而获得胜利。这也会给一对在没有被对手阻挡的线上的一对球员带来重要的价值……等等。
使用alpha-beta修剪来避免在分支中搜索，这些分支在搜索树的早期阶段永远不会导致更好的选择。
使用杀手招式：在对手的某个招式之后被发现是好的招式，也可能是对对手的另一个招式的回应。首先尝试一下，与阿尔法-贝塔修剪相结合可能效果很好。
记忆已经评估过的位置(通过交换移动)，并将位置镜像到等价的位置以减少字典的大小。
但说实话，4x4井字游戏相当无聊:打平局非常容易，而且一名玩家将游戏交给另一名玩家需要非常低劣的动作。举例来说，两个玩家都不能先走一步。不管他们第一步怎么走，只要走得正确，这仍然是一场平局。
所以。。。我建议只使用启发式评估函数，根本不使用搜索。或者，执行浅最小值，并在该固定深度使用此类启发式评估。但是，即使仅用评估函数替换最小最大值算法也非常有效。
要实现这一想法，请按以下步骤进行:
>
将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 函数，但您可能希望保留它，并限制搜索深度。当达到该深度时，调用以评估，...等。我仍然发现上面的实现运行良好。你无法赢得一场比赛。
