Newbie's question about printing the PV

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
maksimKorzh
Posts: 52
Joined: Sat Sep 08, 2018 3:37 pm
Location: Ukraine
Full name: Maksim Korzh
Contact:

Newbie's question about printing the PV

Post by maksimKorzh » Tue Sep 11, 2018 9:33 am

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
Posts: 732
Joined: Sun May 23, 2010 11:32 am
Contact:

Re: Newbie's question about printing the PV

Post by elcabesa » Tue Sep 11, 2018 10:19 am

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

If you still have problem please ask

Sesse
Posts: 142
Joined: Mon Apr 30, 2018 9:51 pm
Contact:

Re: Newbie's question about printing the PV

Post by Sesse » Tue Sep 11, 2018 10:22 am

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).

User avatar
xr_a_y
Posts: 234
Joined: Sat Nov 25, 2017 1:28 pm
Location: France

Re: Newbie's question about printing the PV

Post by xr_a_y » Tue Sep 11, 2018 11:32 am


User avatar
hgm
Posts: 22582
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Newbie's question about printing the PV

Post by hgm » Tue Sep 11, 2018 3:13 pm

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
Posts: 52
Joined: Sat Sep 08, 2018 3:37 pm
Location: Ukraine
Full name: Maksim Korzh
Contact:

Re: Newbie's question about printing the PV

Post by maksimKorzh » Tue Sep 11, 2018 4:09 pm

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

User avatar
hgm
Posts: 22582
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Newbie's question about printing the PV

Post by hgm » Tue Sep 11, 2018 6:25 pm

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
Posts: 52
Joined: Sat Sep 08, 2018 3:37 pm
Location: Ukraine
Full name: Maksim Korzh
Contact:

Re: Newbie's question about printing the PV

Post by maksimKorzh » Sat Sep 15, 2018 6:24 pm

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
Posts: 52
Joined: Sat Sep 08, 2018 3:37 pm
Location: Ukraine
Full name: Maksim Korzh
Contact:

Re: Newbie's question about printing the PV

Post by maksimKorzh » Sat Sep 15, 2018 6:55 pm

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
Posts: 732
Joined: Sun May 23, 2010 11:32 am
Contact:

Re: Newbie's question about printing the PV

Post by elcabesa » Sat Sep 15, 2018 9:35 pm

in your code you didn't define pvstart

Post Reply