Transposition tables and move evaluation, questions/advice

[pete205]

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?

[mcostalba]

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.

Normally it is the history table that takes in account this.

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

int for SIMPLICITY and because is the natural choice for storing a number if there are not very serious reasons to do otherwise....but I don't see them.

P.S: Saving 64*4 - 64 = 192 bytes won't take you very far.

[pete205]

Normally it is the history table that takes in account this.

Ah ok, just googled it, it seems to make sense -- is it effective though?

The system I proposed is slightly different since I'm only considering piece-type and to-square rather than the to-square and from-square that the history table considers -- although it might make no difference.

[bob]

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?

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.

[pete205]

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.

[Harald]

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?

I would not rely on that very much since the hashed values are not only
the score of the immediate position but also the result of a whole search.
That can depend on the small difference sometimes. You have to avoid
such errors.

Another thougt: The castling rights will disappear very soon in a game
for both sides. After that there will be no difference and every special
code is wasted.

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.

Yes I thought or may be dreamt of it for a short moment in the last few
days (nights). But with full consciousness I discarded the idea.
Though either one of us is reading the other one's thoughts or dreams.
Since I am surely innocent, please stop it!

Has anybody else noticed this lately? People asking questions and
announcing ideas that you were working on yourself at that time?
Is telepathy increasing in a global scale? Morphogenetic fields?
World wide consciousness? Enlightening at year 2012?

Harald

[bob]

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.

That's exactly the same thing I mentioned, when you think about it. If you use a position that doesn't really match the current position, you invite trouble. Not to mention the overhead of doing 3 extra probes each time (or actually 16 if you want to test each possibility independently...

[Edmund]

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

Many engines only set the en-passant square if it is actually threatened by an opponent pawn. In this case it very often contributes to the value of a position.

I can't imagine that it would occur frequently in the same tree that king and rooks are standing on their initial squares with changing castling rights.

Anyway you cannot say whether one of these rights is beneficial or not. Most of the cases its of cause beneficial to be allowed to capture en-passant or castle, but similar to the nullmove-observation, in certain zugzwang positions it might even be a bad choice. So you better not use values from one hash entry for the position with a certain right toggled. With TTmoves its different, I think there is nothing wrong with trying a it if it is available. The only problem is the time it takes to probe 2 or more TT entries.

[pete205]

Many engines only set the en-passant square if it is actually threatened by an opponent pawn. In this case it very often contributes to the value of a position.

Ah that makes a lot more sense -- that addresses the problem I was having with having to store 'useless' en-passants that were blocking access to TT entries.

[Fguy64]

Many engines only set the en-passant square if it is actually threatened by an opponent pawn. In this case it very often contributes to the value of a position.

Ah that makes a lot more sense -- that addresses the problem I was having with having to store 'useless' en-passants that were blocking access to TT entries.

The first thing that occurs to me is that the act of deciding whether or not a square is attacked by a neigboring pawn is more work than just setting an ep flag when a pawn moves two squares and be done with it. Given that I don't really know what's going on here, I probably have missed the point of this exchange.

p.s my knowledge of "proper" chess algorithms is limited.