Progress on Rustic

[mvanthoor]

Take your time. I'd like a chance to catch up.

You already did; you got your bitboards working

I'm in no hurry; as I've often said, this engine is not in a race to reach a certain Elo rating before a certain time. Because I test literally every single feature I add by running a 1000 games, this stuff takes a lot of time.

It's also the reason why I'm seriously going to look into an extra computer when AMD releases their next AM5 platform; or when Intel does something of note. I don't need a new computer for day-to-day work. My old i7-6700K with 32 GB RAM and GTX 1070 is more than fast enough to handle everything, except testing chess engines. 2m+1s is 2m+1s on any computer.... the only thing that helps there is more cores.

[Ras]

My old i7-6700K with 32 GB RAM and GTX 1070 is more than fast enough to handle everything, except testing chess engines. 2m+1s is 2m+1s on any computer.... the only thing that helps there is more cores.

Or using shorter time controls. I test at 10s fixed, but 50k games, and eight games in parallel on my quadcore with hyperthreading.

[mvanthoor]

My old i7-6700K with 32 GB RAM and GTX 1070 is more than fast enough to handle everything, except testing chess engines. 2m+1s is 2m+1s on any computer.... the only thing that helps there is more cores.

Or using shorter time controls. I test at 10s fixed, but 50k games, and eight games in parallel on my quadcore with hyperthreading.

I don't really see that as viable game controls for testing... with 1m+0.6s, the available time per move is already down to miliseconds when in the middle game.

[Ras]

I don't really see that as viable game controls for testing... with 1m+0.6s, the available time per move is already down to miliseconds when in the middle game.

That's exaggerated. The fastest my engine can do is 1s/game fixed. With 10s/game, I see 100-200ms per move in the middle game. Plenty of time on today's hardware - and good for 8-11 plies of depth. Of course, if the feature under test had logic that only kicks in with 10+ plies of remaining depth, that time control would not work.

[mvanthoor]

(Planescape: Torment)

What I mean is: I've finally written some pages in Rustic's documentation. They need some polishing, but the outline is online. (I should really stop with the puns and wordplays...) I'm open for suggestions to improvement

[emadsen]

I've finally written some pages in Rustic's documentation. They need some polishing, but the outline is online.

A very good start, Marcel. I like how you start with concepts and high-level architecture.

Even if this has been done before, I still get fun out of doing it myself, in exactly the way I want to be done and in a programming language of my choice.

Above quote from your FAQ. I agree with your sentiment. I have a similar motivation. I want to build an engine from scratch so I get personal experience with that particular engineering challenge. In a professional (work) situation, I would reference existing, stable, thoroughly tested components instead of building everything from scratch. But chess programming is a hobby. I want the full experience.

[mvanthoor]

A very good start, Marcel. I like how you start with concepts and high-level architecture.

Thanks for reading, Eric. I intend to start with the high level concepts, and then unpack one of the objects each at a time. First unpack the engine, and then the board representation. Then the MoveGenerator. And so on.

There's still lots of stuff to write, but at least I have the start now, and the first version of an outline in the table of contents. Now I'm "just" having to make the correct pages and fill in the blanks. I do hope I can achieve what I wrote: to be able to consolidate enough chess programming knowledge in this book so that someone who has read it, will be able to write his/her own engine from scratch. (I'm not intending to replace the Chess Programming Wiki, so I'm not going to discuss 6 board representations and 3 different move generators, for example.)

Above quote from your FAQ. I agree with your sentiment. I have a similar motivation. I want to build an engine from scratch so I get personal experience with that particular engineering challenge. In a professional (work) situation, I would reference existing, stable, thoroughly tested components instead of building everything from scratch. But chess programming is a hobby. I want the full experience.

Yes. In daily life, I write business software, like you do. There's no room to just experiment with some stuff, because if it crashes, 500 people can't work. Also, if an implementation takes 1 day to write, and an implementation that is 20% faster takes 1 week to write, the first will always win.

Still... I have been seeing more and more messages around the internet from companies that are now saving tens of MILLIONS of dollars in cloud computing and memory costs, by porting code from Python to Rust (especially with regard to data science). Maybe we are slowly getting back to the point where performance will also count for business applications.

[lithander]

Still... I have been seeing more and more messages around the internet from companies that are now saving tens of MILLIONS of dollars in cloud computing and memory costs, by porting code from Python to Rust (especially with regard to data science). Maybe we are slowly getting back to the point where performance will also count for business applications.

But maybe that just means there's a more serious effort to make established (but historically slow) ecosystems faster. .Net Core has seen a lot of performance improvements since going open source. And Guido van Rossum (original author of Python) claims he can make Python twice as fast in a coming update.
https://github.com/faster-cpython/ideas ... onDark.pdf ...an effort paid for by Microsoft!

[mvanthoor]

This weekend I've finally written some code for Rustic again. I implemented killer moves. It has 2 for now, even though I can make it 3 or more by just setting a constant. I've tried 2-8 killer moves. If you have more than 2 killer moves, it seems that actually looking if a move is in the killer move list costs more time than the better sorting will gain. I observed a decreased number of nodes with each increase of the number of killer moves, but the time to depth got worse.

1 works, 2 works, 3 is inconclusive (depends on the position, some gain, some loss), 4-6 is wonky (all over the place), 7 is similar to 2 killer moves, and 8 gives some improvement in some positions on high depths. I think I'll be sticking with the traditional 2 killer moves.

According to the start position, the implementation seems to work well if using 2 killer moves:

Code: Select all

Startpos, 32 MB TT, no killers
info score cp 70 depth 1 seldepth 1 time 0 nodes 21 nps 0 pv e2e4
info score cp 0 depth 2 seldepth 4 time 0 nodes 132 nps 0 pv e2e4 e7e5
info score cp 60 depth 3 seldepth 8 time 0 nodes 1068 nps 0 pv e2e4 e7e5 d2d4
info score cp 0 depth 4 seldepth 10 time 1 nodes 6372 nps 6372000 pv e2e4 e7e5 d2d4 d7d5
info score cp 20 depth 5 seldepth 14 time 30 nodes 274535 nps 9151167 hashfull 8 pv e2e4 e7e5 d2d4 d7d5 c1e3
info score cp 5 depth 6 seldepth 18 time 71 nodes 566795 nps 7983028 hashfull 19 pv d2d4 d7d5 e2e3 c8d7 c2c4 e7e6 c4d5 e6d5
info score cp 15 depth 7 seldepth 21 time 210 nodes 1631280 nps 7768000 hashfull 49 pv d2d4 d7d5 e2e3 e7e6 c1d2 c7c5 f1e2 c5d4 e3d4
info score cp 5 depth 8 seldepth 23 time 603 nodes 4131456 nps 6851502 hashfull 148 pv d2d4 d7d5 e2e3 e7e6 f1e2 c8d7 c2c4 f8d6 c4d5 e6d5
info score cp 15 depth 9 seldepth 27 time 3659 nodes 26807077 nps 7326340 hashfull 737 pv d2d4 d7d5 e2e3 e7e6 f1e2 c8d7 c1d2 f8d6 g1f3
info score cp 10 depth 10 seldepth 33 time 24720 nodes 173647599 nps 7024579 hashfull 1000 pv d2d4 d7d5 e2e3 e7e6 g1f3 g8f6 f1b5 c7c6 b5e2 f8b4 c1d2 d8b6

Startpos, 32 MB TT, 2 killers
info score cp 70 depth 1 seldepth 1 time 0 nodes 21 nps 0 pv e2e4
info score cp 0 depth 2 seldepth 4 time 0 nodes 98 nps 0 pv e2e4 e7e5
info score cp 60 depth 3 seldepth 8 time 0 nodes 707 nps 0 pv e2e4 e7e5 d2d4
info score cp 0 depth 4 seldepth 9 time 0 nodes 3301 nps 0 pv e2e4 e7e5 d2d4 d7d5
info score cp 20 depth 5 seldepth 14 time 3 nodes 23491 nps 7830333 pv e2e4 e7e5 d2d4 d7d5 c1e3
info score cp 5 depth 6 seldepth 18 time 19 nodes 114759 nps 6039947 hashfull 6 pv d2d4 d7d5 e2e3 c8d7 c2c4 e7e6 c4d5 e6d5
info score cp 15 depth 7 seldepth 18 time 62 nodes 409997 nps 6612855 hashfull 17 pv d2d4 d7d5 e2e3 e7e6 c1d2 c7c5 f1e2 c5d4 e3d4
info score cp 5 depth 8 seldepth 21 time 276 nodes 1640289 nps 5943076 hashfull 83 pv d2d4 d7d5 e2e3 e7e6 f1e2 c8d7 c2c4 f8d6 c4d5 e6d5
info score cp 15 depth 9 seldepth 23 time 1231 nodes 8143084 nps 6615015 hashfull 339 pv d2d4 d7d5 e2e3 e7e6 f1e2 c8d7 c1d2 f8d6 g1f3
info score cp 10 depth 10 seldepth 26 time 6945 nodes 42409207 nps 6106437 hashfull 976 pv d2d4 d7d5 e2e3 e7e6 g1f3 g8f6 f1b5 c7c6 b5e2 f8b4 c1d2 d8b6

Depth 9: 26.8 mln nodes => 8.1 mln nodes, time 3.7 seconds => 1.2 seconds
Depth 10: 173.6 mln nodes => 42.4 mln nodes, time 24.7 seconds => 6.95 seconds

And the output is exactly the same. That is a massive improvement. In other positions such as KiwiPete, the Killer Moves are much less effective. (It's logical for a quiet move to be less effective in a very busy, tactical position, in general.)

What I didn't expect is that implementing _only_ killer moves as an extra on top of the hash table seems to not gain any Elo. It does _cost_ any Elo either. I've deleted the testrun I did, because all engines I picked except 2 were at least +50 over Rustic; so maybe I picked too engines that are too strong.

I'll do another testrun with engines between 1750 and 1850 Elo, and 1-2 under 1750 and 1-2 at around 1900. I'll also do a testrun of Alpha 2 against this new dev version.

If this (and maybe the history heuristic) actually don't gain any strength yet, I may postpone the release of Alpha 3 so I can first add Aspiration Windows and PVS. Even so, I wonder why the dev-version performed almost exactly the same as Alpha 2, even though tests like the above clearly show that the killer moves can save a lot of calculation. (At least, in some positions.)

[Mike Sherwin]

This weekend I've finally written some code for Rustic again. I implemented killer moves. It has 2 for now, even though I can make it 3 or more by just setting a constant. I've tried 2-8 killer moves. If you have more than 2 killer moves, it seems that actually looking if a move is in the killer move list costs more time than the better sorting will gain. I observed a decreased number of nodes with each increase of the number of killer moves, but the time to depth got worse.

1 works, 2 works, 3 is inconclusive (depends on the position, some gain, some loss), 4-6 is wonky (all over the place), 7 is similar to 2 killer moves, and 8 gives some improvement in some positions on high depths. I think I'll be sticking with the traditional 2 killer moves.

According to the start position, the implementation seems to work well if using 2 killer moves:

Code: Select all

Startpos, 32 MB TT, no killers
info score cp 70 depth 1 seldepth 1 time 0 nodes 21 nps 0 pv e2e4
info score cp 0 depth 2 seldepth 4 time 0 nodes 132 nps 0 pv e2e4 e7e5
info score cp 60 depth 3 seldepth 8 time 0 nodes 1068 nps 0 pv e2e4 e7e5 d2d4
info score cp 0 depth 4 seldepth 10 time 1 nodes 6372 nps 6372000 pv e2e4 e7e5 d2d4 d7d5
info score cp 20 depth 5 seldepth 14 time 30 nodes 274535 nps 9151167 hashfull 8 pv e2e4 e7e5 d2d4 d7d5 c1e3
info score cp 5 depth 6 seldepth 18 time 71 nodes 566795 nps 7983028 hashfull 19 pv d2d4 d7d5 e2e3 c8d7 c2c4 e7e6 c4d5 e6d5
info score cp 15 depth 7 seldepth 21 time 210 nodes 1631280 nps 7768000 hashfull 49 pv d2d4 d7d5 e2e3 e7e6 c1d2 c7c5 f1e2 c5d4 e3d4
info score cp 5 depth 8 seldepth 23 time 603 nodes 4131456 nps 6851502 hashfull 148 pv d2d4 d7d5 e2e3 e7e6 f1e2 c8d7 c2c4 f8d6 c4d5 e6d5
info score cp 15 depth 9 seldepth 27 time 3659 nodes 26807077 nps 7326340 hashfull 737 pv d2d4 d7d5 e2e3 e7e6 f1e2 c8d7 c1d2 f8d6 g1f3
info score cp 10 depth 10 seldepth 33 time 24720 nodes 173647599 nps 7024579 hashfull 1000 pv d2d4 d7d5 e2e3 e7e6 g1f3 g8f6 f1b5 c7c6 b5e2 f8b4 c1d2 d8b6

Startpos, 32 MB TT, 2 killers
info score cp 70 depth 1 seldepth 1 time 0 nodes 21 nps 0 pv e2e4
info score cp 0 depth 2 seldepth 4 time 0 nodes 98 nps 0 pv e2e4 e7e5
info score cp 60 depth 3 seldepth 8 time 0 nodes 707 nps 0 pv e2e4 e7e5 d2d4
info score cp 0 depth 4 seldepth 9 time 0 nodes 3301 nps 0 pv e2e4 e7e5 d2d4 d7d5
info score cp 20 depth 5 seldepth 14 time 3 nodes 23491 nps 7830333 pv e2e4 e7e5 d2d4 d7d5 c1e3
info score cp 5 depth 6 seldepth 18 time 19 nodes 114759 nps 6039947 hashfull 6 pv d2d4 d7d5 e2e3 c8d7 c2c4 e7e6 c4d5 e6d5
info score cp 15 depth 7 seldepth 18 time 62 nodes 409997 nps 6612855 hashfull 17 pv d2d4 d7d5 e2e3 e7e6 c1d2 c7c5 f1e2 c5d4 e3d4
info score cp 5 depth 8 seldepth 21 time 276 nodes 1640289 nps 5943076 hashfull 83 pv d2d4 d7d5 e2e3 e7e6 f1e2 c8d7 c2c4 f8d6 c4d5 e6d5
info score cp 15 depth 9 seldepth 23 time 1231 nodes 8143084 nps 6615015 hashfull 339 pv d2d4 d7d5 e2e3 e7e6 f1e2 c8d7 c1d2 f8d6 g1f3
info score cp 10 depth 10 seldepth 26 time 6945 nodes 42409207 nps 6106437 hashfull 976 pv d2d4 d7d5 e2e3 e7e6 g1f3 g8f6 f1b5 c7c6 b5e2 f8b4 c1d2 d8b6

Depth 9: 26.8 mln nodes => 8.1 mln nodes, time 3.7 seconds => 1.2 seconds
Depth 10: 173.6 mln nodes => 42.4 mln nodes, time 24.7 seconds => 6.95 seconds

And the output is exactly the same. That is a massive improvement. In other positions such as KiwiPete, the Killer Moves are much less effective. (It's logical for a quiet move to be less effective in a very busy, tactical position, in general.)

What I didn't expect is that implementing _only_ killer moves as an extra on top of the hash table seems to not gain any Elo. It does _cost_ any Elo either. I've deleted the testrun I did, because all engines I picked except 2 were at least +50 over Rustic; so maybe I picked too engines that are too strong.

I'll do another testrun with engines between 1750 and 1850 Elo, and 1-2 under 1750 and 1-2 at around 1900. I'll also do a testrun of Alpha 2 against this new dev version.

If this (and maybe the history heuristic) actually don't gain any strength yet, I may postpone the release of Alpha 3 so I can first add Aspiration Windows and PVS. Even so, I wonder why the dev-version performed almost exactly the same as Alpha 2, even though tests like the above clearly show that the killer moves can save a lot of calculation. (At least, in some positions.)

All these type things are wonky. They work or don't work depending on the rest of the search characteristics. Killers may work if there was a positive threat in the position before the opposite side made a move. But, what if there was no threat and most moves by the opposite side are not blunders to a specific killer? Maybe, use a killer only if it was a threat before the other side moved.

History tables are almost random. They were removed at one point in Crafty. Maybe they are back in, idk. It might be worth a look. I removed them from RomiChess before they were removed from Crafty. They made it back into RomiChess only because I used them for feedback to the evaluator which gains some elo. Also Rebel incorporated the feedback idea for some positive elo. If you want to experiment with history tables then consider maintaining two history tables, a long period table and a short period table. Interpolate between the two.

I know you probably do not want to hear about Bricabrac, but I'm going to tell you anyway. Currently as I work on the evaluation there are no reductions in the search. I removed them. The search is only pvs negamax with a couple of move ordering tricks. And there are no killers or history tables and to be clear no check extension either.

9 131 59 5488667 d2d4 d7d5 c1f4 b8d7 g1f3 g8f6 b1d2 e7e6 e2e3

I don't think that killers or history tables are going to be of much use in Bricabrac. But, I'll at some point try them anyway.