So recently, I've been trying to improve WDs speed, and one thing I've noticed is just how slow the move gen is! It takes almost 60% of the entire search time!

And after searching around, table-based move generation is something that I think is worthwhile to consider. So I've been wondering what type of speed increase should I expect from this, and how should the pawns esp. be coded?

Thanks!

https://lichess.org/study/PgtRI4b6/vn1uEVo3#158
The chess speaks for itself.

How does stalemate detection work again? I saw some stuff regarding stalemate around pages 45-55 in the forum, but I don't quite understand it.

S_P_A_R_T wrote:

So recently, I've been trying to improve WDs speed, and one thing I've noticed is just how slow the move gen is! It takes almost 60% of the entire search time!

And after searching around, table-based move generation is something that I think is worthwhile to consider. So I've been wondering what type of speed increase should I expect from this, and how should the pawns esp. be coded?

Thanks!

60% sounds like quite some time, but also not completely off. For GoK it was around 45% the last time I checked, but that also includes attack table and mobility calculation, move scoring and ordering, distinguishing full search and quiescence, which is handled by the same code.

Maybe we should talk about moves-generated-per-second instead of runtime percentage. For comparison, on TurboWarp the GoK move generator produces 800,000 moves per second, when invoked on the opening board stand-alone.

BTW. the fastest move generator in the world, created by a fellow Austrian, generates 2,000,000,000 moves per second. Of course it is implemented in C / assembly, and applies massive and specialized tuning on a CPU instruction and cache level.

It is also worth mentioning that a staged move generator might seem to slow things down standalone in terms of moves-generated-per-second, but its huge advantage is that it will generate the moves first that are likely to produce a cutoff, and the other ones will not be generated at all.

Pawns are an issue, because that likely requires more logic blocks and cannot simply use pre-calculated lookup tables only. Still, at least on GoK, most time is spent on sliding pieces.

For 800,000 moves, all those custom block invocations alone cost time because they come with some overhead as well, and several of them are needed per move. For a single invocation it might not seem a lot, but with 5 custom block invocations per move, that overhead is created 4,000,000 times per second.

GoK implementation:

Pre-calculation of lookup tables:
https://github.com/ArnoHue/scratch/blob/c357d524c812886da484775ec99c87bcf0ed0bba/chess/Engine.scratch#L6281

Setup and iterating over pieces, castling, mobility, move ordering:
https://github.com/ArnoHue/scratch/blob/c357d524c812886da484775ec99c87bcf0ed0bba/chess/Engine.scratch#L4498

Calculating move score:
https://github.com/ArnoHue/scratch/blob/c357d524c812886da484775ec99c87bcf0ed0bba/chess/Engine.scratch#L5130

Pawns:
https://github.com/ArnoHue/scratch/blob/c357d524c812886da484775ec99c87bcf0ed0bba/chess/Engine.scratch#L4337

Sliding pieces:
https://github.com/ArnoHue/scratch/blob/c357d524c812886da484775ec99c87bcf0ed0bba/chess/Engine.scratch#L2714

Kings and knights:
https://github.com/ArnoHue/scratch/blob/c357d524c812886da484775ec99c87bcf0ed0bba/chess/Engine.scratch#L812

Adding moves to move list, attack table update:
https://github.com/ArnoHue/scratch/blob/c357d524c812886da484775ec99c87bcf0ed0bba/chess/Engine.scratch#L883

Public API Wrapper, invokes attack table generation, then move generation (attack tables only needed in final move-gen stage and for full search):
https://github.com/ArnoHue/scratch/blob/c357d524c812886da484775ec99c87bcf0ed0bba/chess/Engine.scratch#L4761

Staged move generator:
https://github.com/ArnoHue/scratch/blob/c357d524c812886da484775ec99c87bcf0ed0bba/chess/Engine.scratch#L7773

This is a riddle for me, can someone explain why g4 might not be found here within ply 4 full search (plus quiescence)? I actually guess it is seen, but not evaluated as best move despite the material gain of one pawn (must still check in detail):
https://lichess.org/q2BIRDaX#98

GoK doesn't choose it, and it gets to ply 13 (I disabled LMR, same result), White Dove does not choose it, and it gets to ply 10, but congratulations, Element selects g4 on 6+8!

That game actually is the first draw for a long time, GoK (white) vs. White Dove. I will still add it to study and ELO generator.

ArnoHu wrote:

This is a riddle for me, can someone explain why f4 might not be found here within ply 4 full search (plus quiescence)? I actually guess it is seen, but not evaluated as best move despite the material gain of one pawn (must still check in detail):
https://lichess.org/q2BIRDaX#98

GoK doesn't choose it, and it gets to ply 13 (I disabled LMR, same result), White Dove does not choose it, and it gets to ply 10, but congratulations, Element selects f4 on 6+8!

That game actually is the first draw for a long time, GoK (white) vs. White Dove. I will still add it to study and ELO generator.

Did you mean g4 in the position after 44…Re8 ? Where is the material gain? According to Stockfish, there are alternative moves in the position (e.g. Kf2). g4 isn’t the “only” move.

Again, where is the material gain? I don’t see it anywhere.

Was the game terminated early? Stockfish doesn’t show a threefold repetition.

Hi there! Which method is better for performance when searching by index: using ‘List contains()’ or a ‘repeat’ loop with conditionals?

birdracerthree wrote:

ArnoHu wrote:

This is a riddle for me, can someone explain why f4 might not be found here within ply 4 full search (plus quiescence)? I actually guess it is seen, but not evaluated as best move despite the material gain of one pawn (must still check in detail):
https://lichess.org/q2BIRDaX#98

GoK doesn't choose it, and it gets to ply 13 (I disabled LMR, same result), White Dove does not choose it, and it gets to ply 10, but congratulations, Element selects f4 on 6+8!

That game actually is the first draw for a long time, GoK (white) vs. White Dove. I will still add it to study and ELO generator.

Did you mean g4 in the position after 44…Re8 ? Where is the material gain? According to Stockfish, there are alternative moves in the position (e.g. Kf2). g4 isn’t the “only” move.

Again, where is the material gain? I don’t see it anywhere.

Was the game terminated early? Stockfish doesn’t show a threefold repetition.

Yes g4, f4 was a typo, corrected in original post.

50. g4 e5 51. Ng6 Rb7 52. dxe5 fxe5 53. Nxe5+

White up a pawn, that is at least what Stockfish shows. That static board is evaluated with 155 by GoK (which seems OK), on the path it chooses it gets to 292 at depth 4, it seems to see something there that won't materialize later.

Update: OK one reason (but not the only one) is over-rating king ring attacks (esp. several for on square), which are crazy in that scenario. The other reason is likely that it things the capture sequence is still available.

ScratchChessChampion wrote:

Hi there! Which method is better for performance when searching by index: using ‘List contains()’ or a ‘repeat’ loop with conditionals?

List.contains(), but that is still slow on larger lists. For key-based lookup, a hashtable is better at some point, that is why we use it for transposition tables.

ArnoHu wrote:

ScratchChessChampion wrote:

Hi there! Which method is better for performance when searching by index: using ‘List contains()’ or a ‘repeat’ loop with conditionals?

List.contains(), but that is still slow on larger lists. For key-based lookup, a hashtable is better at some point, that is why we use it for transposition tables.

Oh thanks! I'm simply looking to locate the King's index among 64 squares.

birdracerthree wrote:

https://lichess.org/study/PgtRI4b6/vn1uEVo3#158
The chess speaks for itself.

How does stalemate detection work again? I saw some stuff regarding stalemate around pages 45-55 in the forum, but I don't quite understand it.

Well, simply when move generator is returning 0 moves for full search (and not in check). This requires attack tables that prevent generating king moves to attacked squares, or excluding those moves again after move generator has produced them (the later might be expensive).

GoK implementation:

The expensive variant at low depth (might be required when move generator is in early stages like hash move or MVV-LVA, but TT doesn't provide attack tables):
Invocation:
https://github.com/ArnoHue/scratch/blob/c357d524c812886da484775ec99c87bcf0ed0bba/chess/Engine.scratch#L1259
Implementation:
https://github.com/ArnoHue/scratch/blob/c357d524c812886da484775ec99c87bcf0ed0bba/chess/Engine.scratch#L7169

The fast variant, but requires move generator applying attack tables:
https://github.com/ArnoHue/scratch/blob/c357d524c812886da484775ec99c87bcf0ed0bba/chess/Engine.scratch#L2163

ScratchChessChampion wrote:

ArnoHu wrote:

ScratchChessChampion wrote:

Hi there! Which method is better for performance when searching by index: using ‘List contains()’ or a ‘repeat’ loop with conditionals?

List.contains(), but that is still slow on larger lists. For key-based lookup, a hashtable is better at some point, that is why we use it for transposition tables.

Oh thanks! I'm simply looking to locate the King's index among 64 squares.

Should be OK. I apply an incremental approach, each time a king move is applied ore reverted, a dedicated index variable is updated accordingly. No need to scan for it later.

Q+N vs R+R Endgame Chess Puzzle for GoK, Element and White Dove.
Only GoK managed to solve it perfectly.
https://lichess.org/study/kUJErOlo/VTt1Deon

ArnoHu wrote:

birdracerthree wrote:

ArnoHu wrote:

This is a riddle for me, can someone explain why f4 might not be found here within ply 4 full search (plus quiescence)? I actually guess it is seen, but not evaluated as best move despite the material gain of one pawn (must still check in detail):
https://lichess.org/q2BIRDaX#98

GoK doesn't choose it, and it gets to ply 13 (I disabled LMR, same result), White Dove does not choose it, and it gets to ply 10, but congratulations, Element selects f4 on 6+8!

That game actually is the first draw for a long time, GoK (white) vs. White Dove. I will still add it to study and ELO generator.

Did you mean g4 in the position after 44…Re8 ? Where is the material gain? According to Stockfish, there are alternative moves in the position (e.g. Kf2). g4 isn’t the “only” move.

Again, where is the material gain? I don’t see it anywhere.

Was the game terminated early? Stockfish doesn’t show a threefold repetition.

Yes g4, f4 was a typo, corrected in original post.

50. g4 e5 51. Ng6 Rb7 52. dxe5 fxe5 53. Nxe5+

White up a pawn, that is at least what Stockfish shows. That static board is evaluated with 155 by GoK (which seems OK), on the path it chooses it gets to 292 at depth 4, it seems to see something there that won't materialize later.

Update: OK one reason (but not the only one) is over-rating king ring attacks (esp. several for on square), which are crazy in that scenario. The other reason is likely that it things the capture sequence is still available.

I am so thankful for this game, as it uncovered a major bug in GoK. A combination of code changes around king ring attacks and storage of that part of evaluation in TT led to a regression. I can't say how many games during the last couple of months were influenced, but probably a lot.

Here is the original game, bug-ridden:
https://lichess.org/q2BIRDaX#156

Here is were GoK 6.411 picked up the same game at move 31, it had 0 inaccuracies, mistakes or blunder after that, and finished in 66 moves:
https://lichess.org/KRF8TVnW#131

ScratchChessChampion wrote:

Q+N vs R+R Endgame Chess Puzzle for GoK, Element and White Dove.
Only GoK managed to solve it perfectly.
https://lichess.org/study/kUJErOlo/VTt1Deon

Nice puzzle! Replayed it with current version, GoK found correct moves between 0 and 0.3 seconds, except the final one, which took 21 seconds.

Update: 14 seconds in the latest version.

ArnoHu wrote:

birdracerthree wrote:

ArnoHu wrote:

This is a riddle for me, can someone explain why f4 might not be found here within ply 4 full search (plus quiescence)? I actually guess it is seen, but not evaluated as best move despite the material gain of one pawn (must still check in detail):
https://lichess.org/q2BIRDaX#98

GoK doesn't choose it, and it gets to ply 13 (I disabled LMR, same result), White Dove does not choose it, and it gets to ply 10, but congratulations, Element selects f4 on 6+8!

That game actually is the first draw for a long time, GoK (white) vs. White Dove. I will still add it to study and ELO generator.

Did you mean g4 in the position after 44…Re8 ? Where is the material gain? According to Stockfish, there are alternative moves in the position (e.g. Kf2). g4 isn’t the “only” move.

Again, where is the material gain? I don’t see it anywhere.

Was the game terminated early? Stockfish doesn’t show a threefold repetition.

Yes g4, f4 was a typo, corrected in original post.

50. g4 e5 51. Ng6 Rb7 52. dxe5 fxe5 53. Nxe5+

White up a pawn, that is at least what Stockfish shows. That static board is evaluated with 155 by GoK (which seems OK), on the path it chooses it gets to 292 at depth 4, it seems to see something there that won't materialize later.

Update: OK one reason (but not the only one) is over-rating king ring attacks (esp. several for on square), which are crazy in that scenario. The other reason is likely that it things the capture sequence is still available.

Black can play Re8, pushing the move far beyond the horizon (the white king can walk to h5).

birdracerthree wrote:

ArnoHu wrote:

birdracerthree wrote:

ArnoHu wrote:

This is a riddle for me, can someone explain why f4 might not be found here within ply 4 full search (plus quiescence)? I actually guess it is seen, but not evaluated as best move despite the material gain of one pawn (must still check in detail):
https://lichess.org/q2BIRDaX#98

GoK doesn't choose it, and it gets to ply 13 (I disabled LMR, same result), White Dove does not choose it, and it gets to ply 10, but congratulations, Element selects f4 on 6+8!

That game actually is the first draw for a long time, GoK (white) vs. White Dove. I will still add it to study and ELO generator.

Did you mean g4 in the position after 44…Re8 ? Where is the material gain? According to Stockfish, there are alternative moves in the position (e.g. Kf2). g4 isn’t the “only” move.

Again, where is the material gain? I don’t see it anywhere.

Was the game terminated early? Stockfish doesn’t show a threefold repetition.

Yes g4, f4 was a typo, corrected in original post.

50. g4 e5 51. Ng6 Rb7 52. dxe5 fxe5 53. Nxe5+

White up a pawn, that is at least what Stockfish shows. That static board is evaluated with 155 by GoK (which seems OK), on the path it chooses it gets to 292 at depth 4, it seems to see something there that won't materialize later.

Update: OK one reason (but not the only one) is over-rating king ring attacks (esp. several for on square), which are crazy in that scenario. The other reason is likely that it things the capture sequence is still available.

Black can play Re8, pushing the move far beyond the horizon (the white king can walk to h5).

Yes, this was a combination of an evaluation bug and horizon effect (see latest reply).

About the repetition, I offered a draw for GoK :-) But it would have ended in a “real” repetition, as GoK only checks the previous 32 moves for repetition, hence would not have prevented it. And if not that, it would have ended with 50-moves-rule.

I think the 2nd fastest win of GoK (Medium) on Scratch 3 against Bonsai Blue, in 12 moves. GoK saw the mate-in-3 in 0.1 seconds: https://lichess.org/ZbCw8a8b#24

ArnoHu wrote:

I think the 2nd fastest win of GoK (Medium) on Scratch 3 against Bonsai Blue, in 12 moves. GoK saw the mate-in-3 in 0.1 seconds: https://lichess.org/ZbCw8a8b#24

Wait… If that was the 2nd fastest win, how fast was the #1?

Here's a really strange WD v7.02 self play test.

This was to mainly ensure that the new table-based move gen for the pawns worked (along with some other new stuff), but this game it just terrible!

The queen get's trapped twice (and neither time does the other side realise this) and after this, the rook vs rook ending was just terrible! I stopped this game short even though black was winning because it didn't look like progress was going to occur, and even if a decisive result happened, it wouldn't really be that “important”.

https://lichess.org/jN4nYBid#107

S_P_A_R_T wrote:

ArnoHu wrote:

I think the 2nd fastest win of GoK (Medium) on Scratch 3 against Bonsai Blue, in 12 moves. GoK saw the mate-in-3 in 0.1 seconds: https://lichess.org/ZbCw8a8b#24

Wait… If that was the 2nd fastest win, how fast was the #1?

I think there was one, but most likely I won't be able to find it any more… maybe I am also wrong.