Implementing hash tables for Go looks problematic compared to chess for the following reasons.
- number of captured pieces are always associated with a certain position. Are those numbers hashed in to the key too ? Otherwise we can reach same positions in a tree with different number of capture counts.
- during ko fight we can have two different positons with different 'ko' status like the "enpassant square" chess. Alan Zobrist invented his scheme to detect this situation. Now to detect ko I didn't hash in the 'ko square' like we do "enpassant square'. If we did, we wouldn't be able to detect ko , so I have a special routine to detect this special case during hash table probe and skip the table value in case of sucidal move. I doubt if I am making any sense here
Daniel Shawul wrote:Implementing hash tables for Go looks problematic compared to chess for the following reasons.
- number of captured pieces are always associated with a certain position. Are those numbers hashed in to the key too ? Otherwise we can reach same positions in a tree with different number of capture counts.
- during ko fight we can have two different positons with different 'ko' status like the "enpassant square" chess. Alan Zobrist invented his scheme to detect this situation. Now to detect ko I didn't hash in the 'ko square' like we do "enpassant square'. If we did, we wouldn't be able to detect ko , so I have a special routine to detect this special case during hash table probe and skip the table value in case of sucidal move. I doubt if I am making any sense here
Any ideas ?
Sensible Go programmers don't use Japanese rules, so they don't need to count prisoners. Simple ko should be hashed, since it is so easy to detect. Superko is a bit more tricky, but there should be no need to worry too much about it in practice.
If you are going to write a Go program, maybe you should join the computer-go mailing list. And get ready to forget about alpha-beta. No alpha-beta program is strong.
For your first problem, this is similar to hashng in Crazyhouse and Shogi. You can have the same board position with other pieces in hand there. People use separate keys for board position and holdings, because it is important to recognize pseudo-repetitions, where you return to the same board position with fewer pieces in hand. It means you are in a loop that just burns pieces, which is guaranteed to be not good. Fewer pieces in hand is always worse, by at least the value of a piece in hand.
I guess you would have the same in Go. Same board position with more pieces captured is better by a known amount. So you store the board score with 0 pieces, and if you get a hit on it, correct the score for the number of captured pieces before you use it. A bit like some people correct mate scores.
