path dependent evaluation

[Daniel Shawul]

Hi
i am seriously thinking to add path dependent evaluation in my engine.
there are some ideas that are better evaluated by looking at the previous.
* penalizing lose of castling rights.
* incremental(lazy evaluation) is better done by looking at previous
ply's information as described by ED.
Costly evaluation like mobility can also be obtaned by counting the moves generated (Uri's idea).
* evaluation based on the moves that lead to this position
For example if you can't afford to extend a good looking move,
give it a higher score.
Any other ideas?
One serious problem of this methods is that they corrupt the
hashtable. it is already corrupted by repition draw detection.
despite this integrating search and eval seems a good idea for
pruning decisions. Worst scenario is not using the hashtable to cut off
(ie using it only for move ordering), which i don't think will outweigh
the benefits
what do you think?
daniel

[Daniel Shawul]

oh well, it must be a very bad idea then.
thanks anyway.

[Pallav Nawani]

oh well, it must be a very bad idea then.
thanks anyway.

Or maybe nobody has considered doing it before ( I know I haven't)
I have read Ed's webpage and I think that his Idea on Lazy eval is a good one and I will do it that way too.

I have also thought of evaluating mobility by counting the moves during generation, but evaluation is mostly done either after making a move or before move generation. After a move is made, the mobility counts will change.

Pallav

[Reinhard Scharnagl]

I see problems, if you want to use a transposition table to store evaluations. If those results are path depending and not only related to the position you also have to identify the path by the hash key.

Reinhard.

[Uri Blass]

oh well, it must be a very bad idea then.
thanks anyway.

Or maybe nobody has considered doing it before ( I know I haven't)
I have read Ed's webpage and I think that his Idea on Lazy eval is a good one and I will do it that way too.

I have also thought of evaluating mobility by counting the moves during generation, but evaluation is mostly done either after making a move or before move generation. After a move is made, the mobility counts will change.

Pallav

You are wrong

Movei is using path dependent evaluation.
I am sure that there is a big room for improvement in that part of the evaluation and it is not clear that it is a bad idea.

Uri

[Chan Rasjid]

Unlike repetition draw, evaluation path dependency is not "true" path dependency and such evaluation is stiil valid for the position.

A simple exagerated example of king safety is this :-
at eval(), if the previous 3 moves of the same side are double checks and the xside king only escape without capture, than a good guess is xside
palace is in great trouble and we have score[side] += 3 * something.
One particular path to the node happen to reveal the weakness of xside palace and is valid even if reached through another passive path.

Also i'snt everyone penalizing loss of castle rights by comparing mask at root and at evaluation node.

Rasjid

[Daniel Shawul]

Unlike repetition draw, evaluation path dependency is not "true" path dependency and such evaluation is stiil valid for the position.

I think it may really disrupt the search if i give big scores for path dependent evaluation and store that in the hashtable. Another idea
i read from CCC archieves is to store path dependent and path independent score separately, but it seems more complicated.

the castling problem is easily and better solved by path dependent evaluation rather than looking for trapped rook patterns,and penalizing that with a high score.
sometimes also it may be impossible to write an equivalent static scoring method. for example how do you staticallly evaluate loss of tempo in the opening?
daniel

[Chan Rasjid]

Daniel,

I never did consider path dependency before except in the obvious case
of repetition which I don't hash; I still cannot understand with my cache-1
brain why others seem to have the need to hash. Every re-visit can
be done with a simple rept3() call which has almost no overhead.

I eval loss of castle rights/partial loss by comparing castle-mask at root and at the evaluation node. Now I understand it is not pure positional.
Intuitively, I think it should not be a problem at all. It still can be eliminated like this:-
1) don't hash if score is exact.
2) if outside bounds and undoing the dependent amount is still outside
bound, then hash fail hard, otherwise again don't hash.

Another idea
i read from CCC archieves is to store path dependent and path independent score separately, but it seems more complicated.

I still cannot understand if there can be true path dependent evaluations.
Loss of castling rights strictly belongs to rights dependency.

Psuedo path dependent evaluation is no different from usual evaluation.
They all depend on how good our assessment is and affects search in the
same manner. It is like we can have bad king safety codes that accords
high values wrongly.

Rasjid















[/quote]

[Ross Boyd]

Just on the topic of castling rights... (BTW, I don't think its path dependant)

Also i'snt everyone penalizing loss of castle rights by comparing mask at root and at evaluation node.

Erm, nope.

Castling rights can be rolled into the hashkey, so there will be no path dependancy..

And why compare with the root? I just keep a flag for each side whether it has castled or not. If it hasn't and its lost castling ability on one or both sides, then apply a penalty in proportion to the remaining enemy material.

Have I missed something?

Ross

[mridul]

Hi,

Interesting question Daniel - and unfortunately I dont have an answer other than my own experiences in this.
I have tried time and again to use path dependent evaluation : it solves so many problems if we can get it right !

Like hunted king eval (esp if you do checks in qsearch) , massive king attack (though we can have other heurestics also for this one).
Unless you do complex pin detection in your SEE - we can reuse the search path info to find a lot of interesting things like a) whether a (statically evaluated) block on a passed pawn is really a block ? , b) blocked position (and how to break it) , c) complex pins , etc.

Maybe there are better ways of doing these , and I am sure I have missed a lot of points.
When I started off , there were a lot on my head - seem to be flitted away as soon as I tried putting them down ! ... will need to check old source code for more info if required.
I wont try to discuss the impl of these - should be obvious or easily deduceable : but inspite of all the benifits of path dependent eval (hey - while playing we think that way dont we ?!) I still find the one compelling drawback making it unusable for me YMMV.

The fact that you cant use hashtable.

Now , Uri seems to be sucessfully using an alternate scheme without hashtables - but I never got it to work sufficiently well to my satisfation inspite of trying some interesting ideas
Just imagine how strong movei will be if it also used hashtables (assuming ofcourse that Uri has not tried this seriously enough).
Also note - any search instabilities in a path dependent evaluation can be quiet fatal , and I have found that kicking out lazyeval based on alpha/beta bounds really helps - else for the same path you will have crazy variations in score (same positions through different paths might get evaluated differently already !).
Also , you will get absolutely no benifits of position transpositions : so better pump up that move ordering code : you will need it (you can ofcourse use hashtables just for the sake of transops move - gives a nice speedup ... just cant use it for pruning the search).

That is another problem - a variation of horizon effect I think.
What I see sometimes is this - there are three variations , two of which lead to same/similar position (that is static eval nearly same).
Now , 'cos of the different paths , the second transposition might be evaluated better than the first and second position - and would result in ultimately ruining the game.
So you will need to try to overcome (I dont think you can overcome all) most of these sort of problems too.

Just me 2 cents.

Enjoy !
Mridul

[Uri Blass]

I never tried using hash for pruning seriously and one of the reason that it contradict the idea of path dependent evaluation(when I tried it together with path dependent evaluation it did not help in the gcp test suite so I even did not try it in games).

Movei has a lot of disadvantages that are not related to hash and I am not sure if it could be stronger with using hash tables for pruning without path dependent evaluation.

I believe that there is a lot of room for improvement in Movei not by using hash for pruning and the only question is if I will have the energy to continue to work on it(I did not work much on it lately)

I think that one of the things that I need to do is to print my ugly code read it and think what exactly to change.

The problem is that being long time near the computer cause me to feel bad and looking at it in a paper and making comments may reduce the time that I am going to be near the computer(I also participate in discussions inspite of it because I like it and it does not help to reduce the time that I am near the computer).

Uri

[Daniel Shawul]

Castling rights can be rolled into the hashkey, so there will be no path dependancy..

there is still path dependency. though castling rights are hashed,
the info whether a castling move is actually made is not.

Also note - any search instabilities in a path dependent evaluation can be quiet fatal , and I have found that kicking out lazyeval based on alpha/beta bounds really helps - else for the same path you will have crazy variations in score (same positions through different paths might get evaluated differently already !).
Also , you will get absolutely no benifits of position transpositions : so better pump up that move ordering code : you will need it (you can ofcourse use hashtables just for the sake of transops move - gives a nice speedup ... just cant use it for pruning the search).

Hi Mirudul!
thanks for sharing your experience.
I also feared that it might introduce big search instablility.
despite that kicking out lazy eval may not be a good idea unless you
have a fast evaluation.
best
daniel

[Chan Rasjid]

Hello,

I still keep 2 things from tscp :-
castling rights using bit flags - a nice trick.
using int least_adv_pawn_rank[2][10 / file+1] for pawn eval, king pawn cover, pawn storms.

I learned more common techniques when I found CCC, the interesting ones are:-
fail soft
search instabilities
attack tables(Ed Schroder)
hashing double bounds/ multiple N
ETC
non-recursive search
node counts for root move ordering(Bob Hyatt).
repetion detection with hashkey

Ross,

Castling rights can be rolled into the hashkey, so there will be no path dependancy..

And why compare with the root? I just keep a flag for each side whether it has castled or not. If it hasn't and its lost castling ability on one or both sides, then apply a penalty in proportion to the remaining enemy material.

Have I missed something?

I usually can figure out things(non-advanced) from the hints from posts.
But I still can't figure out how hashkey(hash table?) can properly record castling bonus. penalty full/partial. With the board hashkey, the array
U64 random_C_SQ_TYPE[2][64][6], I can determine if a piece
rook, the king, etc has moved from an initial position, but this is not correct. The king may take 3 steps ahead and 3 step back to E1.

Midrul,
About path dependency evaluation, your post seem take
evaluation to mean just a search score for a position, not necessarily
from int eval(){.... path depedency scoring }. Then it has no solution
as search instabilites is unavoidable with hashing and can be made worst
easily.

Rasjid

[Tom Likens]

Hello,

I usually can figure out things(non-advanced) from the hints from posts.
But I still can't figure out how hashkey(hash table?) can properly record
castling bonus. penalty full/partial. With the board hashkey, the array
U64 random_C_SQ_TYPE[2][64][6], I can determine if a piece rook,
the king, etc has moved from an initial position, but this is not correct.
The king may take 3 steps ahead and 3 step back to E1.

Rasjid

Hello Chan,

You need to hash the castling *rights* into the hash key, not just the positions
of the kings and rooks. This can be incrementally updated (and undone) just like the rest of the
key when you walk up and down the tree. If during the path to this position the king and/or rooks
moved then the hash key will be different even though the pieces may have returned
to their original squares.

regards,
--tom

[mridul]

Hi Tom,

I used to have this too ... hash castling status into hashkey , and then use that to look at whether the king has "lost" castling privilages or not.

The problems with that are two fold when I try it use this info for eval :

1) The after castling position and without castling position could transpos to eachother.

Now - my assumption when I started off was that this would require quiet a high depth before it will happen ... but putting a few debug statements made me realise that this was not the case.
Since the penality/bonus for this was not trivial - the resulting eval mishaps are not pretty

2) Castling to the "proper" side , the king's vulnerability after castling.
Instead of actually trying to resolve the first in the eval through path/root position dependent heurestics (which would mean I will need to clear the hash between root move changes).

The easiest what I found was this - just evaluate the king's safety properly - atleast as properly as I can
The added benifit (other than path dependent eval for castling penality/castling to "right" side bonus/loss of castling/etc) is also that in closed center's, where this is possibility of flank attack - the king continue to stay in center without a premature castle.

Also , maybe important - I also get to debug my positions without trying to setup a x ply debug tree to get to the relevent subtree (assuming there is root position dependent path info also relevent - like castling to bad side/loss of castling).

Ofcourse , all with a YMMV disclaimer

Thanks
Mridul

[Ross Boyd]

1) The after castling position and without castling position could transpos to eachother.

True. I never considered this.

To solve this problem, you can hash the castling rights AND whether the king has castled or not. Of course, for initialising some fen positions you would need to make some assumptions about whether castling had occured or not.

Edit:
Uh oh, but then, you won't detect a repetition. The rules of chess don't care whether you castled or not to reach the same position. Doh!
End Edit


This has been a thought provoking thread.
I've examined my eval and found no obvious path dependancies.


However, lazy eval can certainly cause different scores to show up in the hash table. For example, during search, the full eval will occur depending on how close we are to a beta cutoff, otherwise the eval gets stored with a lot of positional scoring ignored. So, therefore, for PV nodes it is possible that full evaluation has NOT occurred. Is that right?

Thinking about this, since PV nodes are not alpha or beta cuts, I wonder if its worth calling the full eval again when we think we have a PV node and store an accurate score rather than a lazy score.

Ok, its Saturday morning so I may be talking complete rubbish. Am I?
I'll have to run some tests to see if PV nodes are indeed being stored with lazy scores. I need to think this through more carefully...

Cheers,

Ross

[mridul]

Hi Ross ,

The benifits of lazy eval can outweigh the instability (which I think is not escapable) if done right.
Ed Schroeder discusses some possibilities - you can definitely come up with your own ideas , to minimise the effects of that.
Ofcourse , the irony is , bigger and more exhaustive your eval is - the bigger the benifit from lazy eval ! (You have bigger eval to more finetune and increase accuracy of your eval )

If you do stuff like attacktables , pin detection , etc - you can reuse some of that info in qsearch to generate a fraction of threatening moves (kind of convert an upper portion of your qsearch sub-tree into a very specialised selective search) like attacking pins , forks , not prune some of the loosing captures (since the capturer maybe pinned on higher piece ,etc).
All computationally heavy - but hey , from 120knps to 100 knps (on an athlon 2400xp : yep my current engine is a slow tortoise)- it is not big a drop for me to gain the added benifits of these

I did have an engine which used lazy eval - which did quiet well to handle the instabilities. (was doing some 250 knps or so - much slimmer eval ....)
I remember someone mentioning (was it Anthony Cozzi ?) that either you need lazy eval or you need some pruning to search efficiently , and I have to agree to that ... computers visit way too many junk nodes !

Now to try to comment on what you wrote

To solve this problem, you can hash the castling rights AND whether the king has castled or not. Of course, for initialising some fen positions you would need to make some assumptions about whether castling had occured or not.

Both are orthogonal to each other ... but I dont see how you will solve the problem by hashing whether the king has castled or not.
More so across root moves you will face the problem of transposition with higher severity.

We can use alternate schemes of repetition detection ... so that is not a problem if we can solve this

In the current program , I use fail-soft AB and I found lack of lazy eval to be better .... also since my kingsafety can throw up > 7 pawn eval (no mate detection in eval yet) , the lazy window can become pretty much so huge as to lose much of its benifit ... and what all it does save can come back and bite me so I just kicked it out.
(I have some elementary pruning in qsearch which helps out in this case ...)

I frequently go back to first principles and rethink my eval , search , extensions , pruning , move ordering (a lot !) ... and usually I realize how stupid my current idea is - not if only I had noted down all my stupid ideas - next time I could have avoided all of them

Regards
Mridul

[Tom Likens]

Hey Mridul,

Hi Tom,

I used to have this too ... hash castling status into hashkey , and then use that to look at whether the king has "lost" castling privilages or not.

Does this mean you've taken it out?

The problems with that are two fold when I try it use this info for eval :

1) The after castling position and without castling position could transpos to eachother.

Why is this a problem. If the positions are *exactly* the same. What I mean is, if the the castling rights are the same, the piece locations are identical as well as the right to move, why shouldn't the evaluation score them the same. The only real difference could be in the tempi count to reach the position. But if the right to move is the same then both sides wasted moves to get here. So the penalites will be the same.

The easiest what I found was this - just evaluate the king's safety properly - atleast as properly as I can

Yes, when you discover this *please* let the rest of us know as well.

I believe your answer is the correct one. Instead of penalizing castling, evaluate the king's safety for the position on the board. It doesn't matter if we castle if we arrive at the exact same position and our king is safe. Castling is important because it protects the king.

regards,
--tom

[mridul]

Hi Tom,

Yes , I have taken it out - I have also taken out the enpassent hashing.
The added advantage of it is that now transpositions of the same position will now share the hashmoves - more relevent to enpassent hashing ofcourse.

The problems with that are two fold when I try it use this info for eval :

1) The after castling position and without castling position could transpos to eachother.

Why is this a problem. If the positions are *exactly* the same. What I mean is, if the the castling rights are the same, the piece locations are identical as well as the right to move, why shouldn't the evaluation score them the same.

You mentioned the exact problem with path dependent eval !
What will happen is that , the eval will penalise the non-castled path for not having "castled" !
(Extrension of this concept would be when after castling and without castling , both the kings wander to same location , etc. - that is different discussion , but vey similar to this one.)

What I have usually seen everybody discuss is something like this :

Code: Select all

if (root_can_castle[side]){
  if (!current_position_has_castled[side]){
     penalise so that you castle and get king to safety;
    // typically some have code to check which is safer side ,e tc , etc.
  }
  else if (current_position_has_castled[side]){
    if (root_can_castle_both_ways[side]){
      // some code to check which is safer side ,e tc , etc.
    }
  }
  else if (castling_lost[side]){
    // Since we "lost" castling, penalise high !
    penalise_a_bit_more_extensively;
  }
}


So you see - when the uncastled king wanders to same location and same resulting position (and so same hashkey) the evaluation is going to be different depending on whether it was a castled into this position or transposed into this position.
I am sure lot of people might have alternate ideas on how to handle this - though from my side , I just went the other direction and just try to make the kingsafety so big and clunky that I hope it catches all these just on the static eval
Having mobility eval makes sure that the rook does not get trapped on h/a with king on g/b file (the king safety eval will prevent blowing the king cover to get the rook out)

I am sure that there are much more things yet to be done !

But it feels damn good when the king remains in the center without castling in a closed center position (with adequate defence) with opponent saying huge bonus and CEng saying even eval

Ofcourse , please note - the very fact that most people dont use these ideas (idiotic ?) and yet write much more stronger programs might mean that the cost benifit ratio makes it just not worth it !
YMMV as always


Regards
Mridul

[Tom Likens]

Mridul,

Hi Tom,

Yes , I have taken it out - I have also taken out the enpassent hashing.
The added advantage of it is that now transpositions of the same position will now share the hashmoves - more relevent to enpassent hashing ofcourse.
hello

Believe it or not, (before I hashed the en'passant rights into the key), during a game a couple of years back my engine thought it had found a mate against another engine and played a very poor move to "force" the mate. Of course, the mate was bogus and it went on to lose the game. When I tracked down the bug I found that the mate was delivered by a pawn that could have been captured en'passant (thus stopping the mate). The hash table returned an exact hit because the search had managed to create the same position by transposition except that the pawn took two moves to reach the critical mating square, when an en'passant was not valid.


So, ironically, it can make a difference. Of course the truth is that these things happen so rarely it makes no practical difference. It did however, bring a wry smile to my face when I finally discovered what had happened.

But it feels damn good when the king remains in the center without castling in a closed center position (with adequate defence) with opponent saying huge bonus and CEng saying even eval

Yes, these are the moments when chess programming is most rewarding.

Ofcourse , please note - the very fact that most people dont use these ideas (idiotic ?) and yet write much more stronger programs might mean that the cost benifit ratio makes it just not worth it !

Yes, and some of those "idiotic" ideas create programs like Shredder and Ruffian, so don't stop!

regards,
--tom