Winboard Forum

How fast is your check move generator?
I just found out that mine is very slow. It is almost as fast as generating all moves and then testing if it is a check.
are bitboards better than offset methods for this kind of stuff?
daniel

Daniel Shawul wrote:How fast is your check move generator?
I just found out that mine is very slow. It is almost as fast as generating all moves and then testing if it is a check.
are bitboards better than offset methods for this kind of stuff?
daniel

If you are using 0x88:

You can use the "can piece on fsq attack tosq" trick.

Then it becomes: Can piece on fsq attack tosq via another square". Do not give a yes/no but give the actual squares on wich it does.

For a knight,rook,bishop you give atmost 2 squares, pawn 1, queen 11 (? iirc)

Warning: Check first if the piece is already on the same file (meaning a piece is blocking the check) and treat that different.


Tony

Hi Daniel!

Daniel Shawul wrote:How fast is your check move generator?

Do you have a suggestion for a good benchmark? According to my profiler, my generate_checks() functions consume 1.2% of the CPU time in tactical positions. Of course this number by itself means nothing (except that cannot hope to improve my program by optimising this function). Perhaps I just call generate_checks() less often than you do, or the rest of my code is very slow?

Perhaps a better measure of the speed is that generate_checks() was called 2,219,416 times during my profiling run, and the total time consumed by this function was 2.15 seconds. In other words, I can generate checks about 1 million times/second. I have no idea whether this is very fast, but at least it seems to be fast enough for my rather slow engine.

My hardware is an iMac G5 1.8 GHz.

I just found out that mine is very slow. It is almost as fast as generating all moves and then testing if it is a check.
are bitboards better than offset methods for this kind of stuff?

Shouldn't matter much, I think. I use offset methods.

Tord

Daniel Shawul wrote:How fast is your check move generator?

I do not know exactly what you are targeting. If it is the creation of moves including the information, whether they are no, single or double check threats, there is a special perft routine of mine. An example:

Code: Select all

FEN: rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1

  +-*--b--c--d--*--f--g--*-+ MS Vis. Studio C++ Vers. 13.10
8 |[r][n][b][q][k][b][n][r]| (Compilation: Nov  7 2004)
7 |[p][p][p][p][p][p][p][p]|
6 |   :::   :::   :::   :::| Perft Testseries
5 |:::   :::   :::   :::   |
4 |   :::   :::   :::   :::| (without caching)
3 |:::   :::   :::   :::   |
2 |<P><P><P><P><P><P><P><P>| Smirf Test No.: 00
1 |<R><N><B><Q><K><B><N><R>|
=>+-*--b--c--d--*--f--g--*-+ Break Time 250.0 Sec.

Ply     Nodes    all (x)   (e.p.)    all (+) all (++)    Promot.    Castl. Sec.
-------------------------------------------------------------------------------
1          20          0        0          0        0          0         0    0
2         400          0        0          0        0          0         0    0
3        8902         34        0         12        0          0         0    0
4      197281       1576        0        469        0          0         0    0
5     4865609      82719      258      27351        0          0         0  0.2
6   119060324    2812008     5248     809099       46          0         0  4.5
7  3195901860  108329926   319617   33103848     1628          0    883453  116
8 84998978956 3523740106  7187977  968981593   147215          0  23605205 3116
-------------------------------------------------------------------------------

I am not using bitboards, but instead a flat data structure arranging pieces in two sorted double linked lists containing bit encoded informations on the pieces' properties.

Regards, Reinhard.

Hi All

If you are using 0x88:
You can use the "can piece on fsq attack tosq" trick.
Then it becomes: Can piece on fsq attack tosq via another square". Do not give a yes/no but give the actual squares on wich it does.
For a knight,rook,bishop you give atmost 2 squares, pawn 1, queen 11 (? iirc)

yes i use 0x88. what i do is loop over the pieces check if it is pinned,if
so generate all moves, otherwise continue checing every tosq if it gives a direct check. What you suggested above must be faster for generating checks only,but i generate captures and checks simultaneously. This may zero the gain? The capture generation requires looping over all the squares unless you know the attacked opponent pieces before hand.

Do you have a suggestion for a good benchmark? According to my profiler, my generate_checks() functions consume 1.2% of the CPU time in tactical positions. Of course this number by itself means nothing (except that cannot hope to improve my program by optimising this function). Perhaps I just call generate_checks() less often than you do, or the rest of my code is very slow?

i used the starting position and it dropped my nps from 1,110,000 to
850,000. Note this is with pcsq only evaluation. It should drop further
on tactical suites. I will post results on a tactical position later.
My NPS further drops to 500,000 by generating attack tables with in the eval. This is equivalent to 2x move generation.
so i am thinking i would gain something by trying to optimize these generation routines??

I do not know exactly what you are targeting. If it is the creation of moves including the information, whether they are no, single or double check threats, there is a special perft routine of mine. An example:

only generation of check moves(+ captures if possible) to be used in qsearch.The perft you posted is for generating all moves.
BTW Reinhard ,do you see any advantage by using an offset method other
than 0x88? This method gives nice square relation ships which helps in fast attack generation.

best
daniel

Daniel Shawul wrote:BTW Reinhard ,do you see any advantage by using an offset method other
than 0x88? This method gives nice square relation ships which helps in fast attack generation.

best
daniel

I think all offset methods are equally fast. All square relationships that may be obtained in 0x88 are obtainable in other methods too (At least most of them), even if it may take some work.

In fact Christophe Theron has posted on the CCC that 10x12 board is faster than 0x88 for capture generation, since you can avoid testing for hitting the end of board in the 10x12 method.

But then again, with a little trick or two, you can do the same in 0x88 as well.

Pallav

Thanks pallav!
i read that post and it seems he is using 16x12 which
can avoid the !(sq & 0x88) test.
daniel

As I'm using a legal move generator I also have to check quite often to make sure that my king isn't left in check after a move. In the beginning I checked after every single move. No good idea: after profiling my program I noted that the program spent most of its time in the attack function to check if the king is under attack.
After rewritting the attack function and especially after the suggestion made by Dan Honeycutt to use distance tables to check if the squares where I'm going to move a piece and the square of the king have any connection and if not to avoid the call to attack the program speed went up a great deal. Another approach could be to see if the king is still shielded by own pawns and own pieces and only check for opposite coloured knights (I didn't try that yet though).

Roman

PS: I estimate that I'm about checking 50% of all my generated moves if the king is in check now. Perft 6 from the start pos. takes about 18s (on a Athlon XP 2.2Ghz) which isn't too bad imo.

Hi Daniel!

Daniel Shawul wrote:

Reinhard wrote:I do not know exactly what you are targeting. If it is the creation of moves including the information, whether they are no, single or double check threats, there is a special perft routine of mine. An example:

BTW Reinhard ,do you see any advantage by using an offset method other
than 0x88? This method gives nice square relation ships which helps in fast attack generation.

I cannot use a specialized 0x88 approach because Smirf simultaneously is supporting 8x8 and 10x8 boards. I cannot imagine using BitBoards to be that dynamically flexible. Thus I am using a flat structure with additional overlayed substructures. E.g. my Perft results have shown, that this finally is an extremly fast approach. I have managed to enable my move generator to "look" into directions of sliding pieces. Thus I cannot see any advantage of BitBoard approaches remaining at all compared to more intuitively to be handled flat structures.

Here are some examples of (preevaluated and sorted) generated moves (with full information), where time has been stopped for generating, preevaluating and sorting of node moves:

Code: Select all

FEN: 3R4/b1N1Q3/2B4K/r2P3b/pB1k2p1/1qR1p3/1Nn5/6n1 w - - 0 1

  +-a--b--c--d--e--f--g--h-+ MS Vis. Studio C++ Vers. 13.10
8 |   :::   <R>   :::   :::| (Compilation: Nov  7 2004)
7 |[b]   <N>   <Q>   :::   | Testscenario (sorted, O(n*log(n))):
6 |   :::<B>:::   :::   <K>| Move generation
5 |[r]   :::<P>:::   :::[b]|
4 |[p]<B>   [k]   :::[p]:::| Smirf Test No.: 01
3 |:::[q]<R>   [p]   :::   |
2 |   <N>[n]:::   :::   :::| Move Count:  54*1347179
1 |:::   :::   :::   [n]   | per Second:  19898158
=>+-a--b--c--d--e--f--g--h-+ Time:        3.656 sec

  7.980 Rc3xb3   4.672 Bb4xa5   3.172 Kh6xh5   2.605 Rc3xc2   1.152 Qe7xe3+
  0.793 Nb2xa4   0.715 Qe7-e4+  0.711 Bc6xa4   0.688 Rc3xe3   0.676 Qe7-c5+
  0.676 Qe7-e5+  0.594 Nc7-e6+  0.594 Nc7-b5+  0.559 Bb4-c5+  0.539 Rc3-c4+
  0.539 Rc3-d3+  0.535 Qe7-f6+  0.391 Qe7-g7+  0.199 Rd8-d6   0.180 Nb2-c4
  0.180 Nb2-d3   0.129 Kh6-g5   0.117 Qe7-d6   0.098 Rd8-d7   0.094 Qe7-e6
  0.020 Kh6-g7   0.016 Qe7-d7   0.000 Bb4-d6   0.000 Rc3-c5   0.000 Bc6-b5
  0.000 Qe7-g5  -0.016 Rd8-c8  -0.016 Rd8-e8  -0.020 Nb2-d1  -0.043 Qe7-f7
 -0.043 Nc7-a6  -0.047 Rd8-b8  -0.047 Rd8-f8  -0.055 Kh6-h7  -0.078 Bc6-d7
 -0.082 Qe7-h4  -0.098 Nc7-e8  -0.098 Qe7-e8  -0.098 d5-d6   -0.102 Rd8-g8
 -0.102 Rd8-a8  -0.117 Bb4-a3  -0.129 Qe7-f8  -0.137 Bc6-b7  -0.168 Rd8-h8
 -0.184 Qe7-h7  -0.184 Nc7-a8  -0.191 Bc6-e8  -0.277 Bc6-a8

FEN: cr5nr1/p1p1p1Pppp/3p2a3/PpPk4N1/1PC2P4/4BN1PA1/1Q2B3PP/1R3K2R1 w Q b6 0 1

  +-a--b--c--d--e--f--g--h--i--j-+ MS Vis. Studio C++ Vers. 13.10
8 |[c][r]   :::   :::   [n][r]:::| (Compilation: Nov  7 2004)
7 |[p]   [p]   [p]   <P>[p][p][p]| Testscenario (sorted, O(n*log(n))):
6 |   :*:   [p]   :::[a]:::   :::| Move generation
5 |<P>[p]<P>[k]:::   :::   <N>   |
4 |   <P><C>:::   <P>   :::   :::| Smirf Test No.: 21
3 |:::   :::   <B><N>:::<P><A>   |
2 |   <Q>   :::<B>:::   :::<P><P>| Move Count:  87*836180
1 |:::<R>:::   :::<K>:::   <R>   | per Second:  16055541
=>+-a--*--c--d--e--*--g--h--i--j-+ Time:        4.531 sec

  10.38 g7xh8Q   9.871 g7xh8C   8.461 g7-g8Q+  8.152 g7xh8A   7.418 g7-g8C
  7.008 g7xh8R   6.648 Ni5xg6   6.086 g7-g8A+  5.289 g7xh8B   4.781 g7xh8N
  4.363 g7-g8R   3.031 g7-g8B+  1.988 g7-g8N   1.402 Ai3xe7+  1.031 O-O-O+
  1.016 a5xb6    1.012 Cc4xd6+  0.938 c5xd6    0.867 Ni5xh7   0.816 Ai3-f6+
  0.816 c5xb6    0.758 Qb2-e5+  0.758 Qb2-d4+  0.680 Ni5xj7   0.559 Qb2-d2+
  0.547 Rb1-d1+  0.539 Cc4-e5+  0.539 Cc4-d4+  0.418 Cc4-c3+  0.418 Cc4-b6+
  0.340 Cc4-d2+  0.238 Ai3-g5   0.223 Ai3-g4   0.184 Ni5-g4   0.180 Nf3-e5
  0.180 Nf3-d4   0.141 Ai3-h5   0.141 Ri1-g1   0.137 Qb2-c3   0.137 Qb2-f6
  0.125 Ai3-h4   0.121 Be3-d4   0.117 Be2-d3   0.113 Ai3-g2   0.086 Kf1-f2
  0.078 Qb2-b3   0.074 Ri1-h1   0.063 j2-j4    0.043 Qb2-c2   0.039 Ai3-g1
  0.039 Ai3-h2   0.039 j2-j3    0.031 Rb1-c1   0.031 h3-h4    0.031 Kf1-e1
  0.031 Rb1-e1   0.023 f4-f5    0.020 Kf1-g2   0.000 Qb2-a3   0.000 Cc4-e4
 -0.016 a5-a6   -0.020 Nf3-g5  -0.020 Nf3-d2  -0.027 Ai3-h1  -0.039 c5-c6
 -0.055 Rb1-a1  -0.055 Qb2-c1  -0.055 Kf1-g1  -0.063 Ai3-j5  -0.066 Qb2-a2
 -0.070 Ai3-j4  -0.078 Be3-d2  -0.082 Ri1-j1  -0.082 Be2-d1  -0.133 Ni5-j3
 -0.133 Nf3-e1  -0.133 Nf3-h4  -0.137 Be3-f2  -0.141 Qb2-a1  -0.176 Cc4-c2
 -0.184 Ai3-j1  -0.191 Be3-c1  -0.219 Cc4-a3  -0.219 Nf3-g1  -0.219 Nf3-h2
 -0.273 Cc4-c1  -0.277 Be3-g1


Regards, Reinhard.