Perft results?

Code, algorithms, languages, construction...
thevinenator
Posts: 68
Joined: Tue Jun 02, 2015 11:02 pm
Real Name: Vince

Re: Perft results?

Post by thevinenator » Sun Feb 12, 2017 4:30 am

I forgot to add that the makemove also keeps track of the serialized board Board[64].
that is needed to prevent you from having to loop so much in bitboards.

I was late to using bitboards but I would never go back. they are great for solving a multitude of evaluation questions. check the chess wiki evaluation pages for examples of how much you can do with bitboards.

my code is in C/C++ using MSVS. I use that tool for my work and I am very familiar with it.

code in what you are familiar with. once you get a good solid program you can port it to something else if you like. if you do plan to use bitboards, be sure to check if your development platform/IDE supports unsigned long long (64-bit unsigned) data types.

good luck.
"An Engine's strength flows from the Search. But beware, pruning, extensions, reductions; the dark side of the Search are they. Once you start down the dark path, it will dominate and consume you, as it has to so many developers before.” -- Yoda

BrianR
Posts: 17
Joined: Thu Jun 10, 2010 4:48 am

Re: Perft results?

Post by BrianR » Sun Feb 12, 2017 3:16 pm

notachessplayer wrote:Alright, after optimizing my code structure and algorithms, I have come down to:

1048ms for perft 6!

Pretty good, considering I started this whole ordeal with an initial time of 120s :roll:
I've been working so hard on it that I needed to share, even though it is essentially useless for an actual engine.
I still have some optimization ideas that could perhaps give me 1020ms. I think I will set my goal on going under 1s, and then finally improve my search engine lol.

Is there any documentation about the fastest engines out there? There doesn't seem to be much love for speed, but I thought I'd ask anyway.

Cheers.
Excellent progress.

For a different approach (with source code) see
https://github.com/ankan-ban/perft_gpu
https://raw.githubusercontent.com/ankan ... erft14.txt

I get perft 9 in 3.6 sec on my single GTX 1070 GPU.

Perft 14 link above is with 3 GPUs and much faster.

He also has a CPU perft repository here
https://github.com/ankan-ban/perft_cpu

notachessplayer
Posts: 30
Joined: Thu Dec 29, 2016 10:13 pm

Re: Perft results?

Post by notachessplayer » Tue Feb 14, 2017 2:01 am

My bad thevineator, I was convinced you were coding in Java, for some reason.

Could you educate me with this following question: are things done with bitboards impossible with other structures? I reckon it's less memory consuming, but aren't 64bits essentially boolean arrays? Not trying to be a smartass, genuine question.

BrianR, I tested his executables and it's pretty insane. Although I personally do not appreciate the multi-threading approach (feels like cheating :roll:), I'm sure he really understands how to optimize it. Not sure if his move generation is really that good, though?

Btw, I'm now under 1020ms. Getting closer to 0.xs!

notachessplayer
Posts: 30
Joined: Thu Dec 29, 2016 10:13 pm

Re: Perft results?

Post by notachessplayer » Wed Feb 15, 2017 3:50 pm

We did it boys!

perft 6
Depth: 6
Nodes: 119060324
Time: 998 ms

thevinenator
Posts: 68
Joined: Tue Jun 02, 2015 11:02 pm
Real Name: Vince

Re: Perft results?

Post by thevinenator » Wed Feb 15, 2017 7:32 pm

notachessplayer wrote:My bad thevineator, I was convinced you were coding in Java, for some reason.

Could you educate me with this following question: are things done with bitboards impossible with other structures? I reckon it's less memory consuming, but aren't 64bits essentially boolean arrays? Not trying to be a smartass, genuine question.
There are many threads about the benefits of bitboards. just for starters, how would you code "how many pawns are on the opponents side of the board?", using arrays? you would have to loop through each square on the board (or piece table if you have those) and determine it's rank and then increment a counter if the rank is considered on the opponents side of the board.
with bitboards, you'll already have a bitboard that has the location of the pawns of each color (pretty typical to have this), and since you know you'll want to ask the question at some point, you can created an array of two bitboards (one for each color), that has the bits set that represents the squares that are on the our side of the board. you "and" the two together and then call "popcount" to return the count.

in this example, color is 0 for black, 1 for white (I do it this way because of how I have everything else structured). POPCNT is a macro that calls the implementation of the population count. on some processors, that is a built in machine instruction, if not, there are many ways (see wiki chess programming pages) for examples. bbPieces[] is an array of bitboards that contains the locations of all the pieces. my implementation is:

BLACK = 0
WHITE = 1
PAWN = 2
KNIGHT = 4
etc

element
0 location of all the black pieces
1 location of all the white pieces
2 black pawns
3 white pawns
4 black knights
5 white knights
... etc.

cnt = POPCNT(bbPieces[PAWN + color] & bbOurSqrs[color ^ 1]);

adding the color to PAWN points to the element for the pawns from the point of view of "color"
(color ^ 1) flips color so white is black and visa versa (opponents color).

hope this helps...
"An Engine's strength flows from the Search. But beware, pruning, extensions, reductions; the dark side of the Search are they. Once you start down the dark path, it will dominate and consume you, as it has to so many developers before.” -- Yoda

thevinenator
Posts: 68
Joined: Tue Jun 02, 2015 11:02 pm
Real Name: Vince

Re: Perft results?

Post by thevinenator » Wed Feb 15, 2017 7:42 pm

[/quote]
For a different approach (with source code) see
https://github.com/ankan-ban/perft_gpu
https://raw.githubusercontent.com/ankan ... erft14.txt
[/quote]

amazing results. it probably isn't easy to interface to, but what performance!

how does it actually perform when used in a tree search. do you have any comparisons?

question though, does this only work on the high end graphic cards or can the cards that are built into laptops, for example be used?
"An Engine's strength flows from the Search. But beware, pruning, extensions, reductions; the dark side of the Search are they. Once you start down the dark path, it will dominate and consume you, as it has to so many developers before.” -- Yoda

notachessplayer
Posts: 30
Joined: Thu Dec 29, 2016 10:13 pm

Re: Perft results?

Post by notachessplayer » Sat Feb 18, 2017 5:05 am

I see. I'm still not sold on bitboards, but I shall try for sure at some point.

I also wonder how well this guy's program would do. Obviously the search approach would be a little different, but I can see it work pretty well regardless. Still though, it's probably not for every machine.


As for me, I'm finally satisfied with my program, reached my goals and can now work on my AI!

I tried storing moves for already visited positions, but it's significantly slower because of the copy of the array of moves (which are structs) into my table.
I wonder if it is what people do when they talk about a hash table for move generation, or if there is another way I didn't consider (granted I didn't give it much thought).

For the record, I do, from the initial position:
-perft 6 in 968ms
-perft 7 (forgot)
-perft 8 in ~11min30s
-perft 9 in ~5h30min

I don't think perft 10 will happen though, I don't want to let my pc run for that long :ugeek:. I also don't think I can realistically go under 900ms with my structure.

peterellisjones
Posts: 2
Joined: Sat Mar 18, 2017 4:50 pm
Real Name: Peter Ellis Jones

Re: Perft results?

Post by peterellisjones » Sat Mar 18, 2017 5:02 pm

I recently open-sourced a perft generation tool I'm building in Rust as a stepping-stone to building my own engine that I think is reasonably fast. I get perft(6) in about 0.21 seconds on my 2015 2.5Ghz i7 Macbook Pro. I'm cheating a bit because it's multi-threaded but when it was single-threaded with no hashing the nodes-per-second were about 1X to 3X compared to QPerft compiled with -O3, depending on the position. The speed varies greatly with position — it seems to be much faster at open positions with many sliding pieces (eg Kiwipete), rather than blocked positions like the starting position.

Source code [here][https://github.com/peterellisjones/rustperft]

Starting position depth 6:

Code: Select all

➜  rustperft git:(master) ./target/release/rustperft --fen "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w QqKk - 0 1" --depth 6
Using 7500000 bytes shared hash and 312496 bytes per-thread hash accross 8 threads (total: 9999968 bytes)
+-------+---------+------------------+-----------+----------+-------------+---------+------------+
| depth | seconds | nodes per second |     nodes | captures | ep captures | castles | promotions |
+-------+---------+------------------+-----------+----------+-------------+---------+------------+
|     6 |    0.22 |        531683698 | 119060324 |  2812008 |        5248 |       0 |          0 |
+-------+---------+------------------+-----------+----------+-------------+---------+------------+
Kiwipete depth 5

Code: Select all

➜  rustperft git:(master) ./target/release/rustperft --fen "r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq -" --depth 5
Using 7500000 bytes shared hash and 312496 bytes per-thread hash accross 8 threads (total: 9999968 bytes)
+-------+---------+------------------+-----------+----------+-------------+---------+------------+
| depth | seconds | nodes per second |     nodes | captures | ep captures | castles | promotions |
+-------+---------+------------------+-----------+----------+-------------+---------+------------+
|     5 |    0.19 |       1034192071 | 193690690 | 35043416 |       73365 | 4993637 |       8392 |
+-------+---------+------------------+-----------+----------+-------------+---------+------------+

peterellisjones
Posts: 2
Joined: Sat Mar 18, 2017 4:50 pm
Real Name: Peter Ellis Jones

Re: Perft results?

Post by peterellisjones » Wed Apr 05, 2017 2:09 pm

For an added datapoint: I've managed to get a pretty fast perft using bitboards. Code is all open source and available here: https://github.com/peterellisjones/rust_move_gen

For the initial position I get 0.79 seconds for P6 single threaded, no hash vs 0.655 for qperft compiled with -O3. This goes down to 0.19 when you add in multi-threading and hashing.

For kiwipete ("r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq -") I get 0.64 for P5 single threaded, no hash vs 0.973 for qperft compiled with -O3).

It seems to be faster when there are many sliders and a lot of space for them, probably due to the fact I'm using bitboards and kogge-stone algorithms for checking pins and checks, which scale well with multiple sliders.

Post Reply