Transposition tables and move evaluation, questions/advice

[sje]

If an en passant target square is set only after a double pawn advance, then it is impossible for the resulting position to be a draw by repetition or by the fifty move rule.

duly noted, but it is possible according to the rules of chess for double pawn advance to create the first instance of a three fold repetition, right? In which case the existence of an ep target is not part of the repeated position according to my definitions.

If an en passant capture is available in one position and not another, then those two positions are different and so do not count towards a repetition.

[Fguy64]

interesting, so 3-fold is about more than the physical layout of the pieces and who has the move. After 35+ years of chess, I have learned something new about the rules of the game. It also means that my own program does not fully correspond to all the rules of chess. Thanks for that.

p.s. I suppose the same applies to right of castling. It is part of the condition of threefold. if so that is two ways my program needs fixing.

[Zach Wegner]

If an en passant target square is set only after a double pawn advance, then it is impossible for the resulting position to be a draw by repetition or by the fifty move rule.

duly noted, but it is possible according to the rules of chess for double pawn advance to create the first instance of a three fold repetition, right? In which case the existence of an ep target is not part of the repeated position according to my definitions.

No, the ep rights factor into the position, which means that it can't be repeated. But as Teemu says, you want to consider it as a draw anyways inside the tree, since obviously the e.p. rights weren't taken advantage of.

Technically the e.p. rights are only set if a pawn can legally make the capture. This actually means that most engines would incorrectly say this game is not a repetition:
[d]4k2n/8/8/8/4p3/8/3P4/3KR2N w - -
1. d4 Ng6
2. Ng3 Nh8
3. Nh1 Ng6
4. Ng3 Nh8
5. Nh1

[Fguy64]

If an en passant target square is set only after a double pawn advance, then it is impossible for the resulting position to be a draw by repetition or by the fifty move rule.

duly noted, but it is possible according to the rules of chess for double pawn advance to create the first instance of a three fold repetition, right? In which case the existence of an ep target is not part of the repeated position according to my definitions.

No, the ep rights factor into the position, which means that it can't be repeated. But as Teemu says, you want to consider it as a draw anyways inside the tree, since obviously the e.p. rights weren't taken advantage of.

Technically the e.p. rights are only set if a pawn can legally make the capture. This actually means that most engines would incorrectly say this game is not a repetition:
[d]4k2n/8/8/8/4p3/8/3P4/3KR2N w - -
1. d4 Ng6
2. Ng3 Nh8
3. Nh1 Ng6
4. Ng3 Nh8
5. Nh1

Ah thanks for that. So epTarget is part of the three fold repetition condition, but simply advancing your pawn two squares does not automatically create an epTarget. Make that 3 ways my program is wrong

edit: but... The final stage of my legal move checker wont allow the ep capture to be made, even though an the ep Target flag is set earlier in the checker. so with the program design I have, I don't need to worry about illegal moves, but I do need to fix my repition condition somewhat

[diep]

There are three key pieces of information you need besides the basic Zobrist signature... you need the side to move, ep indication, and castle status. If you omit any of those, you will reach positions where your search completely breaks, because thinking that two positions with identical piece locations, but either different castling rights, different sides to move, or presence/lack-of en passant capture are the same will lead to gross mistakes. It is trivial to add in all three pieces of information and not fall into any traps later on.

I didn't mean to omit the information in the saving of the ep and castle status -- I just meant that when you search the transposition table and you have, say, an ep flag set in your position, you also search the position without the ep flag set (which might have a much greater chance of being present in the table) in order to get a lower bound, or upper bound on the score depending on which side has the ep attack -- since we can generally say that for a given position score+ep target > score (if the side to move has the ep attack), and that the differences in the two scores are probably very slight, so you'd get quite a close bound. It only fails in the very rare cases of zuzgwang/3-move rule type scenarios.

Suppose we have a zobrist key P' where after hashing e3 as we just played e2-e4, we get zobrist key P.

For the side to move that can capture en passant it makes, from a theoretic viewpoint seen, indeed sense to probe also P' provided we just check it for lowerbound properties.

How useful it is i'm not sure. Probably it is not worth the extra code. Price of 1 additional RAM access (in diep's case doing 8 probes) is not a problem by the way. That code is active also during the entire search, even in endgame, which might be a bigger problem than very seldom doing that probe.

Additional to that regurarly capturing en passant is the best move in a position when it is possible and you're ignoring that in position P'.

So the heuristic soon becomes IF it is possible to capture en passant AND some big material is there to win, THEN also try that other probe.

Further if your program has a very good move ordering you keep researching the same tree, so previous time you got into position P' it probably also was a P with en passant possible.

From a complete theoretic viewpoint however you're right, no question about it.

Should be fairly easy to test this in openingsposition.

[diep]

Actually it goes even further.

Let's consider 2 positions P and P'

In P we can capture en passant
In P' we cannot capture en passant

If we're in P then for transposition table next is true:
If we normally spoken would get a cutoff based upon P'
so the only criterium that limits us is the fact that en passant is
possible here then there is 2 possibilities
a) in case of lowerbound cutoff we can give that
b) in case of upperbound or truebound score in hashtable,
we need to only calculate the value of the en passant move
and then can maximize the score with the value from hashtable
and return that

If we're in P' and in hashtable we find a positoin P that's based upon
en passant, then in case of:
a) upperbound we can safely give a cutoff
b) lowerbound or truebound we can give a cutoff in case the best
move is not an en passant move

Vincent

[bob]

Actually it goes even further.

Let's consider 2 positions P and P'

In P we can capture en passant
In P' we cannot capture en passant

If we're in P then for transposition table next is true:
If we normally spoken would get a cutoff based upon P'
so the only criterium that limits us is the fact that en passant is
possible here then there is 2 possibilities
a) in case of lowerbound cutoff we can give that
b) in case of upperbound or truebound score in hashtable,
we need to only calculate the value of the en passant move
and then can maximize the score with the value from hashtable
and return that

If we're in P' and in hashtable we find a positoin P that's based upon
en passant, then in case of:
a) upperbound we can safely give a cutoff
b) lowerbound or truebound we can give a cutoff in case the best
move is not an en passant move

Vincent

I am not sure I buy that. If the positions are not equal because of en passant capture possibility, then they are simply different. One might lead to a draw by repetition the other will not. EP captures are sometimes subtle "get out of check" moves as I discovered when writing my legal-move generator for Crafty years ago. I would not use an entry for a "different position" with respect to EP status, castling status or side-on-move any more than I would use an entry for a position that is different because pieces are on different squares...

[Sven]

I think you must check whether or not a square is attacked by a neighboring pawn and set the ep flag, regardless of the amount of work and whether or not it seems justified. Remember that that information becomes part of the position hash which is used for detecting repetitions. If you don't check it, you could see a position reoccur where at one time there is a possible en-passant capture and at another time there isn't and incorrectly determine that its a repetition draw when really it isn't.

The position with the enpassant square can never re-occur during the game. But you're right that you still need to know if there is an attacking pawn or not in order to handle the repetitions correctly.

One major problem of always setting an ep target square after a pawn double step even if there is no attacking pawn may be that you miss detecting a 3-fold rep.

A simple but of course stupid example would be 1.e4 Nc6 2.Nf3 Nb8 3.Ng1 Nc6 4.Nf3 Nb8 5.Ng1 from the initial chess position. A program that sets e3 as ep target after 1.e4 will miss the repetition since it would regard the positions after 3.Ng1 and 5.Ng1 as different from that after 1.e4 due to the (wrong) ep target setting which already disappears with 1...Nc6.

EDIT: I think Zach already posted nearly the same with a different example, I simply missed to notice it.

Sven

[diep]

Actually it goes even further.

Let's consider 2 positions P and P'

In P we can capture en passant
In P' we cannot capture en passant

If we're in P then for transposition table next is true:
If we normally spoken would get a cutoff based upon P'
so the only criterium that limits us is the fact that en passant is
possible here then there is 2 possibilities
a) in case of lowerbound cutoff we can give that
b) in case of upperbound or truebound score in hashtable,
we need to only calculate the value of the en passant move
and then can maximize the score with the value from hashtable
and return that

If we're in P' and in hashtable we find a positoin P that's based upon
en passant, then in case of:
a) upperbound we can safely give a cutoff
b) lowerbound or truebound we can give a cutoff in case the best
move is not an en passant move

Vincent

I am not sure I buy that. If the positions are not equal because of en passant capture possibility, then they are simply different. One might lead to a draw by repetition the other will not. EP captures are sometimes subtle "get out of check" moves as I discovered when writing my legal-move generator for Crafty years ago. I would not use an entry for a "different position" with respect to EP status, castling status or side-on-move any more than I would use an entry for a position that is different because pieces are on different squares...

Let's refute all your arguments 1 by 1.

a) repetition: how would this go wrong now when it didn't already go wrong in your regular search? It is a total different problem unrelated to this.

b) extension problem: You can prove with natural induction (0,1,n+1..n) for all cases that this goes ok.

c) we're speaking just about en passant here, not about castling. However what holds true for en passant also holds true for castling.

d) whether effectively it speeds up our software in openingsphase remains to be seen. I guess we all agree about this. In a program like diep using a lot of cycles a node i have of course more headroom for algorithmic tricks and enhancements than you've got in crafty which is approaching the 1000 cycles a node. As comparision the 32 bits engines out of 90s already at 'crappy' p5 processors were underneath 1000 cycles a node, just to show how efficient those engines were, despite inline intrinsics and the best possible compiler support someone could wish on this planet, as crafty was in specint.

Yet it remains a fact that the en passant capture usually is giving a cutoff when it is possible. Secondly for all that administration and extra code, only under the CONDITION we don't have this position stored yet AND we have it stored with other properties at the same search depth, THEN our code gets triggered.

Normal odds for a transposition entry that gives a success is roughly 4% to 5% (at non-qsearch depths) in most chess engines. So for that 1 in 20 odds for just a few positions in the search tree, we're doing all that administration here.

If we'd be searching 100 plies deep that would be fantastic of course, yet we aren't.

I'm producing later some outputs of diep where i ignore en passant completely in hashtable (yet i generate it in search) to see whether it has a potential to reduce a lot of nodes in openingsposition at a tad bigger search depth single core.

Idea is that if this reduces a lot of nodes and/or search time, that it's worth taking a better look at this.

Vincent

[diep]

I think you must check whether or not a square is attacked by a neighboring pawn and set the ep flag, regardless of the amount of work and whether or not it seems justified. Remember that that information becomes part of the position hash which is used for detecting repetitions. If you don't check it, you could see a position reoccur where at one time there is a possible en-passant capture and at another time there isn't and incorrectly determine that its a repetition draw when really it isn't.

The position with the enpassant square can never re-occur during the game. But you're right that you still need to know if there is an attacking pawn or not in order to handle the repetitions correctly.

One major problem of always setting an ep target square after a pawn double step even if there is no attacking pawn may be that you miss detecting a 3-fold rep.

A simple but of course stupid example would be 1.e4 Nc6 2.Nf3 Nb8 3.Ng1 Nc6 4.Nf3 Nb8 5.Ng1 from the initial chess position. A program that sets e3 as ep target after 1.e4 will miss the repetition since it would regard the positions after 3.Ng1 and 5.Ng1 as different from that after 1.e4 due to the (wrong) ep target setting which already disappears with 1...Nc6.

Sven

With respect to transpositiontable cutoff this is no big deal.

Basically we're for example dealing with the position:

P position after e4 c6 e5 d5 versus P' is position after e4 d5 e5 c6

If in position P you look in hashtable and find that P' is there and lowerbound. Now you can safely give a cutoff there.

Vincent