title: C++ checkers using alpha-beta pruning
body: <p>I am trying to write an algorithm using <a href="https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning" rel="nofollow noreferrer">alpha-beta pruning</a> for Checkers game (AI vs AI). You can see the code &amp; comments
  below or in this <a href="http://pastebin.com/PYmnKY9H" rel="nofollow noreferrer">PasteBin</a>.</p>
  
  <p>The game itself works fine but the AI (the alpha-beta pruning algorithm) seems to have an error in it, because the bots basically feed the checkers to each other (no calculations showed at all). The code contains 2 different versions of alpha-beta algorithm functions (more detailed and less detailed).</p>
  
  <p>I've tried tracking value of <code>tmp</code> in <code>alphabeta()</code> and it seems to have normal values (ranging from -3 to 3 in case of depth = 5).</p>
  
  <p>I've also tried implementing <a href="https://stackoverflow.com/questions/18816088/conversion-of-minimax-with-alpha-beta-pruning-to-negamax">this</a> code into mine, but got the same results.</p>
  
  <p>My best guess is that the problem is in <code>bool whiteTurn</code>, which declares whose turn it is now, but I can't find any problems with it - the turns switch correctly.</p>
  
  <p>Second best guess - <code>Move bestMove</code>. I am not sure if it is right to rip it out of recursive function.</p>
  
  <p>What is the error?</p>
  
  <pre><code>#include "stdafx.h"
  #include &lt;iostream&gt;
  #include &lt;vector&gt;
  #include &lt;algorithm&gt;
  using namespace std;
  
  class Move
  {
  public:
      pair&lt;int, int&gt; start;
      pair&lt;int, int&gt; end;
      bool lethal;
      Move(int x, int y, int x1, int y1, bool kill)
      {
          start.first = x; start.second = y;
          end.first = x1; end.second = y1;
          lethal = kill;
      }
  };
  
  
  char **initBoard(int size)
  {
      char **board = new char*[size];
      for (int count = 0; count &lt; size; count++)
          board[count] = new char[size];
      return board;
  }
  
  void newGame(char **board, int size)
  {
      for (int i = 0; i &lt; size; i++)
          for (int j = 0; j &lt; size; j++)
          {
              board[i][j] = '-';
              if ((i == 0 || i == 2) &amp;&amp; j % 2 == 1) board[i][j] = 'O';
              if (i == 1 &amp;&amp; j % 2 == 0) board[i][j] = 'O';
              if ((i == size - 3 || i == size - 1) &amp;&amp; j % 2 == 0) board[i][j] = 'X';
              if (i == size - 2 &amp;&amp; j % 2 == 1) board[i][j] = 'X';
          }
  }
  
  void printBoard(char **board, int size)
  {
      for (int i = 0; i &lt; size; i++)
      {
          for (int j = 0; j &lt; size; j++)
          {
              cout &lt;&lt; board[i][j] &lt;&lt; " ";
          }
          cout &lt;&lt; endl;
      }
      cout &lt;&lt; endl;
  }
  
  void do_move(char **board, Move play)
  {
      char temp = board[play.start.first][play.start.second];
      board[play.start.first][play.start.second] = board[play.end.first][play.end.second];
      board[play.end.first][play.end.second] = temp;
      if (play.lethal)
          board[(play.end.first + play.start.first) / 2][(play.end.second + play.start.second) / 2] = '-';
  }
  
  void undo_move(char **board, Move play)
  {
      board[play.start.first][play.start.second] = board[play.end.first][play.end.second];
      board[play.end.first][play.end.second] = '-';
      if (play.lethal)
      {
          if (board[play.start.first][play.start.second] == 'X')
              board[(play.end.first + play.start.first) / 2][(play.end.second + play.start.second) / 2] = 'O';
          if (board[play.start.first][play.start.second] == 'O')
              board[(play.end.first + play.start.first) / 2][(play.end.second + play.start.second) / 2] = 'X';
      }
  }
  
  vector&lt;Move&gt; findMoves(char **board, int size, bool whiteTurn)
  {
      vector&lt;Move&gt; moves;
      //first jump (if possible)
      for (int x = 0; x &lt; size; x++)
      {
          for (int y = 0; y &lt; size; y++)
          {
              if (whiteTurn &amp;&amp; board[x][y] == 'X')
              {   
                  if (x &gt; 1 &amp;&amp; y &gt; 1 &amp;&amp; board[x - 1][y - 1] == 'O' &amp;&amp; board[x - 2][y - 2] == '-')
                      moves.push_back(Move(x, y, x - 2, y - 2, true));
                  if (x &gt; 1 &amp;&amp; y &lt; size - 2 &amp;&amp; board[x - 1][y + 1] == 'O' &amp;&amp; board[x - 2][y + 2] == '-')
                      moves.push_back(Move(x, y, x - 2, y + 2, true));
                  if (x &lt; size - 2 &amp;&amp; y &gt; 1 &amp;&amp; board[x + 1][y - 1] == 'O' &amp;&amp; board[x + 2][y - 2] == '-')
                      moves.push_back(Move(x, y, x + 2, y - 2, true));
                  if (x &lt; size - 2 &amp;&amp; y &lt; size - 2 &amp;&amp; board[x + 1][y + 1] == 'O' &amp;&amp; board[x + 2][y + 2] == '-')
                      moves.push_back(Move(x, y, x + 2, y + 2, true));
              }
              if (!whiteTurn &amp;&amp; board[x][y] == 'O')
              {
                  if (x &gt; 1 &amp;&amp; y &gt; 1 &amp;&amp; board[x - 1][y - 1] == 'X' &amp;&amp; board[x - 2][y - 2] == '-')
                      moves.push_back(Move(x, y, x - 2, y - 2, true));
                  if (x &gt; 1 &amp;&amp; y &lt; size - 2 &amp;&amp; board[x - 1][y + 1] == 'X' &amp;&amp; board[x - 2][y + 2] == '-')
                      moves.push_back(Move(x, y, x - 2, y + 2, true));
                  if (x &lt; size - 2 &amp;&amp; y &gt; 1 &amp;&amp; board[x + 1][y - 1] == 'X' &amp;&amp; board[x + 2][y - 2] == '-')
                      moves.push_back(Move(x, y, x + 2, y - 2, true));
                  if (x &lt; size - 2 &amp;&amp; y &lt; size - 2 &amp;&amp; board[x + 1][y + 1] == 'X' &amp;&amp; board[x + 2][y + 2] == '-')
                      moves.push_back(Move(x, y, x + 2, y + 2, true));
              }
          }
      }
      //then move
      for (int x = 0; x &lt; size; x++)
      {
          for (int y = 0; y &lt; size; y++)
          {
              if (whiteTurn &amp;&amp; board[x][y] == 'X')
              {
                  if (x &gt; 0 &amp;&amp; y &gt; 0 &amp;&amp; board[x - 1][y - 1] == '-')
                      moves.push_back(Move(x, y, x - 1, y - 1, false));
                  if (x &gt; 0 &amp;&amp; y &lt; size - 1 &amp;&amp; board[x - 1][y + 1] == '-')
                      moves.push_back(Move(x, y, x - 1, y + 1, false));
  
              }
              if (!whiteTurn &amp;&amp; board[x][y] == 'O')
              {
                  if (x &lt; size - 1 &amp;&amp; y &gt; 0 &amp;&amp; board[x + 1][y - 1] == '-')
                      moves.push_back(Move(x, y, x + 1, y - 1, false));
                  if (x &lt; size - 1 &amp;&amp; y &lt; size - 1 &amp;&amp; board[x + 1][y + 1] == '-')
                      moves.push_back(Move(x, y, x + 1, y + 1, false));
              }
          }
      }
      return moves;
  }
  
  //plain score calculation function
  int getScore(char **board, int size, bool whiteTurn)
  {
      int whiteNum = 0, blackNum = 0;
  
      for (int i = 0; i &lt; size; i++)
      {
          for (int j = 0; j &lt; size; j++)
          {
              if (board[i][j] == 'X') whiteNum++;
              if (board[i][j] == 'O') blackNum++;
          }
      }
  
      if (whiteTurn)
          return whiteNum - blackNum;
      else
          return blackNum - whiteNum;
  }
  
  //old function, doesnt work as intended too
  /*Move getBestMove(char **board, int size, bool whiteTurn)
  {
      int score, tmp;
      Move bestMove(0, 0, 0, 0, false);
      vector&lt;Move&gt; movelist = findMoves(board, size, whiteTurn);
      score = getScore(board, size, whiteTurn);
  
      for (unsigned int i = 0; i &lt; movelist.size(); i++)
      {
          do_move(board, movelist.at(i));
          tmp = getScore(board, size, whiteTurn);
          undo_move(board, movelist.at(i));
  
          if (tmp &gt;= score)
          {
              score = tmp;
              bestMove = movelist.at(i);
          }
      }
      return bestMove;
  }*/
  
  //made this global - no idea how to avoid it being global with recursion in alphabeta
  Move bestMove(0, 0, 0, 0, false);
  
  //alphabeta function with more detailed calculations
  /*int AlphaBeta(char **board, int size, bool whiteTurn, int depth, int alpha, int beta)
  {
      if (depth == 0) return getScore(board, size, whiteTurn);
      int score = -100;
      vector&lt;Move&gt; movelist = findMoves(board, size, whiteTurn);
  
      for (unsigned int i = 0; i &lt; movelist.size(); i++)
      {
          do_move(board, movelist.at(i));
          int tmp = -AlphaBeta(board, size, !whiteTurn, depth - 1, alpha, beta);
          undo_move(board, movelist.at(i));
          if (tmp &gt; score)
          {
              if (whiteTurn)
              {
                  if (score &gt; alpha) 
                  {
                      alpha = score;
                  }
                  if (-alpha &lt;= beta)
                  {
                      return alpha;
                  }
              }
              else
              {
                  if (score &gt; beta)
                  {
                      beta = score;
                  }
                  if (-beta &lt;= alpha)
                  {
                      return beta;
                  }
              }
          }
      }
      return score;
  }*/
  
  //generic alphabeta function
  int alphabeta(char **board, int size, bool whiteTurn, int depth, int alpha, int beta)
  {
      if (depth == 0) return getScore(board, size, whiteTurn);
      vector&lt;Move&gt; movelist = findMoves(board, size, whiteTurn);
  
      for (const Move &amp;move : movelist)
      {
          do_move(board, move);
          int tmp = -alphabeta(board, size, !whiteTurn, depth - 1, -beta, -alpha);
          undo_move(board, move);
          if (tmp &gt; alpha)
          {
              if (depth == 5)
                  bestMove = move;
              alpha = tmp;
          }
      }
      return alpha;
  }
  
  //main game loop
  void game(char **board, int size, bool &amp;whiteTurn)
  {
      newGame(board, size);
      printBoard(board, size);
      system("PAUSE");
  
      int a = -std::numeric_limits&lt;int&gt;::max();
      int b = std::numeric_limits&lt;int&gt;::max();
  
      do
      {
          alphabeta(board, size, whiteTurn, 5, a, b);
          do_move(board, bestMove);
          whiteTurn = !whiteTurn;
          system("cls");
          printBoard(board, size);
          system("PAUSE");
      } while (!findMoves(board, size, whiteTurn).empty());
  }
  
  int main()
  {   
      int n = 8;
      bool whTurn = true;
      char **board=initBoard(n);
      game(board, n, whTurn);
      return 0;
  }
  </code></pre>