title: Infinite recursive call minimax algorithm
body: <p>I have recently implemented the code for a <strong>4X4 tic tac toe game</strong> which is using minimax algorithm.
  However, my minimax function is calling itself recursively infinite no. of times.</p>
  <p><strong>Initial Board (4X4) tic tac toe -&gt;</strong></p>
  <pre><code>board = np.array([['_','_','_', '_'],['_','_','_', '_'],['_','_','_', '_'],['_','_','_', '_']])
  </code></pre>
  <p><strong>Code for the computer's turn -&gt;</strong></p>
  <pre><code>import math
  from utility import *
  
  def minimax(board, spotsLeft, maximizing):
      bestIdx = (0,0)
      p1 = 'X'
      p2 = 'O'
      res, stat = checkGameOver(board, spotsLeft)
      if res==True:
          if stat == 'X': return 17-spotsLeft, bestIdx
          elif stat == 'O': return -17+spotsLeft, bestIdx
          else: return 0, bestIdx
      
      if maximizing:
          # return max score
          bestMove = -math.inf
          for i in range(4):
              for j in range(4):
                  if board[i][j] == '_':
                      board[i][j] = p1
                      score, idx = minimax(board, spotsLeft-1, False)
                      print(score, idx)
                      board[i][j] = '_'
                      if bestMove&lt;score:
                          bestMove = score
                          bestIdx = (i,j)
          return bestMove, bestIdx
      else:
          # return min score
          bestMove = math.inf
          for i in range(4):
              for j in range(4):
                  if board[i][j] == '_':
                      board[i][j] = p2
                      score, idx = minimax(board, spotsLeft-1, True)
                      print(score, idx)
                      board[i][j] = '_'
                      if bestMove&gt;score:
                          bestMove = score
                          bestIdx = (i,j)
          return bestMove, bestIdx
      
  
  def ai(board):
      spotsLeft = 16
      p1 = 'X'    # Computer
      p2 = 'O'    # Player
      turn = p1
      while True:
          res, stat = checkGameOver(board, spotsLeft)
          if res==False:
              if turn == p1:
                  # AI
                  boardCopy = board[:]
                  score, idx = minimax(boardCopy, spotsLeft, True)
                  board[idx[0]][idx[1]] = turn
                  turn = p2
                  spotsLeft-=1
              else:
                  # Human
                  inp = int(input(f&quot;Your turn: &quot;))
                  i, j = spotToIdx(inp)
                  if board[i][j]=='_':
                      board[i][j] = turn
                      turn = p1
                      spotsLeft-=1
          else: return stat
          printBoard(board)
  </code></pre>
  <p>In the above code
  <code>spotsLeft</code> is the empty places on board,
  <code>checkGameOver</code> returns &quot;X&quot; (if Player X wins), returns &quot;O&quot; (if Player O wins) &amp; returns &quot;T&quot; (if game is tied)</p>
  <p><strong>checkGameOver function</strong> -&gt;</p>
  <pre><code>def checkWin(board):
      # Check Row
      for i in board:
          if len(set(i)) == 1 and i[0]!='_':
              return i[0]
          
      # Check Column
      for i in range(4):
          if (board[0][i] == board[1][i] == board[2][i] == board[3][i]) and board[0][i]!='_':
              return board[0][i]
      
      # Check Diagonals
      if (board[0][0]==board[1][1]==board[2][2]==board[3][3]) and board[0][0]!='_':
              return board[0][0]
      if (board[0][3]==board[1][2]==board[2][1]==board[3][0]) and board[0][3]!='_':
          return board[0][3]
      
      # No One Won Yet
      return -1
      
  
  def checkGameOver(board, spotsLeft):
      # t -&gt; Game Tied
      # x -&gt; Player X won
      # o -&gt; Player O won
      
      # if tied - all spots filled
      if spotsLeft == 0:
          return True, 'T'
      
      # if any player won the game
      result = checkWin(board)
      if result!=-1:
          return True, result
      
      return False, -1
  </code></pre>