About implementing MultiPV

[hgm]

How do you send multi PV in winboard (from a wb engine)? I could not find anything in the protocol and only some discussions related to polyglot in the WB forum

The same way as you send single PV. Just send the lines that you want the user to see. The GUI will always sort them by score in the engine-output window (within a group of the same depth). This does not affect single-PV mode, because there PVs always come in in order of ascending score anyway.

(This applies to the development version; not sure if 4.4.3 already sorts. 4.4.3 is so obsolete by now that I can hardy bear to use it, and indeed I almost never do...)

[Kempelen]

This is how I have implemented my first attempt:

At the definition file:

Code: Select all

typedef struct {
	int score;
	int pv[MAX_PLY];
	int pv_length;
} t_multipv;

At the root node function (which it receive alpha = -INFINITE and beta = INFINITE):

Code: Select all

int best_multiPV = -INFINITO;
t_multipv m_pv&#91;MAX_JUGADAS&#93;; // <- where to store all multi-pvs
// multiPV variable store max pvs


if &#40;multiPV > 1&#41;
	for &#40;int x = 0; x < MAX_JUGADAS; x ++)
		m_pv&#91;x&#93;.score = NO_SCORE;

for ( cont = 1 to totalmoves&#41; &#123;

	mov = moves&#91;cont&#93;;

	// MultiPV
	if &#40;protocolo == UCI && multiPV>1&#41; &#123;
		if &#40;cont < multiPV&#41; alpha = -INFINITO;
		else alpha = best_multiPV;
	&#125;
	
	..
	
	do_move&#40;mov&#41;;
	
	search&#40;depth -1, -beta, -alpha&#41;;
	
	undo_move&#40;);
	
	..

	if eval > alpha &#123;
		alpha = eval;
		
		...

		// Store main PV
		pv&#91;0&#93;&#91;0&#93; = mov;

		for &#40;int j = 1; j < pv_length&#91;1&#93;; ++j&#41;
			pv&#91;0&#93;&#91;j&#93; = pv&#91;1&#93;&#91;j&#93;;

		pv_length&#91;0&#93; = pv_length&#91;1&#93;;

		// Store in multi-pv table
		if &#40;multiPV > 1&#41; &#123;
			// Nos guardamos el score para este movimiento
			int x = 0;
			for &#40;x = 0; x < MAX_JUGADAS && m_pv&#91;x&#93;.score!=NO_SCORE; x++) &#123;&#125;
			m_pv&#91;x&#93;.score = eval;
			memcpy&#40;m_pv&#91;x&#93;.pv,pv&#91;0&#93;,sizeof&#40;pv&#91;0&#93;));
			m_pv&#91;x&#93;.pv_length = pv_length&#91;0&#93;;

			// Ordenamos la tabla multi_pv
			sort_m_pv&#40;);

			// Cogemos el mejor corte hasta el momento
			best_multiPV = m_pv&#91;multiPV-1&#93;.score;
		&#125;

		BOOL print_vp = FALSE;
		if &#40;multiPV <= 1&#41; print_vp = TRUE;
		else for &#40;int x = 0; x < multiPV; x++) &#123;
			if &#40;m_pv&#91;x&#93;.pv&#91;0&#93; == mov&#41; &#123;print_vp = TRUE;&#125;
		&#125;
		hash_vp&#40;);

		// En profundidad == 1 no imprimimos, porque se puede producir varias
		// variantes y preferimos solo imprimir la ultima
		if &#40;print_vp&#41;  &#123;
			show_pv&#40;); // In multiPV show k-best pv each time this function is called.
		&#125;
&#125;
...

My first tests show it run OK, but in Chessbase from time to time font lines change color from bold to light, mainly when it start a new iteration, while other engines looks like they dont have this problem. do you know why this happend? Also do you see something bad in the above code?

[michiguel]

How do you send multi PV in winboard (from a wb engine)? I could not find anything in the protocol and only some discussions related to polyglot in the WB forum

The same way as you send single PV. Just send the lines that you want the user to see. The GUI will always sort them by score in the engine-output window (within a group of the same depth). This does not affect single-PV mode, because there PVs always come in in order of ascending score anyway.

(This applies to the development version; not sure if 4.4.3 already sorts. 4.4.3 is so obsolete by now that I can hardy bear to use it, and indeed I almost never do...)

Duh!

Ok, I see. Then I just set my own option like this
feature option="Multi variation -spin 1 1 10"
So, the user can tell how many they want etc.

MultiPV is not a matter of protocol then, it is a matter of the GUI willing to deal with sorting pvs. Interesting.

Miguel

[Kempelen]

How do you send multi PV in winboard (from a wb engine)? I could not find anything in the protocol and only some discussions related to polyglot in the WB forum

The same way as you send single PV. Just send the lines that you want the user to see. The GUI will always sort them by score in the engine-output window (within a group of the same depth). This does not affect single-PV mode, because there PVs always come in in order of ascending score anyway.

(This applies to the development version; not sure if 4.4.3 already sorts. 4.4.3 is so obsolete by now that I can hardy bear to use it, and indeed I almost never do...)

Duh!

Ok, I see. Then I just set my own option like this
feature option="Multi variation -spin 1 1 10"
So, the user can tell how many they want etc.

MultiPV is not a matter of protocol then, it is a matter of the GUI willing to deal with sorting pvs. Interesting.

Miguel

... but not all GUIs do a sort based on score, I think Chessbase does sorting based on multipv index received....

[bob]

OK, one more time.

You search at depth N and find that the three best moves are A=+100, B=+50 and C=0. All other moves are < 0 and fail low.

Now you start the search at depth N and find A=100, B=30, C=0, D=150. So after a full search at N+1 you now have D, A, B as the three best moves. But unfortunately, after move D there is a move E with a score of +120. How will you ever pick that one up since it will fail low on the +150 alpha value from D? Your list ends up incomplete, and wrong...

You can't take unsafe shortcuts unless you are willing to accept the error that can produce...

You obviously set the value for the zero-window search to the lowest of the pv values, in this case 30, since this gives the answer you want, which is whether any of the remaining moves are better than any of the pv moves you have found.

A math question.

Which is preferable:

(1) searching all root moves with a normal search, to pick up the best. Then re-searching the remaining root-moves with a normal search to pick up the second-best, etc... or

(2) Searching all moves with an artificially lowered alpha value?

The answer might be surprising...

In any iteration, the first move takes the majority of the time, and the rest rip by quickly. If you lower alpha by any amount, artificially, the rest of the moves no longer "fly by".

[michiguel]

How do you send multi PV in winboard (from a wb engine)? I could not find anything in the protocol and only some discussions related to polyglot in the WB forum

The same way as you send single PV. Just send the lines that you want the user to see. The GUI will always sort them by score in the engine-output window (within a group of the same depth). This does not affect single-PV mode, because there PVs always come in in order of ascending score anyway.

(This applies to the development version; not sure if 4.4.3 already sorts. 4.4.3 is so obsolete by now that I can hardy bear to use it, and indeed I almost never do...)

Duh!

Ok, I see. Then I just set my own option like this
feature option="Multi variation -spin 1 1 10"
So, the user can tell how many they want etc.

MultiPV is not a matter of protocol then, it is a matter of the GUI willing to deal with sorting pvs. Interesting.

Miguel

... but not all GUIs do a sort based on score, I think Chessbase does sorting based on multipv index received....

Which is fine with the winboard spirit, in which the engine keeps control of what is done. The engine could presort that information and make sure there is no problem whatsoever. In fact, that is what I am going to do.

The only thing is needed is that the GUI supports the "feature option" extension of the protocol. Unfortunately, I cannot see this happening with the commercial GUIs.

Miguel

[jwes]

OK, one more time.

You search at depth N and find that the three best moves are A=+100, B=+50 and C=0. All other moves are < 0 and fail low.

Now you start the search at depth N and find A=100, B=30, C=0, D=150. So after a full search at N+1 you now have D, A, B as the three best moves. But unfortunately, after move D there is a move E with a score of +120. How will you ever pick that one up since it will fail low on the +150 alpha value from D? Your list ends up incomplete, and wrong...

You can't take unsafe shortcuts unless you are willing to accept the error that can produce...

You obviously set the value for the zero-window search to the lowest of the pv values, in this case 30, since this gives the answer you want, which is whether any of the remaining moves are better than any of the pv moves you have found.

A math question.

Which is preferable:

(1) searching all root moves with a normal search, to pick up the best. Then re-searching the remaining root-moves with a normal search to pick up the second-best, etc... or

(2) Searching all moves with an artificially lowered alpha value?

The answer might be surprising...

In any iteration, the first move takes the majority of the time, and the rest rip by quickly. If you lower alpha by any amount, artificially, the rest of the moves no longer "fly by".

It is clear that you would find the answer suprising. I have tried it and searching n open windows in 1 search is significantly faster than doing n searches, even ignoring that you feel you need to clear the hash table between searches to avoid hash inconsistencies.
Let me try to illustrate this with a very simple example: There are thirty moves, you want 3 PVs, the top three moves have a value on .8, .5. and .3, and they never change. Your method searches the first move with an open window, and 29 moves with a zero window with alpha of .8, then the second move with an open window, and 28 moves with a zero window with alpha of .5, then the third move with an open window, and 27 moves with a zero window with alpha of .2.
The other method searches the first three moves with open windows and 27 moves with a zero window with alpha of .2. The difference between the two methods is that your method unnecessarily searches 29 moves with a zero window with alpha of .8 and 28 moves with a zero window with alpha of .5

[hgm]

A math question.

...

Indeed a difficult math question. What takes more time? Searching 40 moves with open window, or searching 3...

[bob]

OK, one more time.

You search at depth N and find that the three best moves are A=+100, B=+50 and C=0. All other moves are < 0 and fail low.

Now you start the search at depth N and find A=100, B=30, C=0, D=150. So after a full search at N+1 you now have D, A, B as the three best moves. But unfortunately, after move D there is a move E with a score of +120. How will you ever pick that one up since it will fail low on the +150 alpha value from D? Your list ends up incomplete, and wrong...

You can't take unsafe shortcuts unless you are willing to accept the error that can produce...

You obviously set the value for the zero-window search to the lowest of the pv values, in this case 30, since this gives the answer you want, which is whether any of the remaining moves are better than any of the pv moves you have found.

A math question.

Which is preferable:

(1) searching all root moves with a normal search, to pick up the best. Then re-searching the remaining root-moves with a normal search to pick up the second-best, etc... or

(2) Searching all moves with an artificially lowered alpha value?

The answer might be surprising...

In any iteration, the first move takes the majority of the time, and the rest rip by quickly. If you lower alpha by any amount, artificially, the rest of the moves no longer "fly by".

It is clear that you would find the answer suprising. I have tried it and searching n open windows in 1 search is significantly faster than doing n searches, even ignoring that you feel you need to clear the hash table between searches to avoid hash inconsistencies.
Let me try to illustrate this with a very simple example: There are thirty moves, you want 3 PVs, the top three moves have a value on .8, .5. and .3, and they never change. Your method searches the first move with an open window, and 29 moves with a zero window with alpha of .8, then the second move with an open window, and 28 moves with a zero window with alpha of .5, then the third move with an open window, and 27 moves with a zero window with alpha of .2.
The other method searches the first three moves with open windows and 27 moves with a zero window with alpha of .2. The difference between the two methods is that your method unnecessarily searches 29 moves with a zero window with alpha of .8 and 28 moves with a zero window with alpha of .5

Funny, because I just finished some experiments with the "annotate" code in Crafty, which does exactly what I explained. I tried several alternative approaches, and overall, the current approach was faster. Not in every position, to be sure. But _overall_. And it would be easy for anyone to run a similar test since the annotate.c code is pretty short, and what is going on is well-documented. As far as clearing the hash, why? Too many other things get changed anyway to expect perfect consistency.

BTW, exactly how do you guarantee that you only search the first 3 moves with an open window, and all the rest with null? Is your root move ordering perfect? What if the 3rd best move is the last one? It's not quite so simple.

[bob]

A math question.

...

Indeed a difficult math question. What takes more time? Searching 40 moves with open window, or searching 3...

Not searching 40 with an open window here, so don't care, although the answer is obvious.

BTW you will _never_ search just 3 moves with open window to find the best 3, unless you have perfect root move ordering. So the real question here is, given a set of (say) 40 moves, what is the most efficient way to find the best three moves, when they might be in any of the 40 positions in the move list?

If you search the first, then artificially lower alpha so that you can discover the second, how much do you lower alpha? What if none trip that bound? Lower again? What if you lower it too far so that every move will trip it and fail high? Both of the approaches (one originally posted, the one I use in Crafty's annotate command) have some issues.

I like the idea of searching for the best, removing it, searching for the best, letting the hash table help with search efficiency. Older versions of annotate.c completely cleared the hash table between picking out each move as keeping it leads to some interesting conditions, where (say) the second move comes back with a better score than the best move, because of grafting. I decided that this was a bad idea and removed the clearing code with the proviso that the moves are in order of 1st to nth, even if the scores might not be in descending order. Scores are not exactly precise things in today's programs anyway.