2

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);

Gaspy
  • 188
  • 1
  • 8
  • Posting your structures and some code WITH recursion will help the one who will de-recurse it for you. At least you'll get what you want more precisely. – Daniel Mošmondor Nov 05 '10 at 08:35
  • 1
    Google: java alpha-beta search negamax – Halil Özgür Nov 05 '10 at 08:39
  • @battal, I have the normal, recursive code. I was not able to find a non-recursive one. – Gaspy Nov 05 '10 at 15:24
  • Adding variations of "nonrecursive" to search terms looks like to provide a few results, nevertheless it's true that there are not many examples on this. Looks like you may have to make up one. By the way, is [this](http://aima-java.googlecode.com/svn/trunk/aima-core/src/main/java/aima/core/search/adversarial/Game.java) related? – Halil Özgür Nov 05 '10 at 17:58
  • http://stackoverflow.com/questions/931762/can-every-recursion-be-converted-into-iteration – user1709408 Dec 21 '15 at 16:19
  • https://secweb.cs.odu.edu/~zeil/cs361/web/website/Lectures/recursionConversion/page/recursionConversion.html – user1709408 Dec 22 '15 at 01:32

2 Answers2

1

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?

JohnAD
  • 879
  • 6
  • 6
1

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

Steve Mulligan
  • 21
  • 5