MiniMax遞歸算法（Python）

我很新，所以我很抱歉，如果我在這裏發佈任何錯誤...我做了一個搜索，但沒有拿出很多，這將幫助我。我正在爲Tic Tac Toe編寫一個miniMax算法。這個變化允許任何一個玩家在棋盤上的任何位置放置X或O.我在遞歸方面遇到了問題，希望能得到一些指導。MiniMax遞歸算法（Python）

class TicTacToeBoard: 

def __init__(self, initGameBoard): 
    #initGameBoard is a string 
    self.board = initGameBoard 

def getEmptySpaces(self): 
    return self.board.count("-") 

def markX(self, index): 
    self.board = self.board[:index] + "x" + self.board[index+1:] 

def markO(self, index): 
    self.board = self.board[:index] + "o" + self.board[index+1:] 

def endGame(self): 
    #determines if someone has won 
    endGameStates = [[0,1,2],[3,4,5],[6,7,8],[0,3,6],[1,4,7],[2,5,8],[0,4,8],[2,4,6]] 
    for x in range(len(endGameStates)): 
     trySlice = self.board[endGameStates[x][0]] + self.board[endGameStates[x][1]] + \ 
        self.board[endGameStates[x][2]] 
     if trySlice[0] == trySlice[1] == trySlice[2] and "-" not in trySlice: 
      return True 
    return False 

def draw(self): 
    #determines if there has been a draw 
    if "-" not in self.board: 
     endGameStates = [[0,1,2],[3,4,5],[6,7,8],[0,3,6],[1,4,7],[2,5,8],[0,4,8],[2,4,6]] 
     for x in range(len(endGameStates)): 
      trySlice = self.board[endGameStates[x][0]] + self.board[endGameStates[x][1]] + \ 
         self.board[endGameStates[x][2]] 
      if trySlice[0] == trySlice[1] == trySlice[2] and "-" not in trySlice: 
       return False 
     return True 
    else: 
     return False 

def __str__(self): 
    boardStr = "" 
    for char in self.board: 
     boardStr += char 
    return boardStr

以上是我的課程。我只是使用字符串，沒有做任何太花哨的事情。我還使用一個非常簡單的Node類，只是將數據（雖然我想我也許可以只使用字符串嫌我猜...）

from tic_tac_toe_board import TicTacToeBoard  
from node import Node 

nodeQueue = [] 

def fitnessFunction(gameBoard): 
    #only runs if end game or if all full 
    if gameBoard.draw(): 
     return 0 
    else: 
     emptySpaces = gameBoard.getEmptySpaces() 
     if emptySpaces %2 == 0: 
      #max won 
      return (emptySpaces + 1) *1 
     else: 
      #max lost 
      return (emptySpaces + 1) *-1 

def miniMax(gameBoard): 
    if gameBoard.endGame() or if "-" not in gameBoard: 
     #end game checks for winner, second clause checks for full/draw 
     return fitnessFunction(gameBoard) 
    else: 
     emptyIndexes = [] #keeps track of which indexes are empty 
     count = 0 
     for char in gameBoard: 
      if char == "-": 
       emptyIndexes.append(count) 
      count +=1    
     if len(emptyIndexes) %2 != 0: 
      #max's turn 
      for index in emptyIndexes: 
       childNode = Node(gameBoard.markX(index)) 
       nodeQueue.append(childNode) 
       childNode = Node(gameBoard.markO(index)) 
       nodeQueue.append(childNode) 
     return miniMax()

的fitnessFunction返回基於數量得分空的空間。我遇到了遞歸miniMax方法的麻煩。我需要做的是檢查基礎案例（無論是玩家獲勝還是抽獎），如果這些基礎案例不是真實的，我會根據剩餘的空白空間數量來確定它的移動。我想我已經得到了很多，但我不知道下一步該怎麼做（遞歸部分）。我還需要能夠得到兒童的最小或最大值，取決於輪到誰。我猜我在遞歸中迷路了。我是新來的CS，並沒有涉及太多。任何提示將不勝感激！ :)

來源

2013-10-22 AbigailB

不知道我明白這個問題。當你知道這是誰的舉動之後，你想做什麼？ – aIKid

如果輪到最大，它的最大值將被返回。如果輪到分鐘，分鐘將被退回。 – AbigailB

如果你正在尋找一個迷你最大算法，你不需要一個應用它的例子。大多數遊戲都需要一個迷你最大算法。

所以，如果你想要一個，決定它如何表現。然後爲這種行爲至少編寫一個測試例子。

發佈您的測試。（不是遊戲，而只是對遊戲產生的數據的測試。）

如果你的算法不起作用，你的遊戲程序將無法工作。

提示：迷你最大算法僅取決於遊戲路徑的評估，而不取決於遊戲的播放。

來源

2013-10-22 04:02:06

MiniMax遞歸算法（Python）

回答

相關問題