path dependent evaluation

[mridul]

Btw , I might have forgotten to mention this.
In hashtable probe - if the move returned is not valid for that position (like castling move for a position where the king cant castle , enpassent that you described ,etc) - I ignore that hash entry : pretend as though the hash hit did not happen and return 0
Did not really think it was necessary to mention since I am sure you would have figured that part out


Mridul

[Sune Fischer]

Meridul and Tom,

I don't quite understand this conversation.

Meridul:
"In hashtable probe - if the move returned is not valid for that position (like castling move for a position where the king cant castle , enpassent that you described ,etc) - I ignore that hash entry : pretend as though the hash hit did not happen and return 0 Smile "

AFAIK this can only happen in two cases, you have a hash bug or a collision!?

Tom:
"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. "

This would seem like the same problem, I'm guessing a hash bug.

Tom:
"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. "

You should hash the castle keys whenever the king loses its castle rights permanently, whether this is by doing the castle or moving the rook or king doesn't matter.

The same position should not have two corresponding keys (inefficient) and more importantly two positions must never have the same key (huge bug).

Unfortunately this is a bit ugly since you have to check for it at every rook and king move. At least I have not found a better way
Some I know use a table with mostly zero entries and just mask everything avoiding the check.

-S.

[mridul]

Hi Sune , all,

oops - you are right
Problem with having all caching code in same file - a pageup/pagedown and i am looking at entirely different code which looks quiet similar

I rechecked my code (just to be sure) - keep forgettin some of these details ... been a while since I had to fix bugs here.

No enpassent hashing.
For the purpose of eval cache , qsearch cache , book probe - castling flag is masked out - so effectively , as though castling is not hashed into the key. (I dont do castling moves in the qsearch - even if there is a potential castling move which can check).
Only for the main search do I also have castling flag in hashkey.

Thanks for pointing out this blunder in my comment !

Thanks and Regards
Mridul

[Sune Fischer]

Hehe, I don't know if we are talking about the same thing,
but you bring up an interesting point.

With respect to the evaluation some positions that really are different
will get evaluated the same.

It's a bit inefficient I guess, but can it be optimized for better hashing?
Running with two keys seems like a lot of trouble..?

-S.

[Ross Boyd]

Hi Sunee,

You should hash the castle keys whenever the king loses its castle rights permanently, whether this is by doing the castle or moving the rook or king doesn't matter.

I agree entirely with you, but... in the context of the path dependant evaluation, there still remains a little problem....

Take the following position...

[diag]1r1k1r2/p5Q1/2p3p1/8/1q1p2n1/3P2P1/P3RPP1/4RK2 b - - 0 1[/diag]

It is possible for white to reach the above position with and without castling.

Clearly, the castling rights are non-existent for both sides so the hashkey will be the same. However, if you reward the act of castling your hash score may include the bonus or it may not. It all depends on the search path.

That's the problem.

Now, my first thought was to roll in an additional "side_has_castled" flag into the hashkey and then the hash scores will be correct. BUT, then your repetition detection will fail, because the rules of chess don't differentiate between positions based on whether you castled or not. Its only the castling rights that count.

So, IF you reward castling there remains a little hash table instability problem. And its probably completely insignificant in Elo terms.

Cheers

Ross

[Sune Fischer]

Hi Ross,

I guess you add a bonus directly in the MakeMove if it is a castle move?

It probably works okay but still it's a bit primitive way of doing king safety,
and the score also becomes path dependent.

I did it also in some earlier versions, but eventually took it out for those reasons.
As a principle I want the same position to be evaluated the same no matter
how it is reached.

-S.

[Ross Boyd]

Sune,

Sorry for mis-spelling your name.

I did it also in some earlier versions, but eventually took it out for those reasons.
As a principle I want the same position to be evaluated the same no matter
how it is reached.

I agree with you 100%.

As it so happens, TRACE rewards castling.... so I'm going to have to fix that now... probably just let the king safety eval sort it out.



Ross

[mridul]

As a principle I want the same position to be evaluated the same no matter
how it is reached.

You said it
And that is the reason why path dependent eval was kicked out by me.
Now, this is something that I found to be more in liking to the way I think.
Ofcourse , you can take a non-hashing , etc approach and still play arond with path dependent evals : I would really love to hear Uri comment about what he does here - esp since I never got it to work well.

Regards
Mridul

[Sune Fischer]

What Uri does is very impressive.
Not only is it a novel approach but he can actually make it work too.

I suspect that the transpositional aspect is not that important in the middle
game, but it must cost some plies in the endgame.

Currently I believe there must be better ways to remove silly lines than to
make the eval itself path dependent, but I will admit that some things are
better seen through search than static eval.

Things like measuring progress and seeing perpetuals is easier scored by
evaluating the searched line directly.

Perhaps Uri is just ahead of his time, soon we will all come to realize
how important path dependency is

-S.

[Tom Likens]

Hey Sune,

Wow, this thread grew exponentially overnight.

Tom:
"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. "

This would seem like the same problem, I'm guessing a hash bug.

It's possible of course, but I don't believe so (I've *never* had a bug in my hash table :D). The position in question *was* a mate if the opponent couldn't capture the checking pawn en'passant (the pawn actually delivered the mate). The search managed to create two identical positions but in one the en'passant capture was illegal and hence a real mate. In the 2nd the mate could be prevented by the pawn capture. The mate position was stored in the hash tree first and later retrieved incorrectly for the non-mate position because the hash keys, without the en'passant information, were the same.

Regardless, the problem was eliminated when I added en'passant information to the key.

"Tom:
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. "

Um, actually I never said this, nor implied it. If two positions are *identical* (ignoring 3-fold repetitions and such, since they are legitimately path dependent) then the hashkey and the evaluations should be identical. A number of people fold in a path-dependent "loss-of-castling-rights" penalty or bonus, but it's probably not the right thing to do. Real king safety is (IMHO) better.

You should hash the castle keys whenever the king loses its castle rights permanently, whether this is by doing the castle or moving the rook or king doesn't matter.

Yes, exactly--this is the right way to do it.

The same position should not have two corresponding keys (inefficient) and more importantly two positions must never have the same key (huge bug).

I would consider the same position with two different hashkeys a bug as well.

Unfortunately this is a bit ugly since you have to check for it at every rook and king move. At least I have not found a better way

Nor I.

regards,
--tom

[Tom Likens]

What Uri does is very impressive.
Not only is it a novel approach but he can actually make it work too.

What approach does Uri take?

--tom

[Sune Fischer]

Hi Tom,

It's possible of course, but I don't believe so (I've *never* had a bug in my hash table :D). The position in question *was* a mate if the opponent couldn't capture the checking pawn en'passant (the pawn actually delivered the mate). The search managed to create two identical positions but in one the en'passant capture was illegal and hence a real mate. In the 2nd the mate could be prevented by the pawn capture. The mate position was stored in the hash tree first and later retrieved incorrectly for the non-mate position because the hash keys, without the en'passant information, were the same.

Regardless, the problem was eliminated when I added en'passant information to the key.

Ahem okay, so let's not call it a bug. Let's just say there was something
unintentionally missing in the code that caused the engine to seemingly misbehave a little bit at random.

What approach does Uri take? "

He takes the non-transpositional approach
Really attacking an old dogme of computer chess, and not completely
unsuccessful at it either
Perhaps some day they have to rewrite the books on graph theory and
tree search.
Who knows what will happen when Movei becomes WCCC.


-S.

[Tom Likens]

Hey Sune,

Hi Tom,

Ahem okay, so let's not call it a bug. Let's just say there was something
unintentionally missing in the code that caused the engine to seemingly misbehave a little bit at random.

Yes, exactly it was a "feature"!

What approach does Uri take? "

He takes the non-transpositional approach
Really attacking an old dogme of computer chess, and not completely
unsuccessful at it either
Perhaps some day they have to rewrite the books on graph theory and
tree search.
Who knows what will happen when Movei becomes WCCC.


-S.

I always find Uri and his ideas invigorating. He goes his own way on many things (and takes quite a bit of heat along the way) but his discoveries and revelations are unique. I too hope he makes it to the top one day. Or at least is able to become a professional chess programmer--which I know is one of his ambitions.

regards,
--tom

[Uri Blass]

Thanks for the support

I am sure that there is a lot of room for improvement.
I am less sure if I am going to do it.

Uri

[Chan Rasjid]

Maybe some who use hashkey for castling do not know tscp.

I'm not sure this method is very much less efficient.
The little trick is:-

int castle, castle_root; //== 15 at start; 1,2 for A1, H1, 4,8 for A8,H8
int castle-mask[64]=
{
11, 15, 15, 15, 3, 15, 15, 7,
...
15, 15, 15, 15, 15, 15, 15, 15,
...
14, 15, 15, 15, 12, 15, 15, 13
};

the castle flag is restored at takeback();
on makemove() a line is needed,
castle &= castle_mask[from]&castle_mask[to];
//the only overhead- is this expensive for top top program
//this may be remove using a different copy of takeback(), makemove()
after castling.

Bonus/penalty done by comparing flags at root and eval();

If on probehash in search() and the bestmove is castling, then
if the move is available, ok; else hit ignored as transposition unacceptable here.

In qsearch probe hit, bestmove is never castling; and even if the score has castling bonus and the position is through transpositon, the bonus is
"right"; it is irrelevant how the "castling position" is reached.


Rasjid

[Gerd Isenberg]

Hi all,

in my current position structure i have one byte with castle rights and en passant state - four bits each. En passant state is zero except after double pawn push with at least one possible pseudolegal enpassant capture option (opponent pawn(s) on neighboured file(s) on the same 4. or 5.rank), with bit 3 set and bit 0,1,2 determining the file of the pushed pawn (for both sides).

During update by makemove, i xor before/after castleEp bytes. If there are any set bits, either castle rights or ep-state (or both) changed. Xoring the hashkey with an entry of a preinitialized lookup-table[256], indexed by delta, considers castle-rights as well as en passant state.

An ep-xor-delta != 0 usually occurs immediately after an appropriate double pawn push and the same delta most likely after opponent's move, ep-capture or not. So the hashkey-change for ep only temporary reflects the potential ep-option (i ignore cases where ep-capture is illegal and may therefor rarely miss a repetition because i distinguish equal positions with same moves). This also holds for series of alternating ep options, let say white play d2-d4 while black has e4xd3, but black plays d7-d5 while white has c5xd6.

Cheers,
Gerd