Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Iterative alpha-beta search?

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.