fast(er) movegen

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.
alessandro
Posts: 17
Joined: Tue Aug 12, 2014 9:21 am
Location: Oldenburg
Full name: Alessandro Iavicoli
Contact:

Re: fast(er) movegen

Post by alessandro » Mon Dec 10, 2018 4:01 pm

AdaChess uses a 10x12 array for the board design plus and a pieces-list to quickly find where the pieces are located.

The most expensive task while generating moves is the test for validity: not leaving the king in check. Therefore, engines tends to either don't test it (and leave the search to skip those nodes) or perform the legality check only when strictly required. AdaChess uses this second approach, by considering absolute pinned pieces movement, king escapes and so on.

Those are the best number on my Surface Pro after some tries. No hash used, and 1 core.

Code: Select all

Depth     Nodes      Captures    En-Passant       Castles    Promotions        Checks    Checkmates   Time
1            20             0             0             0             0             0             0   0.00
2           400             0             0             0             0             0             0   0.00
3          8902            34             0             0             0            12             0   0.00
4        197281          1576             0             0             0           469             8   0.02
5       4865609         82719           258             0             0         27351           347   0.47
6     119060324       2812008          5248             0             0        809099         10828  11.50
AdaChess, however, performs a search to detect the kind of check (if a move checks the opponent king), that makes the generation a bit more heavy than necessary.
In the italian forum, by talking about perft with other italian programmers, we agreed that once the move generator is optimized to reduce the legality test on the minimum, then there's no reason to spend more time to optimize it further (due to the limited amount of time that the engine spend in generating moves).

I believe that the optimization of the move generator became significant only once the engine reaches 3000+ Elo or when every small improvements matters.
--
Have a look at AdaChess - https://www.adachess.com

Image

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

Re: fast(er) movegen

Post by hgm » Mon Dec 10, 2018 6:35 pm

xr_a_y wrote:
Mon Dec 10, 2018 3:50 pm
qperft is optimized a lot, this is not a move generator to use in engine I think.
It was used in Joker.

User avatar
xr_a_y
Posts: 356
Joined: Sat Nov 25, 2017 1:28 pm
Location: France

Re: fast(er) movegen

Post by xr_a_y » Mon Dec 10, 2018 7:21 pm

sorry, didn't know.

Ratosh
Posts: 57
Joined: Mon Apr 16, 2018 4:56 pm

Re: fast(er) movegen

Post by Ratosh » Mon Dec 10, 2018 7:58 pm

HGM's move generation on qperft is a good reference for speed. If you want to change your board representation there is no doubt that bitboard representation is the fastest.

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

Re: fast(er) movegen

Post by hgm » Mon Dec 10, 2018 8:01 pm

Ratosh wrote:
Mon Dec 10, 2018 7:58 pm
HGM's move generation on qperft is a good reference for speed. If you want to change your board representation there is no doubt that bitboard representation is the fastest.
Actually I doubt that.

Dann Corbit
Posts: 9289
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: fast(er) movegen

Post by Dann Corbit » Mon Dec 10, 2018 8:20 pm

hgm wrote:
Mon Dec 10, 2018 8:01 pm
Ratosh wrote:
Mon Dec 10, 2018 7:58 pm
HGM's move generation on qperft is a good reference for speed. If you want to change your board representation there is no doubt that bitboard representation is the fastest.
Actually I doubt that.
The fastest is using GPUs.
Ankan's GPU perft is absurdly faster than anything else.
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.

Ratosh
Posts: 57
Joined: Mon Apr 16, 2018 4:56 pm

Re: fast(er) movegen

Post by Ratosh » Mon Dec 10, 2018 9:50 pm

Oh, i assumed it since most top engines use bitboard. What would be the reason why they would chose it over other options?

Michael Sherwin
Posts: 2850
Joined: Fri May 26, 2006 1:00 am
Location: OH, USA

Re: fast(er) movegen

Post by Michael Sherwin » Mon Dec 10, 2018 10:09 pm

For people that have no idea how to program a GPU, like me, I did some CPU perft examples about 15 years ago.

On my computer, an i7-3930k, running at 3.2 GHz single threaded I get the following results.

Stockfish 10 bench 6 1,697,099 nodes/sec

My Examples: Every move made and unmade and no move counts cashed.

Carnivor: GNU 4 style move generator - enhanced
36,649,859 nodes/sec

Halfwit: Classic Chess 4.5 style bitboards - enhanced
25,930,980 nodes/sec

Conundrum: Move generation as a state machine (I think or maybe just incremental) 100% original
38,679,036 nodes/sec

Godzilla: A purely jump table driven move generator in x86 32 bit assembly 100% original with a top level C main() module
66,799,849 nodes/sec

NOTE: These examples are just for speed and not accuracy as they just count pseudo legal moves.

My processor i7-3930k CPU MARK 1935 an i9-9900k CPU MARK 2898

Source code for the examples is available on request.
Regards,
Mike

User avatar
gbtami
Posts: 355
Joined: Wed Sep 26, 2012 11:29 am
Location: Hungary
Contact:

Re: fast(er) movegen

Post by gbtami » Mon Dec 10, 2018 10:16 pm

It would be very kind if you can put these sources to a github repo.

Michael Sherwin
Posts: 2850
Joined: Fri May 26, 2006 1:00 am
Location: OH, USA

Re: fast(er) movegen

Post by Michael Sherwin » Mon Dec 10, 2018 10:22 pm

gbtami wrote:
Mon Dec 10, 2018 10:16 pm
It would be very kind if you can put these sources to a github repo.
I'll see if I can figure out how to do that. But, I'm an old dog and it's not easy for me to learn new tricks, wuf wuf. :?
Regards,
Mike

Post Reply