Devlog of Leorik

[lithander]

The answer is almost 10 years old. I just started with chess programming last year!

A few clicks later I found the author's engine btw: https://github.com/zongzhengli/absolute-zero
With that feature set I would have expected it to play stronger than 2340 ELO, though.

[Mike Sherwin]

Too many words for me to keep in memory. The way I do this in RomiChess and Bricabrac is while generating moves all captures are accumulated in one u64. After all moves have been generated it becomes as easy as if (captures & king[1 - stm]) return ILLEGAL;

Sorry for being so verbose. I'll try to keep my posts shorter in the future.

Do you use the 'captures' bitboard for anything else?

A two piece sacrifice.

It's astonishing to me how well an engine plays already that has no features other than mvv-lva move sorting, alpha/beta (q)search and PSTs. After adding a TT it would probably see something like the forced mate sequence it was getting caught in, too.

It actually turns out that I did use it for something else! In GenMoves() or GenCapts() in Search() and CaptSearch() I use the one from the previous ply to see if the to-square of this ply is attacked and the move of the previous ply was not to this ply's to-square. Then the move is scored either as value of the captured piece or as value of the captured piece - value of the moving piece. It is stupid compared to a full SEE but much faster, but right far more times than it is wrong. I think it is an excellent trade off. To be honest though I never tried a full SEE.

[lithander]

Since the last progress update Leorik has received an entry in the CCRL list at 2178 ELO and that's almost 300 ELO behind my older engine Minimal Chess.

I talked already about MMC's 13th table that augments the PSTs and is worth ~60 ELO. But the key difference between the two engines is that Leorik 1.0 only implements save pruning and wastes a lot of time on proving that certain lines are not worth playing instead of just skipping them. MinimalChess implements three features that each gave it a rather huge boost in time-to-depth.

Null Move Pruning, Late Move Reductions and Futility Pruning. And I have now implemented all three of these features in the dev version 1.5 of Leorik too.

Version 1.1 adds Null Move Pruning

Code: Select all

R_NULL_MOVE = 2
bool inCheck = current.InCheck();
//consider null move pruning first           
if (remaining >= 2 && !inCheck && beta < MAX_BETA && AllowNullMove(ply))
{
	//if stm can skip a move and the position is still "too good" we can assume that this position, after making a move, would also fail high
	PlayNullMove(ply);
	if (FailHigh(ply, remaining - R_NULL_MOVE, beta, moveGen))
		return beta;
}

If there are 2 or more plies remaining to be searched we try to take a shortcut. Skip a move and then make a narrow search around beta with depth reduced by 2. If we get a beta cutoff like that we can assume that making a move wouldn't have changed the fact that this is going to end up over beta. Of course in Zugzwang situation that assumption does not hold and that's why I don't do NullMove pruning when in check.

This is just like in MinimalChess and it's worth 160 Elo in selfplay!

Version 1.2 adds Futility Pruning

Code: Select all

FUTILITY_RANGE = 4
MAX_GAIN_PER_PLY = 70
bool interesting = playState.Stage == Stage.New || inCheck || next.InCheck();

//some nodes near the leaves that appear hopeless can be skipped without evaluation
if (remaining <= FUTILITY_RANGE && !interesting)
{
	//if the static eval looks much worse than alpha also skip it
	float futilityMargin = alpha - remaining * MAX_GAIN_PER_PLY;
	if (next.RelativeScore(current.SideToMove) < futilityMargin)
		continue;
}

I believe futility pruning is normally only done to frontier nodes so it might be a misleading name. But I adapted the same idea. Because I do incrementally evaluation with PSTs I can get a score for each position very very cheap. It's basically just the cost of playing the move and reading the score. If a full evaluation of that node would yield a score below alpha the line didn't do anything for us. And now the assumption is that if the static evaluation of that position is already remaining depth * 70 cp below alpha then it's pretty unlikely that this score is going to improve so much by searching it that we will still beat alpha. So I just skip those moves that look futile, hence the name.

It's important to balance the amount of mispredictions against the improved from a better time-to-depth but with the above values it was worth around 50 ELO in selfplay.

Version 1.3

Here I noticed that my Move struct was taking up way too much memory. This was because the Piece enum was stored with 32 bits. It's amazing how much handholding the C# compiler needs... the compiler just emits IL code and leaves the optimizations to the JIT compiler and the JIT compiler is operating under time pressure while the runtime is alread executing the code. And so in the end you have to help your runtime out.

Code: Select all

public enum Piece : byte
{
        None = 0,
        Black = 1,      //01
        White = 3,      //11
        Pawn = 4,       //00100
        ....
}

So by adding the : byte you tell the compiler/runtime that you want your Piece encoded in bytes not ints.

Code: Select all

public readonly struct Move
{
        public readonly Piece Flags;
        public readonly Piece Target;
        public readonly byte FromSquare;
        public readonly byte ToSquare;
}

...and this means that for example a move is now stored in 4 bytes instead of 12 bytes. And this makes a big difference in how many moves fit into a cache line and also how big the TT entries are and in the end you just get a 1 Million additional NPS (or 40 ELO) for free. Duh!

Version 1.4 adds History

Now... this step took me a long while. The idea is that you keep a tally on the moves you played before so that when you generate the quiet moves in a certain position you can make a guess which of the moves are likely good and which are pointless. Then you sort the good moves to the front and play the bad moves last. The problem is that there are a bazillion different implementations of this that all seem plausible. And it's not easy at all to test whether your implementation is doing you good. Because keeping this tally takes time. Sorting the quiet moves based on that history takes time. By the time you play the late moves your history data has changed so do you just ignore this new information? Is it better to just pick moves? How many will you pick?
...many questions and they all look pretty samey in testing. You lose raw speed but search less nodes so the time to depth stagnates. I suppose this feature would be more beneficial in an engine that has a more sophisticated evaluation. But for Leorik we're talking about something like ~10 ELO from the entire feature.

Why bother? Well because it has a nice synergy with late move reductions. And I figured that those two really need to be considered to be two sides of the same feature.

Version 1.5 adds Late Move Reductions

Late move reductions was a pretty powerful addition for MinimalChess and the way I used it was in combination with the PVS part of the search like this:

Code: Select all

//moves after the PV node are unlikely to raise alpha. 
//avoid a full evaluation by searching with a null-sized window around alpha first
//...we expect it to fail low but if it does not we have to research it!
if (depth >= 2 && expandedNodes > 1)
{
	//non-tactical late moves are searched at a reduced depth to make this test even faster!
	int R =  (interesting || expandedNodes < 4) ? 0 : 2;
	(int score, _) = EvalPositionTT(child, ply + 1, depth - R - 1, window.GetLowerBound(color));
	if (window.FailLow(score, color))
		continue;
}

So in the PVS search you search a node on a null window to prove that it's score is above alpha. When it fails you are done and when it succeeds you have to search it again. But in the end it's still a win because most nodes after the PV node fail.

Adding LMR just means that I don't do the null window search with full depth. The late moves get reduced by 2. And what exactly is a late move? Well if it's not interesting (in check, giving check) or when 3 moves have already been played. The 4th is late. Wow... why the 4th? Well, because it performed better than the version with 3 or 5. Very minimal but for Leorik I wanted to improve upon this.

So here's the new idea... we use the history to determine when the late moves start. We play PV, captures and even killers at full depth. Then we play a few good quiets moves and then when we don't find any good moves anymore we stop playing quiet moves in the order determined by the history heuristic but just in random order. And these "late" unsorted quiet moves get the reduction applied.

It the fusion of one of my favorite history implementations (where I split the quiet stage into a sorted and unsorted quiet stage and drop out of the former when the history value of the most recent pick is below a threshold) and LMR. In Leorik it looks like this:

Code: Select all

//moves after the PV move are unlikely to raise alpha! searching with a null-sized window around alpha first...
bool interesting = playState.Stage == Stage.New || inCheck || next.InCheck();
if (remaining >= 2 && playState.PlayedMoves > 1)
{
	//non-tactical late moves are searched at a reduced depth to make this test even faster!
	int R = interesting || playState.Stage < Stage.Quiets ? 0 : 2;
	if (FailLow(ply, remaining - R, alpha, moveGen))
		continue;
}

So only moves that are quiet with a rather bad history score AND not interesting in the sense that they either give check or escape from check are getting reduced.
That's means Leorik does a lot less reductions than MinimalChess. But I feel like it can afford it because it's so fast. And reducing late moves was always the most "risky" form of pruning of the techniques listed above.

I haven't yet sufficiently proved that it is better than MMC's brutish implementation because to do that I would have to try all kind of history implementations again - this time with MMC's way of doing LMR. I'm not sure that I want to. I just like the new implementation too much and it's combined worth is over 100 ELO... so I guess I'll just have faith that it is indeed better. All I can say for sure is that this combination of history and and LMR is 50 ELO stronger than MMC's way of doing LMR without history heuristic.

...so this is the recap of everything that's been happening since the last post. Version 1.5 has now feature parity with MMC except for the evaluation where I still just use tapered tuned PSTs.

The intermediary results of a gauntlet I'm currently running are very promising:

Code: Select all

   # PLAYER          :  RATING  POINTS  PLAYED   (%)
   1 dumb-1.8        :  2680.0   349.5     534    65
   2 Blunder 7.6     :  2634.0   319.5     534    60
   3 MadChess 3.0    :  2593.0   267.5     536    50
   4 Leorik 1.5      :  2591.2  1677.0    3211    52
   5 zahak400        :  2569.0   243.5     536    45
   6 Cosette 5.1     :  2488.0   141.0     536    26
   7 CT800 1.43      :  2487.0   213.0     535    40

The current version of Leorik is already about 150 ELO stronger than MMC even though there's not a single feature in Leorik that MMC is missing. Only implementation details and most importantly: Raw speed!

[Mike Sherwin]

Since the last progress update Leorik has received an entry in the CCRL list at 2178 ELO and that's almost 300 ELO behind my older engine Minimal Chess.

I talked already about MMC's 13th table that augments the PSTs and is worth ~60 ELO. But the key difference between the two engines is that Leorik 1.0 only implements save pruning and wastes a lot of time on proving that certain lines are not worth playing instead of just skipping them. MinimalChess implements three features that each gave it a rather huge boost in time-to-depth.

Null Move Pruning, Late Move Reductions and Futility Pruning. And I have now implemented all three of these features in the dev version 1.5 of Leorik too.

Version 1.1 adds Null Move Pruning

Code: Select all

R_NULL_MOVE = 2
bool inCheck = current.InCheck();
//consider null move pruning first           
if (remaining >= 2 && !inCheck && beta < MAX_BETA && AllowNullMove(ply))
{
	//if stm can skip a move and the position is still "too good" we can assume that this position, after making a move, would also fail high
	PlayNullMove(ply);
	if (FailHigh(ply, remaining - R_NULL_MOVE, beta, moveGen))
		return beta;
}

If there are 2 or more plies remaining to be searched we try to take a shortcut. Skip a move and then make a narrow search around beta with depth reduced by 2. If we get a beta cutoff like that we can assume that making a move wouldn't have changed the fact that this is going to end up over beta. Of course in Zugzwang situation that assumption does not hold and that's why I don't do NullMove pruning when in check.

This is just like in MinimalChess and it's worth 160 Elo in selfplay!

Version 1.2 adds Futility Pruning

Code: Select all

FUTILITY_RANGE = 4
MAX_GAIN_PER_PLY = 70
bool interesting = playState.Stage == Stage.New || inCheck || next.InCheck();

//some nodes near the leaves that appear hopeless can be skipped without evaluation
if (remaining <= FUTILITY_RANGE && !interesting)
{
	//if the static eval looks much worse than alpha also skip it
	float futilityMargin = alpha - remaining * MAX_GAIN_PER_PLY;
	if (next.RelativeScore(current.SideToMove) < futilityMargin)
		continue;
}

I believe futility pruning is normally only done to frontier nodes so it might be a misleading name. But I adapted the same idea. Because I do incrementally evaluation with PSTs I can get a score for each position very very cheap. It's basically just the cost of playing the move and reading the score. If a full evaluation of that node would yield a score below alpha the line didn't do anything for us. And now the assumption is that if the static evaluation of that position is already remaining depth * 70 cp below alpha then it's pretty unlikely that this score is going to improve so much by searching it that we will still beat alpha. So I just skip those moves that look futile, hence the name.

It's important to balance the amount of mispredictions against the improved from a better time-to-depth but with the above values it was worth around 50 ELO in selfplay.

Version 1.3

Here I noticed that my Move struct was taking up way too much memory. This was because the Piece enum was stored with 32 bits. It's amazing how much handholding the C# compiler needs... the compiler just emits IL code and leaves the optimizations to the JIT compiler and the JIT compiler is operating under time pressure while the runtime is alread executing the code. And so in the end you have to help your runtime out.

Code: Select all

public enum Piece : byte
{
        None = 0,
        Black = 1,      //01
        White = 3,      //11
        Pawn = 4,       //00100
        ....
}

So by adding the : byte you tell the compiler/runtime that you want your Piece encoded in bytes not ints.

Code: Select all

public readonly struct Move
{
        public readonly Piece Flags;
        public readonly Piece Target;
        public readonly byte FromSquare;
        public readonly byte ToSquare;
}

...and this means that for example a move is now stored in 4 bytes instead of 12 bytes. And this makes a big difference in how many moves fit into a cache line and also how big the TT entries are and in the end you just get a 1 Million additional NPS (or 40 ELO) for free. Duh!

Version 1.4 adds History

Now... this step took me a long while. The idea is that you keep a tally on the moves you played before so that when you generate the quiet moves in a certain position you can make a guess which of the moves are likely good and which are pointless. Then you sort the good moves to the front and play the bad moves last. The problem is that there are a bazillion different implementations of this that all seem plausible. And it's not easy at all to test whether your implementation is doing you good. Because keeping this tally takes time. Sorting the quiet moves based on that history takes time. By the time you play the late moves your history data has changed so do you just ignore this new information? Is it better to just pick moves? How many will you pick?
...many questions and they all look pretty samey in testing. You lose raw speed but search less nodes so the time to depth stagnates. I suppose this feature would be more beneficial in an engine that has a more sophisticated evaluation. But for Leorik we're talking about something like ~10 ELO from the entire feature.

Why bother? Well because it has a nice synergy with late move reductions. And I figured that those two really need to be considered to be two sides of the same feature.

Version 1.5 adds Late Move Reductions

Late move reductions was a pretty powerful addition for MinimalChess and the way I used it was in combination with the PVS part of the search like this:

Code: Select all

//moves after the PV node are unlikely to raise alpha. 
//avoid a full evaluation by searching with a null-sized window around alpha first
//...we expect it to fail low but if it does not we have to research it!
if (depth >= 2 && expandedNodes > 1)
{
	//non-tactical late moves are searched at a reduced depth to make this test even faster!
	int R =  (interesting || expandedNodes < 4) ? 0 : 2;
	(int score, _) = EvalPositionTT(child, ply + 1, depth - R - 1, window.GetLowerBound(color));
	if (window.FailLow(score, color))
		continue;
}

So in the PVS search you search a node on a null window to prove that it's score is above alpha. When it fails you are done and when it succeeds you have to search it again. But in the end it's still a win because most nodes after the PV node fail.

Adding LMR just means that I don't do the null window search with full depth. The late moves get reduced by 2. And what exactly is a late move? Well if it's not interesting (in check, giving check) or when 3 moves have already been played. The 4th is late. Wow... why the 4th? Well, because it performed better than the version with 3 or 5. Very minimal but for Leorik I wanted to improve upon this.

So here's the new idea... we use the history to determine when the late moves start. We play PV, captures and even killers at full depth. Then we play a few good quiets moves and then when we don't find any good moves anymore we stop playing quiet moves in the order determined by the history heuristic but just in random order. And these "late" unsorted quiet moves get the reduction applied.

It the fusion of one of my favorite history implementations (where I split the quiet stage into a sorted and unsorted quiet stage and drop out of the former when the history value of the most recent pick is below a threshold) and LMR. In Leorik it looks like this:

Code: Select all

//moves after the PV move are unlikely to raise alpha! searching with a null-sized window around alpha first...
bool interesting = playState.Stage == Stage.New || inCheck || next.InCheck();
if (remaining >= 2 && playState.PlayedMoves > 1)
{
	//non-tactical late moves are searched at a reduced depth to make this test even faster!
	int R = interesting || playState.Stage < Stage.Quiets ? 0 : 2;
	if (FailLow(ply, remaining - R, alpha, moveGen))
		continue;
}

So only moves that are quiet with a rather bad history score AND not interesting in the sense that they either give check or escape from check are getting reduced.
That's means Leorik does a lot less reductions than MinimalChess. But I feel like it can afford it because it's so fast. And reducing late moves was always the most "risky" form of pruning of the techniques listed above.

I haven't yet sufficiently proved that it is better than MMC's brutish implementation because to do that I would have to try all kind of history implementations again - this time with MMC's way of doing LMR. I'm not sure that I want to. I just like the new implementation too much and it's combined worth is over 100 ELO... so I guess I'll just have faith that it is indeed better. All I can say for sure is that this combination of history and and LMR is 50 ELO stronger than MMC's way of doing LMR without history heuristic.

...so this is the recap of everything that's been happening since the last post. Version 1.5 has now feature parity with MMC except for the evaluation where I still just use tapered tuned PSTs.

The intermediary results of a gauntlet I'm currently running are very promising:

Code: Select all

   # PLAYER          :  RATING  POINTS  PLAYED   (%)
   1 dumb-1.8        :  2680.0   349.5     534    65
   2 Blunder 7.6     :  2634.0   319.5     534    60
   3 MadChess 3.0    :  2593.0   267.5     536    50
   4 Leorik 1.5      :  2591.2  1677.0    3211    52
   5 zahak400        :  2569.0   243.5     536    45
   6 Cosette 5.1     :  2488.0   141.0     536    26
   7 CT800 1.43      :  2487.0   213.0     535    40

The current version of Leorik is already about 150 ELO stronger than MMC even though there's not a single feature in Leorik that MMC is missing. Only implementation details and most importantly: Raw speed!

A very nice basic tutorial on search optimization! Thanks.

Edit: Making a move, getting a score and taking back the move without searching any deeper according to HGM should not be counted as nodes. I do this in my mailbox engine Carnivor (no e because it was originally written on MSDOS). In the original position Carnivor searches 24.345.090 (24,345,090 US) nodes per second.

[Mike Sherwin]

Just for more info.
Carnivor does bench 6 at 52.6 million moves per second.
And Carnivor's fraternal twin Godzilla programmed in 80386 32 bit assembler does bench 6 at 67.9 million moves per second.
Both make and unmake the leaf moves and use no tricks to inflate the results.

[mvanthoor]

Since the last progress update Leorik has received an entry in the CCRL list at 2178 ELO and that's almost 300 ELO behind my older engine Minimal Chess.

Congratulations While it's almost 300 points behind MMC, it is also (almost) exactly what I predicted with your feature set: 30-40 points stronger than my dev-version of Rustic 4, because you have staged move generation. Rustic 4 routinely scores somewhere around 2150 +/- 30 points, so 2170-2180 is what I'd expect for Rustic + staged move generation, and so also for Leorik.

[mvanthoor]

Almost 2600 with that feature set and only a tapered PST

I had planned for Rustic to hit ~2500 with the mentioned features of Leorik 1.5. And it also seems that, if Leorik is 150 Elo stronger than MMC with the same features minus the extra mobility table, that it is at least 5 times as fast as MMC Rustic is at least as fast, if not faster... this bodes well for future versions of my engine (Assuming I implement this stuff correctly.)

[Guenther]

...

...so this is the recap of everything that's been happening since the last post. Version 1.5 has now feature parity with MMC except for the evaluation where I still just use tapered tuned PSTs.

The intermediary results of a gauntlet I'm currently running are very promising:

Code: Select all

   # PLAYER          :  RATING  POINTS  PLAYED   (%)
   1 dumb-1.8        :  2680.0   349.5     534    65
   2 Blunder 7.6     :  2634.0   319.5     534    60
   3 MadChess 3.0    :  2593.0   267.5     536    50
   4 Leorik 1.5      :  2591.2  1677.0    3211    52
   5 zahak400        :  2569.0   243.5     536    45
   6 Cosette 5.1     :  2488.0   141.0     536    26
   7 CT800 1.43      :  2487.0   213.0     535    40

The current version of Leorik is already about 150 ELO stronger than MMC even though there's not a single feature in Leorik that MMC is missing. Only implementation details and most importantly: Raw speed!

I am surprised that Leorik 1.5 despite having all new features added, which increased depth a lot (of course expected), also has a higher nps
than 1.0 now, at least on my old hardware compiled w/o popcnt. The speed increase is around 20-30% too.

Code: Select all

Leorik 1.5
uci
id name Leorik 1.5
id author Thomas Jahn
option name Hash type spin default 50 min 1 max 2047
uciok
go
info depth 1 score cp 36 nodes 21 nps 21000 time 0 pv d2d4
info depth 2 score cp 0 nodes 88 nps 3034 time 29 pv d2d4 d7d5
info depth 3 score cp 35 nodes 184 nps 5935 time 31 pv d2d4 d7d5 g1f3
info depth 4 score cp 0 nodes 369 nps 11903 time 31 pv d2d4 d7d5 g1f3 g8f6
info depth 5 score cp 33 nodes 666 nps 21483 time 31 pv d2d4 d7d5 g1f3 g8f6 b1c3
info depth 6 score cp 0 nodes 2662 nps 80666 time 33 pv d2d4 d7d5 g1f3 g8f6 b1c3 b8c6
info depth 7 score cp 26 nodes 5353 nps 152942 time 35 pv d2d4 d7d5 g1f3 g8f6 b1c3 b8c6 c1e3
info depth 8 score cp 0 nodes 10168 nps 267578 time 38 pv d2d4 d7d5 g1f3 g8f6 b1c3 b8c6 c1e3 c8f5
info depth 9 score cp 30 nodes 64321 nps 869202 time 74 pv e2e4 g8f6 b1c3 b8c6 g1f3 d7d5 e4d5 f6d5 d2d4
info depth 10 score cp 4 nodes 281066 nps 1283406 time 219 pv e2e4 e7e5 g1f3 g8f6 d2d4 e5d4 e4e5 f8b4 c2c3 d4c3
info depth 11 score cp 23 nodes 470690 nps 1574214 time 299 pv d2d4 d7d5 e2e3 g8f6 f1d3 b8c6 g1f3 c8g4 e1g1 e7e5 c2c3
info depth 12 score cp 7 nodes 808152 nps 1840892 time 439 pv e2e4 e7e5 g1f3 b8c6 f1d3 f8d6 e1g1 g8f6 b1c3 e8g8 c3b5 d6c5
info depth 13 score cp 21 nodes 2621600 nps 2353321 time 1114 pv g1f3 g8f6 g2g3 d7d5 d2d4 e7e6 f1g2 f8d6 e1g1 e8g8 b1c3 b8c6 c1e3
info depth 14 score cp 8 nodes 5331526 nps 2520816 time 2115 pv e2e4 e7e5 g1f3 b8c6 b1c3 g8f6 f1d3 f8d6 e1g1 e8g8 c3b5 f8e8 b5d6 c7d6
info depth 15 score cp 20 nodes 8468661 nps 2557735 time 3311 pv e2e4 e7e5 g1f3 b8c6 b1c3 g8f6 d2d4 e5d4 f3d4 c6d4 d1d4 f8e7 f1c4 e8g8 e1g1
info depth 16 score cp 9 nodes 12188383 nps 2549337 time 4781 pv e2e4 e7e5 g1f3 b8c6 b1c3 g8f6 f1d3 f8d6 e1g1 e8g8 c3b5 d6c5 c2c4 f8e8 f1e1 d7d6
info depth 17 score cp 24 nodes 26917401 nps 2618169 time 10281 pv g1f3 g8f6 d2d4 d7d5 c1f4 g7g6 e2e3 f8g7 f1d3 b8c6 e1g1 e8g8 b1c3 c8e6 a1c1 a8c8 f3e5
info depth 18 score cp 9 nodes 66417668 nps 2587062 time 25673 pv e2e4 e7e5 g1f3 b8c6 b1c3 g8f6 d2d4 e5d4 f3d4 c6d4 d1d4 f8e7 f1c4 e8g8 e1g1 c7c5 d4d1 d7d6
info depth 19 score cp 28 nodes 115148947 nps 2536599 time 45395 pv e2e4 e7e5 g1f3 b8c6 b1c3 g8f6 d2d4 f8b4 d4d5 f6e4 d5c6 e4c3 b2c3 b4c3 c1d2 c3a1 d1a1 d7c6 f3e5
info depth 20 score cp 7 nodes 282116352 nps 2493383 time 113146 pv e2e4 e7e5 g1f3 b8c6 b1c3 g8f6 f1d3 f8d6 e1g1 e8g8 c3d5 f8e8 f1e1 c6d4 f3d4 e5d4 c2c4 f6d5 c4d5 d6f4

Code: Select all

Leorik 1.0
uci
id name Leorik 1.0
id author Thomas Jahn
option name Hash type spin default 50 min 1 max 2047
uciok
isready
readyok
position startpos
go depth 12
info depth 1 score cp 36 nodes 21 nps 21000 time 0 pv d2d4
info depth 2 score cp 0 nodes 86 nps 4300 time 20 pv d2d4 d7d5
info depth 3 score cp 35 nodes 654 nps 31142 time 21 pv d2d4 d7d5 g1f3
info depth 4 score cp 0 nodes 2324 nps 96833 time 24 pv d2d4 d7d5 g1f3 g8f6
info depth 5 score cp 33 nodes 13691 nps 402676 time 34 pv d2d4 d7d5 g1f3 g8f6 b1c3
info depth 6 score cp 1 nodes 70430 nps 658224 time 107 pv e2e4 b8c6 d2d4 g8f6 b1c3 e7e5
info depth 7 score cp 26 nodes 297216 nps 1134412 time 262 pv e2e4 b8c6 d2d4 e7e5 d4e5 c6e5 g1f3
info depth 8 score cp 10 nodes 1408742 nps 1288876 time 1093 pv e2e4 e7e5 b1c3 g8f6 g1f3 b8c6 d2d4 f8d6
info depth 9 score cp 34 nodes 5229417 nps 2039554 time 2564 pv e2e4 e7e5 b1c3 g8f6 g1f3 f8d6 d2d4 b8c6 c1e3
info depth 10 score cp 8 nodes 23412852 nps 1674739 time 13980 pv e2e4 e7e5 g1f3 b8c6 b1c3 g8f6 d2d4 e5d4 f3d4 f8d6
info depth 11 score cp 33 nodes 185781564 nps 1826796 time 101698 pv d2d4 d7d5 g1f3 g8f6 e2e3 e7e6 b1c3 f8d6 f1d3 e8g8 e1g1

[lithander]

A very nice basic tutorial on search optimization! Thanks.

Back in the day I would have blogged about it. But the forum has the advantage that it comes with an audience!

Edit: Making a move, getting a score and taking back the move without searching any deeper according to HGM should not be counted as nodes.

That's what I do already. Nodes that don't pass the futility check aren't counted because the node counter is incremented only when Evaluate is called on a node. Which in this case does not happen. The cheapest way to get a node increment in Leorik is actually in QSearch when you Evaluate a node that you find to be not in check and which has a standpat score above beta so that you get a beta cut-off immediately.

Almost 2600 with that feature set and only a tapered PST

That puts it already in spitting distance to MadChess, which is the strongest classical C# engine I know of. Is there a stronger one?

if Leorik is 150 Elo stronger than MMC with the same features minus the extra mobility table, that it is at least 5 times as fast as MMC

That it is indeed. And given that this was the whole point of starting from scratch it's a very pleasing result.

Rustic is at least as fast, if not faster... this bodes well for future versions of my engine (Assuming I implement this stuff correctly.)

With the fix from Version 1.3. already in Leorik would have been faster than Rustic, though. And I found it not completely trivial to preserve that speed while adding more features even if it's only about pruning. History pruning especially cost me a lot of NPS... but it's still 5x faster than MMC.

I am surprised that Leorik 1.5 despite having all new features added, which increased depth a lot (of course expected), also has a higher nps
than 1.0 now, at least on my old hardware compiled w/o popcnt. The speed increase is around 20-30% too.

There's no binary published... oh, wait... you made a build from the current master version checked in on github? Nice! Yeah that's exactly the version I've been running my gauntlet with.

Null move and futility is really cheep... only history heuristics had a real price in terms of performance. But most of the time is spent in Qsearch and Qsearch hasn't become any slower. Actually it got faster due to the fix I introduced with version 1.3 and apparently that is enough to compensate for the price of doing history heuristics.

I could also imagine that the deeper, narrower tree structure means the ratio of nodes that are getting searched in Qsearch is bigger. I think I will test that... the qsearch vs normal node ratio in 1.0 vs 1.5 and report back.

[lithander]

I am surprised that Leorik 1.5 despite having all new features added, which increased depth a lot (of course expected), also has a higher nps
than 1.0 now, at least on my old hardware compiled w/o popcnt. The speed increase is around 20-30% too.

I see the same difference in reported nps on my hardware and I admit that I wasn't fully aware of it either. I never really compared the current build with the last public release before but the speed difference is significant. To the best of my knowledge I'm not counting 'nps' differently, though.

Code: Select all

Leorik 1.0
go depth 12
info depth 1 score cp 36 nodes 21 nps 21000 time 0 pv d2d4
info depth 2 score cp 0 nodes 86 nps 14333 time 6 pv d2d4 d7d5
info depth 3 score cp 35 nodes 654 nps 93428 time 7 pv d2d4 d7d5 g1f3
info depth 4 score cp 0 nodes 2324 nps 258222 time 9 pv d2d4 d7d5 g1f3 g8f6
info depth 5 score cp 33 nodes 13691 nps 1053153 time 13 pv d2d4 d7d5 g1f3 g8f6 b1c3
info depth 6 score cp 1 nodes 70430 nps 1354423 time 52 pv e2e4 b8c6 d2d4 g8f6 b1c3 e7e5
info depth 7 score cp 26 nodes 297216 nps 2358857 time 126 pv e2e4 b8c6 d2d4 e7e5 d4e5 c6e5 g1f3
info depth 8 score cp 10 nodes 1408742 nps 2767666 time 509 pv e2e4 e7e5 b1c3 g8f6 g1f3 b8c6 d2d4 f8d6
info depth 9 score cp 34 nodes 5229417 nps 4860052 time 1076 pv e2e4 e7e5 b1c3 g8f6 g1f3 f8d6 d2d4 b8c6 c1e3
info depth 10 score cp 8 nodes 23412852 nps 4151214 time 5640 pv e2e4 e7e5 g1f3 b8c6 b1c3 g8f6 d2d4 e5d4 f3d4 f8d6
info depth 11 score cp 33 nodes 185781564 nps 4655012 time 39910 pv d2d4 d7d5 g1f3 g8f6 e2e3 e7e6 b1c3 f8d6 f1d3 e8g8 e1g1
info depth 12 score cp 10 nodes 1185922448 nps 4549359 time 260679 pv e2e4 e7e5 g1f3 g8f6 b1c3 b8c6 f1c4 f6e4 c3e4 d7d5 c4d3 d5e4
bestmove e2e4

Code: Select all

Leorik 1.5
go movetime 260000
info depth 1 score cp 36 nodes 21 nps 21000 time 0 pv d2d4
info depth 2 score cp 0 nodes 88 nps 8800 time 10 pv d2d4 d7d5
info depth 3 score cp 35 nodes 184 nps 16727 time 11 pv d2d4 d7d5 g1f3
info depth 4 score cp 0 nodes 369 nps 33545 time 11 pv d2d4 d7d5 g1f3 g8f6
info depth 5 score cp 33 nodes 666 nps 60545 time 11 pv d2d4 d7d5 g1f3 g8f6 b1c3
info depth 6 score cp 0 nodes 2662 nps 221833 time 12 pv d2d4 d7d5 g1f3 g8f6 b1c3 b8c6
info depth 7 score cp 26 nodes 5353 nps 411769 time 13 pv d2d4 d7d5 g1f3 g8f6 b1c3 b8c6 c1e3
info depth 8 score cp 0 nodes 10168 nps 726285 time 14 pv d2d4 d7d5 g1f3 g8f6 b1c3 b8c6 c1e3 c8f5
info depth 9 score cp 30 nodes 64321 nps 2382259 time 27 pv e2e4 g8f6 b1c3 b8c6 g1f3 d7d5 e4d5 f6d5 d2d4
info depth 10 score cp 4 nodes 281066 nps 3469950 time 81 pv e2e4 e7e5 g1f3 g8f6 d2d4 e5d4 e4e5 f8b4 c2c3 d4c3
info depth 11 score cp 23 nodes 470690 nps 3677265 time 128 pv d2d4 d7d5 e2e3 g8f6 f1d3 b8c6 g1f3 c8g4 e1g1 e7e5 c2c3
info depth 12 score cp 7 nodes 808152 nps 3794140 time 213 pv e2e4 e7e5 g1f3 b8c6 f1d3 f8d6 e1g1 g8f6 b1c3 e8g8 c3b5 d6c5
info depth 13 score cp 21 nodes 2621600 nps 5350204 time 490 pv g1f3 g8f6 g2g3 d7d5 d2d4 e7e6 f1g2 f8d6 e1g1 e8g8 b1c3 b8c6 c1e3
info depth 14 score cp 8 nodes 5331526 nps 6010739 time 887 pv e2e4 e7e5 g1f3 b8c6 b1c3 g8f6 f1d3 f8d6 e1g1 e8g8 c3b5 f8e8 b5d6 c7d6
info depth 15 score cp 20 nodes 8468661 nps 6222381 time 1361 pv e2e4 e7e5 g1f3 b8c6 b1c3 g8f6 d2d4 e5d4 f3d4 c6d4 d1d4 f8e7 f1c4 e8g8 e1g1
info depth 16 score cp 9 nodes 12188383 nps 6344811 time 1921 pv e2e4 e7e5 g1f3 b8c6 b1c3 g8f6 f1d3 f8d6 e1g1 e8g8 c3b5 d6c5 c2c4 f8e8 f1e1 d7d6
info depth 17 score cp 24 nodes 26917401 nps 6441110 time 4179 pv g1f3 g8f6 d2d4 d7d5 c1f4 g7g6 e2e3 f8g7 f1d3 b8c6 e1g1 e8g8 b1c3 c8e6 a1c1 a8c8 f3e5
info depth 18 score cp 9 nodes 66417668 nps 6436444 time 10319 pv e2e4 e7e5 g1f3 b8c6 b1c3 g8f6 d2d4 e5d4 f3d4 c6d4 d1d4 f8e7 f1c4 e8g8 e1g1 c7c5 d4d1 d7d6
info depth 19 score cp 28 nodes 115148947 nps 6397519 time 17999 pv e2e4 e7e5 g1f3 b8c6 b1c3 g8f6 d2d4 f8b4 d4d5 f6e4 d5c6 e4c3 b2c3 b4c3 c1d2 c3a1 d1a1 d7c6 f3e5
info depth 20 score cp 7 nodes 282116352 nps 6346396 time 44453 pv e2e4 e7e5 g1f3 b8c6 b1c3 g8f6 f1d3 f8d6 e1g1 e8g8 c3d5 f8e8 f1e1 c6d4 f3d4 e5d4 c2c4 f6d5 c4d5 d6f4
info depth 21 score cp 21 nodes 738038262 nps 6262362 time 117853 pv e2e4 e7e5 g1f3 b8c6 b1c3 g8f6 d2d4 f8b4 d4d5 f6e4 d5c6 e4c3 b2c3 b4c3 c1d2 c3a1 c6d7 c8d7 d1a1 f7f6 f1d3
bestmove e2e4