Perft

[Harm Jetten]

Hello all,

Your interesting discussions on this forum have inspired me to try my hand at draughts programming again. I'm starting from scratch with a bitboard-based move generator, and hope to grow it into a draughts engine that can be controlled by a GUI using the GUIDE protocol.
I'm also looking for a good name (it won't be Dam x.y).
Here are the perft results, they look competitive already.

The 3 standard positions on my Core2 2.53GHz (E7200), 64-bit code, gcc 4.3.4 on linux:

perft(11) 1665861398 nodes, 45.35 sec, 36731 kN/s, nobulk
perft(9) 1216917193 nodes, 29.75 sec, 40901 kN/s, nobulk
perft(15) 346184885 nodes, 12.09 sec, 28627 kN/s, nobulk

perft(11) 1665861398 nodes, 21.89 sec, 76100 kN/s, bulk
perft(9) 1216917193 nodes, 13.55 sec, 89823 kN/s, bulk
perft(15) 346184885 nodes, 7.01 sec, 49388 kN/s, bulk

For comparison, the Dam 2.2 move generator, same machine, 32-bit code, gcc 4.3.4 on linux:

perft(11) 1665861398 nodes, 220.37 sec, 7560 kN/s, nobulk
perft(9) 1216917193 nodes, 124.85 sec, 9747 kN/s, nobulk
perft(15) 346184885 nodes, 48.62 sec, 7120 kN/s, nobulk

perft(11) 1665861398 nodes, 132.34 sec, 12587 kN/s, bulk
perft(9) 1216917193 nodes, 53.80 sec, 22621 kN/s, bulk
perft(15) 346184885 nodes, 27.69 sec, 12500 kN/s, bulk

Harm.

[Rein Halbersma]

Hello all,

Your interesting discussions on this forum have inspired me to try my hand at draughts programming again. I'm starting from scratch with a bitboard-based move generator, and hope to grow it into a draughts engine that can be controlled by a GUI using the GUIDE protocol.
I'm also looking for a good name (it won't be Dam x.y).
Here are the perft results, they look competitive already.

The 3 standard positions on my Core2 2.53GHz (E7200), 64-bit code, gcc 4.3.4 on linux:

perft(11) 1665861398 nodes, 45.35 sec, 36731 kN/s, nobulk
perft(9) 1216917193 nodes, 29.75 sec, 40901 kN/s, nobulk
perft(15) 346184885 nodes, 12.09 sec, 28627 kN/s, nobulk

perft(11) 1665861398 nodes, 21.89 sec, 76100 kN/s, bulk
perft(9) 1216917193 nodes, 13.55 sec, 89823 kN/s, bulk
perft(15) 346184885 nodes, 7.01 sec, 49388 kN/s, bulk

For comparison, the Dam 2.2 move generator, same machine, 32-bit code, gcc 4.3.4 on linux:

perft(11) 1665861398 nodes, 220.37 sec, 7560 kN/s, nobulk
perft(9) 1216917193 nodes, 124.85 sec, 9747 kN/s, nobulk
perft(15) 346184885 nodes, 48.62 sec, 7120 kN/s, nobulk

perft(11) 1665861398 nodes, 132.34 sec, 12587 kN/s, bulk
perft(9) 1216917193 nodes, 53.80 sec, 22621 kN/s, bulk
perft(15) 346184885 nodes, 27.69 sec, 12500 kN/s, bulk

Harm.

Hi Harm,

That are certainly some impressive speedups. How was your old generator set up? With a board as an array of squares?

And can you tell us some more about the GUIDE protocol? Where can I read the standard?

Rein

[Harm Jetten]

Hi Rein,

The Dam 2.2 move generator indeed uses an array of bytes, indexed by square number 1..50. There is also a 2-dimensional array [51][4] that has for each square the 4 neighboring square numbers. That makes for pretty efficient code to e.g. slide along the empty leading squares for king captures.

The GUIDE protocol was developed by Bert Tuyt and Michel Grimminck in 2004. I saw a reference to it on this board and asked Bert for the spec. He actually sent me 3 slightly different versions, I would prefer if Bert could consolidate them and publish it.
The freely downloadable versions of Damage and Dragon both use GUIDE.

Harm.

[BertTuyt]

Herewith some GUIDE (Graphical Universal Interface Draughts Engines) background.

The basic idea was that if we (Michel and myself) provided a free GUI, and a standard protocol for Engine GUI communication, programmers only have to focus on Engine Development.

I started with this GUIDE idea, based on a similar approach in Chess (WinBoard). Also I liked the idea of 2 separate applications for Engine and GUI.

With Michel we discussed the details, and in the end we have both (more or less) implemented this in our GUI (both are free available, as a download).

Im sure that both implementations are slightly different (and don't fully comply with the proposed standard), nor do i believe we have included all options yet.

If some-one is interested i can update the GUIDE protocol document (word file) and post it here on the forum (if some-one could explain how to do this).

Because i would like to have an open standard in the end, I would appreciate all kinds of comments/suggestions, so we can all agree on the final implementation.

Next to that, for all who want to further improve develop my Damage GUI (see my download page), I don't have any problem in sharing all sources (Visual Studio C++, which is quite extensive), with the boundary conditions, that if improvements are made I would like to receive updated sources.
And the other condition is that there is no commercial use.

With kind regards,

Bert

[Maurits Meijer]

i'd love to see the GUIDE specs, i think you can upload files and attach them to your posts. it's under the box you type in.

[ildjarn]

Can something like UCI be used for draughts?

[Ed Gilbert]

Hello all,

Your interesting discussions on this forum have inspired me to try my hand at draughts programming again. I'm starting from scratch with a bitboard-based move generator, and hope to grow it into a draughts engine that can be controlled by a GUI using the GUIDE protocol.

Hi Harm,

It is nice to hear that you are actively working on draughts programming again. I will look forward to seeing your new engine.

-- Ed

[Ed Gilbert]

Harm, are you also developing a gui based on the guide protocol, or do you plan to use an existing gui?

-- Ed

[Harm Jetten]

Ed,

I'm planning to use the Bert's Damage2000 as a GUI for the time being. That way I can concentrate on engine performance first. Later on perhaps I'd like to make a GUI as well, possibly in Java or Python for portability across platforms.

Harm.

[jj]

Hello all,

Here are my perft results, slightly optimized after the Leiden tournament:

perft(11) total 1665861398 nodes, 53,53 sec, 31120 knodes/sec NO BULK
perft( 9) total 1216917193 nodes, 38,80 sec, 30375 knodes/sec NO BULK
perft(15) total 346184885 nodes, 14,88 sec, 23273 knodes/sec NO BULK

perft(11) total 1665861398 nodes, 28,81 sec, 57816 knodes/sec BULK
perft( 9) total 1216917193 nodes, 22,22 sec, 54769 knodes/sec BULK
perft(15) total 346184885 nodes, 10,42 sec, 33217 knodes/sec BULK

Running on Intel Core2 E8400 3.0 GHz, Windows XP pro x64, and Java HotSpot VM 64-bits.

A 64-bit Java to native compiler is not yet available

However, Excelsior has finally announced the 64-bit version of their JET compiler.
The 32-bit version gives a speedup of about 30% for ABCdam on 32-bit platforms,
compared to the HotSpot VM.

Jan-Jaap

[Ed Gilbert]

Hi Jan-Jaap,

Those are very good numbers for an interpreted language. I did not think it would be possible to get a move generator to run that quickly in (not compiled) Java.

-- Ed

[MichelG]

An old topic revisited

So if you are around 140 MN/s , this would imply you are twice as fast as Harm.
Even when you correct for a faster processor and higher speed, this is still remarkable.
Could you share the result (maybe including position 2 and 3, see the perft blog)?
Maybe you could post in the perft section, so we have a new yardstick to focus on...

Bert

These are the numbers of 2 of my computers. All bulk counting.

Code: Select all

i7 980 @ 3.33 Ghz
pos 1(11) 1.665.861.398  time: 12.85  nps:129.6
pos 2(9)  1.216.917.193  time: 9.61  nps:126.6
pos 3(15) 346.184.885  time: 4.45  nps:77.9

core2 @ 2.66 Gz
pos 1(11) 1.665.861.398  time: 16.66  nps:100.0
pos 2(9)  1.216.917.193  time: 13.88  nps:87.7
pos 3(15) 346.184.885  time: 6.33  nps:54.7

Note that it gets very difficult to compare values on different computers. For instance, the i7 980 will most likely run in turbo mode at 3.6 Ghz, but i can't be sure. And different architectures can have different latencies for stuff like bitScan or multiply.

I think i can get the times a bit down by a few percent, but that will also increase the amount of code a lot, so i am not sure if i will.

Michel

[BertTuyt]

Michel thanks for sharing.

Comparing this with my old numbers (on a 2.93 GHZ i7940) 22.79 (56%) sec, 12.40 (78%) sec and 5.96 (75%) sec you are remarkably faster.
Especially the first benchmark difference is striking (and certainly not only attributed to the differences in clock speed).
After i have stabilized the new search, debugged the evaluation and get the parallel YBWC implementation running, i also think i need to convert to Position output for the MoveGenerator in stead on Move output..

Bert

[MichelG]

Michel thanks for sharing.

Comparing this with my old numbers (on a 2.93 GHZ i7940) 22.79 (56%) sec, 12.40 (78%) sec and 5.96 (75%) sec you are remarkably faster.
Especially the first benchmark difference is striking (and certainly not only attributed to the differences in clock speed).
After i have stabilized the new search, debugged the evaluation and get the parallel YBWC implementation running, i also think i need to convert to Position output for the MoveGenerator in stead on Move output..

Bert

After adding some more code:

Code: Select all

1: 11 1.665.861.398  time: 10.73  nps:155.2
2: 9 1.216.917.193  time: 9.72  nps:125.2
3: 346.184.885  time: 4.41  nps:78.4

Here you can see a bit of choice for optimization. Here position 1 and 3 are faster, but 2 is slower.

edit 26-9-2012: fixed a bug, rerun the test

[Maurits Meijer]

This topic was very useful in building my new javascript bitboard engine.
Here are some of my stats.
Everything is 32 bit and runs in a single thread on an Athlon 4450e 2.3 GHz.
Node.js

Code: Select all

Start position
1.      9          1       9kN/s
2.      81         0       81kN/s
3.      658        24      27.42kN/s
4.      4265       52      82.02kN/s
5.      27117      77      352.17kN/s
6.      167140     55      3038.91kN/s
7.      1049442    355     2956.17kN/s
8.      6483961    2100    3087.6kN/s
9.      41022423   12766   3213.41kN/s

Test position with 530 redundant moves
1.      14       11      1.27kN/s
2.      55       21      2.62kN/s
3.      1168     21      55.62kN/s
4.      5432     21      258.67kN/s
5.      87195    59      1477.88kN/s
6.      629010   252     2496.07kN/s
7.      9041010  2145    4214.92kN/s
8.      86724219 22909   3785.6kN/s

Woldouby
1.      6        0       6kN/s
2.      12       0       12kN/s
3.      30       16      1.88kN/s
4.      73       1       73kN/s
5.      215      2       107.5kN/s
6.      590      8       73.75kN/s
7.      1944     8       243kN/s
8.      6269     11      569.91kN/s
9.      22369    43      520.21kN/s
10.     88050    96      917.19kN/s
11.     377436   239     1579.23kN/s
12.     1910989  1039    1839.26kN/s
13.     9872645  5126    1925.99kN/s
14.     58360286 27982   2085.64kN/s

In browsers
To keep things brief I'll give just the nodes per second for the depest level of the start position
Chrome 22.0.1229.94
2227.4 kN/s

Internet Explorer 9.0.8112.16421
756.63 kN/s

FireFox 16.0.1
976.23 kN/s

Safari 5.1.7
671.43 kN/s

Ipad(Safari)
36.49 kN/s

Ipad3(Safari)
120.91 kN/s

I would like to get the scores from some other mobile devices. You can run the perft here http://slagzet.com/perft (it stops when every position has reached a depth that took more then half a second to compute)
You can play the engine on http://slagzet.com/play