Minimalism in chess programming

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
odomobo
Posts: 59
Joined: Thu Jul 05, 2018 11:09 pm
Location: Chicago, IL
Full name: Josh Odom

Re: Minimalism in chess programming

Post by odomobo » Wed Sep 26, 2018 4:42 pm

I feel completely lost and need help
I know that feeling. In order to solve this, you need to implement a divide routine (prints perft for each root move, so you can see which branch has the problem). Then you need to download a robust engine with a divide routine (any engine should be fine). Then, compare the two divide results, pick a move which has a problem, and repeat for that new position (with reduced depth). This lets you follow the path until it happens at depth 1, which will show you the wrong move. Of course, once you see the specific wrong move, you can investigate why it's happening.

Since your engine can't input moves, but only read FEN positions, you'll probably also want a GUI which can output a FEN for a given position, so you can paste those into your engine. You'll probably also want to update your engine so you can paste in a FEN and depth, instead of recompiling for each new position.

maksimKorzh
Posts: 76
Joined: Sat Sep 08, 2018 3:37 pm
Location: Ukraine
Full name: Maksim Korzh
Contact:

Re: Minimalism in chess programming

Post by maksimKorzh » Wed Sep 26, 2018 6:10 pm

Yep :) That's what I am actually doing now. I did this before using vice to calibrate my previous engines but they all had separated MakeMove(), TakeBack() etc. functions compare to one I'm currently working now, but nevertheless I've managed to print root nodes internally (like internal iterative deepening vs the common). This new all-in-one design is pretty tricky, but I love it, thanks for a try to help :D

User avatar
lucasart
Posts: 3031
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: Minimalism in chess programming

Post by lucasart » Fri Sep 28, 2018 11:46 pm

maksimKorzh wrote:
Wed Sep 26, 2018 6:10 pm
Yep :) That's what I am actually doing now. I did this before using vice to calibrate my previous engines but they all had separated MakeMove(), TakeBack() etc. functions compare to one I'm currently working now, but nevertheless I've managed to print root nodes internally (like internal iterative deepening vs the common). This new all-in-one design is pretty tricky, but I love it, thanks for a try to help :D
If you're into minimalism and robustness, I suggest you avoid TakeBack() completely, and follow the copy/make paradigm. This is simpler to code, and more robust (you can use "const" to guarantee that the Position is not modified, you just modify the copy).

As for performance, well Komodo does it, so it can't be too bad. And Demolito does it too, not that it's a top engine, but it's still reasonably fast (in NPS). Theoretically there is a slowdown due to the memcpy() when playing move, but there is a speedup thanks to the removal of TakeBack(). The overall trade-off seems to be roughly break-even in my experience. Anyway, it doesn't matter, there are so many more important things that take more time to compute, and correctness is far more important elo-wise than raw speed, especially for beginner engines full of bugs.
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

maksimKorzh
Posts: 76
Joined: Sat Sep 08, 2018 3:37 pm
Location: Ukraine
Full name: Maksim Korzh
Contact:

Re: Minimalism in chess programming

Post by maksimKorzh » Sat Sep 29, 2018 7:35 am

lucasart wrote:
Fri Sep 28, 2018 11:46 pm
maksimKorzh wrote:
Wed Sep 26, 2018 6:10 pm
Yep :) That's what I am actually doing now. I did this before using vice to calibrate my previous engines but they all had separated MakeMove(), TakeBack() etc. functions compare to one I'm currently working now, but nevertheless I've managed to print root nodes internally (like internal iterative deepening vs the common). This new all-in-one design is pretty tricky, but I love it, thanks for a try to help :D
If you're into minimalism and robustness, I suggest you avoid TakeBack() completely, and follow the copy/make paradigm. This is simpler to code, and more robust (you can use "const" to guarantee that the Position is not modified, you just modify the copy).

As for performance, well Komodo does it, so it can't be too bad. And Demolito does it too, not that it's a top engine, but it's still reasonably fast (in NPS). Theoretically there is a slowdown due to the memcpy() when playing move, but there is a speedup thanks to the removal of TakeBack(). The overall trade-off seems to be roughly break-even in my experience. Anyway, it doesn't matter, there are so many more important things that take more time to compute, and correctness is far more important elo-wise than raw speed, especially for beginner engines full of bugs.
I'm following H.G.Muller's tutorial on micro-Max at his site, there's the only search() function containing movegen(), makemove(), takeback() and so on, it doesn't even keep track of a move list, searching move as far as it has been generated. My problem is how to correctly count nodes which I'm working at now.

maksimKorzh
Posts: 76
Joined: Sat Sep 08, 2018 3:37 pm
Location: Ukraine
Full name: Maksim Korzh
Contact:

Re: Minimalism in chess programming

Post by maksimKorzh » Sat Sep 29, 2018 12:45 pm

Mr. Muller, I've been researching my node calculating issue for several days and didn't find the solution so far, BUT now I know exactly where is the particular problem.

in this position:


my engine makes move d7d6 at depth 1, which puts king into check... and then starts to test opponent's(white) responses. It starts with bishop on b5. This is the move sequence being tested: b5a4(doesn't cause a beta cutoff due to the king wasn't capthured), b5c6(same), b5d7(same), b5e8(beta cutoff here, for the king capture has been detected). The problem is that the first three moves were counted as nodes for the condition if(score != -INF) failed, so it returned bestScore equals to 0 as common but even worth problem is that the move generation in this phantom line wasn't aborted. I've read at your site these words:
King captures never have to be executed. They lead to termination of the move generation altogether, because the previous move was apparently already an illegal one and we are working on a phantom branch of the search tree.
I assume this means that micro-Max aborts move generation in the case of king capture in such a way that previous illegal moves(king was in check) have not been researched recursively any further. So does it actually mean I have bug in my code?

Could you please tell me what would(or at least assumed to be) be the exact behavior of micro-Max in the position I've mentioned at depth 2? I really wonder.

Piotr Cichy
Posts: 75
Joined: Sun Jul 30, 2006 9:13 pm
Location: Kalisz, Poland
Contact:

Re: Minimalism in chess programming

Post by Piotr Cichy » Thu Oct 04, 2018 12:16 pm

maksimKorzh wrote:
Tue Sep 18, 2018 7:49 am
Thank you guys for sharing your thoughts, but I'm still wondering about H.G.Muller's opinion at this point and the other question - is there somebody but H.G.Muller or Oscar Toledo to get close to 2kb sized engine? I mean why people don't try to write minimalistic program's? Why most choose to increase the strength rather than keep it and reduce the code size?
I was also involved in writting small chess engines, but I focused rather on the size of executable, not the source code. My engine pikoSzachy Extreme Edition 2 has the size 6.5 KB and playing strength about 2300 ELO.

http://www.kalisz.mm.pl/~pic/nanochess/

tpoppins
Posts: 918
Joined: Tue Nov 24, 2015 8:11 pm
Location: upstate

Re: Minimalism in chess programming

Post by tpoppins » Thu Oct 04, 2018 6:55 pm

Piotr Cichy wrote:
Thu Oct 04, 2018 12:16 pm
I was also involved in writting small chess engines, but I focused rather on the size of executable, not the source code. My engine pikoSzachy Extreme Edition 2 has the size 6.5 KB and playing strength about 2300 ELO.

http://www.kalisz.mm.pl/~pic/nanochess/
Piotr, could you check the Download link on your web page? It appears broken (a 404 error).
Tirsa Poppins
CCRL

Piotr Cichy
Posts: 75
Joined: Sun Jul 30, 2006 9:13 pm
Location: Kalisz, Poland
Contact:

Re: Minimalism in chess programming

Post by Piotr Cichy » Thu Oct 04, 2018 9:22 pm

tpoppins wrote:
Thu Oct 04, 2018 6:55 pm

Piotr, could you check the Download link on your web page? It appears broken (a 404 error).
Thank you for the information, it seems the file is deleted by ISP. When I try to upload it again I get the message the file contains a virus (this is false alert, it is probably because my engines are compressed with executable packers).

:-(

tpoppins
Posts: 918
Joined: Tue Nov 24, 2015 8:11 pm
Location: upstate

Re: Minimalism in chess programming

Post by tpoppins » Thu Oct 04, 2018 10:52 pm

You could always put the archive on Filedropper, Mediafire or another filehosting site of your choice, and link to it on your web page. The reason I brought it up is it is easy to find nanoSzachy 4.0 on the net, but not v4.1.
Tirsa Poppins
CCRL

User avatar
hgm
Posts: 23205
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Minimalism in chess programming

Post by hgm » Fri Oct 05, 2018 6:48 am

maksimKorzh wrote:
Sat Sep 29, 2018 12:45 pm
Mr. Muller, I've been researching my node calculating issue for several days and didn't find the solution so far, BUT now I know exactly where is the particular problem.

in this position:


my engine makes move d7d6 at depth 1, which puts king into check... and then starts to test opponent's(white) responses. It starts with bishop on b5. This is the move sequence being tested: b5a4(doesn't cause a beta cutoff due to the king wasn't capthured), b5c6(same), b5d7(same), b5e8(beta cutoff here, for the king capture has been detected). The problem is that the first three moves were counted as nodes for the condition if(score != -INF) failed, so it returned bestScore equals to 0 as common but even worth problem is that the move generation in this phantom line wasn't aborted. I've read at your site these words:
King captures never have to be executed. They lead to termination of the move generation altogether, because the previous move was apparently already an illegal one and we are working on a phantom branch of the search tree.
I assume this means that micro-Max aborts move generation in the case of king capture in such a way that previous illegal moves(king was in check) have not been researched recursively any further. So does it actually mean I have bug in my code?

Could you please tell me what would(or at least assumed to be) be the exact behavior of micro-Max in the position I've mentioned at depth 2? I really wonder.
The idea was that you would only count at d=1. The Bishop moves you describe should all occur at d=0, (reply to a d=1 move), and thus should not be counted. The d=0 level serves no other purpose than checking whether King capture is possible, so that the parent node can ignore moves that put the King in check.

Post Reply