Perishing Perft !

[tvrzsky]

Quick Perft (7) takes only 8.9 sec on my new Core 2 Duo machine (E6600, 2.4GHz)!

It seems that I have got perhaps even little bit faster compilation of your Perft, on my Core2Duo T5500@1.66GHz it takes only 11.3 sec (by accident, my engine is exactly just as fast, but only in this particular position ; usually your one is considerable better).

[GeoffW]

Hi

Thanks to everyone for the assorted results, they are all impressively short !!


To Reinhard
Your Perft webpage was very handy, thats how I realised my bug was e.p related. Thanks


To H.G
Ah, now why didnt I think of that !

I was trying to figure out a way of doing that adjustment without an if, I came up with

Code: Select all

#define EP_TAKEN_SQUARE(side, square)	(square - (side*32)-16)

which does the job, but is a bit ugly

Code: Select all

#define EP_TAKEN_SQUARE(square)	(square ^ 0x10)

looks much tidier

Thanks for the tip


To Allard
My makemove code uses the 0x88 delta trick you mentioned to figure out if in check, but I am currently doing this right at the end of makemove().
This is less than optimum as it would be best to do it at the start of makemove(), to save the move make and move undo code. That is much trickier to code however, so i am just contemplating that one now.

Where do you test for sideToMove in check ? At start or end of makemove() ?



Geoff[/b]

[Allard Siemelink]

To Allard
My makemove code uses the 0x88 delta trick you mentioned to figure out if in check, but I am currently doing this right at the end of makemove().
This is less than optimum as it would be best to do it at the start of makemove(), to save the move make and move undo code. That is much trickier to code however, so i am just contemplating that one now.

Where do you test for sideToMove in check ? At start or end of makemove() ?

It sounds like you are doing it right; I also do it at the end.
E.g. the folowing code checks if the moving piece delivers check:

Code: Select all

    if (type88(to, king) & sqCtype(to)) {
        if (sqIsSlider(to)) {
            int dir = dir88(to, king);
            do { to+=dir; } while (!index[to]);
            if (to!=king) return move;
        }
        move.setDirectcheck();
    }

The legality check (self check) is at the beginning though, this does indeed save the (relatively infrequent) call to undo().
btw, how big is your move data structure? It should not be larger than 4 bytes.

[Dann Corbit]

Quick Perft is also very fast IIRC but on same Mac (compiled on the fly with a simple gcc -O3) it cannot complete without a hash table and takes 25 secs just to reach perft 7.

Yes, a hash gives an enormous speed-up in perfting, where, unlike alpha-beta trees, you are sure to walk every existing transposition.

Although I do have hashing versions of Quick Perft, they are meant mainly to test the hash-table logic and evaluate replacement policies. I decided against putting those on my web-site, as the intended purpose for this perft was to get reliable counts. And with hashing, there always is the possibility of a key collission...

(Originally I wrote the perft for testing my move-generator speed, of course.)

In thoery you are right.
practically I do not know about a single case when my results are wrong.
If you want to be sure of no mistake you can still use hash if you use store all the position in the hash and storing all the position can be done easily by 200 bits for every hash entry.

1 bit for the side to move
4 bits for castling right
3 bits for enpassent square
64 bits for every square to tell if the square is empty.
4 bits for the content of every non empty square(4*32=128 in the worst case)

Uri

If you hash the full board as a minimized structure, it goes back to the old encoding method where we tried to squeeze the board as small as possible. I believe Karin's Dad got to about 160 bits.

It is certainly possible to hash with less bits but I do not see the point in doing it.

If we are talking about safe fast perft then the target is to translate every position to a number that is easy to calculate.

If you spend too much time in calculating the hash number your perft is going to be slower inspite of slightly more positions in the hash.

Uri

I have a fast way that uses 192 bits total.

[hgm]

My makemove code uses the 0x88 delta trick you mentioned to figure out if in check, but I am currently doing this right at the end of makemove().
This is less than optimum as it would be best to do it at the start of makemove(), to save the move make and move undo code. That is much trickier to code however, so i am just contemplating that one now.

Where do you test for sideToMove in check ? At start or end of makemove() ?

Quick Perft (which is actually the basis of Joker) does the self-check test after MakeMove, but only for King moves, e.p. captures. This to prevent the King from trying to hide behind himself, end because e.p. pins are not trivially detected (e.g. if both involved Pawns are n the pin line).

Castlings are King moves, but in the MakeMove part that moves the Rook it is checked if the Rook ends up in-check. (So illegal castlings are treated as self-checks.)

Other moves can never cause self-check, and thus do not have to be tested at all. This because the move generator does not generate illegal moves with pinned pieces. This is much more efficient: There are only 5 enemy sliders that could pin something, and most of those fail the 0x88 test for alignment with your King. If occasionally one is aligned, that piece is excluded from normal move generation, disabling many moves at once. This saves a lot of time compared to testing each move separately for the pin condition. If a pinned piece has moves along the pin line, they are generated in the code section that handles the pins, as it is already aware what the pin line is, and has already determined upto where the moves can go (from own King upto and including pinner).

As a fringe benifit, testing for the pins automatically tell you if you are in distant check yourself. Alternatively, if you test moves for delivering check to the opponent after they are made, you can at the same time without much extra work detect new pins as well, and differentially maintain a list of pinned pieces.

When you are in check before the move, your primary concern is not if your move puts you in check, but to get out of it. It helps if your 0x88 test already tells you if the move is a distant check or a contact check. In the latter case you can limit yourself to King moves and capture of the checker. (With non-pinned pieces. Note that a move of a pinned piece on the pin line can never capture the checker or block the check.) The distant case is a pain, and I could not devise any quicker way than simply generating all moves, and then doing the 0x88 test compared to own King to see if they fal on the check line, and if they do, test if they indeed block it. (Perhaps the latter could be still sped up by also having a 0x88 distance table, but checks are not sufficiently common to care very much how you handle them.)

How exactly you handle the castlings and e.p. captures is also completely irrelevant fr speed.