Stand Pat penalty

[spambanane]

An excellent way of thinking. Removing features (and code) by changing the way your software works is an effective (and maybe the only) way to prevent bloat. Most programmers are not aware of this.

As Ken Thompson said: "One of my most productive days was throwing away 1,000 lines of code."

All in all writing a chess engine is a very uncommon way of writing code for me - usually I would never write another 50 lines of code just to make my program 5% faster.

[lucasart]

LESS IS MORE

I am a purist of the concept...

[michiguel]

But outside of the QS you don't stand pat, so I don't really understand the name then.

Yes, I do stand pat in the search, when doing eval pruning near the leaves:

Code: Select all

// Eval pruning
if ( node_type != PV
	&& depth <= 3
	&& !in_check
	&& !is_mate_score&#40;beta&#41;
	&& ss->eval + TEMPO >= beta + EvalMargin&#91;depth&#93;
	&& B.st&#40;).piece_psq&#91;B.get_turn&#40;)&#93; ) &#123;
	const int stand_pat = ss->eval + TEMPO - stand_pat_penalty&#40;B&#41; - EvalMargin&#91;depth&#93;;
	if &#40;stand_pat >= beta&#41;
		return stand_pat;
&#125;

If you just apply it as a correction to the stand-pat score, isn't it simply a side-to-move dependent term in the evaluation?

My eval must remain symmetric. That is why I do this outside the eval (side to move dependant), as well as the Tempo bonus (handled in the search). The reason is that after a null move I can just negate the eval of the parent node, and skip a call to the eval. This is a really big speed gain, and reduces quite significantly the number of eval calls.

I was confused too in regards of the difference between adding this to the stand pat score or sticking it to eval. If you do not stand pat because of this, and you do not find any good capture in qsearch, what do you return?

I have these type of terms in eval (I call them "pressure"). I add them long time ago so I do not remember the testing details but I have the recollection it was a positive addition. So it makes sense you see improvement. I count the number of pieces hanging from each side and apply penalties depending if they are one or two (fork etc.) for both sides. However, I needed some corrections based on a position Adam Hair sent me. When both sides have pieces hanging I set this term to zero, but that is wrong. I am still playing around with it (my penalties are not big, maybe they should be...)

[D]1n2k2r/r4ppp/p2b1q2/3Q1b2/1p1P4/5NP1/PP2PPBP/R4RK1 w k - 1 14

In that position, white should have a positive score (higher than +1) after e4 in 6 or less plies (e5 fork in coming). Without these terms in eval, unless you tweak all the pruning decisions everywhere, e4 with a positive score will be delayed.

Miguel

[spambanane]

@lucas: Why do you still use c++? Beeing a purist and using c++ seems like a contradiction to me. I remember there is a topic about the c++ insanity in this forum, not long ago.

[lucasart]

If you do not stand pat because of this, and you do not find any good capture in qsearch, what do you return?

The best score between:
1/ eval + tempo - stand_pat_penalty()
2/ qsearch captures (and quiet checks if depth == 0)

This is *in general* incorrect, and one can make plenty of examples of where that will be wrong. But it's no less incorrect than standing pat with plenty of hanging pieces... You're just swapping one error for another one.

It's essentially conservative. If the qsearch decides to stand pat on a position where the side to move has several hanging pieces then:
- it is quite likely that another variation will lead to a similar score, but without leaving several hanging pieces. the stand pat version will simply prefer this new variation.
- if there are really no other solutions (rare?) and the only way to obtain the good score is to leave pieces hanging, then we will stand pat with a penalty, or enter into a slightly losing capture (like losing a pawn) to solve the hanging pieces problem (if the penalty is indees more than a pawn), etc. Also when you have hanging pieces, they are often attacking their own attackers, so you can solve the problem by exchanging.

So it's not 100% correct, and it's really a risk/reward analysis. It solves previous mistakes, and creates new ones instead. But the bet is that the overal result is positive. At least it was in DiscoCheck.

Anyway, I don't know if it will work for Gaviota or any other engine, but it's worth a try.

[michiguel]

An excellent way of thinking. Removing features (and code) by changing the way your software works is an effective (and maybe the only) way to prevent bloat. Most programmers are not aware of this.

As Ken Thompson said: "One of my most productive days was throwing away 1,000 lines of code."

All in all writing a chess engine is a very uncommon way of writing code for me - usually I would never write another 50 lines of code just to make my program 5% faster.

5% faster? Who do I kill?

Miguel

[michiguel]

If you do not stand pat because of this, and you do not find any good capture in qsearch, what do you return?

The best score between:
1/ eval + tempo - stand_pat_penalty()
2/ qsearch captures (and quiet checks if depth == 0)

This is *in general* incorrect, and one can make plenty of examples of where that will be wrong. But it's no less incorrect than standing pat with plenty of hanging pieces... You're just swapping one error for another one.

I know that. I was trying to understand how it was implemented, if it was in eval or outside eval and if there was any difference. In qsearch, if you do the above, it should be identical if you also include this penalty in delta (futility) pruning considerations.

It's essentially conservative. If the qsearch decides to stand pat on a position where the side to move has several hanging pieces then:
- it is quite likely that another variation will lead to a similar score, but without leaving several hanging pieces. the stand pat version will simply prefer this new variation.
- if there are really no other solutions (rare?) and the only way to obtain the good score is to leave pieces hanging, then we will stand pat with a penalty, or enter into a slightly losing capture (like losing a pawn) to solve the hanging pieces problem (if the penalty is indees more than a pawn), etc. Also when you have hanging pieces, they are often attacking their own attackers, so you can solve the problem by exchanging.

So it's not 100% correct, and it's really a risk/reward analysis. It solves previous mistakes, and creates new ones instead. But the bet is that the overal result is positive. At least it was in DiscoCheck.

Anyway, I don't know if it will work for Gaviota or any other engine, but it's worth a try.

As I mentioned in my previous post, I have this term in Gaviota, but stuck in eval. What is certainly worth trying is to revisit the value of the bonuses. On top of that, I have something more complex (and slow) used in search: I check all the pieces hanging with see and come up with a "threat value" that is added to the pruning margins. I wonder if they are interacting badly since some of those could be measuring overlapping threats.

Miguel

[Evert]

Yes, I do stand pat in the search, when doing eval pruning near the leaves:

Code: Select all

// Eval pruning
if ( node_type != PV
	&& depth <= 3
	&& !in_check
	&& !is_mate_score&#40;beta&#41;
	&& ss->eval + TEMPO >= beta + EvalMargin&#91;depth&#93;
	&& B.st&#40;).piece_psq&#91;B.get_turn&#40;)&#93; ) &#123;
	const int stand_pat = ss->eval + TEMPO - stand_pat_penalty&#40;B&#41; - EvalMargin&#91;depth&#93;;
	if &#40;stand_pat >= beta&#41;
		return stand_pat;
&#125;

Ok. I guess I would call that "a form of razoring", except you're not testing whether your position is particularly bad but whether it's particularly good (like null move).

My eval must remain symmetric. That is why I do this outside the eval (side to move dependant), as well as the Tempo bonus (handled in the search). The reason is that after a null move I can just negate the eval of the parent node, and skip a call to the eval. This is a really big speed gain, and reduces quite significantly the number of eval calls.

I use an evaluation cache and store both score and -score (with flipped side-to-move in the hash key) for the same effect. The exception is if there are side-to-move dependent terms contributing to the evaluation, which is rare though (KPK and KBKP(ah) are examples, some other end-game situations too). In that case I don't store the negated score.

You may be right that including this term would disable the evaluation cache too often, but that actually raises another question: what do you do if the side to move can capture a piece? Do you give a bonus? How big? A rough guestimate may be half the value of the most valuable hanging piece, but does it make much practical difference if you picked the least valued one? If you did that the evaluation term becomes symmetric again...

[Desperado]

Hi Lucas,

Code: Select all

// Eval pruning 
if ( node_type != PV 
   && depth <= 3 
   && !in_check 
   && !is_mate_score&#40;beta&#41; 
   && ss->eval + TEMPO >= beta + EvalMargin&#91;depth&#93; 
   && B.st&#40;).piece_psq&#91;B.get_turn&#40;)&#93; ) &#123; 
   const int stand_pat = ss->eval + TEMPO - stand_pat_penalty&#40;B&#41; - EvalMargin&#91;depth&#93;; 
   if &#40;stand_pat >= beta&#41; 
      return stand_pat; 
&#125;

Well, all i can see here is the "Static Nullmove Pruning" technique.
Let me explain, what i mean...

1. The margin
==========

The expression

Code: Select all

ss->eval + TEMPO  - EvalMargin[depth] >= beta 

is replaced with

Code: Select all

ss->eval + TEMPO - StaticBiggerDynamicMargin(depth) >= beta

Now, because the conditional margin is bigger than the standard depth
margin, you do not need to check it conditionally. You can do it immediatelly.

2. The Conditions

Beside some standard conditions for pruning near the leaves,
you introduced the "hangingPiece" condition, AND let out the
"isNullmoveAllowed" condition.

3. So, finally it becomes sth. like this...

Code: Select all

if(       myStandardConditionsAreOk(depth) 
    &&  myPreferedConditionsAreOk()
    &&  myStaticMargin() >= beta )
    {  return myStaticMargin() ;}
  

So, putting it all in a blackbox it becomes pretty clear what it is.
Much more clear if you add now myNullmoveIsAllowedCondition() to
the above snippet.

So, it is certainly, like i read here in the thread, not a form of
futility, so implicit no razoring technique where you check against the
alpha bound ( the situation is so bad, no need to continue ...)

Anyway, what is interesting to examine is why there is an elo gain of
nearly 10 elo. 2 parts which i would review in your situation.

Part 1
====

You mentioned you use your condition also in QS.

a. here if the condition is part of the "Standard" standpat condition
the qs would be more conservative, so the QS may get more accurate.

b. if you check the condition after your regular Standpat condition it
looks buggy, because at the point where you check the condition you,
i mean the search should already have returned by the normal
StandPat. ( my assumption is you handle TEMPO and some minor things
identically ). Pretty simple logic:

Code: Select all

  evalValue - 0 >= evalValue - BiggerMarin

So, in that case there is no gain possible.

Part 2
=====

I assume you already implemented "Static Nullmove Pruning", so
following cases may be interesting to examine further.

a. Missing "NullmoveIsAllowed()" check is leading to more prunings
but implicit adds a double nullmove in some cases. So, having
a nullmove at ply x and returning at ply+x+1 with your code is effective
doing 2 nullmoves in a row, but because of returning immediatelly, it is
like a reduction of 2 plies at ply x-1. ( ugly to think this way around )

b. Try to add the NullmoveIsAllowed() condition, and look what happens.
Through some more analysis you may merge these code parts, to get
a finally more effective StaticNullmove Pruning code.

c. On the other hand it may be a good idea to have something like
a doubleNullmove Pruning technique near the leaves ( or similiar
prun more aggressive on static data 2 plies before ). That would be
the contrary, instead of adding the NullmoveIsAllowed() condition, let
it out completly. ( i mean the contrary to case "b." )

d. You can/should merge you StaticNullmovePruning code with this code.
and combine the most effective conditions.

e. Finally you can play around with the given ideas, it would blast
my answer unnecessary.

Last but not least, if you doubt that you are implicit doing a nullmove,
(ignoring tempo value), think of sth. like that.

Code: Select all

doNullmove()
value = -evaluate()
undoNullmove()

which is pretty equal to

Code: Select all

value = evaluate()

Well, i read you thread on the way home on my handy, so i hope i did
not miss something substantial, writing down my ideas when i arrived at
home immediatelly.

regards Michael

[Don]

Nice gain! I've given it a shot here: http://tests.stockfishchess.org/tests/v ... 7dd8b5f3fa. We shall see how it goes .

Something looks wrong in your patch: why do you exclude the case where tte != NULL ?

As we don't call the eval in that case, unless the score is VALUE_NONE, which is incredibly rare. For example, running sf bench, that eval call is never hit.

The stand pat idea didn't make it past stage 1, but adding a bonus to the side that is attacking multiple weak pieces has, which is very nice! With a straight up simple value of 60, 60 as well. Some good potential there for improvement it looks like.

Is this the same as the version that showed 9 ELO for 10,000 games or something else? That is a pretty big margin to not make it.

Komodo has symmetrical evaluation but we do give attack bonuses IN the evaluation function and these get larger when multiple pieces are attacked. And it was definitely an improvement but I cannot remember how much (This was done between Komodo 4 and 5 I think.)

I remember experimenting with asymmetrical bonuses (based on the side to move) but nothing came of it. Doesn't mean it's bad though, it just means we did not succeed in figure it out.