title: Alpha-beta prunning with transposition table, iterative deepening
body: <p>I'm trying to implement alpha-beta min-max prunning enhanced with transposition tables. I use this pseudocode as reference:</p>
  
  <p><a href="http://people.csail.mit.edu/plaat/mtdf.html#abmem">http://people.csail.mit.edu/plaat/mtdf.html#abmem</a></p>
  
  <pre><code>function AlphaBetaWithMemory(n : node_type; alpha , beta , d : integer) : integer;
      if retrieve(n) == OK then /* Transposition table lookup */
          if n.lowerbound &gt;= beta then return n.lowerbound;
          if n.upperbound &lt;= alpha then return n.upperbound;
          alpha := max(alpha, n.lowerbound);
          beta := min(beta, n.upperbound);
      if d == 0 then g := evaluate(n); /* leaf node */
      else if n == MAXNODE then
          g := -INFINITY; a := alpha; /* save original alpha value */
          c := firstchild(n);
          while (g &lt; beta) and (c != NOCHILD) do
              g := max(g, AlphaBetaWithMemory(c, a, beta, d - 1));
              a := max(a, g);
              c := nextbrother(c);
      else /* n is a MINNODE */
          g := +INFINITY; b := beta; /* save original beta value */
          c := firstchild(n);
          while (g &gt; alpha) and (c != NOCHILD) do
              g := min(g, AlphaBetaWithMemory(c, alpha, b, d - 1));
              b := min(b, g);
              c := nextbrother(c);
  
      if g &lt;= alpha then 
          n.upperbound := g; 
          store n.upperbound;
      if g &gt;  alpha and g &lt; beta then
          n.lowerbound := g; 
          n.upperbound := g; 
          store n.lowerbound, n.upperbound;
      if g &gt;= beta then 
          n.lowerbound := g; 
          store n.lowerbound;
  return g;
  </code></pre>
  
  <p>Three questions to this algorithm:</p>
  
  <ol>
  <li><p>I belive that I should store depth (=distance to leaf level) with each saved transposition table entry and use entry only when entry.depth>=currentDepth  (= entry is more or equal distant from leaves level). That is not shown in above pseudocode and is not discussed there, I wanted to make sure I understand that correctly.</p></li>
  <li><p>I would like to store best move for each position to use it for move ordering AND extracting best move after the search stops. In pure min-max it's obvious which move is the best, but which move is the best when iterating with alpha-beta cutoffs? Can I assume that the best move for given position is the best move found when the loop ends (with cut-off or without)?</p></li>
  <li><p>When executing this algorithm in iterative deepening scheme - should I clear transposition table before each depth increase? I think not, I'd like tu use stored position from previous iteration, but I'm not sure if the information is adequate for deeper searches (It should be when checking table entry depth)?    </p></li>
  </ol>