Author: Chan Rasjid
Date: 12:30:30 01/11/06
Go up one level in this thread
On January 11, 2006 at 12:33:04, Dan Honeycutt wrote: >On January 11, 2006 at 02:14:53, Andrew Wagner wrote: > >>This is going to sound like a really odd question. That's because it is. But I >>really do have a good reason for asking it. Anyway, here goes... >> >>Is it feasible to implemet a typical alpha-beta search in an iterative fashion? >>I'm not talking about iterative deepening, but I want to do alphabeta without >>any recursion. If it's possible, can you give me a suggestion what it might look >>like? > >Hi Andrew > >You can see an implementation of a non-recursive alpha-beta search in the >Spracklin's book, "Sargon, A Computer Chess Program". I thought it was >available on-line somewhere, but a quick google search failed to find it. > >Best >Dan H. I have been doing non-recursive search for some time and it seems ok, not much different from recursive once the "template" is reasoned through and observed. It is known there is no "measurable" recursive overheads, but it may be easier if we want to implement incremental move generation (Fabien seems to stress the importance of incremental generation which is different from partial generation). I have the non recursive template here which requires only a global stack pointed to all times with stack_t * pS; //called at rootSearch() with iterative deepening, start at ply = 1; int searchFull(board_t * board, stack_t * pS, int depth, int alpha, int beta, int side, int followPV, int pvLength){ move_t rootPV[MaxHeight];//local to PV search() . int ply = 1; int score; int captureKing = 0; assert(pS == pRootStack + 1); assert(alpha == -INFI); if (!followPV); else{ memcpy(rootPV, (pS - 1)->pv, MaxHeight * sizeof(move_t)); assert(debugRootPV(rootPV, pvLength)); } //come to this label after makemove() SEARCH_START: assert(side <= 1); assert(!captureKing); if (depth <= 0){ if (genQS(board, pS, side)){ captureKing = 1; assert(debug1 = brqAttack88(board, board->piece[side ^ 1][0], side)); goto SEARCH_RET; } score = eval(); //etc }else{ if (genFull(board, pS, side)){//captureKing captureKing = 1; goto SEARCH_RET; } pS->best = -INFI;//for Full Search } while (*pS->pCurrentMove){//list thru moves, last move-stack == 0 doMove(board, pS, *pS->pCurrentMove, side); side ^= 1; depth--; assert(beta == pS->beta); alpha = -beta; beta = pS->best > pS->alpha ? -pS->best: -pS->alpha; ply++; pS++; //goto SEARCH_START is equivalent to calling recursive search() after makemove() goto SEARCH_START; SEARCH_RET: //This label is equivalent to return from recursive search() before takeback() if (ply == 1){ //return to root-search() assert(score > -INFI && score < INFI); return score; } score = -score; pS--; ply--; //restore on undo() depth = pS->depth; alpha = pS->alpha;//begin alpha beta = pS->beta; side ^= 1; undoMove(board, pS, *pS->pCurrentMove, side); *(pS + 1)->bbMoveStack = *(pS - 1)->bbMoveStack; if (!captureKing); else{//capt K // swap last move valid move *pS->pCurrentMove = pS->moveStack[--pS->nGeneratedMove]; assert(pS->nGeneratedMove >= 0); pS->moveStack[pS->nGeneratedMove] = 0;//set last == 0 //do same slot move captureKing = 0; assert(!followPV); continue; } if (score > pS->best){ //best move ? if (score >= beta){ return score; } pS->best = score; pS->bestType = REVERSE_TYPE(retType); //may use pv[0] as bestmove pS->bestMove = *pS->pCurrentMove; if (score > alpha){ *pS->pv = pS->bestMove; //pvLength passed down on return pS->pvLength = ++pvLength; if (pvLength > 1){ //copy +1 element ok memcpy(pS->pv + 1, (pS + 1)->pv, pvLength * sizeof(move_t)); } }//else{//FL pS->nMoveDone++; } ++pS->pCurrentMove; }//end while() //etc goto SEARCH_RET; } Best Regards Rasjid
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.