billforsternz / thc-chess-library

General Purpose Rules of Chess Library for C++
MIT License
38 stars 13 forks source link

On the difference between PlayMove(Move) and PushMove(Move) in relation to draw detection #14

Closed bolomcs50 closed 2 years ago

bolomcs50 commented 2 years ago

Hi, I'm using your library to write a chess engine. I have come across what I think is an issue: if I use the thc::ChessRules::PlayMove(Move) function to update the history of the game, then draws by repetition are counted correctly. On the other hand, if I use thc::ChessRules::PushMove(Move), e.g. for searching the space of possible future moves without actually playing them, draws are not detected.

For example, the following code, playing a simple threefold repetition draw from the starting position:

#include <iostream>
#include "thc.h"

int main(int argc, char const *argv[])
{
    // Initial Position
    thc::ChessEvaluation cr;
    cr.Forsyth("rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1");
    std::vector<std::string> moves {"d2d4", "d7d5", "d1d2", "d8d7", "d2d1", "d7d8", "d1d2", "d8d7", "d2d1"};
    thc::Move mv;
    for (int i = 0; i < moves.size(); i++){
        mv.TerseIn(&cr, moves[i].c_str());
        cr.PlayMove(mv);
    }

    printf( "Position = %s", cr.ToDebugStr().c_str() );
    printf( "RepCount %d\n\n", cr.GetRepetitionCount());

    mv.TerseIn(&cr, "d7d8");
    cr.PlayMove(mv);
    printf( "Position = %s", cr.ToDebugStr().c_str() );
    printf( "RepCount %d\n\n", cr.GetRepetitionCount());

    return 0;
}

produces the expected output:

Position = 
Black to move
rnb.kbnr
pppqpppp
........
...p....
...P....
........
PPP.PPPP
RNBQKBNR
RepCount 2

Position = 
White to move
rnbqkbnr
ppp.pppp
........
...p....
...P....
........
PPP.PPPP
RNBQKBNR
RepCount 3

but if the last move is added with cr.PushMove(mv), then the draw is not detected:

Position = 
Black to move
rnb.kbnr
pppqpppp
........
...p....
...P....
........
PPP.PPPP
RNBQKBNR
RepCount 2

Position = 
White to move
rnbqkbnr
ppp.pppp
........
...p....
...P....
........
PPP.PPPP
RNBQKBNR
RepCount 1

My understanding is that PushMove() should be used during search, as the moves are not really played on the board and the related counters are not updated, whereas PlayMove() should be used for moves tha were actually played, and the counters do increase. As a consequence, one should not use PopMove() after PlayMove(), but only after PushMove(). Is this non-detection of draws by repetition after PushMove() the intended behavior? If so, should one detect a draws by repetition during search by keeping a separate history of the played+simulated moves? Am I misunderstanding the use of these functions?

Thank you

billforsternz commented 2 years ago

I think your analysis is accurate and you've identified a real problem, or at least a mismatch between the way the library is conceptualised and your use case. For my own purposes, basically a GUI (serious effort) and a toy engine (hobbyist effort only), the behaviour as you describe it is a good fit because I saw no point in including repetition draws in search. My reasoning was that chess AI should be looking for a path forward, and a repetition was never in that category. In other words, an engine should take a draw if given a chance at ply 1 (in a game situation) if it's backed up minimax score is negative. Similarly it should spurn the same chance if it thinks it's better. I am actually just rationalising after the fact, I didn't explicitly spell that out, I suspect I just intuited it at the time I was thinking about it (it was a long time ago!). The manifestation of this thinking is that PushMove/PopMove is intended to be as fast as possible suitable for search, whereas PlayMove (needs to support all the rules of chess for my GUI), which tracks repetition and can afford to be much (much!) slower. I imagine that the tortuous way I go back up to 50 moves looking for various types of draws would slow down search with my code by 2, 3 maybe 4 orders of magnitude. I'm sorry this is likely to be very disappointing for you. Assuming my thinking was hopelessly naive (I'm guessing it probably was, sorry again) and sophisticated engines include repetition draws in search, they'd likely use their hashes/transposition table capability. I don't really have any support for that in my code. I did implement hash codes at some stage for my database features, and I've left the functions in the library even though I subsequently stopped using them as I changed the approach for the database stuff in Tarrasch. My hashes just use random constants, not industry standard (Zobrist etc.). In fact only very recently (long after I wrote the hash code) did I find out chess programmers routinely ignore the possibility of hash collisions - they really assume a 64 bit code can represent a complete chess position that strictly speaking requires much more than 64 bits. I naively believed all hash based operations were somehow subsequently checked for collision (as I did in my hash based database code). I say all this just to explain that my code is not state of the art in any way, having no useful hash capability. Also it's mailbox code, not bitboard (although I suspect it is very fast mailbox code - the lookup tables should look after that).

I'm sorry not to have better news for you. I've pecked this out on my phone while watching TV, sorry it's not better organised.

Bill.

On Sat, 28 May 2022, 19:48 bolomcs50, @.***> wrote:

Hi, I'm using your library to write a chess engine. I have come across what I think is an issue: if I use the thc::ChessRules::PlayMove(Move) function to update the history of the game, then draws by repetition are counted correctly. On the other hand, if I use thc::ChessRules::PushMove(Move), e.g. for searching the space of possible future moves without actually playing them, draws are not detected.

For example, the following code, playing a simple threefold repetition draw from the starting position:

include

include "thc.h"

int main(int argc, char const *argv[]) { // Initial Position thc::ChessEvaluation cr; cr.Forsyth("rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1"); std::vector moves {"d2d4", "d7d5", "d1d2", "d8d7", "d2d1", "d7d8", "d1d2", "d8d7", "d2d1"}; thc::Move mv; for (int i = 0; i < moves.size(); i++){ mv.TerseIn(&cr, moves[i].c_str()); cr.PlayMove(mv); }

printf( "Position = %s", cr.ToDebugStr().c_str() ); printf( "RepCount %d\n\n", cr.GetRepetitionCount());

mv.TerseIn(&cr, "d7d8"); cr.PlayMove(mv); printf( "Position = %s", cr.ToDebugStr().c_str() ); printf( "RepCount %d\n\n", cr.GetRepetitionCount());

return 0; }

produces the expected output:

Position = Black to move rnb.kbnr pppqpppp ........ ...p.... ...P.... ........ PPP.PPPP RNBQKBNR RepCount 2

Position = White to move rnbqkbnr ppp.pppp ........ ...p.... ...P.... ........ PPP.PPPP RNBQKBNR RepCount 3

but if the last move is added with cr.PushMove(mv), then the draw is not detected:

Position = Black to move rnb.kbnr pppqpppp ........ ...p.... ...P.... ........ PPP.PPPP RNBQKBNR RepCount 2

Position = White to move rnbqkbnr ppp.pppp ........ ...p.... ...P.... ........ PPP.PPPP RNBQKBNR RepCount 1

My understanding is that PushMove() should be used during search, as the moves are not really played on the board and the related counters are not updated, whereas PlayMove() should be used for moves tha were actually played, and the counters do increase. As a consequence, one should not use PopMove() after PlayMove(), but only after PushMove(). Is this non-detection of draws by repetition after PushMove() the intended behavior? If so, how does one detect a draw by repetition during search? Am I misunderstanding the use of these functions?

Thank you

— Reply to this email directly, view it on GitHub https://github.com/billforsternz/thc-chess-library/issues/14, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABSQYSW7GG2TQWGCC3ZJEGDVMHFUVANCNFSM5XGIL4NA . You are receiving this because you are subscribed to this thread.Message ID: @.***>

bolomcs50 commented 2 years ago

I think your analysis is accurate and you've identified a real problem, or at least a mismatch between the way the library is conceptualised and your use case. For my own purposes, basically a GUI (serious effort) and a toy engine (hobbyist effort only), the behaviour as you describe it is a good fit because I saw no point in including repetition draws in search.

Ok, this makes it clear: the intended behaviour of the functions overlaps with my use case but not completely.

My reasoning was that chess AI should be looking for a path forward, and a repetition was never in that category. In other words, an engine should take a draw if given a chance at ply 1 (in a game situation) if it's backed up minimax score is negative. Similarly it should spurn the same chance if it thinks it's better. [...] Assuming my thinking was hopelessly naive (I'm guessing it probably was, sorry again) and sophisticated engines include repetition draws in search, they'd likely use their hashes/transposition table capability.

I agree, that's what an engine should do, though I feel like there is a subtle flaw in your line of reasoning: the engine does not know if a move leads to a threefold repetition without search+evaluation. The repetition is not in the "path forward" category, but the engine can't know that until it simulates it in search. Unless, as you correctly pointed out, one performs the checks on hash values, which I intuitively think should also be faster.

I'm sorry this is likely to be very disappointing for you.

Actually it is the opposite. The fact that I, a beginner, could investigate this issue and track it from its manifestation (an otherwise won game drawn by my engine), to its origin (a misinterpretation of the intended behavior of a function of a library I rely upon), and that the expert author of such library agrees with my analysis is a confidence booster.

I don't really have any support for that in my code. I did implement hash codes at some stage for my database features, and I've left the functions in the library even though I subsequently stopped using them as I changed the approach for the database stuff in Tarrasch. My hashes just use random constants, not industry standard (Zobrist etc.). In fact only very recently (long after I wrote the hash code) did I find out chess programmers routinely ignore the possibility of hash collisions - they really assume a 64 bit code can represent a complete chess position that strictly speaking requires much more than 64 bits. I naively believed all hash based operations were somehow subsequently checked for collision (as I did in my hash based database code). I say all this just to explain that my code is not state of the art in any way, having no useful hash capability. Also it's mailbox code, not bitboard (although I suspect it is very fast mailbox code - the lookup tables should look after that).

Thanks a lot, this is all very valuable information to me.

Finally, let me take this opportunity to thank you for sharing this library. It's been great so far, it's very well commented and I'm having fun using it. I also really appreciate the fact that you still take the time to respond to users' comments so quickly. Thank you Bill.

Michele.