Implications of Lazy eval on Don Beal effect in Fail Soft

Discussion of chess software programming and technical issues.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Henk
Posts: 6998
Joined: Mon May 27, 2013 8:31 am

Implications of Lazy eval on Don Beal effect in Fail Soft

Post by Henk » Wed Nov 19, 2014 12:49 pm

I use fail soft in my engine. If I would interpret my evaluation as material + random value then I think applying lazy evaluation would be bad for playing strength. It would exclude the random value in some nodes and would reduce the Don Beal effect.

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

Re: Implications of Lazy eval on Don Beal effect in Fail Sof

Post by bob » Wed Nov 19, 2014 2:20 pm

Henk wrote:I use fail soft in my engine. If I would interpret my evaluation as material + random value then I think applying lazy evaluation would be bad for playing strength. It would exclude the random value in some nodes and would reduce the Don Beal effect.
Not enough to worry about. In fact, the beal effect does not even need the material score, just a purely random evaluation.

Joost Buijs
Posts: 1357
Joined: Thu Jul 16, 2009 8:47 am
Location: Almere, The Netherlands

Re: Implications of Lazy eval on Don Beal effect in Fail Sof

Post by Joost Buijs » Wed Nov 19, 2014 3:24 pm

Henk wrote:I use fail soft in my engine. If I would interpret my evaluation as material + random value then I think applying lazy evaluation would be bad for playing strength. It would exclude the random value in some nodes and would reduce the Don Beal effect.
Maybe the best is to avoid lazy evaluation all together, you gain maybe 10% in speed but you will introduce a lot of error.
In positions with heavy king attacks and/or passed pawns the positional evaluation can get a very high value, that is where you will introduce the most errors with lazy evaluation.
When you use your evaluation function to make decisions about pruning lazy evaluation can completely break things.

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

Re: Implications of Lazy eval on Don Beal effect in Fail Sof

Post by bob » Wed Nov 19, 2014 4:56 pm

Joost Buijs wrote:
Henk wrote:I use fail soft in my engine. If I would interpret my evaluation as material + random value then I think applying lazy evaluation would be bad for playing strength. It would exclude the random value in some nodes and would reduce the Don Beal effect.
Maybe the best is to avoid lazy evaluation all together, you gain maybe 10% in speed but you will introduce a lot of error.
In positions with heavy king attacks and/or passed pawns the positional evaluation can get a very high value, that is where you will introduce the most errors with lazy evaluation.
When you use your evaluation function to make decisions about pruning lazy evaluation can completely break things.
Actually it is possible to do an error-free lazy evaluation. Bruce Moreland did this in his program "Ferret". For each piece, compute the largest/smallest positional scores. Then when you do a lazy cutoff, you know absolutely whether a piece or group of pieces can get you back inside the window or not with zero error...

Or you can have an adjustable bound that is larger when king safety is problematic, smaller when not. Larger with passed pawns present, smaller if not. Etc.

Henk
Posts: 6998
Joined: Mon May 27, 2013 8:31 am

Re: Implications of Lazy eval on Don Beal effect in Fail Sof

Post by Henk » Wed Nov 19, 2014 5:01 pm

Joost Buijs wrote:
Henk wrote:I use fail soft in my engine. If I would interpret my evaluation as material + random value then I think applying lazy evaluation would be bad for playing strength. It would exclude the random value in some nodes and would reduce the Don Beal effect.
Maybe the best is to avoid lazy evaluation all together, you gain maybe 10% in speed but you will introduce a lot of error.
In positions with heavy king attacks and/or passed pawns the positional evaluation can get a very high value, that is where you will introduce the most errors with lazy evaluation.
When you use your evaluation function to make decisions about pruning lazy evaluation can completely break things.
Even in this simple case Material + random. Lazy evaluation (Material >= beta) performs significantly worse in my chess program. Don't know why. But computing a random value doesn't cost much cpu time.

AlvaroBegue
Posts: 930
Joined: Tue Mar 09, 2010 2:46 pm
Location: New York
Full name: Álvaro Begué (RuyDos)

Re: Implications of Lazy eval on Don Beal effect in Fail Sof

Post by AlvaroBegue » Wed Nov 19, 2014 8:35 pm

That's not how you do lazy evaluation. If your partial score is more than beta or less than alpha by some margin, then you can return early.

Henk
Posts: 6998
Joined: Mon May 27, 2013 8:31 am

Re: Implications of Lazy eval on Don Beal effect in Fail Sof

Post by Henk » Wed Nov 19, 2014 9:15 pm

AlvaroBegue wrote:That's not how you do lazy evaluation. If your partial score is more than beta or less than alpha by some margin, then you can return early.
[Random value that I used is always greater than zero.]
I don't understand why compare with alpha for the side to move may also capture a piece and then there is no difference with futility pruning.

User avatar
Evert
Posts: 2929
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: Implications of Lazy eval on Don Beal effect in Fail Sof

Post by Evert » Wed Nov 19, 2014 9:33 pm

The idea of lazy evaluation is that if you know, say after material evaluation, that 1) the score is below alpha (or above beta) and 2) the remaining evaluation terms, say mobility and king safety, cannot change the score sufficiently to bring it above alpha (or below beta), then you can simply return the score as-is. It's like taking an alpha-beta cut-off.

This is a totally safe form of lazy evaluation in the sense that you never take a cut-off that you shouldn't (but in a fail-soft framework, it can and will still change the bounds for a position in the TT). You can use an un-safe version that uses some margin that you can tune. It ends up saving more time, but at the cost of eroding the accuracy of the evaluation. Testing tells you which is more important.

AlvaroBegue
Posts: 930
Joined: Tue Mar 09, 2010 2:46 pm
Location: New York
Full name: Álvaro Begué (RuyDos)

Re: Implications of Lazy eval on Don Beal effect in Fail Sof

Post by AlvaroBegue » Wed Nov 19, 2014 9:36 pm

Henk wrote:
AlvaroBegue wrote:That's not how you do lazy evaluation. If your partial score is more than beta or less than alpha by some margin, then you can return early.
[Random value that I used is always greater than zero.]
When one adds a random value, it is usually symmetric around 0. Otherwise you are basically adding a bonus for the side to move and a symmetric random value on top of it.

I don't understand why compare with alpha for the side to move may also capture a piece and then there is no difference with futility pruning.
I am not sure what you are saying. The general idea of alpha-beta is that we only need an exact score if the minimax value of a node is between alpha and beta; otherwise you just need to know that its <=alpha or >=beta. This applies to the leaves as well, so you can return some cheap evaluation if you can prove the final evaluation is outside of the (alpha,beta) window. This probably doesn't play well with fail-soft schemes, but thinking about those things makes my brain hurt. :)

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

Re: Implications of Lazy eval on Don Beal effect in Fail Sof

Post by bob » Thu Nov 20, 2014 1:51 am

Henk wrote:
AlvaroBegue wrote:That's not how you do lazy evaluation. If your partial score is more than beta or less than alpha by some margin, then you can return early.
[Random value that I used is always greater than zero.]
I don't understand why compare with alpha for the side to move may also capture a piece and then there is no difference with futility pruning.
The question you want to ask is "If I do a full evaluation, will the score end up inside the current alpha/beta window? If not, there is no need in doing the full evaluation. The typical test is something like this, in simple terms:

if (partial_score + fudge_factor < alpha)
return alpha;
if (partial_score - fudge_factor > beta)
return beta;

fudge factor is some number that represents what you think is the biggest (or smallest) value the code you are about to execute will produce here. so if current + fudge is < alpha, and fudge represents the best score this code would produce, it would still be less than alpha, which is no good and not worth the effort to compute. Same for the other search bound.

Post Reply