TicTacToe Alpha Beta pruning RuntimeError: maximum recursion depth exceeded python with pygame
TicTacToe Alpha Beta pruning RuntimeError: maximum recursion depth exceeded python with pygame
所以，我正在编写一个非常简单的 TicTacToe 程序，它使用 alpha-beta p运行ing 来搜索对玩家的下一步行动，但 运行 我想随时遇到问题运行它。我已经尝试了任何想到的方法来解决它，甚至逐行制作了一个 Java 等同于 运行 完美但 python 的逻辑的逻辑。
这是我的代码：
#encoding: UTF-8
#Andres de Lago Gomez
#A01371779
from random import randint
from utils import *
def getEnemy(who):
return 1 if who==2 else 2
def getLetter(who):
return "X" if who==1 else "O"
class TicTacToe:
winningCombos =[[0, 1, 2], [3, 4, 5],
[6, 7, 8], [0, 3, 6],
[1, 4, 7], [2, 5, 8],
[0, 4, 8], [2, 4, 6]]
board = [0 for i in range(9)]
player = 1
cpu = 2
def __init__(self):
pass
def makeMove(self, who, pos):
self.board[pos] = who
def setCpu(self, who):
self.player = who
self.cpu = getEnemy(who)
def availableMoves(self):
return [i for i in range(9) if self.board[i]==0]
def isOver(self):
if 0 not in self.board:
return True
if self.Winner():
return True
return False
def Winner(self):
for i in [1,2]:
positions = self.getSquares(i)
for combo in self.winningCombos:
win = True
for pos in combo:
if pos not in positions:
win = False
if win:
return i
return False
def getSquares(self, player):
return [i for i in range(9) if self.board[i]==player]
def alphaBeta(self, player, alpha, beta):
if self.isOver():
return self.evaluateNode()
for move in self.availableMoves():
self.makeMove(move, player)
value = self.alphaBeta(getEnemy(player),alpha,beta)
self.makeMove(move, 0)
if player == self.cpu:
if alpha < value:
alpha = value
if alpha >=beta:
return beta
else:
if beta > value:
beta = value
if beta <= alpha:
return alpha
return alpha if player==self.cpu else beta
def evaluateNode(self):
tmp = self.Winner()
if tmp==self.cpu:
return 1
elif tmp==self.player:
return -1
else:
return 0
def getNextMove(self, player):
test = -5
possibleMoves = []
for move in self.availableMoves():
self.makeMove(player, move)
value = self.alphaBeta(getEnemy(player), -5, 5)
self.makeMove(0, move)
if value>test:
test = value
possibleMoves = [move]
elif value == test:
possibleMoves.append(move)
return possibleMoves[randint(0, len(possibleMoves)-1)]
class Tile(pygame.sprite.Sprite):
def __init__(self, rect, screen, player="X"):
pygame.sprite.Sprite.__init__(self)
self.rect = rect
self.images = [load_png(get_path()+"\data\TicTacToe\"+player+"Tile\{0:0>2d}.png".format(x)) for x in range(21)]
clock = pygame.time.Clock()
for i in range(21):
self.image = self.images[i]
screen.blit(self.image, self.rect)
pygame.display.update(self.rect)
clock.tick(80)
class GUI:
def __init__(self):
pygame.init()
self.screen = pygame.display.set_mode([100,100])
self.dir = get_path()
#get background
self.background = pygame.image.load(self.dir+"\data\TicTacToe\Background.png")
self.background.convert()
self.tiles = pygame.sprite.Group()
#blit to screen
self.screen = pygame.display.set_mode(self.background.get_size())
self.screen.blit(self.background,(0,0))
pygame.display.update()
#create tiles
self.places = [pygame.Rect((15+165*x, 110+165*y), (150,150) )for x in range(3) for y in range (3)]
#create game
self.board = TicTacToe()
done = False
goFirstI = load_png(get_path()+"\data\TicTacToe\GoFirst.png")
goFirstR = pygame.Rect((0,0), (400,200))
goFirstR.center = self.places[4].center
self.screen.blit(goFirstI,goFirstR)
pygame.display.update(goFirstR)
yesR = pygame.Rect((97,382),(115,45))
noR = pygame.Rect((297,382),(115,45))
while not done:
for event in pygame.event.get():
if event.type == pygame.MOUSEBUTTONUP:
if event.button == 1:
if yesR.collidepoint(event.pos):
done = True
self.board.setCpu(1)
elif noR.collidepoint(event.pos):
done = True
self.board.setCpu(2)
self.screen.blit(self.background,(0,0))
pygame.display.update(goFirstR)
#start clock
clock = pygame.time.Clock()
done = False
turn = 1
bdown = 0
while not done:
for event in pygame.event.get():
if event.type == pygame.QUIT:
done = True
elif event.type == pygame.KEYDOWN:
if event.key == pygame.K_ESCAPE:
pass #pause menu?
elif event.type == pygame.MOUSEBUTTONUP:
if event.button == 1:
bdown = event
if turn == self.board.player:
if bdown != 0:
index = 0
for rect in self.places:
if rect.collidepoint(bdown.pos):
moves = self.board.availableMoves()
if index in moves:
self.board.makeMove(turn, index)
self.tiles.add(Tile(rect, self.screen, getLetter(self.board.player)))
turn = getEnemy(turn)
index += 1
else:
pos = self.board.getNextMove(self.board.cpu)
self.board.makeMove(turn, pos)
self.tiles.add(Tile(self.tiles[pos], self.screen, getLetter(self.board.cpu)))
clock.tick(60)
a = GUI()
我得到的错误是：RuntimeError: maximum recursion depth exceeded
我真的很想知道是什么导致了它。
Python 和 Java 以不同方式处理递归。 Python 有相当大的堆栈帧，因此在崩溃和抛出该错误之前，对递归次数或代码可以调用自身的次数有严格限制。在您的代码中，这是您的 def alphaBeta(self, player, alpha, beta) 方法，它本身调用：value = self.alphaBeta(getEnemy(player),alpha,beta)
在Java中，这有点不同，因为Java做了更多的优化。这意味着您可以在收到 Java 堆栈溢出错误之前进行更多的回溯调用。
最好的办法是将代码从递归函数更改为迭代函数。即，更改您的 alphaBeta 方法，使其不调用自身，而是使用 for 或 while 循环来做同样的事情
所以，我正在编写一个非常简单的 TicTacToe 程序，它使用 alpha-beta p运行ing 来搜索对玩家的下一步行动，但 运行 我想随时遇到问题运行它。我已经尝试了任何想到的方法来解决它，甚至逐行制作了一个 Java 等同于 运行 完美但 python 的逻辑的逻辑。
这是我的代码：
#encoding: UTF-8
#Andres de Lago Gomez
#A01371779
from random import randint
from utils import *
def getEnemy(who):
return 1 if who==2 else 2
def getLetter(who):
return "X" if who==1 else "O"
class TicTacToe:
winningCombos =[[0, 1, 2], [3, 4, 5],
[6, 7, 8], [0, 3, 6],
[1, 4, 7], [2, 5, 8],
[0, 4, 8], [2, 4, 6]]
board = [0 for i in range(9)]
player = 1
cpu = 2
def __init__(self):
pass
def makeMove(self, who, pos):
self.board[pos] = who
def setCpu(self, who):
self.player = who
self.cpu = getEnemy(who)
def availableMoves(self):
return [i for i in range(9) if self.board[i]==0]
def isOver(self):
if 0 not in self.board:
return True
if self.Winner():
return True
return False
def Winner(self):
for i in [1,2]:
positions = self.getSquares(i)
for combo in self.winningCombos:
win = True
for pos in combo:
if pos not in positions:
win = False
if win:
return i
return False
def getSquares(self, player):
return [i for i in range(9) if self.board[i]==player]
def alphaBeta(self, player, alpha, beta):
if self.isOver():
return self.evaluateNode()
for move in self.availableMoves():
self.makeMove(move, player)
value = self.alphaBeta(getEnemy(player),alpha,beta)
self.makeMove(move, 0)
if player == self.cpu:
if alpha < value:
alpha = value
if alpha >=beta:
return beta
else:
if beta > value:
beta = value
if beta <= alpha:
return alpha
return alpha if player==self.cpu else beta
def evaluateNode(self):
tmp = self.Winner()
if tmp==self.cpu:
return 1
elif tmp==self.player:
return -1
else:
return 0
def getNextMove(self, player):
test = -5
possibleMoves = []
for move in self.availableMoves():
self.makeMove(player, move)
value = self.alphaBeta(getEnemy(player), -5, 5)
self.makeMove(0, move)
if value>test:
test = value
possibleMoves = [move]
elif value == test:
possibleMoves.append(move)
return possibleMoves[randint(0, len(possibleMoves)-1)]
class Tile(pygame.sprite.Sprite):
def __init__(self, rect, screen, player="X"):
pygame.sprite.Sprite.__init__(self)
self.rect = rect
self.images = [load_png(get_path()+"\data\TicTacToe\"+player+"Tile\{0:0>2d}.png".format(x)) for x in range(21)]
clock = pygame.time.Clock()
for i in range(21):
self.image = self.images[i]
screen.blit(self.image, self.rect)
pygame.display.update(self.rect)
clock.tick(80)
class GUI:
def __init__(self):
pygame.init()
self.screen = pygame.display.set_mode([100,100])
self.dir = get_path()
#get background
self.background = pygame.image.load(self.dir+"\data\TicTacToe\Background.png")
self.background.convert()
self.tiles = pygame.sprite.Group()
#blit to screen
self.screen = pygame.display.set_mode(self.background.get_size())
self.screen.blit(self.background,(0,0))
pygame.display.update()
#create tiles
self.places = [pygame.Rect((15+165*x, 110+165*y), (150,150) )for x in range(3) for y in range (3)]
#create game
self.board = TicTacToe()
done = False
goFirstI = load_png(get_path()+"\data\TicTacToe\GoFirst.png")
goFirstR = pygame.Rect((0,0), (400,200))
goFirstR.center = self.places[4].center
self.screen.blit(goFirstI,goFirstR)
pygame.display.update(goFirstR)
yesR = pygame.Rect((97,382),(115,45))
noR = pygame.Rect((297,382),(115,45))
while not done:
for event in pygame.event.get():
if event.type == pygame.MOUSEBUTTONUP:
if event.button == 1:
if yesR.collidepoint(event.pos):
done = True
self.board.setCpu(1)
elif noR.collidepoint(event.pos):
done = True
self.board.setCpu(2)
self.screen.blit(self.background,(0,0))
pygame.display.update(goFirstR)
#start clock
clock = pygame.time.Clock()
done = False
turn = 1
bdown = 0
while not done:
for event in pygame.event.get():
if event.type == pygame.QUIT:
done = True
elif event.type == pygame.KEYDOWN:
if event.key == pygame.K_ESCAPE:
pass #pause menu?
elif event.type == pygame.MOUSEBUTTONUP:
if event.button == 1:
bdown = event
if turn == self.board.player:
if bdown != 0:
index = 0
for rect in self.places:
if rect.collidepoint(bdown.pos):
moves = self.board.availableMoves()
if index in moves:
self.board.makeMove(turn, index)
self.tiles.add(Tile(rect, self.screen, getLetter(self.board.player)))
turn = getEnemy(turn)
index += 1
else:
pos = self.board.getNextMove(self.board.cpu)
self.board.makeMove(turn, pos)
self.tiles.add(Tile(self.tiles[pos], self.screen, getLetter(self.board.cpu)))
clock.tick(60)
a = GUI()
我得到的错误是：RuntimeError: maximum recursion depth exceeded
我真的很想知道是什么导致了它。
Python 和 Java 以不同方式处理递归。 Python 有相当大的堆栈帧，因此在崩溃和抛出该错误之前，对递归次数或代码可以调用自身的次数有严格限制。在您的代码中，这是您的 def alphaBeta(self, player, alpha, beta) 方法，它本身调用：value = self.alphaBeta(getEnemy(player),alpha,beta)
在Java中，这有点不同，因为Java做了更多的优化。这意味着您可以在收到 Java 堆栈溢出错误之前进行更多的回溯调用。
最好的办法是将代码从递归函数更改为迭代函数。即，更改您的 alphaBeta 方法，使其不调用自身，而是使用 for 或 while 循环来做同样的事情