hgm wrote:Just the opposite, right? They do detect false repetitions when you exchange two unequal pieces, as they only consider square occupancy, and thus implicitly consider all pieces equal. This could be fixed by not incrementing the square counters by 1, but by a piece-type-dependent number. This would require storing of the piece type in the move list, however.
That's even worse than what I thought: not only colors but also piece types are not considered.
I think there is still nothing substantially better for repetition detection than the current "state of the art" approach of comparing hash keys for ply-4, ply-6, ... until the 50 moves counter is reached.
hgm wrote:Just the opposite, right? They do detect false repetitions when you exchange two unequal pieces, as they only consider square occupancy, and thus implicitly consider all pieces equal. This could be fixed by not incrementing the square counters by 1, but by a piece-type-dependent number. This would require storing of the piece type in the move list, however.
Yes, you are right. So this gnu chess aproach is really buggy.
Indeed, keys are superior. Especially if you already have calculated them for other purposes.
Whether performing a linear search through the list is the optimal method is debatable, though. Organizing them in a small hash table that stores (key, count) pairs (where count is the number of times the position occurred, i.e. an entry with count=0 is empty). Even with only 64 entries in the table the table would almost always be mostly empty, so that your first probe in it would already hit on a position with count=0, proving the current position is not a repetition. If you hit upon a non-zero count you step through the table with the usual linear search until you reach a zero count or a matching key. (And without a match you would use the entry where the search ended to store the key of the new position with count=1.) If you want to discard null-move-spanning repeats, the table would have to record the ply level of the latest occurrence of that position, which you would have to compare to your current level minus irreversible move counter.
Especially in variants where there are no irreversible moves (such as Crazyhouse), this gives a huge gain.
hgm wrote:Indeed, keys are superior. Especially if you already have calculated them for other purposes.
Whether performing a linear search through the list is the optimal method is debatable, though. Organizing them in a small hash table that stores (key, count) pairs (where count is the number of times the position occurred, i.e. an entry with count=0 is empty). Even with only 64 entries in the table the table would almost always be mostly empty, so that your first probe in it would already hit on a position with count=0, proving the current position is not a repetition. If you hit upon a non-zero count you step through the table with the usual linear search until you reach a zero count or a matching key. (And without a match you would use the entry where the search ended to store the key of the new position with count=1.) If you want to discard null-move-spanning repeats, the table would have to record the ply level of the latest occurrence of that position, which you would have to compare to your current level minus irreversible move counter.
Especially in variants where there are no irreversible moves (such as Crazyhouse), this gives a huge gain.
I think I don't fully comprehend. Am I getting your right?
You have a list of hash values as well as a small (64 entries) transposition table.
When you make a move on the board you try to skip the linear search through the list if the count of the tt entry on slot (hash & 63) is either 0 or 1. 0 meaning no repetition, 1 meaning either repetition or not depending on whether the keys match.
When you make a valid move, you add the new key to the list. If the tt entry slot is count 0 you add the key and make count 1; if count > 0 you increment count.
int gen_moves(int is_rook, uint32_t * stack, int offset, int from)
{
mt_node node;
int piece;
int side;
int to;
int x;
x = offset;
side = WHITE;
node = move_head[is_rook][from];
do {
to = node->to;
stack[x] = from | to << 6;
x += !(board[to] & side);
node = node->next[board[to] != NP];
} while (node);
return x;
}
Matthew:out
I don't know what should do this code but i would change the do...while loop this way:
// global
struct {
int64 key;
int ply;
} repTab[150];
// In Search:
if(reversibleMoveCnt > 3) {
for(i=hashKey&127; repTab[i].ply; i++) {
if(repTab[i].key == hashKey) {
repetition = (repTab[i].ply >= ply - reversibleMoveCnt); // occurred after last null move
break;
}
} // leaves i at first empty slot
}
if(repetition) score = 0; else {
int previousOccurrence = repTab[i].ply;
repTab[i].key = hashKey;
repTab[i].ply = ply; // suppose ply counting is such that 0 never occurs
MakeMove();
score = -Search(...);
UnMake();
repTab[i].ply = previousOccurrence;
}
Note I did not bother to make the linear search through the hash table wrap (i = i+1&127), but just declared a bit larger table.
Clever idea. I missed the idea that you could save the index to the entry between repetition check and move make/unmake.
This should be faster than any list searches. (even though most engines have to keep their hash values in a list anyway, if they are not incrementally updating hash values on unmake)
The only problem I see remaining is your 150 bound. In chess you can get upto 100 halfmoves before the 50-move rule kicks in. so you can easily run into an out of bound error here.
// global
struct {
int64 key;
int ply;
} repTab[150];
// In Search:
if(reversibleMoveCnt > 3) {
for(i=hashKey&127; repTab[i].ply; i++) {
if(repTab[i].key == hashKey) {
repetition = (repTab[i].ply >= ply - reversibleMoveCnt); // occurred after last null move
break;
}
} // leaves i at first empty slot
}
if(repetition) score = 0; else {
int previousOccurrence = repTab[i].ply;
repTab[i].key = hashKey;
repTab[i].ply = ply; // suppose ply counting is such that 0 never occurs
MakeMove();
score = -Search(...);
UnMake();
repTab[i].ply = previousOccurrence;
}
Note I did not bother to make the linear search through the hash table wrap (i = i+1&127), but just declared a bit larger table.
Clever idea. I missed the idea that you could save the index to the entry between repetition check and move make/unmake.
This should be faster than any list searches. (even though most engines have to keep their hash values in a list anyway, if they are not incrementally updating hash values on unmake)
The only problem I see remaining is your 150 bound. In chess you can get upto 100 halfmoves before the 50-move rule kicks in. so you can easily run into an out of bound error here.
What about SMP search? During the split() operation you would need to copy the entire repetition hash structure. It is way more costly than to copy just a few entries from a list of keys (since long chains of reversible moves are rare in the search tree, most of the time the rule50 counter is some small value, say <= 10).
