Page 1 of 2

Perft results?

Posted: Sun Jan 01, 2017 11:36 pm
by notachessplayer
Hello,

I wanted to have your engine's perft results, and the methods used (all moves made/unmade, threading, hash update, checks...).
My engine is written in Java and I'm starting to feel like the language has its limits when it comes to chess programming, therefore I would really like to be able to compare.
Sharper executes a perft 6 about in 1s, but I do not believe it is doing all the moves normally and is "cheating" the test. Only now do I realize it and was getting nearly depressed that my engine was nearly 10 times slower when in fact I was making every single move and also verifying checkmates.

On the initial position, with legal moves, draw updates, hashing updates, check verification... except I do not make/unmake at depth 1:
-at depth 5: 4865609 nodes / 406ms
-at depth 6: 119060324 nodes / 4035ms

Also, windows 10 64bits / laptop with processor i7-6700HQ @ 2.60GHz

How fast is this compared to you? And also, is it slow, keeping in mind it's Java (specifically, aimed for Android)?

I have made my very own representation (with the obvious 8x8 two dimensional array, and many less obvious ideas :D) without documenting myself and no prior knowledge of chess, and am now looking in starting over with a popular style. How fast do you think I could make it?

Also (this is a little off-topic), what is the point of generating pseudo-legal moves? Isn't it much slower, because you have to verify a check position for every move made? Are there awesome formulas to find those with each famous board representation?

Re: Perft results?

Posted: Mon Jan 02, 2017 1:02 pm
by H.G.Muller
qperft (which is the perft based on Joker's move generator and MakeMove(), written in plain C) does perft(6) in 1.073 sec, on a 2.4GHz i3. It does not make the moves at d=1 (in a search you would not do that either, so it is a better speed measure for an engine that way). Except for King moves, as it was easier to test their legality after you make them.

Re: Perft results?

Posted: Mon Jan 02, 2017 9:38 pm
by notachessplayer
That is insanely fast if it does everything fairly, without a TT, multi-threading, etc.

Do you know the board representation used?

I just can't help finding it hard to believe that an engine would generate every single move, make and unmake them up to depth 6 (without last depth). My solution is certainly not de best by any means, but I found so many shortcuts that it makes me incredulous that and engine can be legitimately so fast...

Anyway, do you have an engine of your own? If so, what are your results?

Re: Perft results?

Posted: Sun Jan 08, 2017 9:30 pm
by sandermvdb
My engine which uses a bitboard and is also written in Java gives the following results on an Intel Q9550 (2,83 Ghz):

QPerft 5: 264ms
QPerft 6: 2948ms

Perft 5: 3069ms
Perft 6: 75648ms

QPerft is without making the last move, Perft is with.

The following info is updated incrementally every move:
- hashkey
- pawn-hashkey
- pinned-pieces
- slidingpiece attacks (on an empty board)
- psqt-score

I think this is fast enough for a decent engine. At the moment I have bottlenecks at other parts :P
Point of only generating pseudo-legal moves is that a lot of moves won't be played since they are cutoff. I DO calculate only legal-moves because of simplicity.

Re: Perft results?

Posted: Mon Jan 09, 2017 10:12 am
by H.G.Muller
notachessplayer wrote:That is insanely fast if it does everything fairly, without a TT, multi-threading, etc.
Sure, that is for single-thread,without hashing.With 128MB hash it drops to 0.434 for perft(6).
Do you know the board representation used?
Yes, it is 16x12 mailbox, with a piece list. Qperft is open source, btw ( http://home.hccnet.nl/h.g.muller/dwnldpage.html ).
I just can't help finding it hard to believe that an engine would generate every single move, make and unmake them up to depth 6 (without last depth). My solution is certainly not de best by any means, but I found so many shortcuts that it makes me incredulous that and engine can be legitimately so fast...
Well, as perft(6) = 119M it counts about one move every 8 ns. An i3 CPU at 2.4GHz does 20 clock cycles in that time, and can do upto 4 instructions per clock. So that makes 80 instructions. That seems a lot for just counting one move. The basic process is adding the step to the latest to-square, fetching the board content for that new location, testing it against what you need, combining to- and from-square into a move encoding, storing that, and increasing the move stack pointer. That is much less than 80 operations. But of course from the initial position most of the attempts to generate moves are failures that are aborted. Because they stray off board or bump into own pieces, packed as they are along the edge.

As qperft is not an engine, there is no updating of PST evaluation, Pawn hash and such. Pinned pieces are detected anew in every position.
Anyway, do you have an engine of your own? If so, what are your results?
I have written many engines. Joker (which uses the same move generator as qperft) is one of those. It is not very strong, but that is mainly an evaluation matter. Other engines I wrote are micro-Max/Fairy-Max, Spartacus, KingSlayer, HaQiKi D, Shokidoki, HaChu and CrazyWa.

Re: Perft results?

Posted: Tue Jan 10, 2017 8:35 pm
by sandermvdb
sandermvdb wrote:My engine which uses a bitboard and is also written in Java gives the following results on an Intel Q9550 (2,83 Ghz):

QPerft 5: 264ms
QPerft 6: 2948ms

Perft 5: 3069ms
Perft 6: 75648ms

QPerft is without making the last move, Perft is with.
CORRECTION:
Perft does NOT make the actual move. Sorry for the confusion!
The difference in my case is that QPerft counts the number of possible moves at d=1 whereas Perft does one more recursive call to itself and then does moveCounter++.

Re: Perft results?

Posted: Wed Jan 18, 2017 10:07 pm
by notachessplayer
sandermvdb wrote: QPerft 5: 264ms
QPerft 6: 2948ms
Nice. I reworked my engine since the last time I posted, and get the same results (varying from 2.8 to 3.1 for some reason).

I changed the board structure (8x8 to 120 array) and completely removed dynamic object creation.
Moves and pieces are now integers and I use bitwise operations to retrieve information instead of objects.

I have found a way to improve some more, I will update when I'm done.

Re: Perft results?

Posted: Sun Feb 12, 2017 1:09 am
by notachessplayer
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.

Re: Perft results?

Posted: Sun Feb 12, 2017 1:39 am
by thevinenator
What are you updating in your "makemove"?

my engine does P6 in about ~4 second, but it is incrementally updating hash keys, piece counts, etc. I never bothered to try the bare bones "moves only" since the engine will never work that way. I think it is a more realistic measure and one I use to tuning code.

BTW, move generation is bit-boards with modified shift code for sliding pieces.

Re: Perft results?

Posted: Sun Feb 12, 2017 3:44 am
by notachessplayer
It is updating pieces count (also light/dark squared bishops) and the fifty moves rule.

I have not done the hash yet, as I had in mind to use them to store moves generated in a TT and make it even faster (perhaps twice or more), and just wanted a raw result of my move generation atm, although I agree that the engine won't work before I do that.
I'm thinking of combining a key of the whole board with a key of the pawn positions to make collisions nearly impossible (I say that without testing, because it might not be true), so I don't use stored moves that are not possible for a given position. But that will almost certainly not be my final idea, so I'm not starting yet!

I am using a 16x12 board representation, and nearly 0 for loops lol.

I was thinking about bit-boards and how they work, granted I only read an article about them, but aren't there a lot of loops to 64? I have no idea how quickly the final results can be found, but that seems time consuming.
I will probably try it at some point, but the way it works is so unintuitive and confusing :oops:

Btw, my results are now in C++, as I have learned the language solely to verify if it is faster than Java, since nowhere on the internet is it possible to find an unbiased answer.
My conclusion is that C++ is faster, but I will have to put as much effort in optimizing the Java engine to be sure, although I really doubt it will be as fast.

Which IDE do you use for Java?