search

SebLague / Chess-Challenge

Create your own tiny chess bot!
https://www.youtube.com/watch?v=Ne40a5LkK6A
MIT License
1.77k stars 1.06k forks source link

Repetition detection bug #170

Open Firestorm-253 opened 1 year ago

Firestorm-253 commented 1 year ago

https://github.com/SebLague/Chess-Challenge/blob/385851a329499701ca0faa94d3de6fa1265a70c7/Chess-Challenge/src/Framework/Chess/Result/Arbiter.cs#L54C46-L54C46 triggers before https://github.com/SebLague/Chess-Challenge/blob/385851a329499701ca0faa94d3de6fa1265a70c7/Chess-Challenge/src/API/Board.cs#L159C13-L159C13 does. Can't prevent repetitional draw.. very annoying.

YesilHiyar commented 1 year ago

Happens to me too

ArtHell commented 1 year ago

I experience something similar. But in my case call board.IsDraw() returns True, when it's not draw yet.

Diamoundz commented 1 year ago

has anybody found a work around to this problem ?? this is really annoying when testing ...

Firestorm-253 commented 1 year ago

has anybody found a work around to this problem ?? this is really annoying when testing ...

nope sadly not

Firestorm-253 commented 1 year ago

@SebLague pls fix, bcs i can't continue and the commitment date gets closer <3

ginop commented 1 year ago

Why does the API use bool IsRepetition() => repetitionHistory.Contains(board.ZobristKey); instead of the version found in the Arbiter, which could be written bool IsRepetition() => board.RepetitionPositionHistory.Count((x => x == board.currentGameState.zobristKey)) == 3;?

It seems that the existing IsRepetition method only checks if this position exists in the repetition set, rather than if it is the third visit which results in a draw.

To complicate this, though, the RepetitionPositionHistory stack does not get updated when moves are made with isSearch = true which appears to always be the case in the API.

This is my first C# project, so I'm not confident enough in the side effects of just changing all of that to make a pull request just yet. I would love to see this bug fixed, though, as my bot always dives right into threefold repetition draws...

Firestorm-253 commented 1 year ago

i have only taken a glance at it yet, but as i see it 'RepetitionPositionHistory' only gets updated when the move is actually being played, while 'repetitionHistory' is for the API search.

ginop commented 1 year ago

(* Thought I should add that I am no C# expert and this all might be wrong! Just trying to help sort through this bug. In particular, I am unsure if RepetitionPositionHistory = new Stack<ulong>(capacity: 64); indicates a maximum capacity of 64 (which is what I assumed in the original comment below) or if the stack will grow as needed after 64, in which case I don't see why any of the existing complexity is needed.)

After reading through the code some more, I see why we cannot simply use the ChessChallenge.Chess.Board.RepetitionPositionHistory property, but I do not think that the ChessChallenge.API.Board.repetitionHistory adequately replaces it (I don't understand what the use of that property is at all, though).

ChessChallenge.Chess.Board.RepetitionPositionHistory is a stack of board hashes with finite length (64 here). If you modified this while searching, it could irreversibly discard information in the current board's stack. To avoid this, the ChessChallenge.API.Board can't touch that stack, and instead has a set of hashes that have been visited (evidently excluding the current board for some reason). That set cannot tell you if a position will be a draw by threefold repetition, since it only knows if the position has been reached, not if it has been reached twice.

I see two routes to fixing this.

  1. The simple option is to change ChessChallenge.Chess.Board.RepetitionPositionHistory into a regular list and permit the API to .Add and .Pop from it as search moves are made. This has unlimited possible memory requirements, but I am not sure if that would be a problem in real uses.
  2. The second is to split the API's repetition set into two: ChessChallenge.API.Board.setOfHashesForBoardsThatHaveHappenedOnce and ChessChallenge.API.Board.setOfHashesForBoardsThatHaveHappenedTwice (with extra verbose names here only for explaination). New hashes are always added to the first, and also added to the second iff they were already in the first. Then draw by threefold repetition can be detected by reaching a board whose hash is already in setOfHashesForBoardsThatHaveHappenedTwice. However, this cannot accurately be rewound once you search past a draw. Again, I'm not sure if that is a practical problem.

* small edit: C# lists don't have .Pop so I guess it would need to be .RemoveAt(list_name.Count)

ginop commented 1 year ago

Getting up to speed with C# and learning that stacks don't discard when pushed above capacity, they grow. I have made an attempt at resolving this issue with #261, but am very unsure of the possible implications of those changes for others' bots...

Firestorm-253 commented 1 year ago

Getting up to speed with C# and learning that stacks don't discard when pushed above capacity, they grow. I have made an attempt at resolving this issue with #261, but am very unsure of the possible implications of those changes for others' bots...

i will have a look when finding the time, thx. i also attemted a fix myself but couldn't afford to put more time into it and instead opened this issue, hoping SebLague would fix it.

ginop commented 1 year ago

Draw detection has changed in recent commits, but it does not seem to have fixed this.

rokbok commented 1 year ago

This appears to be at least partially be caused by #424. The reason I created a separate bug is that it is not clear that #424 is the only cause for this.

emiljanQ3 commented 1 year ago

I'm struggling with this issue aswell on build 1.19. My bot draws due to repeated moves which are not detected when searching and using board.IsDraw.

Im suspecting we might be missing something though, or else all chess programmers in the challenge would be in this issue thread. How are others handling this? 🤔

ginop commented 1 year ago

It looks like draw detection was entirely re-worked in this commit: https://github.com/SebLague/Chess-Challenge/commit/a6c102ba305af872aca09b4db1753608798386eb

My bot is now able to avoid draws. If your bot still does not find repetition while searching, it could be due to using a transposition table keyed by Zobrist hash. That hash value only reflects the board position, not the repetition history.

rokbok commented 1 year ago

What happens is I do a bunch of searching, undo all the moves to go back to the start, and now it tells me it is a draw. The FEN is identical. When I single step through the code, the reason it was not considered a draw the first time around was because of depth being 0. depth does not get decremented when undoing moves, so it is not 0 the second time around (see #424)

emiljanQ3 commented 1 year ago

My issue turned out to be related to #295. I was only looking for draws and checkmates when there were no available moves. Did not expect the board to return moves after draw from repetition.

Now that i know this the bot works as expected. 😊