Answers.Body: <p>Add the depth information to the <code>99999</code>. Let's look at Stockfish:</p>
  
  <blockquote>
    <p><a href="https://github.com/official-stockfish/Stockfish/blob/master/src/search.cpp" rel="nofollow noreferrer">https://github.com/official-stockfish/Stockfish/blob/master/src/search.cpp</a></p>
  </blockquote>
  
  <p>This block returns mate if <strong>mated_in</strong> is true.</p>
  
  <pre><code>if (!moveCount)
          bestValue = excludedMove ? alpha
                     :     inCheck ? mated_in(ss-&gt;ply) : DrawValue[pos.side_to_move()];
  </code></pre>
  
  <p>Let's check the <strong>mated_in</strong> function:</p>
  
  <blockquote>
    <p><a href="https://github.com/official-stockfish/Stockfish/blob/master/src/types.h" rel="nofollow noreferrer">https://github.com/official-stockfish/Stockfish/blob/master/src/types.h</a></p>
  </blockquote>
  
  <p>Please note Stockfish returns checkmate <strong>plus</strong> depth. That'd solve your problem.</p>
  
  <pre><code>inline Value mated_in(int ply) {
    return -VALUE_MATE + ply;
  }
  </code></pre>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-08-27T13:28:33.543Z
Answers.LastActivityDate: 2017-08-27T13:28:33.543Z
Answers.UserDisplayName: SmallChess
Answers.Body: <p>Well, there are two problems with your algorithm:</p>
  
  <ol>
  <li><p>You don't treat draw (by whatever rule) in any way, meaning your AI will stubbornly run against a wall trying to keep the best possible position even if sacrificing a bit is likely to lead to a better outcome than draw.</p></li>
  <li><p>You treat all moves leading to mate as equal. But as you found out, they aren't, which should be reflected in your code. So the evaluation should be a discriminated union:</p>
  
  <ul>
  <li>Number of Moves to mate, OR</li>
  <li>heuristic evaluation of relative strength of players positions</li>
  </ul></li>
  </ol>
  
  <p>You might be able to map it to a single value, with abs(value) &lt; MATE for the first, and BIG_VALUE - abs(value) for the number of moves to mate otherwise.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-08-26T16:32:40.113Z
Answers.Text: Thanks! I wanted to also comment and note that move ordering is another implementation that I learned about and which works here. In that case, we order the moves on a more shallow depth, and search the branches of the move tree with the highest score first. In this case, this means that we search the checkmate position in one move before the one in two moves, and the alpha-beta pruning stops the searching from there.
Answers.UserDisplayName: keyan.r
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-08-27T13:31:21.923Z
Answers.Text: This answer is incorrect, nonsense and just wrong. Evaluation function doesn't know "number of moves to mate" because it's just mate or not mate. You should add the information to the search as in Stockfish, please study my answer.
Answers.UserDisplayName: SmallChess
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-08-26T15:56:10.233Z
Answers.LastActivityDate: 2017-08-27T13:46:11.303Z
Answers.LastEditDate: 2017-08-27T13:46:11.303Z
Answers.UserDisplayName: Deduplicator
Body: <p>I have an alpha-beta pruning chess AI that I have implemented using chessjs and chessboardjs. A friend of mine was playtesting it and came across the following position:</p>
  
  <pre><code>7r/ppp1k1rp/8/8/7K/4qb2/8/8 b - - 0 1
  
  1... Qh6#
  (1... Rhg8 2. Kh3 Qh6# (2... Rh8 Qh6))
  </code></pre>
  
  <p>In the position, black has a clear mate in 1 with Qh6. However, my alpha-beta algorithm, which is set to depth 4, first evaluates Rg8 (as it is the first move in the game.ugly_moves() array from chessjs). With Rg8, black still has mate in two, with white playing Kh3 and black playing Qh6. Thus, alpha and beta will both equal the "checkmate score", beta&lt;=alpha satisfies, and the program returns, pruning the mate in one solution. Also, after playing Rg8, Kh3, black evaluates the board again, looking at Rh8 first, and yet again sees mate in two! (Either Kh2 or Kh4, then Qh6) and then the cycle continues (i.e. the AI plays Rg8, Rh8 until threefold repetition). Basically, in this position, I am always getting a draw instead of an obvious win.</p>
  
  <p>Below is my alpha-beta implementation of this algorithm, in Javascript:</p>
  
  <pre><code>var minAI = function(depth, alpha, beta) {
    var options = game.ugly_moves();
    if (depth &lt;= 0 || options.length === 0)
      return boardScore('b', game);
  
    var bestMin = 99999;
    for (var i = 0; i &lt; options.length; i ++)
    {
      game.ugly_move(options[i]);
      if (game.in_threefold_repetition())
      {
        game.undo();
        continue;
      }
      bestMin = Math.min(bestMin, maxAI(depth - 1, alpha, beta));
      beta = Math.min(beta, bestMin);
      game.undo();
      if (beta &lt;= alpha)
        break;
    }
    return bestMin;
  }
  
  var maxAI = function(depth, alpha, beta) {
    var options = game.ugly_moves();
    console.log("in maxAI");
    if (depth &lt;= 0 || options.length === 0)
      return boardScore('b', game);
    var bestMax = -99999;
    for (var i = 0; i &lt; options.length; i ++)
    {
      game.ugly_move(options[i]);
      if (game.in_threefold_repetition())
      {
        game.undo();
        continue;
      }
      bestMax = Math.max(bestMax, minAI(depth - 1, alpha, beta));
      alpha = Math.max(alpha, bestMax);
      game.undo();
      if (beta &lt;= alpha)
        break;
    }
    return bestMax;
  }
  
  var bestAI = function() {
    var options = game.ugly_moves();
    if (!options.length) return;
    var bestScore = -99999;
    var moveIndex = -1;
    var alpha = -99999;
    var beta = 99999;
    for (i = 0; i &lt; options.length; i++)
    {
      game.ugly_move(options[i]);
      var moveScore = minAI(maxDepth - 1, alpha, beta);
      if (moveScore &gt; bestScore)
      {
        moveIndex = i;
        bestScore = moveScore;
        alpha = Math.max(alpha, bestScore);
      };
      game.undo();
      if (beta &lt;= alpha)
      {
        console.log("we've been beta blocked");
        console.log(alpha);
        console.log(beta);
        break;
      }
    }
    game.ugly_move(options[moveIndex]);
    board.position(game.fen()); 
    if (game.in_checkmate())
      window.setTimeout(alert("checkmate!"), 250);
  }
  </code></pre>
  
  <p>And here is how I give the board a score for a player (either 'w' for white, or 'b' for black):</p>
  
  <pre><code>var value = function(piece, player, i, j)
  {
    if (piece === 'r') return (500 + 
      (player === 'w' ? rookGridWhite[i][j] : rookGridBlack[i][j]));
    else if (piece === 'n') return (320 + 
      (player === 'w' ? knightGridWhite[i][j] : knightGridBlack[i][j]));
    else if (piece === 'b') return (330 + 
      (player === 'w' ? bishopGridWhite[i][j] : bishopGridBlack[i][j]));
    else if (piece === 'k') return (0 + 
      (player === 'w' ? kingGridWhiteStart[i][j] : kingGridBlackStart[i][j]));
    else if (piece === 'q') return (900 + 
      (player === 'w' ? queenGridWhite[i][j] : queenGridBlack[i][j]));
    else if (piece === 'p') return (100 + 
      (player === 'w' ? pawnGridWhite[i][j] : pawnGridBlack[i][j]));
  }
  
  var boardScore = function(player, game) {
    if (scoreDict[game.fen() + ' [' + player + ']'])
      return scoreDict(game.fen() + ' [' + player + ']');
    if (game.turn() === player &amp;&amp; game.in_checkmate())
      return -99999;
    else if (game.turn() !== player &amp;&amp; game.in_checkmate())
      return 99999;
    var scoreWhite = 0;
    var scoreBlack = 0;
    for (var i = 0; i &lt; 8; i ++)
    {
      for (var j = 0; j &lt; 8; j ++)
      {
        var square = game.board()[i][j]
        if (square &amp;&amp; square["color"] === 'w')
          scoreWhite += value(square["type"], player, i, j);
        else if (square &amp;&amp; square["color"] !== 'w')
          scoreBlack += value(square["type"], player, i, j);
        if (scoreWhite &lt;= 1100 || scoreBlack &lt;= 1100)
        {
          kingGridWhiteStart = kingGridWhiteEnd;
          kingGridBlackStart = kingGridBlackEnd;
        }
      }
    }
    var posScoreWhite = scoreWhite - scoreBlack;
    scoreDict.push({
        key:   game.fen() + ' [w]',
        value: posScoreWhite
    });
    var posScoreBlack = scoreBlack - scoreWhite;
    scoreDict.push({
        key:   game.fen() + ' [b]',
        value: posScoreBlack
    });
    return (player === 'w' ? posScoreWhite : posScoreBlack);
  } 
  </code></pre>
  
  <p>The "grids" referred to above are 2D position-value tables as given in the link below:
  <a href="https://chessprogramming.wikispaces.com/Simplified+evaluation+function" rel="nofollow noreferrer">https://chessprogramming.wikispaces.com/Simplified+evaluation+function</a></p>
  
  <p>I reversed the arrays given in that link for black's evaluations, and used the kingGridStart arrays until an endgame condition is reached, in which case I use the kingGridEnd arrays.</p>
  
  <p>I am not sure how to go about fixing this. Did I understand why my alpha beta program is failing, or is there another reason I am not aware of? </p>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-08-26T22:42:17.480Z
Comments.Text: You might want to look at [this](https://chessprogramming.wikispaces.com/Coko#MateBug).
Comments.UserDisplayName: boboquack
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-09-01T14:58:29.350Z
Comments.Text: To the people voting to close: The [community has decided](https://chess.meta.stackexchange.com/q/418/7297) that questions about chess programming are **on-topic**. This is also stated in the [help center](/help/on-topic): *Chess-specific questions about programming a chess engine or other chess software are welcome.*
Comments.UserDisplayName: Herb
Tags: <engines>
Title: Alpha-Beta Pruning returns mate in two instead of obvious mate in one
ThreadText: # Alpha-Beta Pruning returns mate in two instead of obvious mate in one
  
  (Asked by: username_0 on 2017-08-26)
  
  I have an alpha-beta pruning chess AI that I have implemented using chessjs and chessboardjs. A friend of mine was playtesting it and came across the following position:
  7r/ppp1k1rp/8/8/7K/4qb2/8/8 b - - 0 1
  
  1... Qh6#
  (1... Rhg8 2. Kh3 Qh6# (2... Rh8 Qh6))
  
  In the position, black has a clear mate in 1 with Qh6. However, my alpha-beta algorithm, which is set to depth 4, first evaluates Rg8 (as it is the first move in the game.ugly_moves() array from chessjs). With Rg8, black still has mate in two, with white playing Kh3 and black playing Qh6. Thus, alpha and beta will both equal the "checkmate score", beta<=alpha satisfies, and the program returns, pruning the mate in one solution. Also, after playing Rg8, Kh3, black evaluates the board again, looking at Rh8 first, and yet again sees mate in two! (Either Kh2 or Kh4, then Qh6) and then the cycle continues (i.e. the AI plays Rg8, Rh8 until threefold repetition). Basically, in this position, I am always getting a draw instead of an obvious win.
  Below is my alpha-beta implementation of this algorithm, in Javascript:
  var minAI = function(depth, alpha, beta) {
    var options = game.ugly_moves();
    if (depth <= 0 || options.length === 0)
      return boardScore('b', game);
  
    var bestMin = 99999;
    for (var i = 0; i < options.length; i ++)
    {
      game.ugly_move(options[i]);
      if (game.in_threefold_repetition())
      {
        game.undo();
        continue;
      }
      bestMin = Math.min(bestMin, maxAI(depth - 1, alpha, beta));
      beta = Math.min(beta, bestMin);
      game.undo();
      if (beta <= alpha)
        break;
    }
    return bestMin;
  }
  
  var maxAI = function(depth, alpha, beta) {
    var options = game.ugly_moves();
    console.log("in maxAI");
    if (depth <= 0 || options.length === 0)
      return boardScore('b', game);
    var bestMax = -99999;
    for (var i = 0; i < options.length; i ++)
    {
      game.ugly_move(options[i]);
      if (game.in_threefold_repetition())
      {
        game.undo();
        continue;
      }
      bestMax = Math.max(bestMax, minAI(depth - 1, alpha, beta));
      alpha = Math.max(alpha, bestMax);
      game.undo();
      if (beta <= alpha)
        break;
    }
    return bestMax;
  }
  
  var bestAI = function() {
    var options = game.ugly_moves();
    if (!options.length) return;
    var bestScore = -99999;
    var moveIndex = -1;
    var alpha = -99999;
    var beta = 99999;
    for (i = 0; i < options.length; i++)
    {
      game.ugly_move(options[i]);
      var moveScore = minAI(maxDepth - 1, alpha, beta);
      if (moveScore > bestScore)
      {
        moveIndex = i;
        bestScore = moveScore;
        alpha = Math.max(alpha, bestScore);
      };
      game.undo();
      if (beta <= alpha)
      {
        console.log("we've been beta blocked");
        console.log(alpha);
        console.log(beta);
        break;
      }
    }
    game.ugly_move(options[moveIndex]);
    board.position(game.fen()); 
    if (game.in_checkmate())
      window.setTimeout(alert("checkmate!"), 250);
  }
  
  And here is how I give the board a score for a player (either 'w' for white, or 'b' for black):
  var value = function(piece, player, i, j)
  {
    if (piece === 'r') return (500 + 
      (player === 'w' ? rookGridWhite[i][j] : rookGridBlack[i][j]));
    else if (piece === 'n') return (320 + 
      (player === 'w' ? knightGridWhite[i][j] : knightGridBlack[i][j]));
    else if (piece === 'b') return (330 + 
      (player === 'w' ? bishopGridWhite[i][j] : bishopGridBlack[i][j]));
    else if (piece === 'k') return (0 + 
      (player === 'w' ? kingGridWhiteStart[i][j] : kingGridBlackStart[i][j]));
    else if (piece === 'q') return (900 + 
      (player === 'w' ? queenGridWhite[i][j] : queenGridBlack[i][j]));
    else if (piece === 'p') return (100 + 
      (player === 'w' ? pawnGridWhite[i][j] : pawnGridBlack[i][j]));
  }
  
  var boardScore = function(player, game) {
    if (scoreDict[game.fen() + ' [' + player + ']'])
      return scoreDict(game.fen() + ' [' + player + ']');
    if (game.turn() === player && game.in_checkmate())
      return -99999;
    else if (game.turn() !== player && game.in_checkmate())
      return 99999;
    var scoreWhite = 0;
    var scoreBlack = 0;
    for (var i = 0; i < 8; i ++)
    {
      for (var j = 0; j < 8; j ++)
      {
        var square = game.board()[i][j]
        if (square && square["color"] === 'w')
          scoreWhite += value(square["type"], player, i, j);
        else if (square && square["color"] !== 'w')
          scoreBlack += value(square["type"], player, i, j);
        if (scoreWhite <= 1100 || scoreBlack <= 1100)
        {
          kingGridWhiteStart = kingGridWhiteEnd;
          kingGridBlackStart = kingGridBlackEnd;
        }
      }
    }
    var posScoreWhite = scoreWhite - scoreBlack;
    scoreDict.push({
        key:   game.fen() + ' [w]',
        value: posScoreWhite
    });
    var posScoreBlack = scoreBlack - scoreWhite;
    scoreDict.push({
        key:   game.fen() + ' [b]',
        value: posScoreBlack
    });
    return (player === 'w' ? posScoreWhite : posScoreBlack);
  } 
  
  The "grids" referred to above are 2D position-value tables as given in the link below:
  https://chessprogramming.wikispaces.com/Simplified+evaluation+function
  I reversed the arrays given in that link for black's evaluations, and used the kingGridStart arrays until an endgame condition is reached, in which case I use the kingGridEnd arrays.
  I am not sure how to go about fixing this. Did I understand why my alpha beta program is failing, or is there another reason I am not aware of?
  
  **Tags:** engines
  
  > **Comments:**
  > **username_1**: You might want to look at [this](https://chessprogramming.wikispaces.com/Coko#MateBug).  
  > **username_2**: To the people voting to close: The [community has decided](https://chess.meta.stackexchange.com/q/418/7297) that questions about chess programming are **on-topic**. This is also stated in the [help center](/help/on-topic): *Chess-specific questions about programming a chess engine or other chess software are welcome.*  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_3 on 2017-08-27. Score: 3 | Accepted answer
  
  Add the depth information to the 99999. Let's look at Stockfish:
  
  https://github.com/official-stockfish/Stockfish/blob/master/src/search.cpp
  
  This block returns mate if mated_in is true.
  if (!moveCount)
          bestValue = excludedMove ? alpha
                     :     inCheck ? mated_in(ss->ply) : DrawValue[pos.side_to_move()];
  
  Let's check the mated_in function:
  
  https://github.com/official-stockfish/Stockfish/blob/master/src/types.h
  
  Please note Stockfish returns checkmate plus depth. That'd solve your problem.
  inline Value mated_in(int ply) {
    return -VALUE_MATE + ply;
  }
  
  
  ---
  
  ### Answer by username_4 on 2017-08-26. Score: 3
  
  Well, there are two problems with your algorithm:
  
  1. You don't treat draw (by whatever rule) in any way, meaning your AI will stubbornly run against a wall trying to keep the best possible position even if sacrificing a bit is likely to lead to a better outcome than draw.
  2. You treat all moves leading to mate as equal. But as you found out, they aren't, which should be reflected in your code. So the evaluation should be a discriminated union:
  
     * Number of Moves to mate, OR
     * heuristic evaluation of relative strength of players positions
  
  You might be able to map it to a single value, with abs(value) < MATE for the first, and BIG\_VALUE - abs(value) for the number of moves to mate otherwise.
  
  > **Comments:**
  > **username_0**: Thanks! I wanted to also comment and note that move ordering is another implementation that I learned about and which works here. In that case, we order the moves on a more shallow depth, and search the branches of the move tree with the highest score first. In this case, this means that we search the checkmate position in one move before the one in two moves, and the alpha-beta pruning stops the searching from there.  
  > **username_3**: This answer is incorrect, nonsense and just wrong. Evaluation function doesn't know "number of moves to mate" because it's just mate or not mate. You should add the information to the search as in Stockfish, please study my answer.  
  
  ---
  
  