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.
Ryan Benitez
Posts: 719
Joined: Thu Mar 09, 2006 12:21 am
Location: Portland Oregon

Re: Stockfish search

Post by Ryan Benitez » Wed Oct 30, 2013 11:46 pm

Milos wrote:
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.
I think you mistake the goal of the Stockfish team. They clearly are making an engine for computer vs computer play strength and they have nothing to be embarrassed about. It would however be simple to write a game analysis mode option for Stockfish and within the spirit of the GPL for someone to do so. I nominate you since it sounds like an option you would use.

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

Re: Stockfish search

Post by Milos » Thu Oct 31, 2013 12:04 am

Ryan Benitez wrote:I think you mistake the goal of the Stockfish team. They clearly are making an engine for computer vs computer play strength and they have nothing to be embarrassed about. It would however be simple to write a game analysis mode option for Stockfish and within the spirit of the GPL for someone to do so. I nominate you since it sounds like an option you would use.
Turning SF into useful analysis tool requires much more than just clean PV return, inflated scores, score instability, seeing ghosts, often crazy prunning with depth inflation, unreleliable behavior in endings, it's simply not worth the effort when there are other engines much better for analysis either comercial or open source.

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

Re: Stockfish search

Post by bob » Thu Oct 31, 2013 12:27 am

Tord Romstad wrote:
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.
When you say simpler and shorter, this REALLY is a tiny piece of code...

In q-search, one does this at the top, with 3 lines of code, at the bottom with 3 lines of code, and inside search at the bottom where you return an actual best move with score > alpha and score < beta, another 2 lines of code. The code has no conditionals, just direct assignments, so I don't see where it is more complicated than running through the hash table, making moves and doing lookups... Maybe I am missing something.

Ryan Benitez
Posts: 719
Joined: Thu Mar 09, 2006 12:21 am
Location: Portland Oregon

Re: Stockfish search

Post by Ryan Benitez » Thu Oct 31, 2013 1:00 am

Milos wrote: Turning SF into useful analysis tool requires much more than just clean PV return
Maybe
Milos wrote: inflated scores, score instability, seeing ghosts
Taking out the limited search window may help. It can be a new UCI option.
Milos wrote: often crazy prunning with depth inflation, unreleliable behavior in endings
The comments in the source code almost walk you though fixing this. I vote for another UCI option to include the style pruning you prefer.
Milos wrote: it's simply not worth the effort when there are other engines much better for analysis either comercial or open source.
Use the right tool for the job I guess. I can't get the wheel off of my car with a screwdriver but I do not deny that it is a useful tool. The GPL does give you options with Stockfish however.

IQ
Posts: 161
Joined: Thu Dec 17, 2009 9:46 am

Re: Stockfish search

Post by IQ » Thu Oct 31, 2013 5:10 am

In this case I tend to agree with bob and I don't quite buy the "easier to read and reason about the code" part. In this case this would be a completely modular piece of code with minimal impact on other parts. With a well placed comment it should not confuse anybody, not even amateurs.

Especially as the benefits for debugging totally outweigh the cost. This in itself is a huge "simplification", just of another kind. And it also enhances readability of the programs output - another form of readability and enhanced functionality for analysis.

In this case the old proverb might apply: "As simple as possible, but as complex as needed"
Tord Romstad wrote:
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.

mcostalba
Posts: 2684
Joined: Sat Jun 14, 2008 7:17 pm

Re: Stockfish search

Post by mcostalba » Thu Oct 31, 2013 5:53 am

IQ wrote: In this case the old proverb might apply: "As simple as possible, but as complex as needed"
It is not with proverbs that SF development will be influenced.

I reply to you but is a reply for also many other posts. As an open sorce project everybody is free to submit his patches for review.

OTH this has consequences because argumentations like:

- feature requests
- wishes
- I think that...
- If you don't do this SF will remain a crap
- If you don't do this you are a bunch of morons
- etc.

Will have (near) zero probability to be evaluated. So you may think that this moves the bias in the SF development to favour developers willing to put their typing fingers where mouth is...yes you are right. It is exactly this.

Code talks words walk.

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

Re: Stockfish search

Post by Uri Blass » Thu Oct 31, 2013 6:36 am

Milos wrote:
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.
If there are significant number of positions when stockfish suggest better moves than other engines then stockfish clearly help in analysis even if it is gives only the first pv move.

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

Re: Stockfish search

Post by hgm » Thu Oct 31, 2013 8:36 am

Whether it is better for Stockfish to get PV from hash or from a tri-angular array is an interesting discussion, but it does not resolve my astonishment. Even if Stockfish extracts the PV from the hash table, how can it extract a move from a node that failed low? Does Stockfish also store hash moves in upper-bound entries? If so, how does it decide which move to put there? The one with the highest upper bound?

Basically these are just random moves. Why print them in a PV? The routine that extracts the PV from the hash should certainly be able to detect if it hits on an upper-bound entry, and stop printing at that point rather than print a nonsense move.

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

Re: Stockfish search

Post by Tord Romstad » Thu Oct 31, 2013 9:57 am

Milos wrote:Returning PV from hash is pretty embarassing for top engine pretending to be useful for analysis.
Hardly unique for Stockfish, though. I know some (all?) Rybka versions also build PVs from the transposition table, and I'm sure there are others. Most users put way too much emphasis on the PV, and particularly the final position of the PV anyway. The last few moves of a PV (the ones where a real PV and a transposition table PV differ) are very low quality, and the position at the end of the PV will never appear on the board. And it's just a single line out of a giant search tree, and except in exceptional position with a clear forced win, you can't understand the analysis without playing out the suggested moves and experimenting with alternatives along the way.
Thanks to this and rediculously scaled scores
I've never understood this argument. There is no God-given evaluation scale, and the only objectively correct evaluation function is a function that returns -infinity, 0 or +infinity, depending on whether the position on the board is lost, drawn or won. In practice, it usually isn't possible to determine the game theoretical value of a position, so the evaluation function just assigns higher numbers to positions where we believe we have a better chance of scoring a good result. The scale is completely arbitrary, as long as it's reasonably internally consistent.

The numbers that are printed in the analysis are different from the internal scores, and they are, as you say, scaled. The UCI protocol asks for the score to be displayed as "centipawns", so we divide the internal score by the base value of a middle game pawn before sending it to the user interface. Dividing it by some arbitrary other constant because some users like to see bigger or smaller numbers makes no sense. Anyone is free to mentally multiply the scores by whatever number they want anyway.
(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.
Actually, there are top 10 GMs who consider SF very valuable for analysis.

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

Re: Stockfish search

Post by Tord Romstad » Thu Oct 31, 2013 10:02 am

bob wrote:When you say simpler and shorter, this REALLY is a tiny piece of code...

In q-search, one does this at the top, with 3 lines of code, at the bottom with 3 lines of code, and inside search at the bottom where you return an actual best move with score > alpha and score < beta, another 2 lines of code. The code has no conditionals, just direct assignments, so I don't see where it is more complicated than running through the hash table, making moves and doing lookups... Maybe I am missing something.
There is also one more data structure, and more data to copy between threads at split points. I agree that it's not something super complicated by itself, but like I said, taken together with various other kind of nice, but not strictly necessary pieces of code, getting rid of it all makes the program easier to manage for people like myself.

Post Reply