Progress on Rustic

[mvanthoor]

...

Sounds about right. Rustic can do depth 7-9 (depending on the position) in a few seconds on an i7-6700K, without any other optimizations beside MVV-LVA. I remember HGM once did an experiment in which it was concluded that each extra move adds about 150-200 ELO (to a certain point of course). If Monchester could reach move depth 7, that would add 450 - 600 ELO, which in the latter case would bring it up to the level of the Tarrasch Toy Engine, and older stalwarts such as Nero 6.1.

[mvanthoor]

"Material grabbing game"

Code: Select all

Alpha 1

go
info score cp 540 depth 1 seldepth 4 time 0 nodes 25 nps 0 pv e1g1
info score cp 940 depth 2 seldepth 3 time 0 nodes 564 nps 0 pv e4a8 d8c7 a8h8
info score cp 880 depth 3 seldepth 5 time 1 nodes 5460 nps 5460000 pv e4a8 d8c7 a8h8 d7d5
info score cp 875 depth 4 seldepth 5 time 12 nodes 52460 nps 4371667 pv e4a8 d8c7 a8h8 f6c3 e1f1 d7d5
info score cp 850 depth 5 seldepth 7 time 97 nodes 407503 nps 4201062 pv e4a8 d8e7 a8h8 f6c3 e1f1 b2c2 a1d1 c2a2
info score cp 500 depth 6 seldepth 7 time 781 nodes 3263080 nps 4178079 pv e4a8 d8e7 a8h8 b2b8 h8b8 f6a1 e1d2 a1h1
info score cp 540 depth 7 seldepth 9 time 4942 nodes 20533712 nps 4154940 pv e4a8 d8e7 a8h8 b2b8 h8b8 f6a1 e1d2 a1h1 b8e5

Code: Select all

Alpha 1 (QSearch Fix)

go
info score cp 940 depth 1 seldepth 2 time 0 nodes 41 nps 0 pv e4a8 d8c7 a8h8
info score cp 940 depth 2 seldepth 3 time 0 nodes 733 nps 0 pv e4a8 d8c7 a8h8
info score cp 880 depth 3 seldepth 5 time 2 nodes 7105 nps 3552500 pv e4a8 d8c7 a8h8 d7d5
info score cp 875 depth 4 seldepth 5 time 17 nodes 63387 nps 3728647 pv e4a8 d8c7 a8h8 f6c3 e1f1 d7d5
info score cp 500 depth 5 seldepth 7 time 154 nodes 564572 nps 3666052 pv e4a8 d8e7 a8h8 b2b8 h8b8 f6a1 e1d2 a1h1
info score cp 500 depth 6 seldepth 7 time 1157 nodes 4126979 nps 3566965 pv e4a8 d8e7 a8h8 b2b8 h8b8 f6a1 e1d2 a1h1
info score cp 490 depth 7 seldepth 9 time 8706 nodes 31496000 nps 3617735 pv e4a8 d8e7 a8e4 e7d8 e4d5 d8c7 a1d1 f6e6 d1c1 c7b8
info score cp 505 depth 8 seldepth 9 time 68208 nodes 244704291 nps 3587619 pv e1g1 h8e8 e4a8 d8e7 a8a7 b2c2 f1d1 e8d8 a7d4 f6d4 e3d4

Up to and including depth 6, even the QSearch-fixed version of Rustic does not consider Qc3+ after grabbing the rook. I think, at this point, material is just too important for the engine, and its search depth is not advanced enough. One of the possible advancements could be to move checking moves right after the captures before searching, by giving them extra weight in the sort algorithm. At this point, a check is not yet an important move, so it is not considered before any other move. Maybe I should save positions like these to test later. If I set Rustic to analyze the position for black immediately after white grabs the rook, it will see the mate.

Epaulette mate game:

Code: Select all

Alpha 1:

go
info score cp 1445 depth 1 time 0 nodes 2 nps 0 pv c2c1
info score cp 1540 depth 2 seldepth 3 time 0 nodes 150 nps 0 pv c2c1 g1h2 c1d2
info score cp 1910 depth 3 seldepth 5 time 0 nodes 2075 nps 0 pv f3f2 g1h2 f2f1q g5h5
info score cp 1595 depth 4 seldepth 5 time 6 nodes 20711 nps 3451833 pv f3f2 g1h2 f2f1n h2g1 c2c1 e6e4
info score cp 1605 depth 5 seldepth 7 time 59 nodes 215361 nps 3650186 pv f3f2 g1h2 f2f1q g5h5 g7h6 e6h6 h7g8 h6e6
info score cp 1590 depth 6 seldepth 7 time 453 nodes 1620912 nps 3578172 pv f3f2 g1h2 f2f1q g5h5 g7h6 e6h6 h7g8 h5g5 g8f7 g5g7
info score cp 1565 depth 7 seldepth 9 time 3148 nodes 11613348 nps 3689119 pv f3f2 g1h2 d8d5 g5d5 c6d5 e6h3 g7h6 d2d3 f2f1q c1h6
info score cp 1585 depth 8 seldepth 9 time 24276 nodes 86440604 nps 3560743 pv f3f2 g1h2 d8d5 g5d5 c6d5 e6h3 g7h6 d2d3 f2f1n h2g1 c2c1

Here, the engine considers to promote to a knight at depth 4 (@Günther: underpromotion is implemented, or I wouldn't have released the engine.) At depth 7, Rustic stops considering promotion to a queen, probably because it can now see the mate.

Code: Select all

QSearch fixed version:

go
info score cp 1540 depth 1 seldepth 3 time 0 nodes 40 nps 0 pv c2c1 g1h2 c1d2
info score cp 1910 depth 2 seldepth 3 time 0 nodes 247 nps 0 pv f3f2 g1h2 f2f1q
info score cp 1605 depth 3 seldepth 5 time 1 nodes 4498 nps 4498000 pv f3f2 g1h2 f2f1n h2g1 c2c1
info score cp 1585 depth 4 seldepth 5 time 17 nodes 57612 nps 3388941 pv f3f2 g1h2 f2f1q g5h5 g7h6 h5h6 h7g7
info score cp 1600 depth 5 seldepth 7 time 141 nodes 484626 nps 3437064 pv f3f2 g1h2 f2f1q g5h5 g7h6 e6h6 h7g8 h6g5 g8f7
info score cp 1580 depth 6 seldepth 7 time 835 nodes 2791328 nps 3342908 pv f3f2 g1h2 f2f1q g5h5 g7h6 e6h6 h7g8 h5g5 g8f7 g5g7 f7e8
info score cp 1540 depth 7 seldepth 9 time 5754 nodes 18954868 nps 3294207 pv f3f2 g1h2 d8d5 d2d3 g7e5 g5e5 f2f1q e6h3 h7g8 h3g3 g8f7
info score cp 1585 depth 8 seldepth 9 time 40435 nodes 129788403 nps 3209803 pv f3f2 g1h2 d8d5 g5d5 c6d5 e6h3 g7h6 d2d3 c2c7 g2g3 f2f1n h2g1 c7c1

If I set up the position where Rustic plays f2+, but with WHITE to move, Rustic immediately sees Rh6+ leading to mate in 5 mvoes. Also, when I play f2+, Kh2, f1Q while Rustic is analyzing, it immediately screams Qh6+ Mate in #5. For now, it seems that checking the enemy king pushes the mate after Rh6+ beyond the horizon on lower search depths. Maybe the inclusion of null move (what will happen if I don't move?) will help with this. At the moment, I have no idea how to remedy this problem at search depths of 3 or 4. I assume that this will improve somewhat when enhancements to the search function are being implemented. Even if Rustic COULD extend the search at depth 4 to see the mate, it may not even get the chance in a real game due to the depth being cut off by time constraints.

I'll also look into the fact if Rustic reports depth X, instead of X-1, if X is being cut off. That would be a cosmetic issue only of course, but it would still be better/more accurate.

[unserializable]

Hey Marcel!

Good news -- the 7k batch of 10s+0 games with 'qsearch-fix' branch finished -- Rustic achieved 99.43% score in 7000 games (+6952 =17 -31) and results from this batch are truly boring compared to previous ones, no short losses for Rustic, just various timeouts, shortest one being in 82 moves. Also, there was not a single stalemate among these 7k games (official Alpha batch had 4 in total), which might be either unexpected side-effect of the patch or just coincidence.

...
Epaulette mate game:

If I set up the position where Rustic plays f2+, but with WHITE to move, Rustic immediately sees Rh6+ leading to mate in 5 mvoes. Also, when I play f2+, Kh2, f1Q while Rustic is analyzing, it immediately screams Qh6+ Mate in #5. For now, it seems that checking the enemy king pushes the mate after Rh6+ beyond the horizon on lower search depths.

But 32. .. f2+ is fine move, Stockfish prefers it too, announcing mate in 13 in fact. Later 33. .. f1=Q queening is something that it seemed Rustics' newly fixed check extension could perhaps avoid, as this is very forced sequence and from your draw sample given earlier the extension goes deep.

... your engine could reach much more than depth 4 by simply changing your search from full minimax to negamax + alphabeta and very basic move ordering. ...

Hi Sven, thank you very much for awesome delve into Monchester source code, this analysis is correct, detailed and to the point, I have saved it in my notes and will refer to it when I return to new work on Monchester.

The last game you showed above might reveal a bug in Monchester too?
It still showed negative eval after the wrong f1=Q and I don't understand why? It only changed the eval sign
with mate in two on board - shouldn't it see it earlier at least, or is this just because depth = 4 plies
and everything above is just material count?

Fortunately not a bug , but exactly a limitation of extensionless fixed depth search.

[mvanthoor]

Hey Marcel!

Good news -- the 7k batch of 10s+0 games with 'qsearch-fix' branch finished -- Rustic achieved 99.43% score in 7000 games (+6952 =17 -31) and results from this batch are truly boring compared to previous ones, no short losses for Rustic, just various timeouts, shortest one being in 82 moves. Also, there was not a single stalemate among these 7k games (official Alpha batch had 4 in total), which might be either unexpected side-effect of the patch or just coincidence.

Thanks for testing I am beginning to expect that the time-outs are being caused by XBoard (I noticed somewhere that you use this, even for UCI-engines). I have run many tests of 200 games at several time controls, and Rustic never times out. At some point it's going to play ridiculous moves (basically the first move that comes up at depth 1), but it always finishes the game.

Of course, it's possible to get into a position that is probably drawn, but can avoid the 50 move rule due to pawn pushes. If this position is reached with something like 0.1 seconds on the clock, Rustic will still try to avoid a draw if it has even the least amount of advantage. One of the two engines MUST to time out at some point.

Therefore I prefer a time control such as 10s+1s, or even 10s+0.1s. I'd like to test the strength of the engine, not test how long it can make the last 0.01 second last

But 32. .. f2+ is fine move, Stockfish prefers it too, announcing mate in 13 in fact. Later 33. .. f1=Q queening is something that it seemed Rustics' newly fixed check extension could perhaps avoid, as this is very forced sequence and from your draw sample given earlier the extension goes deep.

Hm... I'll have to test after ... f2+.

Still, it seems that everything is fine now, except for anomalies caused by the hyperspeed time control, and draws that probably come directly from the opening book.

I have not noticed any ELO change between Alpha 1 and the fixed version; it will only save some very specific positions where Rustic will immediately lose when it ignores an upcoming check. When playing Alpha 1 against a copy of itself (1000 games, 10s+0.1s), the result is +7 ELO with something like +/- 20 margin. When playing Alpha 1 against the fixed version, the result is either +7 or +8 for one or the other, also with a margin of around +/- 20. This bugfix may save maybe one position in a few thousand (but still, a fix is a fix...)

[Sven]

Code: Select all

info score cp 505 depth 8 seldepth 9 time 68208 nodes 244704291 nps 3587619 pv e1g1 h8e8 e4a8 d8e7 a8a7 b2c2 f1d1 e8d8 a7d4 f6d4 e3d4

Hi Marcel, I looked into Rustic search code (master branch from Sunday), and currently I am not sure whether your PV management is correct. At the end of Search::alpha_beta() as well as Search::quiescence() I see the following code:

Code: Select all

        refs.search_info.best_move = best_move;
        refs.search_info.pv = pv.clone();

As far as I understand this overwrites the global SearchInfo instance, and you do this everywhere down the tree right before leaving a node and returning to its parent. But that can (and will) destroy useful information since the current node will frequently belong to the subtree of something that comes later than the "true" root PV so it should be discarded. You don't even need to store that information again since you already stored it in the "pv" parameter of the alpha_beta() and quiescence() functions which propagate the correct PV parts up to the root. In Search::iterative_deepening() your "temp_pv" variable actually holds the right data, and that is what you should store in refs.search_info.pv and later print it as part of your search summary.

Maybe that is an explanation of some weird behaviour?

[Sven]

Another point: in iteration N+1 you should try the best root move from the previous iteration N first. This will often lead to a smaller search tree due to more beta cutoffs. It is a very cheap change since you already maintain the PV so you would only have to set the score of the previous best move to a high value in alpha_beta() right after calling score_moves() if you are at root. Have you considered that already?

[Gabor Szots]

First appearance on our list: http://www.computerchess.org.uk/ccrl/40 ... a_1_64-bit

Better than expected. Other impressions: Enterprising style, king safety addition badly needed. Was fun to watch.

[mvanthoor]

First appearance on our list: http://www.computerchess.org.uk/ccrl/40 ... a_1_64-bit

Better than expected. Other impressions: Enterprising style, king safety addition badly needed. Was fun to watch.

I saw the entry earlier today. Thank you for testing, Gabor Thank you so much for testing. I now have my own chess engine in an independent reference list. One goal on my bucket list has been achieved I think it did great for an engine without any features apart from MVV-LVA, in-check extension, material count, and PST's.

My own gauntlets, after calibrating the list against some engines that were already tested at CCRL, showed a performance of 1650 -/- 50 ELO. Therefore 1696 ELO is within the expected range, but I'm very happy it's at the high end

And yes, you're right: Rustic is an engine that sometimes pulls some nice tactical tricks... Sometimes it ignores threats against its own pieces by answering them with stronger threats. I've seen this engine create massively complicated games, where suddenly half the board blows up, and often it comes out ahead, just because of its speed, it can see that ONE move deeper than many other engines in the same rating range. Sometimes it can't, if the other engine already has a hash table, and then it all backfires and Rustic goes down in flames.

I know king safety is needed. A lot of things in the evaluation are needed, because apart from PST's and material counting, this engine is still a bonehead However, I first would like to concentrate on search. That means adding a transposition table, some search enhancements that are said to be easy to implement (such as null move), and look into tuning the PST's. Somewhere along the line, XBoard will also be finished and included (but it won't become the default interface).

Don't worry; I don't intend to release more than one version per month, if that. I don't have the time for that kind of development and testing pace.

[Ronald]

Congratulations

[mvanthoor]

Congratulations

Thanks Ronald

I'm gonna make me some PaSTa... I've heard it goes well with PeSTo

In other words: let's see how far I can get with only PST's, before I get the urge to finally teach the darn thing that triple and quadruple pawns are not good. Triple and Quadruple SEEMS to be a good thing in beer, but I wouldn't know, because I don't like beer.

(Except for the kind that is associated with women... cherry beer. So sue me )