Alpha-beta tree search without recursion

I'd like to see an implementation of an alpha-beta search (negamax to be more precise) without recursion. I know the basic idea - to use one or more stacks to keep track of the levels, but having a real code would spare me a lot of time.

Having it in Java, C# or Javascript would be perfect, but C/C++ is fine.

Here's the (simplified) recursive code:

function search(crtDepth, alpha, beta)
{
  if (crtDepth == 0)
    return eval(board);

  var moves = generateMoves(board);
  var crtMove;
  var score = 200000;

  var i;
  while (i<moves.length) 
  {
    crtMove = moves.moveList[i++];

    doMove(board, crtMove);    
    score = -search(crtDepth-1, -beta, -alpha);
    undoMove(board, crtMove);

    if (score > alpha) 
    {
      if (score >= beta) 
      return beta;

      alpha = score开发者_高级运维;
    } 
  }
  return alpha;
}

search(4, -200000, 200000);

Knuth and Moore published an iterative alpha-beta routine in 1975 using an ad-hoc Algol language.

An Analysis of Alpha Beta Pruning (Page 301)

Also in Chapter 9 of "Selected Papers on Analysis of Algorithms"

It doesn't look very easy to covert into C# but it might help someone who wants to do it for the pure joy of optimization.

I'm very new to chess programming so it's beyond my abilities. Plus, my biggest performance gain was when I switched from "Copy-Make" to "Make-Unmake". I'm using XNA, so getting my GC latency down to almost 0 fixed all my performance issues, now it runs faster on my 360 than it does on my PC so this optimization seems too difficult to attempt for my needs.

Also see Recursion to Iteration

For a more recent bit of code, I wrote a non-recursive Negamax routine as an option in the EasyAI python library. The specific source code is at:

https://github.com/Zulko/easyAI/blob/master/easyAI/AI/NonRecursiveNegamax.py

It uses a simple loop with a fixed array of objects (size determined by target depth) to move up and down the tree in an ordered fashion. For the particular project I was using it on, it was six times faster than the recursive version. But I'm sure each game would respond differently.

There is no way to deny that this is some dense and complex code and conversion to C/Java/C# will be ... challenging. It is pretty much nothing but border cases. :)

If you convert it to C/Java/C#, I would love to see the results. Place an link in the comment?