What is the best known speed of move generation?

[bob]

Code: Select all

rnb1kbnr/ppppqppp/8/8/8/8/PPPPQPPP/RNB1KBNR w KQkq -
(Opening, both queens pinned)
 1.             24              8  33.33%
 2.            547            191  34.92%
 3.          13629           4416  32.40%
 4.         336781         104837  31.13%
 5.        9109498        2495648  27.40%
 6.      246238592       61779149  25.09%

Wow! That is way more than I expected. I pinned both Queens so that I would not have to worry about the side with the pinned piece having the final ply, or not. But I guess that in this case they force each other to maintain the pin. Of course most moves would maintain the pin anyway, as the are with other pieces than the pinner.

Anyway, the example shows that the number of illegal moves need not always be small, and can be as high as 25%.

Adding the critical "in perft results" to the above sentence. programs that dislike pins because of mobility evaluations will do something early in the tree to get rid of the absolute pin deeper in the tree...

One important lesson is that pins behave different from checks. The latter must be resolved. But the very nature of a pin is that it is very difficult to resolve. Another lesson is that after 6 ply, the position in general still looks like the root, as each side could only move 3 of its 16 pieces. So if the root contains no pin, the leaves are unlikely to contain a pin. If the root does contain a pin, the pin will most likely still exist in the leaves.

I am a bit surprised about the end-game example. I cannot imagine many pins there. The illegal moves are probably mostly the King wandering into check. My perft would suffer from that too, btw, I have not devised a trick yet to suppress generation of illegal King moves.

It does

[hgm]

With magic bitboards you get orthogonal checks by getting rook-attacks from king-square to intersect it with opposite rooks/queens. Dito with bishop-attacks and the diagonal sliders.

Code: Select all

r = rookAttacks(occupancy, kingSquare);
if ( r & oppositeRooksOrQueen )
   // in check

What I meant was that you could also start the other way around:

Code: Select all

r = rookAttacks(oppositeRooksOrQueen, kingSquare);

followed by

Code: Select all

index = pinMagic[kingSquare]*(occupancy&r)>>52;
switch(index)
{ // 4096 case labels, of only a few different kinds
    case DOUBLE_CHECK:
        p = possibleSafeEvasionSquares[index];
        ....
    case DISTANT_CHECK:
        p = checkRay[index];
        ....
    case CONTACT_CHECK:
        p = checker[index];
        ....
    case PIN:
        p = pinned[index];
        ....
}

I guess it would not work with normal rookAttacks, as you would only want to have rays in the set where there actually is a slider at the end. But you could tabulate those as well, of course. (I have no idea if 12 bits would be enough, of course.)

[hgm]

Adding the critical "in perft results" to the above sentence. programs that dislike pins because of mobility evaluations will do something early in the tree to get rid of the absolute pin deeper in the tree...

If they can. The other program will of course do its best to maintain the pin, if only because it thinks the opponent dislikes them.

I am not sure that in the given position either opponent would dislike the situation, as their own mobility suffers just as much as that the opponent, and solving it for themselves will also solve ithe pin for the opponent.

Programs with mobility evaluations will usually also not shy from trading Queens, although it costs them a lot of mobility...

[hgm]

The cost is relatively small, but it is a same permanent small loop overhead with several table lookups again and again. It may (or may not dependent to compiler optimizations and other random factors) be slightly faster then pseudo-legal generation, but I cannot accept the given pin implementation as "tidy".

This must be a matter of taste, then. Such loops form the heart of a mailbox move generator everywhere.

The bitboard methods just discussed also have to do a lot of table lookups, and I am not at all convinced that if you call cycles, it would be any faster. One either has enormous tables for the rookAttacks (meaning they have to come from L2 or worse, while my 224 byte 0x88 table is always in L1), or one has to do horizontal and vertical rookAttacks separately, and perhaps same for diagonal / antidiagonal, so that in the end one would have 4 attack-set lookups for the sliders, and 2 tests for N+P. That is already more lookups than my 5 sliders. And there might be only two, later in the game, speeding me up by a factor 2.5, while the bitboard method could not profit at all if they were R + B...

[bob]

Adding the critical "in perft results" to the above sentence. programs that dislike pins because of mobility evaluations will do something early in the tree to get rid of the absolute pin deeper in the tree...

If they can. The other program will of course do its best to maintain the pin, if only because it thinks the opponent dislikes them.

I am not sure that in the given position either opponent would dislike the situation, as their own mobility suffers just as much as that the opponent, and solving it for themselves will also solve ithe pin for the opponent.

Programs with mobility evaluations will usually also not shy from trading Queens, although it costs them a lot of mobility...

You gave the trivial worst-case for perft however. A pair of queens absolute-pinning each other. One move and that all evaporates.. while in perft those pins will exist almost everywhere else even though a real search would have long-since removed them. Mobility for two pinned queens is zero, so trading them solves that. or interposing a minor piece makes the entire thing evaporate as well. If you don't evaluate them, then I suppose they could be a problem in pathological cases such as the one given. But picking a very rare case, then running it in a way that highlights an absolute pin for both sides is just that, pathological, not common.

There are two questions to ask: (1) doing a full-width depth-first fixed-depth search (perft) is going to search a tree of size N. Of those N, how many times do we generate moves and have to cull illegal moves for absolute-pinned pieces? (2) in a normal alpha/beta depth-first search is going to search P positions. Of those P, how many are going to generate moves and have to cull illegal moves for absolute-pinned pieces. Based on the fairly simple test I ran (last night I think) such illegal moves are less common than just moving the king directly into check. At least for the three random positions I checked in a game.

[Gerd Isenberg]

With magic bitboards you get orthogonal checks by getting rook-attacks from king-square to intersect it with opposite rooks/queens. Dito with bishop-attacks and the diagonal sliders.

Code: Select all

r = rookAttacks(occupancy, kingSquare);
if ( r & oppositeRooksOrQueen )
   // in check

What I meant was that you could also start the other way around:

Code: Select all

r = rookAttacks(oppositeRooksOrQueen, kingSquare);

followed by

Code: Select all

index = pinMagic[kingSquare]*(occupancy&r)>>52;
switch(index)
{ // 4096 case labels, of only a few different kinds
    case DOUBLE_CHECK:
        p = possibleSafeEvasionSquares[index];
        ....
    case DISTANT_CHECK:
        p = checkRay[index];
        ....
    case CONTACT_CHECK:
        p = checker[index];
        ....
    case PIN:
        p = pinned[index];
        ....
}

I guess it would not work with normal rookAttacks, as you would only want to have rays in the set where there actually is a slider at the end. But you could tabulate those as well, of course. (I have no idea if 12 bits would be enough, of course.)

Since we may have multiple sliders but only one king, the other way around requires a loop over all potential pinners (as suggested by Jacob) - or directionwise fillstuff with multiple sliders. That is what I actually use in my 32-bit program with mmx and try with my quad-bitboard color-flipper approach with sse2- simd stuff, the extreme counter-approach to Bob's one.

Briefly, with all 16 128-bit xmm registers and some index registers in action (one xmm-register is used to probe the hash-table), I fill white:black sliders and black:white kings in all eight directions by Kogge-Stone or o^(o-2r), and intersect opposite directions (eg. north/south) of sliders and king for pins, discoverd checkers, and interposing targets in case of distant checks. The final output of that almost branchless fill-orgy is a fixed sized move-list. A vector of legal movetarget bitboards for all 16 distinct directions (including the 8 knight directions), plus some stuff for a setwise poor-man's SEE like "at least attacked once", or "at least attacked twice". Other intermediate results, likely reused for reduction/extension decisions, or in eval, is cached for a while until first make.

[hgm]

Since we may have multiple sliders but only one king, the other way around requires a loop over all potential pinners (as suggested by Jacob) - or directionwise fillstuff with multiple sliders.

Are you sure? Why would it matter if you get an attacks set with multiple rays set? Even if all 4 orthogonal rays are set, say Ke4 attacked by Qe1, Qe8, Ra4 and Rh4 (obviously with some of those blocked, but we don't know yet which), the attacks set would always be a subset of the mask of orthogonals. The edge squares would be relevant, though, so it would be a set of 14 squares for which the occupancy matters, which is bigger than the usual 12 for Rooks.

Doing rookAttacks for ranks and files combined is of doubtful use anyway, and if you do ranks and files separately, they would only be 7 squares a piece. Collecting those 7 bits in an index would give you a cheap lookup as to number of checkers and number of pinned pieces / discovered checkers, which you could store in the high and low nybble of a byte, respectively. Adding those bytes for the ranks, files and diagonals would give you an 8-bit index to distinguish check, double check and various numbers of pins.

[Gerd Isenberg]

Are you sure? Why would it matter if you get an attacks set with multiple rays set? Even if all 4 orthogonal rays are set, say Ke4 attacked by Qe1, Qe8, Ra4 and Rh4 (obviously with some of those blocked, but we don't know yet which), the attacks set would always be a subset of the mask of orthogonals. The edge squares would be relevant, though, so it would be a set of 14 squares for which the occupancy matters, which is bigger than the usual 12 for Rooks.

Doing rookAttacks for ranks and files combined is of doubtful use anyway, and if you do ranks and files separately, they would only be 7 squares a piece. Collecting those 7 bits in an index would give you a cheap lookup as to number of checkers and number of pinned pieces / discovered checkers, which you could store in the high and low nybble of a byte, respectively. Adding those bytes for the ranks, files and diagonals would give you an 8-bit index to distinguish check, double check and various numbers of pins.

Interesting - I still don't get your idea.

Code: Select all

r = rookAttacks(oppositeRooksOrQueen, kingSquare)
index = pinMagic[kingSquare]*(occupancy&r)>>52;

In rookAttacks you pass oppositeRooksOrQueen as occupancy, to get an attack-set from the kingsquare. Let say you pass either an empty set or a set of potential pinners on the edges, you get the same set r, independent whether there is a potential pinner or not?
E.g. on a rank:

Code: Select all

R.B.K..R ->  r = 00110111
..B.K... ->  r = 00110111

[hgm]

Yes, this is what I meant when I said that the normal rookAttacks would not do, and you would need a 14-bit variety (with 2D magic). You would need a variant that does pay attention to the edge occupancies, and if the entire ray is empty upto and including the edge, does not include it in the attacks set.

Code: Select all

R.B.K..R ->  r = 11110111 (as the B is not in RooksOrQueen)
.RB.K... ->  r = 01110000 (as the edge square is empty)
..B.K... ->  r = 00000000

[Uri Blass]

On my c2d@2.4GHz, crafty (I've downloaded the most recent 64-bit binary for linux) gives ~19M nodes per second.

Code: Select all

White(1): perft 6
total moves=119060324  time= 6.29
White(1): perft 7
total moves=3195901860  time=167.37

(can't measure for 8 plies, there seem to be an overflow)

With my own engine I get 24M nps on the same machine

This does not seem very fast for a 2.4GHz C2D. Qperft reaches about that speed on a 1GHz Athlon XP...

Code: Select all

$ perft 6
 - - - - - - - - - - - -
 - - - - - - - - - - - -
 - - r n b q k b n r - -
 - - p p p p p p p p - -
 - - . . . . . . . . - -
 - - . . . . . . . . - -
 - - . . . . . . . . - -
 - - . . . . . . . . - -
 - - P P P P P P P P - -
 - - R N B Q K B N R - -
 - - - - - - - - - - - -
 - - - - - - - - - - - -

Quick Perft by H.G. Muller
Perft mode: No hashing, bulk counting in horizon nodes

perft(1)=20 ( 0.000 sec)

perft(2)=400 ( 0.000 sec)

perft(3)=8902 ( 0.000 sec)

perft(4)=197281 ( 0.010 sec)

perft(5)=4865609 ( 0.210 sec)

perft(6)=119060324 ( 5.498 sec)

1)I cannot compile the code of the move generator with microsoft visual C++2005.

I got the following errors.


------ Build started: Project: Perft, Configuration: Debug Win32 ------
Compiling...
main.c
.\main.c(838) : warning C4996: 'sscanf' was declared deprecated
C:\Program Files\Microsoft Visual Studio 8\VC\include\stdio.h(311) : see declaration of 'sscanf'
Message: 'This function or variable may be unsafe. Consider using sscanf_s instead. To disable deprecation, use _CRT_SECURE_NO_DEPRECATE. See online help for details.'
.\main.c(846) : warning C4996: 'sscanf' was declared deprecated
C:\Program Files\Microsoft Visual Studio 8\VC\include\stdio.h(311) : see declaration of 'sscanf'
Message: 'This function or variable may be unsafe. Consider using sscanf_s instead. To disable deprecation, use _CRT_SECURE_NO_DEPRECATE. See online help for details.'
.\main.c(855) : warning C4996: 'sscanf' was declared deprecated
C:\Program Files\Microsoft Visual Studio 8\VC\include\stdio.h(311) : see declaration of 'sscanf'
Message: 'This function or variable may be unsafe. Consider using sscanf_s instead. To disable deprecation, use _CRT_SECURE_NO_DEPRECATE. See online help for details.'
Linking...
main.obj : error LNK2019: unresolved external symbol _lltoa referenced in function _perft
D:\str\perftfolder\Perft\Debug\Perft.exe : fatal error LNK1120: 1 unresolved externals
Build log was saved at "file://d:\str\perftfolder\Perft\Perft\Debug\BuildLog.htm"
Perft - 2 error(s), 3 warning(s)
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========

2)I do not understand the following line

int savsp, mask, new, forward, rank, prank, xcolor, ep_flag;

I understand that new unlike other things that come after int is not a variable so what is the job of "new".

I also looked for the word savsp and it seems that it is not used by the program.

Uri