A new idea for fast repetidion detection?

[mario carbonell]

I'm not aware if this idea existed, checked in the CPW and no mention.

The key idea is that if a white piece moves to a square that no other white piece has been, it cannot be a repetition, so no need to check.

So a fast implementation would be with 2 historic occupancy bitboards, for white and black. The white occupancy bitboard would store one bit for every square that a white piece has been since the last reset of the repetition counter. If a white piece moves to a square that has the historic occupancy of white pieces to zero, it cannot be a repetition.

So for example, from the initial position

0. Initialize historic occupancy for white and black with the current position.
1. Nf3, the f3 bit was 0, no possible repetition, store 1 in f3 bit of white historic occupancy.
2. Nf6, the f6 bit was 0, no possible repetition, store 1 in f6 bit of black historic occupancy.
3. Ng1, the g1 bit was 1, so a possible repetition, but, we need 2 posible repetitions in a row, for white and black.
4. Ng8, the g8 bit was 1, so a possible repetition, now possible because white last white move was 1.
5. Do the normal repetition detection.

We still need the normal repetition detection, but the detection of false repetitions is much faster.

[phhnguyen]

IMHO, your algorithm could work!

I think it is somewhat similar to a method to trace down move by move even that (old) method didn’t use any bitmap (nor hash keys).

However, yours could not be faster than some much simpler ways. Look like you have to do some calculations and maintain a new bitmap, some checks and statuses for each moves. I doubt it could be faster than only-comparison hash keys for every two plies.

My code typically looks as below:

Code: Select all

n = histList.size();
i = n - 1;
key = histList.at(i).key;
k = n - quietCount;
for(i -= 2; i >= k; i -= 2) {
    if (key == histList.at(i).key) {
        // a repetition detected
    }
 }

[mario carbonell]

The overhead would be to maintain 2 new bitboards, next to the historic list of zobrist keys. You could simplify it with only one bitboard with the union of white and black pieces, but supposedly less accurate don't now by how much. You need to copy and update the bitboard on makemove to the next ply. The test for false repetitions only cost you one AND bit operation and can save you a loop with up to 49 comparisons with the hash keys, as listed in your code.

I didn't tested id, just had the idea last night and wanted to share it to see what you think.

[hgm]

I am not sure what you want to save on. Calculating the new hash key? Almost all moves will not be repetitions, and then you would have had to do that anyway. So the overhead caused by calculating the key as part of the repetition test is almost nothing. And updating the key isn't very expensive in the first place.

My repetition test typically looks like

Code: Select all

int index = newHaskKey & 255;
if(newHashKey == repTable[index]) {
  // a repetition is detected
  score = DRAW;
} else { // move must be searched
  Key saved = repTable[index];
  repTable[index] = newHashKey;
  ... // other MakeMove() / Search() / UnMake() stuff
  repTable[index] = saved;
}

Seems to me that this would already be much faster in total than what you propose as a filter for deciding if a more extensive test is needed.

[mario carbonell]

The historic bitboard of occupancies could have some other uses, as move ordering (to not make backward moves, to avoid repetitions) or some heuristic to encourage some sense of progress, to try to occupy new squares. If the popcount of the historic occupancies of some player does not increase, could be and indication of some kind of fortress or to be unable to make progress.

[mario carbonell]

I am not sure what you want to save on. Calculating the new hash key? Almost all moves will not be repetitions, and then you would have had to do that anyway. So the overhead caused by calculating the key as part of the repetition test is almost nothing. And updating the key isn't very expensive in the first place.

My repetition test typically looks like

Code: Select all

int index = newHaskKey & 255;
if(newHashKey == repTable[index]) {
  // a repetition is detected
  score = DRAW;
} else { // move must be searched
  Key saved = repTable[index];
  repTable[index] = newHashKey;
  ... // other MakeMove() / Search() / UnMake() stuff
  repTable[index] = saved;
}

Seems to me that this would already be much faster in total than what you propose as a filter for deciding if a more extensive test is needed.

So you are using a repetition hash table, in that case the benefit is very little if any, as the cost of probing the repetition in your case is O(1). The speed benefit would be if you have a repetition detection not based on a specialized hash table, but a list of zobrist keys.

[hgm]

So wouldn't it be much better to access that list of Zobrist keys through a hash rather than a linear search, rather than complicating things further by adding an additional filtering that in itself is already more expensive than the hash access?

[mario carbonell]

Ok, so if you are only concerned about the speed of rep check, surely there is no gain compared to a small dedicated repetition hash table, but I thought that was an idea worth of mentioning as there are no references on the literature and who knows what other ideas could come next? As I mentioned, could be used for ordering of move generation, encourage progress or fortress detection.

[hgm]

As to fortress detection, I don't really see what it offers extra over the increase of the ply counter. Wich is the more popular method that does not work either. The point is that it takes a lot of ply to reach a conclusion, and by the time you conclude you have a fortress it is already there in the game as well, and there is nothing you can do about it.

Fortresses are usually quite easy to detect directly. The problem here is not that there are no known algorithms, or that the algorithms are complicated or expensive. The problem is that no one bothers, because detecting fortresses doesn't bring measurable Elo.

[mario carbonell]

I cannot understand the obsession with Elo. For me is quite more enjoyable to try to solve unsolved problems, or solve them in a new and original way, than to to try gain a few Elo points repeating the same ideas over and over.