Basic move generator

[jshriver]

Anyone know of a very basic move generator w/ no pruning? Can be any format: bitbase, mbox, etc. I'm more interested in statistics than optimization. I've tried to write one myself, but it hasn't proven fruitful.

Any help is appreciated. I'm working on a "Project GoldenTree" I plan to post results here, but so far the core of the project is feeding a FEN board setup seed, and generating n-depth full length permutations of movements. I have everything else I need to get the project on it's feet, except for the move generator. I'm not out to great the next Rybka, but my research I still feel will be interesting. If anyone would be willing to help, give recommendations or code it would be duly noted.

While I'm not rich, I'd even be willing to pay for such a program. Feed it a FEN board, with n-depth and it spits out all permutations legal moves for that position.

Again, any help is appreciated. Feel free to contact me offlist jshriver <at> gmail.com subject "move generator"

-Josh

[Aleks Peshkov]

Search the web about "perft". Many free programs generate exactly what you want.

[Dann Corbit]

Search the web about "perft". Many free programs generate exactly what you want.

Along those lines, I think this one is the fastest one:
http://home.arcor.de/dreamlike/chess/index.html

You should ask Oliver Brausch about conditions for usage.

[hgm]

Search the web about "perft". Many free programs generate exactly what you want.

Along those lines, I think this one is the fastest one:
http://home.arcor.de/dreamlike/chess/index.html

You should ask Oliver Brausch about conditions for usage.

Why do you think this one is fast? Just because it lies about its nps?
The execution times suggest differently:

Code: Select all

F:\cygwin\home\chess\perft>OliPerft
 r n b q k b n r
 p p p p p p p p
 . . . . . . . .
 . . . . . . . .
 . . . . . . . .
 . . . . . . . .
 P P P P P P P P
 R N B Q K B N R

 1     0      0          20
 2     0      1         400
 3     0      3        8902
 4     0      5      197281
 5     0     33     4865609
 6     0    403   119060324

Nodes: 124132536 cs: 404 knps: 30672

F:\cygwin\home\chess\perft>..\qperft 6 H21
Hash-table size = 1fffff, Starts at 460020
 - - - - - - - - - - - -
 - - - - - - - - - - - -
 - - r n b q k b n r - -
 - - p p p p p p p p - -
 - - . . . . . . . . - -
 - - . . . . . . . . - -
 - - . . . . . . . . - -
 - - . . . . . . . . - -
 - - P P P P P P P P - -
 - - R N B Q K B N R - -
 - - - - - - - - - - - -
 - - - - - - - - - - - -

Quick Perft by H.G. Muller
Perft mode: Hash-table size = 32MB, bulk counting in horizon nodes

perft(1)=20 ( 0.000 sec)

perft(2)=400 ( 0.000 sec)

perft(3)=8902 ( 0.000 sec)

perft(4)=197281 ( 0.010 sec)

perft(5)=4865609 ( 0.120 sec)

perft(6)=119060324 ( 1.933 sec)

Oliperft takes 4.03 sec for perft(6), more than twice what qperft takes... (Both using 32MB hash.) Machine used here was a 1GHz Athlon XP (no DDR memory).

[Dann Corbit]

Here are my results:

Code: Select all

C:\pgn\winboard-engines\oliperft\Release>oliperft 7
 r n b q k b n r
 p p p p p p p p
 . . . . . . . .
 . . . . . . . .
 . . . . . . . .
 . . . . . . . .
 P P P P P P P P
 R N B Q K B N R

1:20:20
2:400:420
3:8902:9322
4:197281:206603
5:4865609:5072212
6:119060324:124132536
7:3195901860:3320034396

Nodes: 3320034396 ms: 31237 knps: 106285

Code: Select all

C:\pgn\WINBOA~1\qperft>qperft 7 H24
Hash-table size = ffffff, Starts at 460020
 - - - - - - - - - - - -
 - - - - - - - - - - - -
 - - r n b q k b n r - -
 - - p p p p p p p p - -
 - - . . . . . . . . - -
 - - . . . . . . . . - -
 - - . . . . . . . . - -
 - - . . . . . . . . - -
 - - P P P P P P P P - -
 - - R N B Q K B N R - -
 - - - - - - - - - - - -
 - - - - - - - - - - - -

Quick Perft by H.G. Muller
Perft mode: Hash-table size = 256MB, bulk counting in horizon nodes

perft(1)=20 ( 0.000 sec)

perft(2)=400 ( 0.000 sec)

perft(3)=8902 ( 0.000 sec)

perft(4)=197281 ( 0.000 sec)

perft(5)=4865609 ( 0.046 sec)

perft(6)=119060324 ( 0.719 sec)

perft(7)=3195901860 ( 8.657 sec)

[hgm]

Yes, and?

On your machine Oliperft needs 31.2 sec to calculate perft(7), qperft only 8.7 sec. Oliperft is nearly 4 times slower...

(This is a bit unfair comparison, as from the task manager I noticed that Oliperft only uses 32MB hash, while you run qperft here with 256MB. And especially for perft(7), where the hash table gets heavily overloaded, I expect this larger hash to make a significant difference. But I don't think this could make up for the factor 4. Perhaps a factor 2, at most. qperft uses a quite advanced replacement scheme, which is not very sensitive to overloading.)

[Dann Corbit]

Code: Select all

C:\pgn\WINBOA~1\qperft>qperft 12 H25
Hash-table size = 1ffffff, Starts at 460020
 - - - - - - - - - - - -
 - - - - - - - - - - - -
 - - r n b q k b n r - -
 - - p p p p p p p p - -
 - - . . . . . . . . - -
 - - . . . . . . . . - -
 - - . . . . . . . . - -
 - - . . . . . . . . - -
 - - P P P P P P P P - -
 - - R N B Q K B N R - -
 - - - - - - - - - - - -
 - - - - - - - - - - - -

Quick Perft by H.G. Muller
Perft mode: Hash-table size = 512MB, bulk counting in horizon nodes

perft(1)=20 ( 0.000 sec)

perft(2)=400 ( 0.000 sec)

perft(3)=8902 ( 0.000 sec)

perft(4)=197281 ( 0.000 sec)

perft(5)=4865609 ( 0.047 sec)

perft(6)=119060324 ( 0.734 sec)

perft(7)=3195901860 ( 8.641 sec)

perft(8)=84998978956 (114.568 sec)

perft(9)=2439530234167 (1848.005 sec)

perft(10)=69352859712417 (52563.045 sec)

[Dann Corbit]

Yes, and?

On your machine Oliperft needs 31.2 sec to calculate perft(7), qperft only 8.7 sec. Oliperft is nearly 4 times slower...

(This is a bit unfair comparison, as from the task manager I noticed that Oliperft only uses 32MB hash, while you run qperft here with 256MB. And especially for perft(7), where the hash table gets heavily overloaded, I expect this larger hash to make a significant difference. But I don't think this could make up for the factor 4. Perhaps a factor 2, at most. qperft uses a quite advanced replacement scheme, which is not very sensitive to overloading.)

I was simply marvelling at the speed of your perft.
I have perft envy!

[hgm]

This is always allowed.

I was just shocked that you suggested above that the other one was faster.

[Dann Corbit]

This is always allowed.

I was just shocked that you suggested above that the other one was faster.

I always seem to think that the fastest thing I have seen must be the fastest thing ever.