Answers.Body: <p>Let's give a try:</p>
  
  <ul>
  <li>Are you sure your <code>fen()</code> is correct? Don't assume, check how many times your TB table is being used. If the <code>fen()</code> is bugged, your TB would never be used. A possibility is that you add halfmove clock and fullmove number into FEN (please check).</li>
  <li>Please note the <code>fen()</code> function is very <strong>slow</strong>. Your line <code>minimaxDict[game.fen() + ' [ ' + depth + ' maximizing ]']</code> is <strong>wrong</strong>, because you are asking the computer to compute the FEN position <strong>twice</strong>. It's important to note computing an FEN position can only be done by looping through the whole board (64 squares). Everytime when we read a square, we must append a character to the existing (possibly immutable) memory array. Appending a character to memory is a <strong>super slow</strong> operation, because the computer might need to allocate new memory. Please ask on Stackoverflow if you want clarification. This is a very <strong>serious</strong> issue. Your TB implementation is meaningless unless you're sure <code>fen()</code> is <strong>fast</strong>, and no reallocation complexity.</li>
  <li>Please note a much better implementation is <strong>zobrist</strong> hashing. Why wouldn't you use it?</li>
  <li>Please <strong>check</strong>, double-check and triple-check if your TB is being used. Are you sure <code>if (minimaxDict[game.fen() + ' [ ' + depth + ' maximizing ]'])</code> is true? Anything could happen in a program.</li>
  <li>How many times your TB value was returned in the search? 1%? 2%? Do you have a number?</li>
  <li>Your TB has the depth information and min/max. I've never done it myself like this. Are you sure it makes sense?</li>
  </ul>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-08-27T16:33:55.687Z
Answers.Text: To points 1 and 4 - I am sure the TB is being used as I have done some logging. To point 5 - I haven't checked it out yet, but will do so. For point 6, since I'm storing the return value from the alpha-beta tree, the depth is required, but you are correct that "min/max" are not required.
  
  For points 2, 3, and 5 - I will take a look at these ASAP. I'll also ask on Stackoverflow as you mentioned for clarification. Thanks for your help!
Answers.UserDisplayName: keyan.r
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-08-27T16:58:40.397Z
Answers.Text: Edit: Actually, it looks like, though the .fen() values are being accessed, they do include additional information! Perhaps this is the point 1 you are mentioning above - I'll give it a quick look ~
Answers.UserDisplayName: keyan.r
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-08-28T02:14:06.237Z
Answers.Text: @keyan.r Good. Now we're getting somewhere. : -)
Answers.UserDisplayName: SmallChess
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-08-27T13:11:10.790Z
Answers.LastActivityDate: 2017-08-27T13:37:43.323Z
Answers.LastEditDate: 2017-08-27T13:37:43.323Z
Answers.UserDisplayName: SmallChess
Body: <p>I have an alpha-beta pruning chess AI that I have implemented using chessjs and chessboardjs. Below is my AI algorithm - it includes move ordering on the first two depths, using the boardScore value at that position as the heuristic, and a hash table of past minimizing and maximizing values for FEN strings at different depths, as a transposition table:</p>
  
  <pre><code>var minAI = function(depth, alpha, beta) {
    if (minimaxDict[game.fen() + ' [ ' + depth + ' minimizing ]'])
      return minimaxDict[game.fen() + ' [ ' + depth + ' minimizing ]'];
    var options = game.ugly_moves();
    if (depth &lt;= 0 || options.length === 0)
      return boardScore('b', game, depth);
    if (maxDepth - 1 === depth) //only perform move ordering on "shallow" iteration
      orderMoves(options, depth, false);
    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;
    }
    minimaxDict[game.fen() + ' [ ' + depth + ' minimizing ]'] = bestMin;
    return bestMin;
  }
  
  var maxAI = function(depth, alpha, beta) {
    if (minimaxDict[game.fen() + ' [ ' + depth + ' maximizing ]'])
      return minimaxDict[game.fen() + ' [ ' + depth + ' maximizing ]'];
    var options = game.ugly_moves();
    if (depth &lt;= 0 || options.length === 0)
      return boardScore('b', game, depth);
    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;
    }
    minimaxDict[game.fen() + ' [ ' + depth + ' maximizing ]'] = bestMax;
    return bestMax;
  }
  
  var bestAI = function() {
    var options = game.ugly_moves();
    if (!options.length) return;
    orderMoves(options, maxDepth, true);
    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)
        break;
    }
    game.ugly_move(options[moveIndex]);
    board.position(game.fen()); 
    if (game.in_checkmate())
      window.setTimeout(alert("Checkmate!"), 250);
    else if (game.in_draw())
      window.setTimeout(alert("Draw!"), 250);
    else if (game.in_stalemate())
      window.setTimeout(alert("Stalemate!"), 250);
    else if (game.in_threefold_repetition())
      window.setTimeout(alert("Threefold repetition!"), 250);
    else if (game.insufficient_material())
      window.setTimeout(alert("Draw by insufficient material!"), 250);
  }
  </code></pre>
  
  <p>Here is my game running on maxDepth = 5 after 5 moves, without the transposition table hash being used. At the bottom of the picture are the setTimeout violations, which (though they aren't supposed to be used as timers) show the time it took for each move to be made.</p>
  
  <p><a href="https://i.sstatic.net/eQVoF.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/eQVoF.png" alt="enter image description here"></a>
  And here is my game with the transposition table hashing:
  <a href="https://i.sstatic.net/zFVZB.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/zFVZB.png" alt="enter image description here"></a></p>
  
  <p>Comparing the two move calculation durations, it doesn't look like my transposition table is helping too much, and is sometimes slowing me down. Is my implementation of the transposition table incorrect? Is the move ordering algorithm hampering me in some way? </p>
  
Tags: <engines>
Title: Why doesn't my transposition table improve my move calculation time?
ThreadText: # Why doesn't my transposition table improve my move calculation time?
  
  (Asked by: username_0 on 2017-08-27)
  
  I have an alpha-beta pruning chess AI that I have implemented using chessjs and chessboardjs. Below is my AI algorithm - it includes move ordering on the first two depths, using the boardScore value at that position as the heuristic, and a hash table of past minimizing and maximizing values for FEN strings at different depths, as a transposition table:
  var minAI = function(depth, alpha, beta) {
    if (minimaxDict[game.fen() + ' [ ' + depth + ' minimizing ]'])
      return minimaxDict[game.fen() + ' [ ' + depth + ' minimizing ]'];
    var options = game.ugly_moves();
    if (depth <= 0 || options.length === 0)
      return boardScore('b', game, depth);
    if (maxDepth - 1 === depth) //only perform move ordering on "shallow" iteration
      orderMoves(options, depth, false);
    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;
    }
    minimaxDict[game.fen() + ' [ ' + depth + ' minimizing ]'] = bestMin;
    return bestMin;
  }
  
  var maxAI = function(depth, alpha, beta) {
    if (minimaxDict[game.fen() + ' [ ' + depth + ' maximizing ]'])
      return minimaxDict[game.fen() + ' [ ' + depth + ' maximizing ]'];
    var options = game.ugly_moves();
    if (depth <= 0 || options.length === 0)
      return boardScore('b', game, depth);
    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;
    }
    minimaxDict[game.fen() + ' [ ' + depth + ' maximizing ]'] = bestMax;
    return bestMax;
  }
  
  var bestAI = function() {
    var options = game.ugly_moves();
    if (!options.length) return;
    orderMoves(options, maxDepth, true);
    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)
        break;
    }
    game.ugly_move(options[moveIndex]);
    board.position(game.fen()); 
    if (game.in_checkmate())
      window.setTimeout(alert("Checkmate!"), 250);
    else if (game.in_draw())
      window.setTimeout(alert("Draw!"), 250);
    else if (game.in_stalemate())
      window.setTimeout(alert("Stalemate!"), 250);
    else if (game.in_threefold_repetition())
      window.setTimeout(alert("Threefold repetition!"), 250);
    else if (game.insufficient_material())
      window.setTimeout(alert("Draw by insufficient material!"), 250);
  }
  
  Here is my game running on maxDepth = 5 after 5 moves, without the transposition table hash being used. At the bottom of the picture are the setTimeout violations, which (though they aren't supposed to be used as timers) show the time it took for each move to be made.
  
  And here is my game with the transposition table hashing:
  
  Comparing the two move calculation durations, it doesn't look like my transposition table is helping too much, and is sometimes slowing me down. Is my implementation of the transposition table incorrect? Is the move ordering algorithm hampering me in some way?
  
  **Tags:** engines
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2017-08-27. Score: 2 | Accepted answer
  
  Let's give a try:
  
  * Are you sure your `fen()` is correct? Don't assume, check how many times your TB table is being used. If the `fen()` is bugged, your TB would never be used. A possibility is that you add halfmove clock and fullmove number into FEN (please check).
  * Please note the `fen()` function is very **slow**. Your line `minimaxDict[game.fen() + ' [ ' + depth + ' maximizing ]']` is **wrong**, because you are asking the computer to compute the FEN position **twice**. It's important to note computing an FEN position can only be done by looping through the whole board (64 squares). Everytime when we read a square, we must append a character to the existing (possibly immutable) memory array. Appending a character to memory is a **super slow** operation, because the computer might need to allocate new memory. Please ask on Stackoverflow if you want clarification. This is a very **serious** issue. Your TB implementation is meaningless unless you're sure `fen()` is **fast**, and no reallocation complexity.
  * Please note a much better implementation is **zobrist** hashing. Why wouldn't you use it?
  * Please **check**, double-check and triple-check if your TB is being used. Are you sure `if (minimaxDict[game.fen() + ' [ ' + depth + ' maximizing ]'])` is true? Anything could happen in a program.
  * How many times your TB value was returned in the search? 1%? 2%? Do you have a number?
  * Your TB has the depth information and min/max. I've never done it myself like this. Are you sure it makes sense?
  
  > **Comments:**
  > **username_0**: To points 1 and 4 - I am sure the TB is being used as I have done some logging. To point 5 - I haven't checked it out yet, but will do so. For point 6, since I'm storing the return value from the alpha-beta tree, the depth is required, but you are correct that "min/max" are not required.  For points 2, 3, and 5 - I will take a look at these ASAP. I'll also ask on Stackoverflow as you mentioned for clarification. Thanks for your help!  
  > **username_0**: Edit: Actually, it looks like, though the .fen() values are being accessed, they do include additional information! Perhaps this is the point 1 you are mentioning above - I'll give it a quick look ~  
  > **username_1**: @username_0 Good. Now we're getting somewhere. : -)  
  
  ---
  
  