Newbie's question about printing the PV

[maksimKorzh]

Currently my engine has a very basic alpha beta pruning and no move ordering for now. For now I want to avoid using of PV-table and simply try to print to the screen the PV-move of each ply, but I'm stuck. Could you please help me finding the right approach? This is my code:

Code: Select all

static inline int NegaMaxSearch(int alpha, int beta, CHESSBOARD *board, SEARCH *info, int depth)
{
	int legalMoves = 0;
	int bestScore = -50000;
	int bestMove = 0;
	int bestLast = 0;
	
	if(info->bestMove)
		bestLast = info->bestMove;
	
	if(InCheck(board, side))
		depth++;

	if(!depth)
	{
		info->nodes++;
		return QuiescenceSearch(alpha, beta, board, info, 4);
	}
	
	MOVELIST list[1];
	GenerateMoves(board, list);
	
	for(int moveNum = 0; moveNum < list->moveCount; ++moveNum)
	{
		CHESSBOARD boardStored[1];
		boardStored[0] = board[0];
		
		if(!MakeMove(board, list->moves[moveNum].move, all))
			continue;
		
		legalMoves++;
		int score = -NegaMaxSearch(-beta, -alpha, board, info, depth - 1);
		
		if(score > bestScore)
		{
			bestScore = score;
			bestMove = list->moves[moveNum].move;
			
			info->bestScore = bestScore;
			info->bestMove = bestMove;
			
			if(score >= beta)
				return beta;
				
			if(score > alpha)
				alpha = score;
		}
		
		TakeBack(board, boardStored);	
	}
	
	// checkmate/stalemate detection
	if(!legalMoves)
	{
		if(InCheck(board, side))
			return -100000; // on checkmate
			
		else
			return 0; // on stalemate
	}
	
	if(bestMove)
	{
		info->bestScore = bestScore;
		info->bestMove = bestMove;
	}
	
	return alpha;
}


static inline void SearchPosition(CHESSBOARD *board, SEARCH *info, int depth)
{
	for(int currentDepth = 1; currentDepth <= depth; currentDepth++)
	{
		NegaMaxSearch(-50000, 50000, board, info, currentDepth);
		printf("info score cp %d depth %d nodes %ld\n", info->bestScore, currentDepth, info->nodes);
	}
	
	if(info->bestMove)
	{
		printf("bestmove ");
		PrintMove(info->bestMove);
		printf("\n");
	}
}

I understand how to collect the best move of each given depth, but how to associate with the ply? How to get the output like this:
white: bestmove e2e4
black: bestmove e7e5
and so on until reach the given depth?

I've spent more then 12 hours researching this subject but feel completely lost due to the lack of basis. Thanks in advance!

[elcabesa]

The algorithm to use is called "triangular pv table".
Try searching the forum and Google.

If you still have problem please ask

[Sesse]

You can also pick the best move out of the transposition hash, recursively. However, you do risk that it has been overwritten (and if so, the PV gets cut short).

[xr_a_y]

You can also have a look here : http://vajoletchess.blogspot.com/2013/1 ... HJ0tvrDQ7r

[hgm]

I usually do it like this:

Code: Select all

Move pvStack[10000];
Move *pvPtr = pvStack;

int Search()
{
  Move *pvStart = pvPtr; // start of own PV
  *pvStart = 0; // initialize empty PV at the top of the PV stack
  
  
  // where you increase alpha because of a better move:
  pvPtr = pvStart + 1;
  while((*pvStart++ = *pvPtr++)) ; // copy PV of daughter, including the terminating 0
  *pvStart = move; // the move we just searched is now the first of the new PV
  
  // when returning
  pvPtr = pvStart; // pop PV (but leave data in place, so daughter can pick it up)
}

[maksimKorzh]

That's exactly what I was asking for, thanks a lot again! Just great!

[hgm]

Beware, though: if you have multiple places from which the routine can return, you have to make sure that it will always leave pvPtr as it found it. Usually there is other stuff to restore (like popping the move stack), and I put all that at the end of the routine, and then use a goto to that block of code. I don't think a goto is worse than a return somewhere in the middle of your routine.

[maksimKorzh]

mr. H.G.Muller, I've implemented mvv_lva, killer and history heuristics and now Chenglite become pretty stronger compare to no move ordering. I've also implemented your method of collecting PV, but the question is how to actually retrieve the line back from pvStack[10000] array. I tried to loop through array and print move if pvStack != 0 but it doesn't seem to be a PV - in initial position depth 4:

Code: Select all

for(int i =0; i < 10000; ++i)
{
	if(pvStack[i])
	{
		PrintMove(pvStack[i]);
	}
}

the output is: d2d4 d7d5 d2d4 f1b5 c8d7 d7d5 d7d5 f4e5 e7e5 c8h3 c8h3 c8h3 c8h3 c8h3 c8h3 c8h3 c8h3 c8h3 c8h3 c8h3 c8h3 c8h3 c8h3 c8h3 c8h3 c8h3 c8g4

please explain this point in more details, thanks in advance.




-----------------------------------------------------------------------------------
Maksim Korzh
Chenglite
https://github.com/maksimKorzh/Chenglite

[maksimKorzh]

Here is the code:

Code: Select all

int pvStack[10000];
int *pvPtr = pvStack;

static int NegaMaxSearch(int alpha, int beta, CHESSBOARD *board, SEARCH *info, int depth)
{
	...
	
	for(int moveNum = 0; moveNum < list->moveCount; ++moveNum)
	{
		...
		
		if(score >= beta)
		{
			...

			return beta; // fail hard beta-cutoff
		}
			
		if(score > alpha)
		{
			alpha = score;			
			...
				
			pvPtr = pvStart + 1;
			
			while((*pvStart++ = *pvPtr++)) ; // copy PV of daughter, including the terminating 0
				*pvStart = list->moves[moveNum].move; // the move we just searched is now the first of the new PV
		}
	}
		
	...
	
	pvPtr = pvStart; // pop PV (but leave data in place, so daughter can pick it up)
	
	return alpha;
}

Code: Select all

for(int i =0; i < 10000; ++i)
{
	if(pvStack[i])
	{
		PrintMove(pvStack[i]);
	}
}

the output is: d2d4 d7d5 d2d4 f1b5 c8d7 d7d5 d7d5 f4e5 e7e5 c8h3 c8h3 c8h3 c8h3 c8h3 c8h3 c8h3 c8h3 c8h3 c8h3 c8h3 c8h3 c8h3 c8h3 c8h3 c8h3 c8h3 c8g4

[elcabesa]

in your code you didn't define pvstart