Stockfish search

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
hgm
Posts: 23791
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Stockfish search

Post by hgm » Mon Oct 28, 2013 11:00 am

I was wondering about the Stockfish search. In positions where it seems to be losing, it produces a large number of PVs, all the same depth, with consecutively lower scores. How can it get a different score for the same move? Are these all fail lows? If so, how can it have a PV at all, on a fail low?

Or is this a Polyglot bug? (Hard to imagine, Polyglot should not be able dream up PVs out of nowhere, and the later PV moves are different...)

Code: Select all

 25	+9.30	670.8M	4:44.12	Qg7 Ne6 Qf1+ Ndf4 Qe7 Nd3 Kb1 N7c5 Qa8 e3 Qa2 Kg6 Qa1 e2
 25	+9.30	628.7M	4:25.86	Qg7 Ne6 Qf1+ Ndf4 Qe7 Nd3 Kb1 N7c5 Qa8 e3 Qa2 Kg6 Qa1 e2
 25	+10.22	474.1M	3:19.44	Qg7 Ne6 Qf1+ Ndf4 Qe7 Nd3 Kb1 N7c5 Qa8 e3 Qf7 e2
 25	+10.83	364.4M	2:32.92	Qg7 Ne6 Qf1+ Ndf4 Qe7 Nd3 Kb1 N7c5 Qa8 e3 Qaf3 Kg5 Qd6 e2
 25	+11.24	308.7M	2:09.67	Qg7 Ne6 Qf1+ Ndf4 Qe7 Nd3 Kb1 N7c5 Qa8 e3 Qaf3 Kg5 Qg1 Kf5 Ka2 e2
 25	+11.51	261.7M	1:50.04	Qg7 Ne6 Qf1+ Ndf4 Qe7 Nd3 Kb1 N7c5 Qa8 e3 Qaf3 Kg5 Qg1 Kf5 Ka2 e2
 25	+11.69	208.7M	1:28.17	Qg7 Ne6 Qf1+ Ndf4 Qe7 Nd3 Kb1 N7c5 Qa8 e3 Qaf3 Kg5 Qg1 Kf5 Ka2 e2
 25	+11.81	173.5M	1:13.50	Qg7 Ne6 Qf1+ Ndf4 Qe7 Nd3 Qb5+ N7c5 Qa5 e3 Qf7 e2
 25	+11.97	85.8M	0:35.40	Qg7 N7b6 Qf8 Ned3 Qa7 e3 Qh7+ Ke5 Qb8+ Ke6 Q8xb6+ Nxb6
 24	+11.89	77.3M	0:31.50	Qg7 N7b6 Qf8 Ned3 Qa7 e3 Qh7+ 

Uri Blass
Posts: 8611
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: Stockfish search

Post by Uri Blass » Mon Oct 28, 2013 12:56 pm

I know that stockfish has pv from the hash and the pv is not reliable so maybe the pv in fail low is based on the move that stockfish has in the hash in previous search.

User avatar
Eelco de Groot
Posts: 4172
Joined: Sun Mar 12, 2006 1:40 am
Location: Groningen

Re: Stockfish search

Post by Eelco de Groot » Wed Oct 30, 2013 4:31 pm

Only the last PV in an iteration is real, the others are Fail Lows or occasional Fail Highs (with a very narrow search window). In the UCI output I think these get a tag according to the UCI protocol:

Code: Select all

* score
		* cp <x>
			the score from the engine's point of view in centipawns.
		* mate <y>
			mate in y moves, not plies.
			If the engine is getting mated use negative values for y.
		* lowerbound
	      the score is just a lower bound.
		* upperbound
		   the score is just an upper bound.

I have not checked the actual Stockfish code, but Fail Lows and Highs are always marked in an interface like Shredder or I think Fritz too.

The PV does not only include exact bounds, because they are coming from the hash without "triangulating" and would otherwise often be cut very short. So in this case they will include the Fail Low moves and the Fail Low/Fail High lines will therefore make little sense.
Debugging is twice as hard as writing the code in the first
place. Therefore, if you write the code as cleverly as possible, you
are, by definition, not smart enough to debug it.
-- Brian W. Kernighan

bob
Posts: 20642
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Stockfish search

Post by bob » Wed Oct 30, 2013 5:07 pm

Eelco de Groot wrote:Only the last PV in an iteration is real, the others are Fail Lows or occasional Fail Highs (with a very narrow search window). In the UCI output I think these get a tag according to the UCI protocol:

Code: Select all

* score
		* cp <x>
			the score from the engine's point of view in centipawns.
		* mate <y>
			mate in y moves, not plies.
			If the engine is getting mated use negative values for y.
		* lowerbound
	      the score is just a lower bound.
		* upperbound
		   the score is just an upper bound.

I have not checked the actual Stockfish code, but Fail Lows and Highs are always marked in an interface like Shredder or I think Fritz too.

The PV does not only include exact bounds, because they are coming from the hash without "triangulating" and would otherwise often be cut very short. So in this case they will include the Fail Low moves and the Fail Low/Fail High lines will therefore make little sense.
How do you get a "fail low" move in a PV???

gladius
Posts: 538
Joined: Tue Dec 12, 2006 9:10 am

Re: Stockfish search

Post by gladius » Wed Oct 30, 2013 6:07 pm

bob wrote:How do you get a "fail low" move in a PV???
It's a fail low on the aspiration window. PV is extracted from the hashtable, so it can be wildly inaccurate :).

User avatar
Eelco de Groot
Posts: 4172
Joined: Sun Mar 12, 2006 1:40 am
Location: Groningen

Re: Stockfish search

Post by Eelco de Groot » Wed Oct 30, 2013 6:13 pm

bob wrote:
Eelco de Groot wrote:Only the last PV in an iteration is real, the others are Fail Lows or occasional Fail Highs (with a very narrow search window). In the UCI output I think these get a tag according to the UCI protocol:

Code: Select all

* score
		* cp <x>
			the score from the engine's point of view in centipawns.
		* mate <y>
			mate in y moves, not plies.
			If the engine is getting mated use negative values for y.
		* lowerbound
	      the score is just a lower bound.
		* upperbound
		   the score is just an upper bound.

I have not checked the actual Stockfish code, but Fail Lows and Highs are always marked in an interface like Shredder or I think Fritz too.

The PV does not only include exact bounds, because they are coming from the hash without "triangulating" and would otherwise often be cut very short. So in this case they will include the Fail Low moves and the Fail Low/Fail High lines will therefore make little sense.
How do you get a "fail low" move in a PV???
You are of course right Bob. That would make no sense. Only in the Fail Low lines that Harm was pointing out, opponent Fail High moves can be seen as "Fail Low moves". In Fail Low nodes you do not store a move, Stockfish also does not. to be honest I don't really know what move Stockfish picks in an ALL node that is not a PV node, for the lines given.

I would like to make such a more accurate PV myself, but have never studied how that is done. It did not seem easy to do to me. I think it would help greatly though for anyone wishing to use a program like Stockfish, for correspondence chess, or for study of chess, for chess studies etcetera. Lucas Braesch has posted some pointers on how it should be done in the Googlegroup, some time ago. And I think it was discussed several times in this forum.
Debugging is twice as hard as writing the code in the first
place. Therefore, if you write the code as cleverly as possible, you
are, by definition, not smart enough to debug it.
-- Brian W. Kernighan

bob
Posts: 20642
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Stockfish search

Post by bob » Wed Oct 30, 2013 8:06 pm

gladius wrote:
bob wrote:How do you get a "fail low" move in a PV???
It's a fail low on the aspiration window. PV is extracted from the hashtable, so it can be wildly inaccurate :).
PV can be wildly inaccurate on a fail low, a fail high, or a true score, if you retrieve it from the hash table. :)

bob
Posts: 20642
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Stockfish search

Post by bob » Wed Oct 30, 2013 8:10 pm

Eelco de Groot wrote:
bob wrote:
Eelco de Groot wrote:Only the last PV in an iteration is real, the others are Fail Lows or occasional Fail Highs (with a very narrow search window). In the UCI output I think these get a tag according to the UCI protocol:

Code: Select all

* score
		* cp <x>
			the score from the engine's point of view in centipawns.
		* mate <y>
			mate in y moves, not plies.
			If the engine is getting mated use negative values for y.
		* lowerbound
	      the score is just a lower bound.
		* upperbound
		   the score is just an upper bound.

I have not checked the actual Stockfish code, but Fail Lows and Highs are always marked in an interface like Shredder or I think Fritz too.

The PV does not only include exact bounds, because they are coming from the hash without "triangulating" and would otherwise often be cut very short. So in this case they will include the Fail Low moves and the Fail Low/Fail High lines will therefore make little sense.
How do you get a "fail low" move in a PV???
You are of course right Bob. That would make no sense. Only in the Fail Low lines that Harm was pointing out, opponent Fail High moves can be seen as "Fail Low moves". In Fail Low nodes you do not store a move, Stockfish also does not. to be honest I don't really know what move Stockfish picks in an ALL node that is not a PV node, for the lines given.

I would like to make such a more accurate PV myself, but have never studied how that is done. It did not seem easy to do to me. I think it would help greatly though for anyone wishing to use a program like Stockfish, for correspondence chess, or for study of chess, for chess studies etcetera. Lucas Braesch has posted some pointers on how it should be done in the Googlegroup, some time ago. And I think it was discussed several times in this forum.
I think the answer is to do what I do, a modification of what many others have been doing for 40 years, the "triangular array". It returns an accurate PV from the root to the actual terminal position that provides the backed-up score. Some refuse to allow EXACT hash matches in PV nodes to avoid short PVs. This too can be easily solved, as is done in Crafty, so you STILL get an accurate PV from the root to the position that actually produced the terminal score that was backed up.

I don't see any reason to do otherwise, there is no overhead that is measurable in the triangular array approach, and it is a WONDERFUL debugging tool to actually be able to see the position that produced the score...

Tord Romstad
Posts: 1808
Joined: Wed Mar 08, 2006 8:19 pm
Location: Oslo, Norway

Re: Stockfish search

Post by Tord Romstad » Wed Oct 30, 2013 10:09 pm

bob wrote:I don't see any reason to do otherwise, there is no overhead that is measurable in the triangular array approach, and it is a WONDERFUL debugging tool to actually be able to see the position that produced the score...
Actually, we did use a triangular PV array initially, but got rid of it in order to make the program slightly simpler and shorter. This may not seem like a major simplification, but by eliminating all sorts of stuff like this, it adds up to something non-trivial. Making the program simpler and more compact makes it easier to read and reason about the code, especially for amateurs like myself.

It's a trade-off between simplicity and accuracy. In principle I agree with you that an accurate PV would be nicer, but at least to me, it's not quite worth it, although it is close.

Milos
Posts: 3387
Joined: Wed Nov 25, 2009 12:47 am

Re: Stockfish search

Post by Milos » Wed Oct 30, 2013 11:36 pm

bob wrote:
gladius wrote:
bob wrote:How do you get a "fail low" move in a PV???
It's a fail low on the aspiration window. PV is extracted from the hashtable, so it can be wildly inaccurate :).
PV can be wildly inaccurate on a fail low, a fail high, or a true score, if you retrieve it from the hash table. :)
Returning PV from hash is pretty embarassing for top engine pretending to be useful for analysis.
Thanks to this and rediculously scaled scores (and couple of other things like search rediculosuly prunning and reaching depth of 100 in relatively standard endings) SF will never be accepted as a serious analysis tool.

Post Reply