Transposition tables and move evaluation, questions/advice

[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...

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.

Not so fast. Suppose I find a repetition that occurs a couple of plies deeper in the tree, and when I get back to this point I store score=draw. But when I reach this position again, except that now an ep capture is possible, I again would use that entry that says "draw" and it would be wrong.

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

No you can't. A position where an EP is possible is different from one where it is not possible. My early legal move generator had this bug and did not recognize the fact that an EP capture can be a check evasion move because the pawn moves to an odd square that blocks the check where without the ep possibility, the check could not be blocked. Both Kim Commons and Brian Hartmann found this bug in an early version of Crafty playing on ICC. It was not that common, but it was happening in more than one game out of a hundred until I fixed it.

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

Nice hand-wave, but the two positions are not equal. We already have this problem surfacing with 5-piece endgame tables and it does make a difference.

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

I'm not going to knowingly use something that has an obvious flaw I can see. There are too many other places to go wrong unintentionally, to risk adding to this by ignoring ep or castling. Shoot, why not ignore side to move as well as you will get more hash hits. Particularly in fine 70.

[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.

Not so fast. Suppose I find a repetition that occurs a couple of plies deeper in the tree, and when I get back to this point I store score=draw. But when I reach this position again, except that now an ep capture is possible, I again would use that entry that says "draw" and it would be wrong.

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

No you can't. A position where an EP is possible is different from one where it is not possible. My early legal move generator had this bug and did not recognize the fact that an EP capture can be a check evasion move because the pawn moves to an odd square that blocks the check where without the ep possibility, the check could not be blocked. Both Kim Commons and Brian Hartmann found this bug in an early version of Crafty playing on ICC. It was not that common, but it was happening in more than one game out of a hundred until I fixed it.

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

Nice hand-wave, but the two positions are not equal. We already have this problem surfacing with 5-piece endgame tables and it does make a difference.

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

I'm not going to knowingly use something that has an obvious flaw I can see. There are too many other places to go wrong unintentionally, to risk adding to this by ignoring ep or castling. Shoot, why not ignore side to move as well as you will get more hash hits. Particularly in fine 70.

Using bugs in crafty as an excuse why it wouldn't be able to work is no good generic argumentation, that's only specific to crafty.

Further there is no flaws in it and i'm not ignoring anything. It's just getting the maximum out of it. We both doubt whether it gives any speedup of course, as at 1000 cycles a node losing a bunch of cycles to code you usually do not use is going to be pricy. ANY enhancement that is tiny is a problem in that case.

[Sven]

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

Vincent,
you may be right of course but I was not talking about transposition table but only about 3-fold rep detection (therefore more about correctness in play than about search), in reply to posts of Greg and Wylie. I.e. I was not on the "PV" of this thread

Sven

[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...

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.

Not so fast. Suppose I find a repetition that occurs a couple of plies deeper in the tree, and when I get back to this point I store score=draw. But when I reach this position again, except that now an ep capture is possible, I again would use that entry that says "draw" and it would be wrong.

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

No you can't. A position where an EP is possible is different from one where it is not possible. My early legal move generator had this bug and did not recognize the fact that an EP capture can be a check evasion move because the pawn moves to an odd square that blocks the check where without the ep possibility, the check could not be blocked. Both Kim Commons and Brian Hartmann found this bug in an early version of Crafty playing on ICC. It was not that common, but it was happening in more than one game out of a hundred until I fixed it.

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

Nice hand-wave, but the two positions are not equal. We already have this problem surfacing with 5-piece endgame tables and it does make a difference.

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

I'm not going to knowingly use something that has an obvious flaw I can see. There are too many other places to go wrong unintentionally, to risk adding to this by ignoring ep or castling. Shoot, why not ignore side to move as well as you will get more hash hits. Particularly in fine 70.

Using bugs in crafty as an excuse why it wouldn't be able to work is no good generic argumentation, that's only specific to crafty.

Further there is no flaws in it and i'm not ignoring anything. It's just getting the maximum out of it. We both doubt whether it gives any speedup of course, as at 1000 cycles a node losing a bunch of cycles to code you usually do not use is going to be pricy. ANY enhancement that is tiny is a problem in that case.

The idea is simply bad. I can easily change my hashing to ignore EP and castling and run a cluster test to see what the effect is...

[Don]

Peter,

Until recently, my program uses a separate piece square table for each pawn structure. And each was stored in a pawn structure hash table. This is pretty doable on modern machines. I gave this up because there are too many downsides.

First of all, you cannot incrementally update your scores from the piece square tables because they change on you every time a pawn moves or is captured. You can of course still incrementally update if you recompute when the pawn structure changes.

The other down-side is that it's pretty memory hungry, depending on how large you set your pawn structure hash table. I did not seem to have any caching issues, but in principle I try not to unduly waste memory.

The worst downside, however, is that this is still a poor substitution for dynamic evaluation. You still have to do mobility, or something equivalent. What I did was do mobility with respect to pawns and build this right into the piece square table.

But the piece square tables when done this way does not know about which stage of the game you are in. My solution was to have 3 game stages but that requires a separate calculation and table entry for each stage. So that is even heavier.

Processing a piece square table is pretty expensive, even when hashed. Mobility (with respect to pawns) turned out to be quite expensive because you have to plug in a value for each of 64 squares. So unless your pawn structure hash table hit rate is really high it starts getting a little dicey.

I eventually concluded that it was a fun experiment, but was not the way to go.

Hi everybody, I am working on my own chess program, and I would like to ask for your opinions/advice.

Firstly, I was wondering whether it is worth checking no-en-passant and poorer-castling-rights in the transposition table look up. The reason I ask is that I reckon that an en-passant target rarely contributes to the value of a position for the side to move -- so all you're doing by including en-passant is cutting off access to entries in the table that could provide valuable information. As for castling rights, these probably add more value -- but it might still be useful to see the best move/score without castling rights.

Do you think it would be worth the cost to check no-en-passant-target and similarly, poorer-castling-rights positions in the transposition table to see if they produce cut-offs? -- it would cost up to three extra look-ups -- since you'd want to check the position without en-passant, the position without QS-castle and without KS-castle (provided the position had these features) -- which you could do just by xor-ing them out of the Zobrist key. Has anyone experimented with this kind of thing?

My second question is about move evaluation. At the moment I'm just using an extremely simple evaluation that only includes material and piece-square values (which I found here) which I have incorporated into a single array so I can evaluate moves without making them. I would like to know if anyone has experimented with dynamically modifying piece-square tables during the search in order to coax the emergence of more nuanced positional evaluation that is static piece-square tables can't do. The kind of system I have in mind is that each time the search function hits a new node, it increments the scores in the piece-square table of the last few moves that led to the currently search position. This would put a higher value on 'hot' squares, that are continually being attacked and defended -- over 'cold' squares, that may otherwise have been overvalued by static piece-square tables.

The main problem with this I think will be choosing the increment value -- too little and it would have no effect; too much and the positive feedback will send the search function on a wild goose chase. Other problems are of when to decrement piece-square scores, so that the table remains fairly normalized; and the fact that a given move will no longer have a 'unique' score, as it will change over time -- which could cause some tricky integration with transposition tables.

Anyway thanks for listening. If you have tried anything similar to what I've talked about (or if you think it has no chance of working ) I would be very grateful if you could tell me about it. Unfortunately I'm learning to program as I'm learning to program chess, so actual implementation is a while off. I have to say though that it has been enormously good fun so far.

ps. quick technical question -- in piece_array[64], should I be using chars to save memory, or ints for speed?

[Aleks Peshkov]

Processing a piece square table is pretty expensive, even when hashed. Mobility (with respect to pawns) turned out to be quite expensive because you have to plug in a value for each of 64 squares.

Your solution sounds very interesting. However you can be lazy and do not calculate evaluation of all squares for all pieces prematurely.
...
The more I think, the more I like it. I wanted to make my pseudo-mobility (safe mobility on the chess board filled by only pawns) evaluation incremental, but it was difficult to manage. Hashing should solve all my troubles.

[Don]

Processing a piece square table is pretty expensive, even when hashed. Mobility (with respect to pawns) turned out to be quite expensive because you have to plug in a value for each of 64 squares.

Your solution sounds very interesting. However you can be lazy and do not calculate evaluation of all squares for all pieces prematurely.

This is probably a good idea. You can do it on a per table basic, or a per square basis. But it will slow down incremental updating because you will first have to test whether your data sources (the piece square table entries involving this move) have been processed. For instance if I move Nc3 x Bd5 I have to check Nc3, Nd5 and Bd5 to see if I need to "process" them. So I will need an additional data structure or else a sentinel value to be stored on those square that have not been processed.

It might be worth it since I expect to only touch a fraction of the squares for any pawn structure / piece /color combination.

Or I can just update the whole table for a given piece just when I know I need to. It may be the bishops have been traded off and it's silly to build the bishop table if I never use it.

[Aleks Peshkov]

Don,
I wanted to have pseudo-attack tables to determine which piece need incremental reevaluation.

But as hash table save most calculations in memory, I think it is much easier to recalculate all existing pieces (on squares they actually stay) on a new pawn configuration. Yes, all other squares would be initialized with default sentinel UNKNOWN value.