title: Tic Tac Toe Alpha Beta Minimax
body: <p>I have been working on a tic tac toe program in order to better understand how the minimax algorithm works. The following implementation is not working correctly, as the computer can loose the game. If the program is working correctly, than in theory this should be impossible...</p>
  
  <p><strong>Have I made a mistake with the implementation of the minimax, or the getting of the best move?</strong></p>
  
  <p>I have never implemented the algorithm before :s</p>
  
  <p><strong>Evaluation Function</strong></p>
  
  <pre><code>public static int evaluate(char[] board, char turn) {
      if (isWinFor('x', board)) {
          return -1;
      } else if (isWinFor('o', board)) {
          return 1;
      } 
      return 0;
  }
  </code></pre>
  
  <p><strong>Minimax</strong></p>
  
  <pre><code>public static int alphabeta(char[] board, int depth, char turn, int alpha, int beta) {
      if (depth == 0 || gameOver(board)) {
          return evaluate(board, turn);
      } else {
          for (int move : possibleMoves(board)) {
              makeMove(board, turn, move);
              turn = changeTurn(turn);
              int value = alphabeta(board, depth--, turn, alpha, beta);   
              makeMove(board, ' ', move);
              if (turn == 'o') {
                  if (value &gt; alpha) {
                      alpha = value;
                  }
                  if (alpha &gt;= beta) {
                      return beta;
                  }
              } else if (turn == 'x') {
                  if (value &lt; beta) {
                      beta = value;
                  }
                  if (beta &lt;= alpha) {
                      return alpha;
                  }
              }               
          }
          if (turn == 'o') {
              return  alpha;
          } else {
              return  beta;
          }             
      }
  }
  </code></pre>
  
  <p><strong>Find best move</strong></p>
  
  <pre><code>public static void getBestMove(char[] board, char turn) {
      Random random  = new Random();
      int bestValue = -10000;
      List&lt;Integer&gt; choices = new ArrayList&lt;Integer&gt;();
      for (int move : possibleMoves(board)) {
          makeMove(board, turn, move);
          turn = changeTurn(turn);
          int value = alphabeta(board, 3, turn, -10000, 10000);   
          makeMove(board, ' ', move);
          if (value &gt; bestValue) {
              bestValue = value;
              //start code edit
              choices.clear();
              //end code edit
              choices.add(move);
          } else if (value == bestValue) {
              choices.add(move);
          }
      }
      makeMove(board, turn, choices.get(random.nextInt(choices.size())));
  }
  </code></pre>
  
  <p>Thank you.</p>