Board claims threefold where not the case (for position hashing)

[dlbbld]

The board claims a threefold at the end of the game, but this is only a twofold repetition. The reason is the position hashing, which treats different positions here as the same.

final PgnHolder pgn = new PgnHolder("test.pgn");
pgn.loadPgn();
final Game game = pgn.getGames().get(0);
game.loadMoveText();

final Board board = new Board();
for (final Move move : game.getHalfMoves()) {
  board.doMove(move);
}
System.out.println(board.isRepetition()); // prints true but is only twofold repetition

test.pgn.txt

[dlbbld]

Here the example shortened to 40 moves, showing that it is not necessary to make 341 moves to trigger the problem. 40 moves can already be enough. test_shortened.pgn.txt

[bhlangonijr]

I will have a look. Thank you.

[bhlangonijr]

Can you check this one with version 1.2.2? There was an issue in the hash key generation (it was actually using same key for different piece-square table).

[dlbbld]

I will have a look. I'm a mathematician and familiar with the concept of hash functions. It is something sophisticated to check position repetition and as encountered here, quickly leads to bugs. How can it be checked that:

• the implementation of the hash function is now correct, and
• the key length is chosen such that the chance of different positions get the same hash is as "rare" as it should be?

For Stockfish, they are not relying on the hash only per my understanding. They rely on the full known board state registered, which gives some extra "bits".

My idea for the problem is as below:

• Add the position repetition without hash and integrate it in tests. Otherwise, the chance of finding hash problems is very low.
• Give the end-user the chance to avoid the hash by supplying a command-line argument.

[dlbbld]

I cannot build 1.2.2. The tests do not pass. Can you please check and come back on the below message?

Tests run: 16, Failures: 0, Errors: 2, Skipped: 0, Time elapsed: 1.608 sec <<< FAILURE!
testUtf8(com.github.bhlangonijr.chesslib.PgnHolderTest)  Time elapsed: 0.009 sec  <<< ERROR!
com.github.bhlangonijr.chesslib.pgn.PgnException: Error parsing PGN[1, ]: 
    at com.github.bhlangonijr.chesslib.pgn.GameLoader.loadNextGame(GameLoader.java:245)

[bhlangonijr]

This is what I get when running the tests:

Results :

Tests run: 73, Failures: 0, Errors: 0, Skipped: 0

Can you make sure there are no local changes? e.g. git reset --hard

[dlbbld]

It's a file encoding problem, I had that before (see #50). I uncommented the two mentioned test cases, then it works fine.

The above test works, but now other tests do not work anymore. I have tested the position hashing several times now, and it costs a lot of time. For me, a simple position check would do. As such, please implement the simple position check for testing, so that during testing, you can test the repetition count without hashing against the position count with hashing. Which, needless to say, must match.

So this will result in less work for me, as it will find some problems early, and surely a fair offer. Thanks!

Here two problems I found:

alekseenko_grachev_2017_ct-2563-2645-2017.10.1.pgn.txt Your API is calling a threefold after 60...Rb1 but this is only a twofold.

nikolic_arsovic_1989.pgn.txt Your API is calling a twofold after 129. Ra8 but this is not the case.

[bhlangonijr]

Ok, I will add the method to facilitate the testing. Would you share which tests are no longer working?

[dlbbld]

The two tests above before worked. There are two other PGN's which also have been ok before and do not work anymore, but I think that is the same problem.

For your testing, I added two other PGN's which might find problems early. If correct, the repetition count throughout all moves is one, no position repeats. Your API however currently flags repetitions.

no_repetition_1.pgn.txt no_repetition_2.pgn.txt

[dlbbld]

How is that going? As I said I meant this just for testing, this must not be in the public API. How you do this is, of course, your decision. But the hash is not working as is, that seems a challenging piece, I found other similar problems in the meantime.

[bhlangonijr]

Hi @dlbbld , There's a newer version out: 1.2.3 I am still working on the testing alternative APIs though. I should release it over the weekend.

[dlbbld]

Thanks for the feedback. The above test case nikolic_arsovic_1989.pgn.txt is still failing, but as you mentioned in progress. I'll check.

[bhlangonijr]

Hi @dlbbld , It looks we have a solid hashing function now. We are using a 64 bits long as the hash key instead of the previous short one. I have added a method Board#getPositionId() which should give you a reliable string id for every unique board setup. This is basically the FEN notation except we only add the en passant square if it allows the passed pawn capture. There's a test named PgnHolderTest#testBoardHashKeyConsistency() which you can feed any big PGN file and it will walk through all the games and positions checking for the consistency between the reliable position id and the full hash key generated for it by using Board#getZobristKey(). The board history is based on the zobrist hashing key, as you may know.

Please see new release version 1.2.4

would you have a look? Thank you Ben

[dlbbld]

Thanks, I'll try to find my way through and report anything I found.

[dlbbld]

I run the examples and for them no hash collision occurred. Board#getPositionId() is ok and PgnHolderTest#testBoardHashKeyConsistency() looks very reasonable to me. I run one large file and no hash collision was indicated. So for what I can say it looks ok.

[dlbbld]

I am not sure after second thought if my test results are correct. Particularly I am fighting with Board.isRepetition(int), I need a repetition count for testing. Can you think of providing a method for the repetition count in the future?

[bhlangonijr]

How does the work? A method that takes a move list and count the number of repetitions for each position?

[dlbbld]

Just the number of repetitions arising after the last move. The required code can be extracted from Board.isRepetition(int). As the code is optimized, this is a bit tricky now. So a method giving the actual repetition count, so three if there is a threefold repetition. Such a method allows checking for "twofolds" as well, which increases test coverage enormously.

[dlbbld]

I have found another bug which made my test results completely useless, for it can result in wrong positives, it can falsify the tests.

This bug #55 passes all your tests; please check how that is possible. This must be catched.

I was performing all the legal moves to check if there is a threefold repetition, see can_claim_threefold_repetition() in #41. But then suddenly repetition results became completely off. It took me hours to find the cause for this problem.

Finally, I found that this is related to undoing a move. I created another issue for this, #55, though it all goes together with the ambitious approach of using a hash for repetition detection.

[dlbbld]

I ran a few tests on 1.2.5. and these few tests look ok.