Diepeveen's move generator

Discussion of chess software programming and technical issues.

Moderators: Harvey Williamson, Dann Corbit, hgm

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
diep
Posts: 1786
Joined: Thu Mar 09, 2006 10:54 pm
Location: The Netherlands
Contact:

Re: Diepeveen's move generator

Post by diep » Tue Nov 20, 2012 10:57 am

Tom Likens wrote:
diep wrote:Had you considered shipping me an e-mail?
Yes, I would think if someone were interested in the Diep move generator, sending you an email
would be the quickest (and safest) way to get it. That *might* even be the best way to get any
questions you might have answered correctly.

My guess is you have 100% of the code for "Diepeveen's move generator" :wink:

regards,
--tom
"Vincent, thank you for offering your help, but I've managed to make my way through, no need for your help now... "

I rest my case.

btw are you going to benchmark a claim from 2000 at todays processors, after intel and AMD optimized them for specint2000, which was the leading benchmark right up to 2006, and which played a major role in deciding how they would optimize their processors... ...with crafty right inside that benchmark...

Tom Likens
Posts: 303
Joined: Sat Apr 28, 2012 4:18 pm
Location: Austin, TX
Contact:

Re: Diepeveen's move generator

Post by Tom Likens » Tue Nov 20, 2012 12:59 pm

Hrvoje Horvatic wrote: Tom,

it is a bit more complicated than that... I actually wanted feedback if anybody else has tried it and what results he got... I actually said that explicitly... :wink:

I started playing with chess programming somewhere around year 2000, and even back then Vincent was talking about how his move generator is faster than "beancounters"..., and it looks incredible to me that 12 years later still NOBODY tried to disprove him, or give him a credit if he is right...
Hello Hrvoje,

No offense intended of course. I actually was trying to be helpful :)

My guess is that you'll find Vincent is right. For raw speed, I think Vincent's approach
is hard to beat, (although bitboards may be somewhat more competitive on today's
machines, if inline assembly is used). Years ago, back in the 32-bit days, I looked at
this and bitboards were not the fastest. I used them for other reasons, as did most
programmers who selected them, (novelty, fad, crafty used them, the idea that a
64-bit word just "fit" the chessboard etc.).

If you have a web page (or some other format you could share) of the various move
generators and their performance, that would be incredibly interesting reading. It would
be even more valuable if you had code and could list the origins and authors. You might
even consider adding it to the chess programming Wiki. It already has a section on move
generation, (Diep's approach is mentioned there , along with Bruce's work on Ferret),
but your data would be a good addition. One suggestion, which may be more work than
you're willing to commit to, would be to separate things by 32-bit vs. 64-bit. The
performance really is different between today's architectures and the CPUs of yore.

regards,
--tom

Karlo Bala
Posts: 323
Joined: Wed Mar 22, 2006 9:17 am
Location: Novi Sad, Serbia

Re: Diepeveen's move generator

Post by Karlo Bala » Tue Nov 20, 2012 3:34 pm

Hrvoje Horvatic wrote:
Gerd Isenberg wrote:I just found some more code of Vincent's generator in Mridul Muralidharan's Random thought blog:
http://mridulm.blogspot.de/2004/06/perm ... ut-up.html
I made it work... I still have several bugs and many things to solve (we all know that chess programming TAKES TIME), but it seems that this stuff is good...

Very early preliminary results show that my bad adaptation of Vincent's move generator is about 20% faster than crafty... I have to check several more things to be sure, I still don't stand behind this, but this DEFINITELY shows promise...
Crafty uses 2 functions to generate moves, "GenerateNoncaptures" and "GenerateCaptures". Basically, Crafty generate same attacks masks 2 times. If Bob wanted to have ultra fast perft he would merged the two functions.
Best Regards,
Karlo Balla Jr.

diep
Posts: 1786
Joined: Thu Mar 09, 2006 10:54 pm
Location: The Netherlands
Contact:

Re: Diepeveen's move generator

Post by diep » Tue Nov 20, 2012 5:12 pm

Karlo Bala wrote:
Hrvoje Horvatic wrote:
Gerd Isenberg wrote:I just found some more code of Vincent's generator in Mridul Muralidharan's Random thought blog:
http://mridulm.blogspot.de/2004/06/perm ... ut-up.html
I made it work... I still have several bugs and many things to solve (we all know that chess programming TAKES TIME), but it seems that this stuff is good...

Very early preliminary results show that my bad adaptation of Vincent's move generator is about 20% faster than crafty... I have to check several more things to be sure, I still don't stand behind this, but this DEFINITELY shows promise...
Crafty uses 2 functions to generate moves, "GenerateNoncaptures" and "GenerateCaptures". Basically, Crafty generate same attacks masks 2 times. If Bob wanted to have ultra fast perft he would merged the two functions.
This has nothing to do with perft. Perft is total uninteresting - only used to verify correctness of your move generator + makemove + incheck function.

Note that to see whether you have a castling bug you already would need to do a perft of depth=10 or more, which is not something you do 'overnight'.

(for example: e4 e5 Nf3 Nf6 Bc4 Bc5 Ke2 d6 Ke1 Nc6 and only now at the 11th ply you might see a bug there.

So perft is not useful to detect all bugs there.

As i posted 10 years ago there is a 100 tricks you can use to speedup perft which has nothing to do with a normal chessprogram.

syzygy
Posts: 4822
Joined: Tue Feb 28, 2012 10:56 pm

Re: Diepeveen's move generator

Post by syzygy » Tue Nov 20, 2012 7:10 pm

Hrvoje Horvatic wrote:Very early preliminary results show that my bad adaptation of Vincent's move generator is about 20% faster than crafty... I have to check several more things to be sure, I still don't stand behind this, but this DEFINITELY shows promise...
Just out of curiosity, what are you measuring exactly?

Karlo Bala
Posts: 323
Joined: Wed Mar 22, 2006 9:17 am
Location: Novi Sad, Serbia

Re: Diepeveen's move generator

Post by Karlo Bala » Tue Nov 20, 2012 7:17 pm

diep wrote:
Karlo Bala wrote:
Hrvoje Horvatic wrote:
Gerd Isenberg wrote:I just found some more code of Vincent's generator in Mridul Muralidharan's Random thought blog:
http://mridulm.blogspot.de/2004/06/perm ... ut-up.html
I made it work... I still have several bugs and many things to solve (we all know that chess programming TAKES TIME), but it seems that this stuff is good...

Very early preliminary results show that my bad adaptation of Vincent's move generator is about 20% faster than crafty... I have to check several more things to be sure, I still don't stand behind this, but this DEFINITELY shows promise...
Crafty uses 2 functions to generate moves, "GenerateNoncaptures" and "GenerateCaptures". Basically, Crafty generate same attacks masks 2 times. If Bob wanted to have ultra fast perft he would merged the two functions.
This has nothing to do with perft. Perft is total uninteresting - only used to verify correctness of your move generator + makemove + incheck function.

Note that to see whether you have a castling bug you already would need to do a perft of depth=10 or more, which is not something you do 'overnight'.

(for example: e4 e5 Nf3 Nf6 Bc4 Bc5 Ke2 d6 Ke1 Nc6 and only now at the 11th ply you might see a bug there.

So perft is not useful to detect all bugs there.

As i posted 10 years ago there is a 100 tricks you can use to speedup perft which has nothing to do with a normal chessprogram.
No, you don't need a perft of depth 10 to find a castling bug, you just need to use a different starting position.
The point was the move generator speed, and one way to measure its speed is perft (without tricks).
Best Regards,
Karlo Balla Jr.

diep
Posts: 1786
Joined: Thu Mar 09, 2006 10:54 pm
Location: The Netherlands
Contact:

Re: Diepeveen's move generator

Post by diep » Tue Nov 20, 2012 7:38 pm

Karlo Bala wrote:
diep wrote:
Karlo Bala wrote:
Hrvoje Horvatic wrote:
Gerd Isenberg wrote:I just found some more code of Vincent's generator in Mridul Muralidharan's Random thought blog:
http://mridulm.blogspot.de/2004/06/perm ... ut-up.html
I made it work... I still have several bugs and many things to solve (we all know that chess programming TAKES TIME), but it seems that this stuff is good...

Very early preliminary results show that my bad adaptation of Vincent's move generator is about 20% faster than crafty... I have to check several more things to be sure, I still don't stand behind this, but this DEFINITELY shows promise...
Crafty uses 2 functions to generate moves, "GenerateNoncaptures" and "GenerateCaptures". Basically, Crafty generate same attacks masks 2 times. If Bob wanted to have ultra fast perft he would merged the two functions.
This has nothing to do with perft. Perft is total uninteresting - only used to verify correctness of your move generator + makemove + incheck function.

Note that to see whether you have a castling bug you already would need to do a perft of depth=10 or more, which is not something you do 'overnight'.

(for example: e4 e5 Nf3 Nf6 Bc4 Bc5 Ke2 d6 Ke1 Nc6 and only now at the 11th ply you might see a bug there.

So perft is not useful to detect all bugs there.

As i posted 10 years ago there is a 100 tricks you can use to speedup perft which has nothing to do with a normal chessprogram.
No, you don't need a perft of depth 10 to find a castling bug, you just need to use a different starting position.
The point was the move generator speed, and one way to measure its speed is perft (without tricks).
Not at all, doing perft in a simple minded manner then you are not spending much system time to generation, all system time goes to checking whether a move is legal or not.

This where the chess engines are not busy with that. They just capture the king when you happen to be in an illegal position. Doing things semi-legal is way faster of course.

Perft however only counts LEGAL positions, which of course needs 100 tricks to speed that up (and they are there) and where incremental type tricks really win all battles.

So perft is total utter useless for chess engines other than measuring whether you can correctly generate when needed. Note i never needed perft myself.

Post Reply