Closed dlbbld closed 3 years ago
There must be something wrong here. Probably only a small problem in the code, I can't see through, but there is something off.
In the first example, both players lose all castling rights by moving their kings. So the position after 5... Ke8 and the initial position are not the same. The position after 7... N8 is the same as after 5... Ke8, so this is a twofold repetition, but flagged as threefold.
// after loosing castling rights
final MoveList moveList = new MoveList();
moveList.loadFromSan("1. e4 e5 2. Nf3 Nf6 3. Ng1 Ng8 4. Ke2 Ke7 5. Ke1 Ke8 6. Na3 Na6 7. Nb1 Nb8");
final Board board = new Board();
final Iterator<Move> moves = moveList.iterator();
while (moves.hasNext()) {
board.doMove(moves.next());
}
System.out.println(board.isRepetition()); // true but should be false (repetition count is 2)
In the second example, there is a pawn two square advance involved. After 3... d5 capturing en passant is not possible. So this is the same position as after 5... Nf6 and 7... Nf6. See "9.2.2.1 at the start of the sequence a pawn could have been captured en passant" in the rules. 7... Nf6 is a threefold repetition but not flagged as such.
// after two square advance
final MoveList moveList = new MoveList();
moveList.loadFromSan("1. Nf3 Nf6 2. Nc3 c5 3. e3 d5 4. Be2 Ne4 5. Bf1 Nf6 6. Be2 Ne4 7. Bf1 Nf6");
final Board board = new Board();
final Iterator<Move> moves = moveList.iterator();
while (moves.hasNext()) {
board.doMove(moves.next());
}
System.out.println(board.isRepetition()); // false but should be true
For the third example, I chose a real game mentioned in Wikipedia. Wikipedia states that there is a threefold repetition after 38... Kf8. But this is not flagged as threefold. Again there is a pawn two square advance at the beginning of the sequence. But because there is no en passant capture possible the positions after 34...h5 36...Kf8 and 38...Kf8 are the same, which gives the threefold repetition after 38...Kf8.
// capablanca - lasker 1921
final MoveList moveList = new MoveList();
moveList.loadFromSan(
"1. d4 d5 2. Nf3 Nf6 3. c4 e6 4. Bg5 Nbd7 5. e3 Be7 6. Nc3 O-O 7. Rc1 b6 8. cxd5 exd5 9. Qa4 c5 10. Qc6 Rb8 11. Nxd5 Bb7 12. Nxe7+ Qxe7 13. Qa4 Rbc8 14. Qa3 Qe6 15. Bxf6 Qxf6 16. Ba6 Bxf3 17. Bxc8 Rxc8 18. gxf3 Qxf3 19. Rg1 Re8 20. Qd3 g6 21. Kf1 Re4 22. Qd1 Qh3+ 23. Rg2 Nf6 24. Kg1 cxd4 25. Rc4 dxe3 26. Rxe4 Nxe4 27. Qd8+ Kg7 28. Qd4+ Nf6 29. fxe3 Qe6 30. Rf2 g5 31. h4 gxh4 32. Qxh4 Ng4 33. Qg5+ Kf8 34. Rf5 h5 35. Qd8+ Kg7 36. Qg5+ Kf8 37. Qd8+ Kg7 38. Qg5+ Kf8");
final Board board = new Board();
final Iterator<Move> moves = moveList.iterator();
while (moves.hasNext()) {
board.doMove(moves.next());
}
System.out.println(board.isRepetition()); // false but should be true
Should I not overlook something, there is something missing here and your API could improve greatly by addressing this. The method board.isRepetition()
says in the code Verify threefold repetition
so is definitely meant for threefold repetition detection!
Hi @dlbbld , thanks for pointing that out. This is a bug in the zobrist incremental hash calculation which I've fixed. It should go in the next release.
Hi Carlos Cool, thanks for checking this. Daniel
Hey @dlbbld Daniel, an interesting situation arose after fixing it. The example you shared 1. e4 e5 2. Be2 Be7 3. Bf1 Bf8 4. Bd3 Bd6 5. Bf1 Bf8
is still not flagged as threefold repetition even after the fix. The reason is by moving king's pawn in the opening creates intermediate positions that are not counted as repetitions because these enabled en passant on e6
and e3
. These positions are not really the same really, see the FEN for each one:
1. e4 e5 :
rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNR b KQkq e3 0 1
rnbqkbnr/pppp1ppp/8/4p3/4P3/8/PPPP1PPP/RNBQKBNR w KQkq e6 0 2
2. Be2 Be7:
rnbqkbnr/pppp1ppp/8/4p3/4P3/8/PPPPBPPP/RNBQK1NR b KQkq - 1 2
rnbqk1nr/ppppbppp/8/4p3/4P3/8/PPPPBPPP/RNBQK1NR w KQkq - 2 3
3. Bf1 Bf8
rnbqk1nr/ppppbppp/8/4p3/4P3/8/PPPP1PPP/RNBQKBNR b KQkq - 3 3
rnbqkbnr/pppp1ppp/8/4p3/4P3/8/PPPP1PPP/RNBQKBNR w KQkq - 4 4
4. Bd3 Bd6
rnbqkbnr/pppp1ppp/8/4p3/4P3/3B4/PPPP1PPP/RNBQK1NR b KQkq - 5 4
rnbqk1nr/pppp1ppp/3b4/4p3/4P3/3B4/PPPP1PPP/RNBQK1NR w KQkq - 6 5
5. Bf1 Bf8
rnbqk1nr/pppp1ppp/3b4/4p3/4P3/8/PPPP1PPP/RNBQKBNR b KQkq - 7 5
rnbqkbnr/pppp1ppp/8/4p3/4P3/8/PPPP1PPP/RNBQKBNR w KQkq - 8 6
So you need to give it some more rounds to effectively trigger the repetition flag:
1. e4 e5 2. Be2 Be7 3. Bf1 Bf8 4. Bd3 Bd6 5. Bf1 Bf8 6. Bd3 Bd6 7. Bf1 Bf8
Also In Capablanca - Lasker 1921 game chesslib has not flagged it as a threefold repetition because move 34.. h5
creates an en passant square in h6
:
34 - h5 ... = 5k2/p4p2/1p2q3/5RQp/6n1/4P3/PP6/6K1 w - h6 0 35
I assume en passant is not accounted for when calling out three fold repetition. If I remove it though it creates another problem when doing other things. Tricky situation here...
Fixed in 1.1.24
En passant rule is very much accounted in the repetition rule, but only the case where en passant capture is possible. Two square pawn advance has no meaning unless after it en passant capture is possible.
So as the FEN only indicates two square pawn advance it cannot be used for checking the en passant condition. The en passant target square in the FEN is only relevant for the repetition rule when starting from a position. If the last move was a two square pawn advance is important to know for the repetition rule, and when starting from a position only the FEN has this information.
There are also situations for a two square pawn advance where an opponent pawn is on the same rank, but cannot capture due to own king already being in check or capturing would expose own king to check.
In these situations, en passant capture is not possible. So the position after the two square pawn advance and later visually same positions are considered the same by the rule. Please check the examples below.
// en passant capture not possible for own king in check
final Board board = new Board();
board.loadFromFen("8/8/8/8/4p3/8/R2P3k/K7 w - - 0 37");
board.doMove(new Move(Square.D2, Square.D4)); // initial position - two square pawn advance
board.doMove(new Move(Square.H2, Square.H3)); // en passant capture not possible - own king in check
board.doMove(new Move(Square.A2, Square.A3));
board.doMove(new Move(Square.H3, Square.H2));
board.doMove(new Move(Square.A3, Square.A2)); // twofold repetition
board.doMove(new Move(Square.H2, Square.H1));
board.doMove(new Move(Square.A2, Square.A3));
board.doMove(new Move(Square.H1, Square.H2));
board.doMove(new Move(Square.A3, Square.A2)); // threefold repetiton
System.out.println(board.isRepetition()); // must be true
// en passant capture not possible for would expose own king to check
final Board board = new Board();
board.loadFromFen("6k1/8/8/8/6p1/8/5PR1/6K1 w - - 0 32");
board.doMove(new Move(Square.F2, Square.F4)); // initial position - two square pawn advance
board.doMove(new Move(Square.G8, Square.F7)); // en passant capture not possible - would expose own king to check
board.doMove(new Move(Square.G1, Square.F2));
board.doMove(new Move(Square.F7, Square.G8));
board.doMove(new Move(Square.F2, Square.G1)); // twofold repetition
board.doMove(new Move(Square.G8, Square.H7));
board.doMove(new Move(Square.G1, Square.H2));
board.doMove(new Move(Square.H7, Square.G8));
board.doMove(new Move(Square.H2, Square.G1)); // threefold repetiton
System.out.println(board.isRepetition()); // must be true
En passant rule is very much accounted in the repetition rule, but only the case where en passant capture is possible. Two square pawn advance has no meaning unless after it en passant capture is possible.
So as the FEN only indicates two square pawn advance it cannot be used for checking the en passant condition. The en passant target square in the FEN is only relevant for the repetition rule when starting from a position. If the last move was a two square pawn advance is important to know for the repetition rule, and when starting from a position only the FEN has this information.
There are also situations for a two square pawn advance where an opponent pawn is on the same rank, but cannot capture due to own king already being in check or capturing would expose own king to check.
In these situations, en passant capture is not possible. So the position after the two square pawn advance and later visually same positions are considered the same by the rule. Please check the examples below.
// en passant capture not possible for own king in check final Board board = new Board(); board.loadFromFen("8/8/8/8/4p3/8/R2P3k/K7 w - - 0 37"); board.doMove(new Move(Square.D2, Square.D4)); // initial position - two square pawn advance board.doMove(new Move(Square.H2, Square.H3)); // en passant capture not possible - own king in check board.doMove(new Move(Square.A2, Square.A3)); board.doMove(new Move(Square.H3, Square.H2)); board.doMove(new Move(Square.A3, Square.A2)); // twofold repetition board.doMove(new Move(Square.H2, Square.H1)); board.doMove(new Move(Square.A2, Square.A3)); board.doMove(new Move(Square.H1, Square.H2)); board.doMove(new Move(Square.A3, Square.A2)); // threefold repetiton System.out.println(board.isRepetition()); // must be true
// en passant capture not possible for would expose own king to check final Board board = new Board(); board.loadFromFen("6k1/8/8/8/6p1/8/5PR1/6K1 w - - 0 32"); board.doMove(new Move(Square.F2, Square.F4)); // initial position - two square pawn advance board.doMove(new Move(Square.G8, Square.F7)); // en passant capture not possible - would expose own king to check board.doMove(new Move(Square.G1, Square.F2)); board.doMove(new Move(Square.F7, Square.G8)); board.doMove(new Move(Square.F2, Square.G1)); // twofold repetition board.doMove(new Move(Square.G8, Square.H7)); board.doMove(new Move(Square.G1, Square.H2)); board.doMove(new Move(Square.H7, Square.G8)); board.doMove(new Move(Square.H2, Square.G1)); // threefold repetiton System.out.println(board.isRepetition()); // must be true
Fixed in 1.1.25
You overlooked that in the example with "losing castling rights" the expected result is false (no repetition). By the way you have added this test two times, as testThreefoldRepetition1()
and testThreefoldRepetition4()
. The castling rights in the different occurrences of the position changed, from full castling rights to no castling rights, so at the end there is only a twofold repetition.
The other cases above work, but a basic example with en passant capture possible does not work. Again it should not flag repetition, for in the first occurrence of the position en passant capture was possible, but later not.
// en passant capture possible
final MoveList moveList = new MoveList();
moveList.loadFromSan("1. e4 Nf6 2. e5 d5 3. Bc4 Nc6 4. Bf1 Nb8 5. Bc4 Nc6 6. Bf1 Nb8");
final Board board = new Board();
final Iterator<Move> moves = moveList.iterator();
while (moves.hasNext()) {
board.doMove(moves.next());
}
System.out.println(!board.isRepetition() ? "Success" : "Failure"); // Failure
Reopening the issue until this is solved in a later release.
You overlooked that in the example with "losing castling rights" the expected result is false (no repetition). By the way you have added this test two times, as
testThreefoldRepetition1()
andtestThreefoldRepetition4()
. The castling rights in the different occurrences of the position changed, from full castling rights to no castling rights, so at the end there is only a twofold repetition.The other cases above work, but a basic example with en passant capture possible does not work. Again it should not flag repetition, for in the first occurrence of the position en passant capture was possible, but later not.
// en passant capture possible final MoveList moveList = new MoveList(); moveList.loadFromSan("1. e4 Nf6 2. e5 d5 3. Bc4 Nc6 4. Bf1 Nb8 5. Bc4 Nc6 6. Bf1 Nb8"); final Board board = new Board(); final Iterator<Move> moves = moveList.iterator(); while (moves.hasNext()) { board.doMove(moves.next()); } System.out.println(!board.isRepetition() ? "Success" : "Failure"); // Failure
Hello @dlbbld ,
In this particular example the castle rights never changed and the same position repeated for 3 times, hence triggering the threefold repetition flag. Did I miss something?
final MoveList moves = new MoveList();
moves.loadFromSan("1. e4 Nf6 2. e5 d5 3. Bc4 Nc6 4. Bf1 Nb8 5. Bc4 Nc6 6. Bf1 Nb8");
final Board board = new Board();
for (Move move : moves) {
board.doMove(move);
System.out.println(board.hashCode() + "\t " + board.getFen());
}
assertTrue(board.isRepetition());
result:
-810608193 rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNR b KQkq e3 0 1
967731539 rnbqkb1r/pppppppp/5n2/8/4P3/8/PPPP1PPP/RNBQKBNR w KQkq - 1 2
1071432780 rnbqkb1r/pppppppp/5n2/4P3/8/8/PPPP1PPP/RNBQKBNR b KQkq - 0 2
2113493858 rnbqkb1r/ppp1pppp/5n2/3pP3/8/8/PPPP1PPP/RNBQKBNR w KQkq d6 0 3
-807948428 rnbqkb1r/ppp1pppp/5n2/3pP3/2B5/8/PPPP1PPP/RNBQK1NR b KQkq - 1 3
-2045144991 r1bqkb1r/ppp1pppp/2n2n2/3pP3/2B5/8/PPPP1PPP/RNBQK1NR w KQkq - 2 4
876045431 r1bqkb1r/ppp1pppp/2n2n2/3pP3/8/8/PPPP1PPP/RNBQKBNR b KQkq - 3 4
2113493858 rnbqkb1r/ppp1pppp/5n2/3pP3/8/8/PPPP1PPP/RNBQKBNR w KQkq - 4 5
-807948428 rnbqkb1r/ppp1pppp/5n2/3pP3/2B5/8/PPPP1PPP/RNBQK1NR b KQkq - 5 5
-2045144991 r1bqkb1r/ppp1pppp/2n2n2/3pP3/2B5/8/PPPP1PPP/RNBQK1NR w KQkq - 6 6
876045431 r1bqkb1r/ppp1pppp/2n2n2/3pP3/8/8/PPPP1PPP/RNBQKBNR b KQkq - 7 6
2113493858 rnbqkb1r/ppp1pppp/5n2/3pP3/8/8/PPPP1PPP/RNBQKBNR w KQkq - 8 7
TRUE
I see it, in the later case you are talking about en passant not castling. I am fixing this one.
Yes right, the example above is about en passant. As you already spotted, the repetition count does not go up to three. For despite having the same visual positions, in the initial position en capture is possible, later not, so the initial position does not go into repetition count.
The above test case still does not work:
// after loosing castling rights
final MoveList moveList = new MoveList();
moveList.loadFromSan("1. e4 e5 2. Nf3 Nf6 3. Ng1 Ng8 4. Ke2 Ke7 5. Ke1 Ke8 6. Na3 Na6 7. Nb1 Nb8");
final Board board = new Board();
final Iterator<Move> moves = moveList.iterator();
while (moves.hasNext()) {
board.doMove(moves.next());
}
System.out.println(!board.isRepetition() ? "Success" : "Failure"); // output is Failure
After 7... Nb8 the position should not be flagged as threefold by the API. The visual position A occurs four times, but of course, as castling right changes this are not four repetitions.
Very special for the castling rule is, that after each player's move, the castling rights of both players are looked at, not only the castling rights of one player. As for the possible future moves, both players castling rights matter, and the current and possible future moves must be the same, for the positions to be the same.
Besides the problem with castling mentioned above, there is also still a problem with en passant. In the real game below, the API flags the position after 51... Kd6 as threefold. Flagging this as threefold is wrong, because in the initial position after 47... f5 en passant capture is possible, so this does not count towards repetition. 51... Kd6 is only a twofold (49... Kd6 and 51... Kd6). Good luck in fixing this!
final MoveList moveList = new MoveList();
moveList.loadFromSan(
"1. Nf3 Nf6 2. c4 c5 3. b3 d6 4. d4 cxd4 5. Nxd4 e5 6. Nb5 Be6 7. g3 a6 8. N5c3 d5 9. cxd5 Nxd5 10. Bg2 Bb4 11. Bd2 Nc6 12. O-O O-O 13. Na4 Rc8 14. a3 Be7 15. e3 b5 16. Nb2 Qb6 17. Nd3 Rfd8 18. Qe2 Nf6 19. Nc1 e4 20. Bc3 Nd5 21. Bxe4 Nxc3 22. Nxc3 Na5 23. N1a2 Nxb3 24. Rad1 Bc4 25. Qf3 Qf6 26. Qg4 Be6 27. Qe2 Rxc3 28. Nxc3 Qxc3 29. Rxd8+ Bxd8 30. Rd1 Be7 31. Bb7 Nc5 32. Qf3 g6 33. Bd5 Bxd5 34. Qxd5 Qxa3 35. Qe5 Ne6 36. Ra1 Qd6 37. Qxd6 Bxd6 38. Rxa6 Bc5 39. Kf1 Kf8 40. Ke2 Ke7 41. Kd3 Kd7 42. g4 Kc7 43. Ra8 Kc6 44. f4 Be7 45. Rc8+ Kd5 46. Re8 Kd6 47. g5 f5 48. Rb8 Kc6 49. Re8 Kd6 50. Rb8 Kc6 51. Re8 Kd6");
final Board board = new Board();
@SuppressWarnings("null") final Iterator<Move> moves = moveList.iterator();
while (moves.hasNext()) {
board.doMove(moves.next());
}
System.out.println(!board.isRepetition() ? "Success" : "Failure"); // output is Failure
Can you please check and reopen this issue? The issue is about game termination and so of course, critical. It is not so easy to get these things right; this not only concerns your API. I found a bug (fixed) in python-chess regarding insufficient material. Then another bug (fixed) in Lichess and one more (not fixed) in chess.com, last two regarding threefold repetition rule. These are major API's. Still, as the examples show, it is possible to have bugs.
Would you test again? Fixed in version 1.2.1.
My pleasure... I found the repetition checks now all ok. However, I find it dubious using a hash for the position (Zobrist), so as I understand on the extreme two different positions can evaluate as the same. How do you deal with this?
My pleasure... I found the repetition checks now all ok. However, I find it dubious using a hash for the position (Zobrist), so as I understand on the extreme two different positions can evaluate as the same. How do you deal with this?
I think you are talking about hash collisions - which will give the same key for two different positions - but these occur very rarely, especially for such use case where you incrementally update the key based on the move and flag changes. Besides, using zobrist is cost-effective: There are several use cases where you have to check for repetition millions of times as when you are traversing a game tree, which by using a more "reliable" ways wouldn't be feasible. Moreover, most strong chess engines and chess software are relying on the same technique when checking for repetitions. Check Stockfish out, as an example.
But that would be low occurrence versus high impact. I don't think this is done in this way. For position evaluation, yes. But not for determining the game result upon a player move. That is allowing draw for threefold or auto drawing for fivefold (this is a must draw since 2014). Even when the chance is very low, the last a chess software wants to do is falsify the output of a game.
When a chess engine is traversing the game tree EVERY node (chessboard state) is checked for repetitions so the search over a specific subtree can return earlier with a draw score, in case it is detected. I fail to see the difference between "position evaluation" and "determine the game result upon a player move", as the player move will result on some position to be evaluated after all - position being a discrete representation of the game state after any arbitrary move is played. Every simulation/evaluation done when searching a chess tree is about determining the game result of any given position, it's not like it's something completely unrelated. Incorrectly determining repetitions on intermediate nodes is leading the search to an unreliable state for all the subsequent subtree. The impact is very high as you can see. Nonetheless, most chess engines are using Zobrist as means of identifying chess positions and making comparisons between them. When we say "collisions are very rare" it's not like it happens every now and then or even once in a while: Rare is used as in "theoretically possible" with almost scientific rigour. The strongest chess software/engine in the world is using this very same technique for no other reason.
To cut a long story short I made an example (#48) where the board calls a threefold (which is only a twofold) after 341 moves. So this is a collision, and after 341 moves already this is not rare.
The distinction between the moves evaluated and moves performed is fundamental. If this problem occurs during move evaluation, it will result in most possibly not finding the "best" move, as you say. If the problem occurs when determining the result of the played move, you may terminate the game on no valid reason. The game will be invalid. I am not sure why you are not making the distinction between a chess engine and the chessboard. Your API is not a chess engine.
Stockfish is using a position hash, but Stockfish is an engine. The engine is queried for moves and should not decide about the game outcome. The software performing the moves must decide about the game outcome. That is again, my opinion stated before. For example, python-chess is not using position hashing. Python-chess is a chess API, not a chess engine, confirming the before mentioned.
There are two problems per my view. The first being that the position hash must have a problem, for occurrences should be "rare", at least so "rare" that the presented simple example should not be possible (that works with like 40 moves as well).
The second one, I am repeating myself now, position hash by nature is not suited to decide about actual game outcome.
To cut a long story short I made an example (#48) where the board calls a threefold (which is only a twofold) after 341 moves. So this is a collision, and after 341 moves already this is not rare.
The distinction between the moves evaluated and moves performed is fundamental. If this problem occurs during move evaluation, it will result in most possibly not finding the "best" move, as you say. If the problem occurs when determining the result of the played move, you may terminate the game on no valid reason. The game will be invalid. I am not sure why you are not making the distinction between a chess engine and the chessboard. Your API is not a chess engine.
Hi @dlbbld, firstly thank you for all the good feedbacks and suggestions.
chesslib is a chess API, indeed. But you can potentially build a chess engine on top of it e.g.: https://github.com/bhlangonijr/kengine.
I get your point about the reliability of determining the game result, but we have two problems here:
1) By replacing the method isRepetition
using some reliable non-hashed solution can dramatically slow it down, making it unfeasible for using inside a chess tree search like here
2) Adding an alternative slower version of the method is also an option, but wouldn't it make the API harder to understand?
PS: Are we sure issue #48 is related to hashing and not a bug in the code? I will have a look anyway.
Your considerations are necessary if you widen the scope. My scope is more limited in that respect: I expect from the API to behave only as a board, but a board with 100% accuracy.
We are sure that #48 is related to hashing. Two visually different positions get the same hash.
@dlbbld all tests passing now, version 1.2.4
would you have a look?
Thank you
The threefold repetition after 5... Bf8 for the below moves is not detected. Why is that the case? Can you please check? The positions, possibilities to capture en passant and castle rights after 1... e5, 3... Bf8 and 5... Bf8 are the same. This is a threefold repetition after 5... Bf8.