displaying the PV

[lucasart]

Hello,

I'm currently writing a chess engine. The search itself seems to work, but can't figure out how to display a PV line accurately. Typically the first few moves of it look good, and then I get some illegal moves, probably those envisaged in other variations, that have not been cleaned up.

Here's the part in the search where I modify the PV, which is stored in an array like this:

Code: Select all

struct SearchInfo {
	move_t best, current, pv;
};
SearchInfo si[MAX_PLY];

At the root level, I reset the array si, and then loop on depth 2,3,4,5... For each depth I search as follows:

Code: Select all

int search(Board &B, SearchInfo* si, bool is_pv, int alpha, int beta, int depth, int ply)
{
	(...)

	int cnt = 0;
	while &#40;alpha < beta && M.next_move&#40;si->current&#41;) &#123;
		++cnt;

		// extend&#58; check, single reply, recaptures at PV nodes
		int new_depth = M.get_count&#40;) == 1 || B.in_check&#40;)
		                || &#40;is_pv && si->current.is_recapture&#40;B&#41; && B.see&#40;si->current&#41; >= 0&#41;
		                ? depth &#58; depth-1;

		B.play&#40;si->current&#41;;

		if &#40;is_pv && cnt == 1&#41;
			// full window search
			score = new_depth > 0
			        ? -search&#40;B, si+1, true, -beta, -alpha, new_depth, ply+1&#41;
			        &#58; -qsearch&#40;B, si+1, true, -beta, -alpha, new_depth, ply+1&#41;;
		else &#123;
			// try zero window first &#40;which is the full window for non PV nodes&#41;
			score = new_depth > 0
			        ? -search&#40;B, si+1, false, -&#40;alpha+1&#41;, -alpha, new_depth, ply+1&#41;
			        &#58; -qsearch&#40;B, si+1, false, -&#40;alpha+1&#41;, -alpha, new_depth, ply+1&#41;;
			// fail high&#58; re-search full window &#40;for PV nodes only&#41;
			if &#40;score > alpha && is_pv&#41;
				score = new_depth > 0
				        ? -search&#40;B, si+1, true, -beta, -alpha, new_depth, ply+1&#41;
				        &#58; -qsearch&#40;B, si+1, true, -beta, -alpha, new_depth, ply+1&#41;;
		&#125;

		B.undo&#40;);

		if &#40;score > best_score&#41; &#123;
			best_score = score;
			si->best = si->current;
			if &#40;is_pv&#41;
				si->pv = si->best;
			if &#40;score > alpha&#41;
				alpha = score;
		&#125;
	&#125;
	
	(...)

	return best_score;
&#125;

[OliverUwira]

I think your approach does not work because as far as I understand it there is no guarantee that the moves you store are part of the same line.

The most common approach is the triangular PV array (see here: http://chessprogramming.wikispaces.com/ ... +variation).

In order to use this, you would have to make the pv member of your struct an array:

Code: Select all

struct SearchInfo {
   move_t best, current, pv[MAX_PLY];
};
SearchInfo si[MAX_PLY]; 

Then, whenever you want to update the PV, you copy the best move to si[ply].pv[ply] and copy the content of si[ply+1].pv (starting at pv[ply+1] to pv[MAX_PLY] up to si[ply].

I do this by means of this function:

Code: Select all

void UpdatePrincipalVariation(Move best, int ply, SearchTree *ptree)
{
	int i;
	Move *pvar_ply = ptree->PathNode[ply  ].PrincipalVariation;
	Move *pvar_src = ptree->PathNode[ply+1].PrincipalVariation;
	
	pvar_ply[ply] = best;
	
	for&#40;i = ply + 1; i < MAXDEPTH; i++)
	&#123;
		pvar_ply&#91;i&#93; = pvar_src&#91;i&#93;;
		if&#40;pvar_ply&#91;i&#93; == 0&#41; 
		&#123;
			return;
		&#125;
	&#125;
&#125;

This can probably done more efficiently by using memcpy, which is what you can see, e.g., in Crafty (search.c around line 480).

[lucasart]

I think your approach does not work because as far as I understand it there is no guarantee that the moves you store are part of the same line.

The most common approach is the triangular PV array (see here: http://chessprogramming.wikispaces.com/ ... +variation).

In order to use this, you would have to make the pv member of your struct an array:

Code: Select all

struct SearchInfo {
   move_t best, current, pv[MAX_PLY];
};
SearchInfo si[MAX_PLY]; 

Then, whenever you want to update the PV, you copy the best move to si[ply].pv[ply] and copy the content of si[ply+1].pv (starting at pv[ply+1] to pv[MAX_PLY] up to si[ply].

I do this by means of this function:

Code: Select all

void UpdatePrincipalVariation(Move best, int ply, SearchTree *ptree)
{
	int i;
	Move *pvar_ply = ptree->PathNode[ply  ].PrincipalVariation;
	Move *pvar_src = ptree->PathNode[ply+1].PrincipalVariation;
	
	pvar_ply[ply] = best;
	
	for&#40;i = ply + 1; i < MAXDEPTH; i++)
	&#123;
		pvar_ply&#91;i&#93; = pvar_src&#91;i&#93;;
		if&#40;pvar_ply&#91;i&#93; == 0&#41; 
		&#123;
			return;
		&#125;
	&#125;
&#125;

This can probably done more efficiently by using memcpy, which is what you can see, e.g., in Crafty (search.c around line 480).

Many thanks ! So it's a lot more complicated than I naively though

I'll have a look at the wiki to understand how it works, and code something like that.

[rbarreira]

I prefer this method, it uses a bit more memory but it's simpler (and the memory penalty is hardly relevant on today's hardware):

http://web.archive.org/web/200404270138 ... ing/pv.htm

[lucasart]

In order to use this, you would have to make the pv member of your struct an array:

Code: Select all

struct SearchInfo {
   move_t best, current, pv[MAX_PLY];
};
SearchInfo si[MAX_PLY]; 

Then, whenever you want to update the PV, you copy the best move to si[ply].pv[ply] and copy the content of si[ply+1].pv (starting at pv[ply+1] to pv[MAX_PLY] up to si[ply].

I do this by means of this function:

Code: Select all

void UpdatePrincipalVariation(Move best, int ply, SearchTree *ptree)
{
	int i;
	Move *pvar_ply = ptree->PathNode[ply  ].PrincipalVariation;
	Move *pvar_src = ptree->PathNode[ply+1].PrincipalVariation;
	
	pvar_ply[ply] = best;
	
	for&#40;i = ply + 1; i < MAXDEPTH; i++)
	&#123;
		pvar_ply&#91;i&#93; = pvar_src&#91;i&#93;;
		if&#40;pvar_ply&#91;i&#93; == 0&#41; 
		&#123;
			return;
		&#125;
	&#125;
&#125;

So if I understand your method correctly, I should do:

Code: Select all

void update_pv(move_t best, int ply, SearchInfo *si)
/* NB si is a pointer to si[ply] already, as the search calls itself with si+1 everytime */
{
	si->pv[ply] = best;
	
	for &#40;int i = ply + 1; i < MAX_PLY-1; i++) &#123;
		si->pv&#91;i&#93; = &#40;si+1&#41;->pv&#91;i&#93;;
		if &#40;si->pv&#91;i&#93; == NoMove&#41;
			break;
	&#125;
&#125;

and in my search loop, once I've found a new best move in a pv node

Code: Select all

if (score > best_score) {
	best_score = score;
	si->best = si->current;
	if (is_pv)
		update_pv(si->best, ply, si);
	if (score > alpha)
		alpha = score;
}

[Sven]

Independent from the concrete implementation the major point is that you have to maintain one PV for each ply but you will only print the PV of the root node (either at the end of each iteration only, or each time the root PV changes).

The definition of PV can be taken recursively somehow: you analyze a node X, try some move M1 there and reach node Y, get back PVy from there, and finally back up to X. If M1 is the new best move at X then the concatenation of M1 and PVy becomes the new PV of X. If X is the root node then you can print the new PV.

I prefer the implementation with the extra PV parameter but the "triangular array" approach works fine and is fully acceptable.

Sven

[OliverUwira]

In order to use this, you would have to make the pv member of your struct an array:

Code: Select all

struct SearchInfo {
   move_t best, current, pv[MAX_PLY];
};
SearchInfo si[MAX_PLY]; 

Then, whenever you want to update the PV, you copy the best move to si[ply].pv[ply] and copy the content of si[ply+1].pv (starting at pv[ply+1] to pv[MAX_PLY] up to si[ply].

I do this by means of this function:

Code: Select all

void UpdatePrincipalVariation(Move best, int ply, SearchTree *ptree)
{
	int i;
	Move *pvar_ply = ptree->PathNode[ply  ].PrincipalVariation;
	Move *pvar_src = ptree->PathNode[ply+1].PrincipalVariation;
	
	pvar_ply[ply] = best;
	
	for&#40;i = ply + 1; i < MAXDEPTH; i++)
	&#123;
		pvar_ply&#91;i&#93; = pvar_src&#91;i&#93;;
		if&#40;pvar_ply&#91;i&#93; == 0&#41; 
		&#123;
			return;
		&#125;
	&#125;
&#125;

So if I understand your method correctly, I should do:

Code: Select all

void update_pv(move_t best, int ply, SearchInfo *si)
/* NB si is a pointer to si[ply] already, as the search calls itself with si+1 everytime */
{
	si->pv[ply] = best;
	
	for &#40;int i = ply + 1; i < MAX_PLY-1; i++) &#123;
		si->pv&#91;i&#93; = &#40;si+1&#41;->pv&#91;i&#93;;
		if &#40;si->pv&#91;i&#93; == NoMove&#41;
			break;
	&#125;
&#125;

and in my search loop, once I've found a new best move in a pv node

Code: Select all

if (score > best_score) {
	best_score = score;
	si->best = si->current;
	if (is_pv)
		update_pv(si->best, ply, si);
	if (score > alpha)
		alpha = score;
}

Your code for update_pv looks correct. I'm not 100% sure about the code where it is called. At a first glance that looks correct, too.

[lucasart]

Code: Select all

struct SearchInfo {
   move_t best, current, pv[MAX_PLY];
};
SearchInfo si[MAX_PLY]; 

void UpdatePrincipalVariation(Move best, int ply, SearchTree *ptree)
{
	int i;
	Move *pvar_ply = ptree->PathNode[ply  ].PrincipalVariation;
	Move *pvar_src = ptree->PathNode[ply+1].PrincipalVariation;
	
	pvar_ply[ply] = best;
	
	for&#40;i = ply + 1; i < MAXDEPTH; i++)
	&#123;
		pvar_ply&#91;i&#93; = pvar_src&#91;i&#93;;
		if&#40;pvar_ply&#91;i&#93; == 0&#41; 
		&#123;
			return;
		&#125;
	&#125;
&#125;

void update_pv&#40;move_t best, int ply, SearchInfo *si&#41;
/* NB si is a pointer to si&#91;ply&#93; already, as the search calls itself with si+1 everytime */
&#123;
	si->pv&#91;ply&#93; = best;
	
	for &#40;int i = ply + 1; i < MAX_PLY-1; i++) &#123;
		si->pv&#91;i&#93; = &#40;si+1&#41;->pv&#91;i&#93;;
		if &#40;si->pv&#91;i&#93; == NoMove&#41;
			break;
	&#125;
&#125;

Actually it still doesn't work. I think it should be

Code: Select all

(si-1)->pv[i] = si->pv[i];

in update_pv instead of

Code: Select all

si->pv[i] = (si+1)->pv[i];

[Sven]

Actually it still doesn't work. I think it should be

Code: Select all

(si-1)->pv[i] = si->pv[i];

in update_pv instead of

Code: Select all

si->pv[i] = (si+1)->pv[i];

I don't think so, this would be one off so you would overwrite 'best' with the first PV move of the node after making 'best'. I think your previous version looks o.k. so I expect your problem is somewhere else.

What exactly does not work with your previous version?

Sven

[Sven]

Actually it still doesn't work. I think it should be

Code: Select all

(si-1)->pv[i] = si->pv[i];

in update_pv instead of

Code: Select all

si->pv[i] = (si+1)->pv[i];

I don't think so, this would be one off so you would overwrite 'best' with the first PV move of the node after making 'best'. I think your previous version looks o.k. so I expect your problem is somewhere else.

What exactly does not work with your previous version?

Sven

One more tiny thing, your loop terminates by "i < MAX_PLY - 1" but I think you can go one entry further, terminating by "i < MAX_PLY" instead since you do not access your pv[] array with index "i + 1". Here I assume that pv[] is defined with size MAX_PLY.

This does not explain the problem you mentioned, though, unless your MAX_PLY is very small.

Sven