TicTacToe Alpha Beta修剪RuntimeError：pygame的最大遞歸深度超出了python

Question

所以，我正在編寫一個非常簡單的TicTacToe程序，它使用alpha-beta修剪搜索下一步移動，但隨時遇到問題運行它。我嘗試了任何想到解決它的東西，甚至一行一行地完成了一行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

我真的apreciate是什麼原因造成的洞察力。

Answer 1

Python和Java處理遞歸的方式不同。 Python具有相當大的堆棧框架，所以在崩潰和拋出錯誤之前，硬限制多少次遞歸，或者多少次代碼可以調用自己。在你的代碼中，這是你自己調用的def alphaBeta(self, player, alpha, beta)方法：value = self.alphaBeta(getEnemy(player),alpha,beta)

在Java中，這有些不同，因爲Java做了更多的優化。這意味着您可以在獲取Java堆棧溢出錯誤之前進行更多的recusive調用。

最好的辦法是將代碼從遞歸函數改爲迭代函數。 I.E.，改變你的alphaBeta方法，以便不用調用它自己，而是使用for或while循環來做同樣的事情