Iterative negamax?

[Armand]

I want to change the usual recursive negamax search into an iterative one. I am implementing chess into a rather primitive environment (if not downright hostile) and the iterative approach would provide benefits.

I've been looking but I couldn't find one semi-legible working code. I'd love to see something that preferably uses a stack and doesn't use GOTOs (I can't use them).

The only place I could find something was on chessprogramming.wikispaces.com but nothing I could actually use.

Any help would be very much appreciated.

[H.G.Muller]

This is a bit hard to answer if we don't know what you can do. At a lower level all control structures are gotos; to make loops you cannot do without them. If statements are disguised forward gotos. The low-leve structure of the search control flow is that of 3 overlapping loops:

Code: Select all

Search:
  GenMoves(); // includes creating new stack frame
NextMove:
  MakeMove():
  if(MORE_DEPTH) goto Search;
Result:
  UnMake();
  if(MORE_MOVES) goto NextMove;
  Cleanup(); // remove the stack frame
  if(!ROOT) goto Result;


So that is basically 3 leapfrog backward conditional jumps.

If you can do only normal (nested) loops ad ifs, you could try to write it as two consecutive loops (the Search and Result loop) within one encompassing loop. The latter must than perform the NextMove loop, meaning you would have to somehow skip the Cleanup() code at the end (by putting it into an if(!MORE_MOVES) or break out of the result loop n stead of the goto. And you would also have to design some condition to decide if you want to skip MoveGen in the first iteration of the Search loop. E.g.

Code: Select all

Search()
do {
  do {
    if(!NextMoveFlag) GenMoves(); // includes creating new stack frame
    NextMoveFlag = FALSE;
    MakeMove():
  } while(MORE_DEPTH);
  do {
    UnMake();
    if(MORE_MOVES) NextMoveFlag = TRUE;
    else Cleanup(); // remove the stack frame
  } while(!ROOT && !NextMoveFlag);
} while(!ROOT && !NextMoveFlag);


[Armand]

Thank you, sorry I haven't been clearer, I've been looking for any info and because I couldn't find it, I ended up writing a poorly-worded question.

So, I wrote a chess game in Flash actionscript, one of the very few engines written in this language.
You can see the current implementation here: http://www.sparkchess.com

The online version can search 4 plies, uses alpha-beta pruning with iterative deepening and principal variation and up to 4 plies of quiescence. The offline version can do more plies but it's pretty slow (can do about 20000 nodes/second).

One of the problems I'm having is that it's single-threaded, once it starts evaluating there's no way to interact with the program until is done (it has time management).

So if I could convert my search to work iteratively, I could have more control over it. I can use conditionals, loops and switches, but no Goto.

Right now, simplied, the search function looks like this:

Code: Select all

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

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

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

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

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

      alpha = score;
    }
  }
  return alpha;
}

I'll have a look at your code in the morning and I'll see how I could adapt it. I've been trying to use a single loop so far and I've been able to traverse the tree with it, but I was having issues doing the alpha-beta pruning...

[Armand]

I think I got it to work, thanks for the help.

I'm now testing on some pre-generated trees to make sure it works exactly the same as the recursive one...