AlfaGemma in Sabrina

[stegemma]

In "Sabrina" I've wrote AlfaGemma in a more "assembly-like" way. I'd never used "goto" in my C++ programs but I can debug easily AlfaGemma in this way. That's because AlfaGemma has born in assembly and the C++ rewrite were somehow non-natural, to me.

Here's the actual code, still "work in progress":

Code: Select all

int clsEngine::AlfaGemma(int iDepth)
{
	int retVal;

	if (nodescount==0) // first iteration
	{
		(pNode + 1)->pFirstMove = pNode->pFirstMove;
		MakeAllMoves();
		SortMovesDesc();
	}
	else
	{
		SortMovesDescAlfa();
		FOR_MOVES
		{
			pLoopMove->boFlags &= ~flg_betacutoff;
		}
	}
	pNode->phase = PHASE_LAST_QUIET;
	pNode->pMove = pNode->pFirstMove;
	goto __jTestTT;
	//****************************************************************
__jNextNode:
	// signals that this is a position in current branch
	pNode->pTT->type.ttCurrent = 1;
	DEBUG_BOARD;
	//------------------------------------- next ply
	SwapColor();
	++pNode;
	pNode->nValidMoves = 0;
__jNodeBeginning: //------------------------------------- node beginning
	PushBoardState(); // store board state
	pNode->alfavalue = (pNode - 2)->alfavalue;
	pNode->nMoves = pNode->phase = 0;
	pNode->pMove = NULL;
__jTestTT: //------------------------------------- test TT
	pNode->hash = board.GetHash();
	pNode->pTT = pEngineShare->GetTT(pNode->hash);
	#if ENABLE_TT
		if (pNode->hash == pNode->pTT->hash)
		{
			// la posizione era già nella TT
			++ttHits;
			if (pNode->pTT->type.ttReal | pNode->pTT->type.ttCurrent)
			{
				// posizione già giocata in questo ramo o in mosse precedenti la root => ripetizione
				pNode->alfavalue = valDraw;
				++ttReptHits;
				goto __jPreviousNode;
			}
			else
			{
				if (pNode->pTT->depth >= iDepth) // valore stessa precisione o maggiore
				{
					if (pNode->pTT->type.ttExact | pNode->pTT->type.ttMin)
					{
						pNode->alfavalue = pNode->pTT->alfavalue;
						goto __jPreviousNode;
					}
				}
			}
		}
		else
		{
			// la posizione non era già nella TT
			pNode->pTT->type.Clear().SetUncknown(1);
			pNode->pTT->hash = pNode->hash;
			pNode->pTT->alfavalue = -valInfinity;
			pNode->pTT->depth = -1;
		}
	#endif
__jMakeMoves: //------------------------------------- make moves
	if (pNode != pFirstNode) 
		while (!MakeMoves(pNode->phase) && pNode->phase < PHASE_LAST_QUIET) ++pNode->phase;
	if (pNode->phase <= PHASE_LAST_QUIET) goto __jExecuteMove;
__jMovesEnd:
	if (pNode->nValidMoves) goto __jPreviousNode;
	pNode->alfavalue = pNode->bIsAlreadyInCheck ? -valMate : valDraw;
	goto __jPreviousNode;
	//**************************************************************************************
__jBetaCutOff: //------------------------------------- beta cut-off
	pNode->alfavalue = valBad;
	// verificare e re-introdurre il concetto di "this was the best" alla radice
	(pNode-1)->pMove->boFlags |= flg_betacutoff;
__jPreviousNode: //------------------------------------- previous node
	if (pNode == pFirstNode || (!DEBUG_ALFAGEMMA && bTimeExpired)) goto __jUnrollMoves; // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<< return
	retVal = -pNode->alfavalue;
	pNode->pTT->type.ttCurrent = 0;
	--pNode;
	pNode->pMove->alfavalue = retVal;
__jTestMoveValue:
	//------------------------------------------- best value for this node?
	if (pNode->pMove->alfavalue <= pNode->alfavalue) goto __jUndoLastMove; // TODO save in TT?
__jNodeBestMove:
	pNode->alfavalue = pNode->pMove->alfavalue;
	//------------------------------------------- store hash
	if (!pNode->pTT->type.ttUncknown && pNode->pTT->depth <= iDepth - pNode->iDepth) goto __jTestBeta;
	pNode->pTT->type.Clear().SetMin(1);
	pNode->pTT->alfavalue = pNode->alfavalue;
	pNode->pTT->depth = iDepth - pNode->iDepth;
__jTestBeta:
	if (pNode == pFirstNode)
		UserSetBestMove(pNode->pMove);	
	else if ((pNode - 1)->alfavalue != -valInfinity && pNode->alfavalue >= -(pNode - 1)->alfavalue) goto __jBetaCutOff;
__jUndoLastMove:
	PopBoardState();
__jNextMove:
	++pNode->pMove;
__jExecuteMove:	//------------------------------------------- execute moves
	if (pNode->pMove >= (pNode + 1)->pFirstMove) { ++pNode->phase;  goto __jMakeMoves; }
	ExecuteMove(pNode->pMove);
	{
		uint64_t boTheKing = board.boBits[clsBoard::boKings] & board.boBits[clsBoard::boFriends];
		bool bIsInCheck = (pNode->bIsAlreadyInCheck ||	/* boTheKing != pNode->boMyKing || */
			(pNode->pMove->boSrc & pNode->boKingRays) != boEmpty)
			? IsInCheck(boTheKing, false)
			: false;
		if (bIsInCheck) goto __jUndoLastMove; // invalid move
	}
	DEBUG_BOARD;
__jEvaluate:	//------------------------------------------- evaluates position
	++nodescount;
	++pNode->nValidMoves;
	if (pNode->iDepth < iDepth) goto __jNextNode; // this is not the last ply
__jLastPly:
	pNode->pMove->alfavalue = board.value + Evaluate();
	goto __jTestMoveValue;
	//**************************************************************************************
__jUnrollMoves:
	for (; pNode >= pFirstNode; --pNode)
	{
		if (pNode->pTT) pNode->pTT->type.SetCurrent(0);
		PopBoardState();
	}
__jEnd:
	pNode = pFirstNode;
	return pNode->alfavalue;
}

[cdani]

I'd never used "goto" in my C++ programs

I use goto in Andscacs to force the compiler (Vc++) to make the assembly code I want in some places, to win some speed. For example in the move generation:

Code: Select all

	a = kingmoves[square] ...
anothermoveofking:
	if (a == 0)
		goto knightmoves;
	uint8_t destination; destination= lsb(a);
	ml->move = MakeMove(kingsquare, destination);
	ml++;
	a &= a - 1;
	goto anothermoveofking;

Maybe gcc or other compilers had optimized well this part of the code by themselves, but was not the case in Vc++.

[stegemma]

I'd never used "goto" in my C++ programs

I use goto in Andscacs to force the compiler (Vc++) to make the assembly code I want in some places, to win some speed. For example in the move generation:

Code: Select all

	a = kingmoves[square] ...
anothermoveofking:
	if (a == 0)
		goto knightmoves;
	uint8_t destination; destination= lsb(a);
	ml->move = MakeMove(kingsquare, destination);
	ml++;
	a &= a - 1;
	goto anothermoveofking;

Maybe gcc or other compilers had optimized well this part of the code by themselves, but was not the case in Vc++.

AlfaGemma doesn't need to be further optimized (in term of speed), because the most costly parts are evaluation and move generation. In short codes maintained by just one person, sometime "goto" is easiest to follow than while/for{...} loops.

In your code, maybe this little changes could be faster:

Code: Select all

	a = kingmoves[square] ...
	if (a == 0) goto knightmoves;
anothermoveofking:
	uint8_t destination = lsb(a);
	ml->move = MakeMove(kingsquare, destination);
	ml++;
	a ^= destination;
	if(a!=0) goto anothermoveofking;
knightmoves:
	...

[cdani]

In your code, maybe this little changes could be faster:

Code: Select all

	a = kingmoves[square] ...
	if (a == 0) goto knightmoves;
anothermoveofking:
	uint8_t destination = lsb(a);
	ml->move = MakeMove(kingsquare, destination);
	ml++;
	a ^= destination;
	if(a!=0) goto anothermoveofking;
knightmoves:
	...

Destination is the square number, so for this to work
a ^= destination;
you have to << destination. So I suppose that a &= a - 1; is faster, or at least is massively used in other engines.
I will try the other change in gotos. Thanks!

[stegemma]

In your code, maybe this little changes could be faster:

Code: Select all

	a = kingmoves[square] ...
	if (a == 0) goto knightmoves;
anothermoveofking:
	uint8_t destination = lsb(a);
	ml->move = MakeMove(kingsquare, destination);
	ml++;
	a ^= destination;
	if(a!=0) goto anothermoveofking;
knightmoves:
	...

Destination is the square number, so for this to work
a ^= destination;
you have to << destination. So I suppose that a &= a - 1; is faster, or at least is massively used in other engines.
I will try the other change in gotos. Thanks!

So your "lsb()" doesn't give the least significant bit but the corresponding square index?

[elcabesa]

Code: Select all

	a = kingmoves[square] ...
anothermoveofking:
	if (a == 0)
		goto knightmoves;
	uint8_t destination; destination= lsb(a);
	ml->move = MakeMove(kingsquare, destination);
	ml++;
	a &= a - 1;
	goto anothermoveofking;

Maybe gcc or other compilers had optimized well this part of the code by themselves, but was not the case in Vc++.

wasn't this code equivalent? I think it's more readable. I don't know how much slower it's with vc++ compiler

Code: Select all

a = kingmoves[square] ...
while(a)
{
	uint8_t destination;
	destination= lsb(a);
	ml->move = MakeMove(kingsquare, destination);
	ml++;
	a &= a - 1;
}

[stegemma]

I agree with you. Looking at the code that the compiler generates using "goto", I've veryfied that it is very poorly efficient. The problem is that the compiler can't assume anything about the life of a variable, so it emit duplicated code to load its value. If the code is embedded in {}, the compiler can knows that a pointer hasn't been modified.

For sample:

Code: Select all

__jNodeBeginning: //------------------------------------- node beginning
	PushBoardState(); // store board state
00007FF79475A03B  movsd       mmword ptr [rax+0F8h],xmm1  
	pNode->alfavalue = (pNode - 2)->alfavalue;
00007FF79475A043  mov         rcx,qword ptr [rbx+9E2D0h]  
00007FF79475A04A  mov         eax,dword ptr [rcx-194h]  
00007FF79475A050  mov         dword ptr [rcx+6Ch],eax  
	pNode->nMoves = pNode->phase = 0;
00007FF79475A053  mov         rax,qword ptr [rbx+9E2D0h]  
00007FF79475A05A  mov         dword ptr [rax+84h],r15d  
00007FF79475A061  mov         rax,qword ptr [rbx+9E2D0h]  
00007FF79475A068  mov         dword ptr [rax+78h],r15d  
	pNode->pMove = NULL;
00007FF79475A06C  mov         rax,qword ptr [rbx+9E2D0h]  
00007FF79475A073  mov         qword ptr [rax+8],r15  
	goto __jTestMoveValue;

The istruction "mov rax,qword ptr [rbx+9E2D0h]" has been repeated multiple times, even if the rax value hasn't changed.

For me is not a problem, because I'm focusing on make the AlfaGemma works well with TT and this "goto" structure is easiest for me to debug but in the move generator or elsewhere it could be slower than good C++ programming pratice.

[cdani]

So your "lsb()" doesn't give the least significant bit but the corresponding square index?

Yes, is just the bsf instruction.

wasn't this code equivalent? I think it's more readable. I don't know how much slower it's with vc++ compiler

Code: Select all

a = kingmoves[square] ...
while(a)
{
	uint8_t destination;
	destination= lsb(a);
	ml->move = MakeMove(kingsquare, destination);
	ml++;
	a &= a - 1;
}

Sure, much more readable. The code originally was something like this, but after trying different ways the one I shown was the fastest, visually inspecting the assembly generated and also by test.

[stegemma]

To merge with iterative deepening, the algorithm requires a separate handling of the root. The "Search" function must be called from the ID main loop:

Code: Select all

bool clsEngine::Execute()
{
	// k7/8/8/8/7p/7p/6PP/K7 w - - 0 1
	// 8/8/2b5/8/3p4/7k/4P2p/7K w - - 0 1
#if RESET_TT
	if (TT) memset(TT, 0, nTT * sizeof(*TT));
#endif
	sfout.Push("# engine's running");
	if (mutex_bestmove.Lock()) // NB: il lock serve per debug (per verificare che i mutex funzionino a dovere)
	{
		objBestMove.boFlags = flg_illegal;
		objBestMove.alfavalue = -valInfinity;
		mutex_bestmove.UnLock();
	}
	bTimeExpired = false;
	nodescount = ttHits = ttReptHits = 0;
	// kSamePawns = kNoSamePawns = 0;
	tEval.Reset();
	// bool bMagic = ssCommandLine.Search("-magic") >= 0;
	bool bRandom = ssCommandLine.Search("-random") >= 0;
	bool bTimed = ssCommandLine.Search("-timed") >= 0;
	bool bProportional = false;
	int iProportional = ssCommandLine.Search("-proportional");
	int iProportionalPerc = 60;
	if (iProportional >= 0)
	{
		bProportional = true;
		iProportionalPerc = ssCommandLine.GetString(iProportional).GetInt(60);
		// PushOut("# proportional " + clsString(iProportionalPerc));
	}

	tEval.Start();


	//nFixedDepth = 3;

	// int vStart = board.value + Evaluate();
	int iMaxLevel = nFixedDepth ? nFixedDepth : ((bRandom && !bTimed && !bProportional) ? 2 : ARRAY_COUNT(nodes) - 1);
	int klevel = 2;

	//DEBUG_BOARD;

	if (bChild || !QueryBook())
	{
		DEBUG_BOARD;
		bool bFirst = true;
		for (level = nFixedDepth ? nFixedDepth : 2; level <= iMaxLevel && (DEBUG_ALFAGEMMA || !bTimeExpired); level += klevel)
		{
#if DEBUG_BESTMOVE
			PushOut("# ------- search " + clsString(level)); //  +" board value " + OUTVD(value));
#endif
			int eval = Search(level, bFirst);    bFirst = false;
			/*uint64_t ms = tEval.ms(); if (ms < 1) ms = 1;
			PushOut("# depth " + clsString(level)
			+ " nodes " + clsString(nodescount)
			+ " ms " + clsString(ms)
			+ " nodes/s " + clsString((nodescount * 1000) / ms)
			+ " branch " + clsString(log((double)nodescount) / log((double)level), 2)
			);*/
			if (RemoveIllegalMoves() <= 1)
			{
				level = iMaxLevel;
				break;
			}
			SortMovesDescAlfa();
			eval = objBestMove.alfavalue;
			if (eval >= valKing)
			{
				int value = 0;
				PushOut("# Winning move: " + UserGetBestMove(false, value));
				break;
			}
			else if (eval <= -valKing)
			{
				PushOut("# I will lose :-(");
				break;
			}
			else
			{
				// termina la ricerca se c'è solo una mossa che non porta a prendere matto
				int nGoodMoves = 0;
				FOR_MOVES
				{
					if ((pLoopMove->boFlags & flg_betacutoff) != 0 || pLoopMove->alfavalue > -valKing) ++nGoodMoves;
				}
				if (nGoodMoves < 2)
				{
					sfout.Push("# forced move");
					break;
				}
			}
			if (bChild) break;
		}
	}

	tEval.Stop();

	if (bRandom)
	{
		RemoveIllegalMoves();

		if (bProportional)
		{
			FOR_MOVES
			{
				int k = Rand(100);
				// PushOut("# randint " + clsString(k));
				if (k <= iProportionalPerc && pLoopMove->alfavalue > -valQueen)
				{
					UserSetBestMove(pLoopMove);
					break;
				}
			}
		}
		else
		{
			int nMoves = int((pNode + 1)->pFirstMove - pNode->pFirstMove);
			int iMove = Rand(nMoves);
			clsMove *pLoopMove = pNode->pFirstMove + iMove;
			UserSetBestMove(pLoopMove);
		}
	}

	sfout.Push("# engine stopped");
	// PushOut("# done! ");
	// DebugMove(&objBestMove);
	return true;
}

int clsEngine::Search(int iDepth, bool bFirstIteration)
{
	SetBoardValue();
	PushBoardState();		DEBUG_BOARD;
	
	pNode->nValidMoves = 0;
	SetPreviousMove();

	if(bFirstIteration)
	{
		if(!MakeAllMoves() || !RemoveIllegalMoves())
			return (IsInCheck(board.boBits[clsBoard::boKings] & board.boBits[clsBoard::boFriends], false) ? -valMate + 1 : 0);
		SortMovesDesc();
	} else
	{
		SortMovesDescAlfa();
	}
	++nodescount;

	pNode->alfavalue = -valInfinity;

	PushBoardState();

	FOR_MOVES
	{
		if(!DEBUG_ALFAGEMMA && bTimeExpired) break;
		// if((pLoopMove->boFlags & flg_illegal)!=flg_empty) continue;
		pNode->pMove = pLoopMove;
		pLoopMove->boFlags &= ~flg_betacutoff;

		if((pLoopMove->boFlags & flg_isTakenKing) != flg_empty)
		{
			UserSetBestMove(pLoopMove);
			return valMate - 1;
		}

		clsTimer t;
		int val;
		// se prende matto e' inutile riesaminare la mossa a profondita' maggiore
		if((pLoopMove->boFlags & flg_lose) != flg_empty)
		{			
			val = pLoopMove->alfavalue;
			DebugMove(pLoopMove);
		} else
		{
			++pNode->nValidMoves;
			ExecuteMove(pLoopMove);
			{
				SwapColor();
				++pNode;
				if(!bTimeExpired)
				{
					val = -AlfaGemma(level);
				}
				--pNode;
			}
			PopBoardState(); // fa anche SwapColor implicitamente
		}

		if(bTimeExpired) break; // ex return alfa;
														//PushOut("#\t" + clsString(iDepth) + "\t" + clsString(t.Elapsed()) + "\t" + GetUserMove(pLoopMove, true));

		if ((pLoopMove->boFlags & flg_betacutoff) == boEmpty)
		{
			pLoopMove->alfavalue = val;

			if (val <= -valKing)
				pLoopMove->boFlags |= flg_lose;

			bool bThisWasTheBest = pLoopMove->boSrc == objBestMove.boSrc
				&& pLoopMove->boDst == objBestMove.boDst
				&& ((pLoopMove->boFlags ^ objBestMove.boFlags) & ~flg_lose) == boEmpty; // eventuale stesso pezzo promosso

			if (val > pNode->alfavalue || bThisWasTheBest) // la mossa migliore è la prima per cui l'|| dovrebbe essere sempre vero
			{
				pNode->alfavalue = val;
				if (pLoopMove->alfavalue > objBestMove.alfavalue || bThisWasTheBest)
				{
					UserSetBestMove(pLoopMove);
				}
				//TODO: verificare
				if (pNode->alfavalue >= valKing) break;
			}
		}
	}
	// DebugMoves();
	// sfout.Push("# same pawns " + clsString(kSamePawns) + "/" + clsString(kSamePawns + kNoSamePawns) + " " + clsString((kSamePawns * 100) /(kSamePawns + kNoSamePawns + 1)) + "%");

	return pNode->alfavalue;
}
#endif

#if 1
int clsEngine::AlfaGemma(int iDepth)
{
	#ifdef _DEBUG
		sfout.Push("-------------------- DEPTH " + clsString(iDepth));
	#endif
	int retVal;

	clsSimpleNode *pMyRootNode = pNode;
	goto __jNodeBeginning;
	//****************************************************************
__jNextNode:
	// signals that this is a position in current branch
	#if ENABLE_TT
		pNode->pTT->type.ttCurrent = 1;
	#endif
	DEBUG_BOARD;
	//------------------------------------- next ply
	SwapColor();
	++pNode;
	pNode->nValidMoves = 0;
__jNodeBeginning: //------------------------------------- node beginning
	PushBoardState(); // store board state
	pNode->alfavalue = (pNode - 2)->alfavalue;
	pNode->nMoves = 0;
	pNode->phase = PHASE_FIRST;
	pNode->pMove = NULL;
__jTestTT: //------------------------------------- test TT
	#if ENABLE_TT
	pNode->hash = board.GetHash();
	pNode->pTT = pEngineShare->GetTT(pNode->hash);
	if (pNode->hash == pNode->pTT->hash)
		{
			// la posizione era già nella TT
			++ttHits;
			if (pNode->pTT->type.ttReal | pNode->pTT->type.ttCurrent)
			{
				// posizione già giocata in questo ramo o in mosse precedenti la root => ripetizione
				pNode->alfavalue = valDraw;
				++ttReptHits;
				goto __jPreviousNode;
			}
			else
			{
				if (pNode->pTT->depth >= iDepth) // valore stessa precisione o maggiore
				{
					if (pNode->pTT->type.ttExact | pNode->pTT->type.ttMin)
					{
						pNode->alfavalue = pNode->pTT->alfavalue;
						goto __jPreviousNode;
					}
				}
			}
		}
		else
		{
			// la posizione non era già nella TT
			pNode->pTT->type.Clear().SetUncknown(1);
			pNode->pTT->hash = pNode->hash;
			pNode->pTT->alfavalue = -valInfinity;
			pNode->pTT->depth = -1;
		}
	#endif
__jMakeMoves: //------------------------------------- make moves
	while (!MakeMoves(pNode->phase) && pNode->phase < PHASE_LAST_QUIET) ++pNode->phase;
	if (pNode->phase <= PHASE_LAST_QUIET) goto __jExecuteMove;
__jMovesEnd:
	if (pNode->nValidMoves) goto __jPreviousNode;
	pNode->alfavalue = pNode->bIsAlreadyInCheck ? -valMate : valDraw;
	goto __jPreviousNode;
	//**************************************************************************************
__jBetaCutOff: //------------------------------------- beta cut-off
	//pNode->alfavalue = valBad;
	PopBoardState();
	// verificare e re-introdurre il concetto di "this was the best" alla radice
	(pNode-1)->pMove->boFlags |= flg_betacutoff;
__jPreviousNode: //------------------------------------- previous node
	if (pNode == pMyRootNode || (!DEBUG_ALFAGEMMA && bTimeExpired)) goto __jUnrollMoves; // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<< return
	retVal = -pNode->alfavalue;
	#if ENABLE_TT
		pNode->pTT->type.ttCurrent = 0;
	#endif
	--pNode;
	pNode->pMove->alfavalue = retVal;
__jTestMoveValue:
	//------------------------------------------- best value for this node?
	if (pNode->pMove->alfavalue <= pNode->alfavalue) goto __jUndoLastMove; // TODO save in TT?
__jNodeBestMove:
	pNode->alfavalue = pNode->pMove->alfavalue;
	//------------------------------------------- store hash
	#if ENABLE_TT
		if (!pNode->pTT->type.ttUncknown && pNode->pTT->depth <= iDepth - pNode->iDepth) goto __jTestBeta;
		pNode->pTT->type.Clear().SetMin(1);
		pNode->pTT->alfavalue = pNode->alfavalue;
		pNode->pTT->depth = iDepth - pNode->iDepth;
	#endif	
__jTestBeta:
	if ((pNode - 1)->alfavalue != -valInfinity && pNode->alfavalue >= -(pNode - 1)->alfavalue) goto __jBetaCutOff;
	if (pNode->pMove->alfavalue >= valKing) goto __jPreviousNode;
__jUndoLastMove:
	PopBoardState();
__jNextMove:
	++pNode->pMove;
__jExecuteMove:	//------------------------------------------- execute moves
	if (pNode->pMove >= (pNode + 1)->pFirstMove) { ++pNode->phase;  goto __jMakeMoves; }
	ExecuteMove(pNode->pMove);
	{
		uint64_t boTheKing = board.boBits[clsBoard::boKings] & board.boBits[clsBoard::boFriends];
		bool bIsInCheck = (pNode->bIsAlreadyInCheck ||	/* boTheKing != pNode->boMyKing || */
			(pNode->pMove->boSrc & pNode->boKingRays) != boEmpty)
			? IsInCheck(boTheKing, false)
			: false;
		if (bIsInCheck) goto __jUndoLastMove; // invalid move
	}
	DEBUG_BOARD;
__jEvaluate:	//------------------------------------------- evaluates position
	++nodescount;
	++pNode->nValidMoves;
	if (pNode->iDepth < iDepth) goto __jNextNode; // this is not the last ply
__jLastPly:
	pNode->pMove->alfavalue = board.value + Evaluate();
	goto __jTestMoveValue;
	//**************************************************************************************
__jUnrollMoves:
	#if ENABLE_TT
		for (; pNode >= pMyRootNode; --pNode) if (pNode->pTT) pNode->pTT->type.SetCurrent(0);
	#endif
__jEnd:
	pNode = pMyRootNode;
	PopBoardState();
	return pNode->alfavalue;
}