title: MiniMax Recursive Algorithm (Python)
body: <p>I am pretty new so I apologize if I make any errors in posting here... I did a search but didn't come up with much that would help me. I am writing a miniMax algorithm for a variation on Tic Tac Toe. This variation allows either player to put an X or an O anywhere on the board. I am having trouble with the recursion and was hoping I could get a bit of guidance. </p>
  
  <pre><code>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
  </code></pre>
  
  <p>Above is my board class. I'm just using strings, not doing anything too fancy. I'm also using a very simple Node class that just stores data (though I suppose I might be able to just use strings too I guess...)</p>
  
  <pre><code>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() 
  </code></pre>
  
  <p>The fitnessFunction returns a score based on the number of empty spaces left. I'm having trouble with my recursive miniMax method. What I need to do is check for the base cases (either player winning, or a draw) and if those base cases are not true, I figure out whose move it is based on the number of empty spaces left. I think I've gotten that far, but I don't know what to do next (the recursive part). I also need to be able to get the min or max of children, depending on whose turn it is. I guess I am lost with the recursion. I'm new to CS and haven't touched much on it. Any hints would be greatly appreciated! :)        </p>