title: 3D Tic Tac Toe with Minimax & Alpha-beta pruning picks sub-optimal moves
body: <p>I'm trying to implement Minimax with Alpha-beta pruning for a game of 3D Tic Tac Toe. However, it appears the algorithm chooses sub optimal paths. </p>
  
  <p>For example, you can win simply by running straight through the middle of the cube, or across a single board. The AI seems to pick cells that would be optimal the <em>next</em> turn, not the current turn.</p>
  
  <p>I've tried recreating and playing with the heuristic I return for the algorithm but I haven't made much progress. Regardless of the ply it appears to have the same problem.</p>
  
  <p>The code is <a href="https://github.com/Battleroid/3ttt/blob/master/ttt.py" rel="nofollow" title="here">here</a>.</p>
  
  <p>The relevant portions are <code>computers_move</code> and <code>think_ahead</code> (and the '2' variants, those are just me experimenting with a slightly alternate approach).</p>
  
  <p>I'm hoping it might be something simple I overlooked, but as far as I can tell I am not sure what the issue is. If anyone can shed light on the problem I'd greatly appreciate it.</p>
  
  <pre><code>def computers_move2(self):
      best_score = -1000
      best_move = None
      h = None
      win = False
  
      for move in self.allowed_moves:
          self.move(move, self.ai)
          if self.complete:
              win = True
              break
          else:
              h = self.think_ahead2(self.human, -1000, 1000)
          self.depth_count = 0
          if h &gt;= best_score:
              best_score = h
              best_move = move
              self.undo_move(move)
          else:
              self.undo_move(move)
  
      if not win:
          self.move(best_move, self.ai)
      self.human_turn = True
  
  def think_ahead2(self, player, a, b):
      if self.depth_count &lt;= self.difficulty:
          self.depth_count += 1
          if player == self.ai:
              h = None
              for move in self.allowed_moves:
                  self.move(move, player)
                  if self.complete:
                      self.undo_move(move)
                      return 1000
                  else:
                      h = self.think_ahead2(self.human, a, b)
                      if h &gt; a:
                          a = h
                          self.undo_move(move)
                      else:
                          self.undo_move(move)
                  if a &gt;= b:
                      break
              return a
          else:
              h = None
              for move in self.allowed_moves:
                  self.move(move, player)
                  if self.complete:
                      self.undo_move(move)
                      return -1000
                  else:
                      h = self.think_ahead2(self.ai, a, b)
                      if h &lt; b:
                          b = h
                          self.undo_move(move)
                      else:
                          self.undo_move(move)
                  if a &gt;= b:
                      break
              return b
      else:
          diff = self.check_available(self.ai) - self.check_available(self.human)
          return diff
  </code></pre>