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）

回答

相关问题