Move Generation Speed

[Zach Wegner]

Is your quicksort recursive? I used to use Shellsort but found "Best in remaining" slightly faster for my code.

The effective move sorting order during search is:

1. Move that is in the PV hash table
2. Move that is in the normal hash table
3. Killer moves
4. Captures with promotions
5. Captures without promotions
6. Moves that has history values
7. Moves that has no history values

I only generate moves when none of the moves gotten in 1 to 3 causes a cutoff.

The move generator generate captures in the least capturing piece value order so pawn captures are before knight captures, etc - this is a kind of presorted list. Similar things happens for promotions - queen first.

Other moves are ordered by the difference of the piece square table scores for each moving pieces.

Check evasions have a different move generator.

Confused? So am I. I think I've gone off topic .

Andrew.

Hello Andrew,

I am not really sure whether or not the qsort is recursive (I am using the C standard qsort()) but I would guess it is iterative. I too use selection sort, and my moves are ordered as follows:
1. Hash move
2. Threat move
3. Counter move
4. Winning captures
5. Killers
6. Even captures
7. Quiet moves
8. Losing captures

4 as well as 6-8 are also ordered using piece-square tables.

Regards,
Zach

[Reinhard Scharnagl]

Hello Zach,

a) my sort is not recursive (because of a limited scope of max. 290 moves, 10x8 board)
b) I do not use quicksort, but currently a type of shell sort instead
c) I am just "inventing" a new direct kind of bubble sort, which seems to have similar speed as my current sort
d) then I try to overlay that new type of sort to a type of shell sort.

I will report my results.

Reinhard.

[Uri Blass]

Hi Uri,

does that mean, that you would change the preevaluation of generated moves after trying the best of them?

Regards, Reinhard.

Yes

I use today history tables value and the history tables values are changed during the search.

Uri

[Zach Wegner]

Hello Reinhard,

I tried using shell sort (source code directly from http://linux.wku.edu/~lamonml/algor/sort/shell.html except the compare line is changed), and here are the results:

Code: Select all

nodes=1494861 q=74.9% time=12.723 NPS=117492
nodes=1494861 q=74.9% time=12.736 NPS=117372
nodes=1494861 q=74.9% time=12.711 NPS=117603
average time=12.723 NPS=117492

So shell sort is slightly faster than selection sort, but still slower than sorting one move at a time. There is also a different node count (for the same reason as the qsort), which makes shell sort much slower.

[Reinhard Scharnagl]

Hello Zach,

my sorting idea has been disappointing, only improvements about 5% (with some few exotic getting slower), all times include move generating:

Code: Select all

FEN: 3q2R1/2P5/1k1B4/4np2/1NPK1Pr1/1R6/PP1N1Q2/3q2b1 w - - 0 1

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

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: Oct 25 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*750000
1 |:::   :::   :::   [n]   | per Second:  20099255
=>+-a--b--c--d--e--f--g--h-+ Time:        2.015 sec (from 2.109)

FEN: R6R/3Q4/1Q4Q1/4Q3/2Q4Q/Q4Q2/pp1Q4/kBNN1KB1 w - - 0 1

  +-a--b--c--d--e--f--g--h-+ MS Vis. Studio C++ Vers. 13.10
8 |<R>:::   :::   :::   <R>| (Compilation: Oct 25 2004)
7 |:::   :::<Q>:::   :::   | Testscenario (sorted, O(n*log(n))):
6 |   <Q>   :::   :::<Q>:::| Move generation
5 |:::   :::   <Q>   :::   |
4 |   :::<Q>:::   :::   <Q>| Smirf Test No.: 13
3 |<Q>   :::   :::<Q>:::   |
2 |[p][p]   <Q>   :::   :::| Move Count:  218*750000
1 |[k]<B><N><N>:::<K><B>   | per Second:  12823529
=>+-a--b--c--d--e--f--g--h-+ Time:        12.750 sec (from 12.265)

Still I do not understand, why your en block sort would be not faster than the other variants. In my examples it is significantly faster.

That the node count could differ because of sorting variances of equal preevaluated moves could be understood, but not that it should have significantly influence on the node count.

Neverthel?ess your statistic is showing clear (as far as I understand) that the sort always technic would be not at all bad, especially, wenn there would be a fast en block sort.

Reinhard

[Marek Strejczek]

Hi Zach,
an O(n*log(n)) search should perform better than a O(n^2) sort.

What about constant hidden behind the O notation? Quick sort is not a suitable method for data sets smaller than 30 elements. Most move lists are about 30 elements, so a compact (low cache usage) O(n^2) algorithm with low constant can easily outperfom O(nlogn) qsort in this case.

Best wishes
Marek Strejczek

[Reinhard Scharnagl]

Hi Marek,

... so a compact (low cache usage) O(n^2) algorithm with low constant can easily outperfom O(nlogn) qsort in this case

If you target qsort, your are right. If you target O(n*log(n)) generally, you are wrong. I use a good shell sort implementation, which seems not to be surpassed by other methods in the relevant range covering created move numbers (0 ... 290 at 10x8 board) in average.

Reinhard.

P.S.: I first had errornously spoken from heap sort.

[Marek Strejczek]

Hi Marek,

... so a compact (low cache usage) O(n^2) algorithm with low constant can easily outperfom O(nlogn) qsort in this case

If you target qsort, your are right. If you target O(n*log(n)) generally, you are wrong. I use a good heap sort implementation, which seems not to be surpassed by other methods in the relevant range covering created move numbers (0 ... 290 at 10x8 board) in average.
Reinhard.

Hi,

it was qsort that was mentioned in that part of the topic, so I meant that specific algorithm. My program doesn't support 10x8 board, so I prepare it to deal with shorter move lists up to 40 moves (and don't seek highest efficiency in those rare cases of more than 40 possible moves). I've been using insertion sort for my move lists, but I'm going to try also some others algorithms, including heapsort, soon as I'm rewriting my program now.

Best wishes
Marek Strejczek

[Pallav Nawani]

First, my assumptions:

(a) Zach's results are based on acutal running of his program on a position. That is, he allowed his program's search to analyze a given position.

(b)Reinhard's results are simply sorting some moves he has generated.

If you take a bunch of move, and then sort them, bubble sort should be slower. But inside a chess program, it is a different case.

Some statistics from Natwarlal (From a randomly chosen position):

Code: Select all

-----------------------------------------
Here comes the statistics:

   Max ply reached: 17
Nodes:   Total: 126209   Qnodes: 78240 (61.99)
Cuts:   Reductions: 1918   Prunings: 42903   Qcuts: 7809
Extensions:
   Check: 10337   PawnPush: 13   Recapture: 295
   ChkMate: 3   Single: 39   Botvinnik 114
Hash probes (Cutoffs) (found): 47962 (18881) (0) 39.37
Evals:   78240
First move cutoffs: 60.53(86.54), Branching factor: 1.851852
Time taken: 1.70s NPS: 74240.58

-----------------------------------------


Note the first move cutoffs stat, it shows that 60.53% of time, the first move produced a cutoff. Since the move has produced a cutoff, other moves in that node need not be searched. Therefore no sorting necessary. Hence bubble sort inside the search, IE fetching the best move next when you are searching may be faster than presorting. That could explain Zach's results.

Best regards,
Pallav.

[Reinhard Scharnagl]

Hello Pallav,

it all tends to become more and more a philosophical question: sort or not or when how. Uri explained that his preevaluations would be affected bei trying some of the calculated moves, thus presort would be not useful. I tried to calculate and test the benefit of dividing sort into two phases: general creating of a priority queue followed by faster picking the remaining optimum until found to be good enough. But that approach has been put aside by me at last, because there seems to be no win in timings.

Because I do not (like Uri) intend to change generated prevaluations during expanding move by move, the question which remains is indeed: to always sort generally or to pick move by move without any presorting.

AndrewFan's results seem to argue for the viewpoint, that it does not matter at all, because there is no real difference to be noticed. But I still am convinced, that the sorting routines used are not implemented efficiently. To document this I posted some results to state, that my way of sorting is highly efficient though I am handling 8 byte long pairs of move and prevalue (still doing that on a 32 bit environment).

But it has been nearly impossible for me to realize sorting times needed by other programs in detail. Thus I am still basing on assumptions what targets sorting times in other programs could be. There will be no way than to finish my Smirf engine and to see the results. But even that would not be a solution to the question above, because of finally still missing sort timings of other programmers.

Reinhard.

[Reinhard Scharnagl]

Hi all,

today I have combined different types of sort together to efficiently sort small and big sets of generated moves. It follows an extrem example:

Code: Select all

FEN: R6R/3Q4/1Q4Q1/4Q3/2Q4Q/Q4Q2/pp1Q4/kBNN1KB1 w - - 0 1

  +-a--b--c--d--e--f--g--h-+ MS Vis. Studio C++ Vers. 13.10
8 |<R>:::   :::   :::   <R>| (Compilation: Oct 27 2004)
7 |:::   :::<Q>:::   :::   | Testscenario (unsorted):
6 |   <Q>   :::   :::<Q>:::| Move generation
5 |:::   :::   <Q>   :::   |
4 |   :::<Q>:::   :::   <Q>| Smirf Test No.: 13
3 |<Q>   :::   :::<Q>:::   |
2 |[p][p]   <Q>   :::   :::| Move Count:  218*333704
1 |[k]<B><N><N>:::<K><B>   | per Second:  44358214
=>+-a--b--c--d--e--f--g--h-+ Time:        1.640 sec

  +-a--b--c--d--e--f--g--h-+ MS Vis. Studio C++ Vers. 13.10
8 |<R>:::   :::   :::   <R>| (Compilation: Oct 27 2004)
7 |:::   :::<Q>:::   :::   | Testscenario (sorted, O(n*log(n))):
6 |   <Q>   :::   :::<Q>:::| Move generation
5 |:::   :::   <Q>   :::   |
4 |   :::<Q>:::   :::   <Q>| Smirf Test No.: 13
3 |<Q>   :::   :::<Q>:::   |
2 |[p][p]   <Q>   :::   :::| Move Count:  218*333704
1 |[k]<B><N><N>:::<K><B>   | per Second:  15838770
=>+-a--b--c--d--e--f--g--h-+ Time:        4.593 sec

  1.405 Qe5xb2+  1.349 Qb6xb2+  1.240 Qc4xa2+  1.153 Qd2xb2+  1.078 Qa3xa2+
  1.036 Qa3xb2+  0.973 Nd1xb2   0.913 Nc1xa2   0.789 Bb1xa2   0.563 Qg6-c2
  0.476 Nc1-b3+  0.425 Qg6-d3   0.404 Ra8-a4   0.374 Qd7-a4   0.365 Qh4-e1
  0.341 Qh4-d4   0.318 Qf3-b3   0.313 Qd7-d3   0.303 Ra8-a5   0.289 Qb6-b3
  0.286 Qe5-c3   0.286 Rh8-b8   0.284 Qg6-e4   0.265 Rh8-c8   0.264 Qh4-e4
  0.261 Qd7-b5   0.258 Qf3-c3   0.254 Qh4-f2   0.249 Qd7-d4   0.245 Qg6-c6
  0.231 Rh8-d8   0.202 Ra8-a6   0.200 Qg6-d6   0.196 Qb6-b4   0.186 Rh8-h5
  0.186 Rh8-e8   0.180 Qh4-f4   0.180 Qf3-d3   0.177 Bg1-d4   0.174 Qg6-g2
  0.173 Qd7-d5   0.167 Qe5-e1   0.167 Qe5-a5   0.155 Qe5-e2   0.155 Qe5-b5
  0.154 Bg1-e3   0.154 Bg1-c5   0.150 Qg6-g3   0.143 Qe5-d4   0.142 Qg6-f5
  0.142 Qg6-e6   0.138 Qc4-c2   0.138 Qc4-b3   0.134 Qd7-c6   0.131 Rh8-h6
  0.131 Rh8-f8   0.130 Qh4-g3   0.127 Qf3-e2   0.120 Qe5-e3   0.120 Qe5-c5
  0.111 Qg6-g4   0.111 Qb6-a5   0.101 Kf1-e1   0.101 Ra8-a7   0.099 Qb6-b5
  0.094 Qd2-c2   0.092 Qf3-e3   0.092 Qh4-g4   0.091 Bg1-f2   0.089 Qd7-d6
  0.089 Kf1-e2   0.087 Qb6-d4   0.079 Qc4-c3   0.075 Qg6-f6   0.071 Qd7-a7
  0.069 Rh8-h7   0.069 Rh8-g8   0.066 Qe5-e4   0.066 Qe5-d5   0.063 Qb6-e3
  0.063 Qb6-c5   0.063 Qd7-b7   0.062 Qh4-h1   0.061 Qc4-a4   0.061 Qg6-g5
  0.055 Qh4-h2   0.055 Qh4-f6   0.045 Qc4-b4   0.041 Qh4-g5   0.041 Qh4-e7
  0.039 Qf3-e4   0.039 Qf3-d5   0.039 Qd7-c7   0.034 Qh4-h3   0.034 Qd2-c3
  0.031 Qd7-f5   0.031 Qd7-e6   0.029 Qf3-f2   0.017 Nd1-c3   0.010 Qb6-a6
  0.000 Qb6-f2   0.000 Qd7-g4   0.000 Qc4-d3  -0.000 Qg6-f7  -0.000 Qh4-d8
 -0.000 Qf3-c6  -0.000 Qd2-b4  -0.007 Ra8-b8  -0.010 Kf1-f2  -0.018 Qe5-f4
 -0.018 Qe5-d6  -0.024 Qa3-b3  -0.025 Qg6-h5  -0.025 Qg6-e8  -0.028 Ra8-c8
 -0.029 Qb6-c6  -0.045 Qd2-d3  -0.045 Qf3-f4  -0.045 Qh4-h5  -0.051 Qd7-e7
 -0.052 Qc4-e2  -0.052 Qc4-b5  -0.058 Qd7-h3  -0.058 Qd7-c8  -0.062 Ra8-d8
 -0.064 Qc4-d4  -0.067 Qe5-g3  -0.067 Qe5-c7  -0.068 Qg6-g7  -0.070 Qf3-g2
 -0.071 Qf3-b7  -0.074 Qb6-d6  -0.075 Qe5-f5  -0.075 Qe5-e6  -0.080 Qg6-h6
 -0.084 Qa3-c3  -0.085 Qd2-e1  -0.085 Qd2-a5  -0.088 Qc4-c5  -0.091 Qb6-a7
 -0.092 Qd7-d8  -0.095 Qf3-g3  -0.097 Qd2-e2  -0.099 Qb6-b7  -0.100 Qh4-h6
 -0.101 Qa3-a4  -0.103 Qf3-f5  -0.107 Ra8-e8  -0.108 Bg1-h2  -0.109 Qd2-d4
 -0.109 Kf1-g2  -0.111 Qd7-f7  -0.117 Qa3-b4  -0.124 Qb6-c7  -0.125 Bb1-c2
 -0.132 Qb6-e6  -0.132 Qd2-e3  -0.134 Qf3-g4  -0.137 Qd7-e8  -0.141 Qc4-e4
 -0.141 Qc4-d5  -0.141 Qc4-a6  -0.142 Qg6-h7  -0.142 Qg6-g8  -0.143 Qe5-h2
 -0.143 Qe5-f6  -0.143 Qe5-b8  -0.149 Nd1-e3  -0.157 Qe5-g5  -0.157 Qe5-e7
 -0.162 Ra8-f8  -0.162 Qh4-h7  -0.162 Qa3-d3  -0.162 Nc1-d3  -0.163 Qf3-h1
 -0.170 Qf3-f6  -0.179 Qd7-g7  -0.180 Qc4-c6  -0.186 Qd2-d5  -0.191 Qf3-h3
 -0.196 Qd2-f2  -0.199 Qb6-f6  -0.199 Qb6-b8  -0.202 Qa3-a5  -0.212 Nd1-f2
 -0.214 Nc1-e2  -0.224 Ra8-g8  -0.225 Qc4-f4  -0.243 Qe5-h5  -0.243 Qe5-e8
 -0.245 Qf3-f7  -0.250 Qa3-e3  -0.250 Qa3-c5  -0.254 Qd7-h7  -0.254 Qb6-d8
 -0.263 Bb1-d3  -0.270 Qd2-f4  -0.270 Qd2-d6  -0.270 Qf3-h5  -0.275 Qc4-c7
 -0.283 Qc4-e6  -0.286 Qe5-g7  -0.295 Qd2-g2  -0.303 Qa3-a6  -0.313 Qc4-g4
 -0.325 Qf3-f8  -0.371 Qc4-c8  -0.387 Qa3-d6  -0.395 Qd2-h2  -0.404 Qa3-a7
 -0.404 Bb1-e4  -0.409 Qd2-g5  -0.425 Qc4-f7  -0.526 Qa3-e7  -0.546 Bb1-f5
 -0.549 Qd2-h6  -0.567 Qc4-g8  -0.667 Qa3-f8

The differens in measured times is caused by sorting (mainly) and preevaluating the generated moves. I selected this extrem example because by this differences in sort performance will be better to detect. I also add a more normal example:

Code: Select all

FEN: r3kN1r/p1ppqpb1/4pn2/3P4/np2P3/2N2Q2/PPPBBPpP/R3K2R b KQkq - 0 1

=>+-*--b--c--d--*--f--g--*-+ MS Vis. Studio C++ Vers. 13.10
8 |[r]:::   :::[k]<N>   [r]| (Compilation: Oct 27 2004)
7 |[p]   [p][p][q][p][b]   | Testscenario (unsorted):
6 |   :::   :::[p][n]   :::| Move generation
5 |:::   :::<P>:::   :::   |
4 |[n][p]   :::<P>:::   :::| Smirf Test No.: 17
3 |:::   <N>   :::<Q>:::   |
2 |<P><P><P><B><B><P>[p]<P>| Move Count:  47*1547822
1 |<R>   :::   <K>   :::<R>| per Second:  36085135
  +-*--b--c--d--*--f--g--*-+ Time:        2.016 sec

=>+-*--b--c--d--*--f--g--*-+ MS Vis. Studio C++ Vers. 13.10
8 |[r]:::   :::[k]<N>   [r]| (Compilation: Oct 27 2004)
7 |[p]   [p][p][q][p][b]   | Testscenario (sorted, O(n*log(n))):
6 |   :::   :::[p][n]   :::| Move generation
5 |:::   :::<P>:::   :::   |
4 |[n][p]   :::<P>:::   :::| Smirf Test No.: 17
3 |:::   <N>   :::<Q>:::   |
2 |<P><P><P><B><B><P>[p]<P>| Move Count:  47*1547822
1 |<R>   :::   <K>   :::<R>| per Second:  18624586
  +-*--b--c--d--*--f--g--*-+ Time:        3.906 sec

  12.27 g2xh1Q+  9.110 g2xh1R+  7.899 g2-g1Q+  7.087 g2xh1B   6.735 g2xh1N
  4.524 g2-g1R+  3.080 b4xc3    3.032 Na4xc3   2.758 Ke8xf8   2.743 Rh8xf8
  2.714 Bg7xf8   2.399 g2-g1B   2.368 Qe7xf8   2.024 g2-g1N   1.137 Rh8xh2
  1.026 e6xd5    1.025 Nf6xe4   0.998 Na4xb2   0.911 Nf6xd5   0.472 O-O-O
  0.405 Rh8-h3   0.341 Rh8-h4   0.264 Rh8-h5   0.180 Rh8-h6   0.157 a7-a5
  0.154 Qe7-c5   0.151 Nf6-g4   0.101 e6-e5    0.100 Ra8-d8   0.099 d7-d6
  0.095 c7-c6    0.092 Rh8-h7   0.091 Qe7-d6   0.082 a7-a6    0.079 Ra8-c8
  0.064 b4-b3    0.062 c7-c5    0.053 Na4-c5   0.050 Bg7-h6   0.045 Ra8-b8
  0.034 Rh8-g8   0.010 Nf6-h5  -0.007 Ke8-d8  -0.084 Na4-b6  -0.108 Qe7-d8
 -0.163 Nf6-h7  -0.220 Nf6-g8

Other results to be compared would be welcomed.

Reinhard.