Perft results?

Code, algorithms, languages, construction...

Re: Perft results?

Postby 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.
thevinenator
 
Posts: 61
Joined: Tue Jun 02, 2015 11:02 pm

Re: Perft results?

Postby 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-ban/perft_gpu/master/perft14.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
BrianR
 
Posts: 9
Joined: Thu Jun 10, 2010 4:48 am

Re: Perft results?

Postby 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?

Postby notachessplayer » Wed Feb 15, 2017 3:50 pm

We did it boys!

perft 6
Depth: 6
Nodes: 119060324
Time: 998 ms
notachessplayer
 
Posts: 30
Joined: Thu Dec 29, 2016 10:13 pm

Re: Perft results?

Postby 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...
thevinenator
 
Posts: 61
Joined: Tue Jun 02, 2015 11:02 pm

Re: Perft results?

Postby 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?
thevinenator
 
Posts: 61
Joined: Tue Jun 02, 2015 11:02 pm

Re: Perft results?

Postby 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.
notachessplayer
 
Posts: 30
Joined: Thu Dec 29, 2016 10:13 pm

Previous

Return to Programming and Technical Discussions

Who is online

Users browsing this forum: No registered users and 1 guest