Performance issue with can_claim_threefold_repetition()

[QueensGambit]

Hey Niklas Fiekas,
thanks again for your awesome library!

Before releasing CrazyAra 0.3.0, I did some profiling on the MCTS search using python's line_profiler.
Here I noticed that the method board.can_claim_threefold_repetition() consumes surprisingly much computation time. It took about a third computation time of the full search at some point.

Therefore, I wrote can_claim_threefold_repetition() for the MCTS search.
https://github.com/QueensGambit/CrazyAra/blob/master/DeepCrazyhouse/src/domain/agent/player/MCTSAgent.py
My implementation seems to work fine for the use-case of MCTS search running with multiple workers
and it triggered in one match with the great Crazyhouse Player IM gsvc last week.
https://lichess.org/DSkZacYn#56
but it's too specific to be used in python-chess.

I know that it's not Python-Chess primary intention to be used for chess engines, but I thought I could be useful for others to have a look at the method again.
The main issue appears to recreating the transposition table each time and the call of generate_legal_moves().
Do you have ideas to improve this without slowing down the board.push(move) method?

I found an interesting blog post about 3-fold-repetition:

• https://chess.stackexchange.com/questions/17127/programming-the-three-fold-repetition-for-my-chess-engine
  which refers to the official Stockfish implementation:
• https://github.com/official-stockfish/Stockfish/blob/master/src/position.cpp

Best wishes,
~QueensGambit

[rpdelaney]

There might be interference between this and #259 in both directions, if the latter is ever implemented.

[niklasf]

Earlier versions (v0.16.x) were maintaining an incremental transposition table as the board was updated, very similar to Stockfish's implementation. However it was incurring significant overhead for everyone that was not using it (most people, as far as I can tell), which is why I removed it.

I tried tweaking the current code.

• First check the board state stack for maybe-repetitions.
• Only if maybe-repetitions exist, replay the positions and see if they are really identical (en passant legality, castling rights).

That was giving a speedup around 25% in your test position, but I am not convinced it's worth the extra code, because it's still so slow that anything engine-like would probably want to implement their own version.

Orthogonally, it would also be possible to provide is_threefold_repetition() (!= can_claim_threefold_repetition()) which only checks the current position, rather than the possibility to claim because of the following move. I imagine that would be quite a bit faster.

[QueensGambit]

I agree that incremental transposition table would mean an overhead for most people and that engine people usually want to implement their own versions.
For earlier version I added an option to chose if the state should be remembered:

board.push(move, remember_state=False) 
board.push_san('e2e4', remember_state=False) 

But this would affect core methods of your library.
Alternatively, one could set the option remember_states in the constructor of the board.
By default this variable is set to False so people don't have to bother about it.

board = chess.Board(remember_states=False)

Adding python is_threefold_repetition() is also an option.
I think all these proposols have in common that they might confuse people at first sight.

So I think it's reasonable to keep it as is, too.
However, I think it's helpful to extend the documentation of the methods board.is_draw() and board.can_claim_threefold_repetition() by making clear that they iterate through the whole move stack and also call board.generate_legal_moves().

This way people know about this much quicker and can implement their own version if they see the need for it.

[niklasf]

Alright, so lets keep it simple for now.