Winboard Forum

by **Dan Honeycutt** » 22 Oct 2004, 16:18

Hi Reinhard:

I don't think it's a psudo name - I think he's Andrew Fan whose program Firefly is among the leaders in Olivier's Chess War F.

Hi Andrew:

Your numbers look OK but I'd suggest you use a perft to benchmark. If you generate moves for the same position over and over I don't know that the processor won't cache everything it needs and give you false results. Plus a perft is a good means to find bugs in your move generator.

Best
Dan H.

by **Reinhard Scharnagl** » 22 Oct 2004, 17:00

Hi andrewfan,

well it seems that I have to excuse myself. I thought there would be an anonymus fan of the british royals, sorry. If you would have added a ULR, I might have been better informed.

Because I am still developing my Smirf very undependently, it easyly might happen that even well known names are not (yet) known by me.

Reinhard.

by **Dan Honeycutt** » 22 Oct 2004, 19:38

Hi Reinhard:

Because I am still developing my Smirf very undependently, it easyly might happen that even well known names are not (yet) known by me.

That's because you spend all your time with the nerds here in programming.

Go to tournaments. Just because Smirf is not yet playing doesn't mean you can't enjoy the action. We have fantastic tournaments running by Olivier, Heinz, Leo, Guenther and many others. Plus, you need to scope out the competition for the time when Smirf enters combat.

Dan H.

by **Reinhard Scharnagl** » 22 Oct 2004, 23:07

Hi AndrewFan,

it seems that we are facing quite comparable situations - hardware (me P4 2.8 GHz) and development environment (equal). So long as no caching would be involved, RAM should be of less importance.

Because my moves and preevaluations are pairs of integers (thus 8 byte together), I am thinking on how to improve my sorting routine. I have thought to compress both data into 2 byte integers, but that would mean to substitute the check threat direction information (I like to have and use) by a single bit and to recalculate it before expanding. Together with packing and unpacking of coordinates it would be too time consuming.

Therefore I am now following a double idea: a) first: sort indirectly b) later: try to make a pseudosort with O(n) costs and an O(n*log(n)) cost picking procedure, hoping that the moves would be only partially requested.

Reinhard

P.S.:
1) Variant a) has not been successfull at my data structure
2) Variant b) seems to be very successfull. Thus from now on I will sort moves no more. Instead I am creating a priority queue of moves (at O(n) costs) and later individually picking the move with highest priority (at maximal O(n*log(n)) costs, but what would be only rarely fully exhausted).

by **Reinhard Scharnagl** » 23 Oct 2004, 15:34

Hi all,

how do you judge on the speed of following results of generated moves (starting with two FRC examples):

legal only, including check threat direction, capturing flag, preevaluation and being priority queued (not shown directly):

Code: Select all: FEN: r1k2r1q/p1ppp1pp/8/8/8/8/P1PPP1PP/R1K2R1Q w KQkq - 0 1 +-*--b--*--d--e--*--g--h-+ MS Vis. Studio C++ Vers. 13.10 8 |[r]:::[k]::: [r] [q]| (Compilation: Oct 23 2004) 7 |[p] [p][p][p] [p][p]| Testscenario (priority queued): 6 | ::: ::: ::: :::| Move generation 5 |::: ::: ::: ::: | 4 | ::: ::: ::: :::| Smirf Test No.: 15 3 |::: ::: ::: ::: | 2 |::::::| Move Count: 28*750000 1 |<R> <K> :::<R>:::<Q>| per Second: 24418604 =>+-*--b--*--d--e--*--g--h-+ Time: 0.860 sec 5.654 Rf1xf8+ 0.500 O-O-O 0.450 Rf1-f7 0.405 Rf1-f6 0.341 Rf1-f5 0.264 Rf1-f4 0.202 c2-c4 0.198 d2-d4 0.187 e2-e4 0.187 a2-a4 0.180 Rf1-f3 0.157 g2-g4 0.142 h2-h4 0.101 c2-c3 0.099 d2-d3 0.095 e2-e3 0.095 a2-a3 0.093 Kc1-b2 0.092 Rf1-f2 0.082 g2-g3 0.075 h2-h3 0.055 Rf1-d1 0.055 Qh1-g1 0.034 Rf1-e1 0.021 Ra1-b1 -0.007 Kc1-d1 -0.007 Kc1-b1 -0.045 Rf1-g1 FEN: 8/8/8/4B2b/6nN/8/5P2/2R1K2k w Q - 0 1 +-a--b--c--d--e--f--g--h-+ MS Vis. Studio C++ Vers. 13.10 8 | ::: ::: ::: :::| (Compilation: Oct 23 2004) 7 |::: ::: ::: ::: | Testscenario (priority queued): 6 | ::: ::: ::: :::| Move generation 5 |::: ::: :::[b]| 4 | ::: ::: :::[n]<N>| Smirf Test No.: 16 3 |::: ::: ::: ::: | 2 | ::: ::: :::| Move Count: 34*750000 1 |::: <R> <K> :::[k]| per Second: 24733268 =>+-a--b--*--d--*--f--g--h-+ Time: 1.031 sec 0.798 O-O-O+ 0.484 Ke1-e2+ 0.404 Be5-h2 0.387 Ke1-d2+ 0.279 Be5-g3 0.160 Nh4-g2 0.141 Be5-f4 0.101 Rc1-d1 0.101 Ke1-f1 0.017 Nh4-f3 0.000 Be5-d4 -0.010 Rc1-c2 -0.039 Be5-c3 -0.039 Rc1-c3 -0.039 Be5-f6 -0.060 f2-f3 -0.084 Rc1-c4 -0.101 Ke1-d1 -0.101 Rc1-b1 -0.109 Be5-b2 -0.109 Be5-g7 -0.138 f2-f4 -0.142 Be5-d6 -0.142 Rc1-c5 -0.149 Nh4-f5 -0.202 Be5-a1 -0.202 Rc1-a1 -0.202 Be5-h8 -0.209 Rc1-c6 -0.212 Nh4-g6 -0.284 Be5-c7 -0.284 Rc1-c7 -0.364 Rc1-c8 -0.426 Be5-b8 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 23 2004) 7 |[p] [p][p][q][p][b] | Testscenario (priority queued): 6 | ::: :::[p][n] :::| Move generation 5 |::: :::::: ::: | 4 |[n][p] :::::: :::| Smirf Test No.: 17 3 |::: <N> :::<Q>::: | 2 |[p]| Move Count: 47*750000 1 |<R> ::: <K> :::<R>| per Second: 23995915 +-*--b--c--d--*--f--g--*-+ Time: 1.469 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

Regards, Reinhard.

by **Reinhard Scharnagl** » 23 Oct 2004, 20:34

Hi all,

the priority queue is working fine. After some improvements, building up the priority queue itself could be made faster by about 50%. Thus the measured time consumption for the last example now has been reduced to:

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 23 2004) 7 |[p] [p][p][q][p][b] | Testscenario (priority queued): 6 | ::: :::[p][n] :::| Move generation 5 |::: :::::: ::: | 4 |[n][p] :::::: :::| Smirf Test No.: 17 3 |::: <N> :::<Q>::: | 2 |[p]| Move Count: 47*750000 1 |<R> ::: <K> :::<R>| per Second: 27517564 +-*--b--c--d--*--f--g--*-+ Time: 1.281 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

Regards, Reinhard.

by **Reinhard Scharnagl** » 24 Oct 2004, 00:19

Hi AndrewFan,

Personally I would like to run the tests a lot longer than 1 or 2 seconds ...

How about following test position (or some common Perft tests):

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 23 2004) 7 |::: :::<Q>::: ::: | Testscenario (priority queued): 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]<N><N>:::<K> | per Second: 30509423 =>+-a--b--c--d--e--f--g--h-+ Time: 5.359 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 Ra8-a7 0.101 Kf1-e1 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

Sorting is done whenever needed - i.e. during search

How is that to be understood? I am just about to go away from sorting, substituting it by building up a priority queue and fetching ordered moves later on demand. I do not know, whether this has been done already, but it is obviously a promising alternative.

Reinhard.

by **Reinhard Scharnagl** » 24 Oct 2004, 17:48

Hi all,

let explain the experiences I have had with splitting the sorting of all node moves into a quick phase of generating a priority queue and a slow phase of dequeuing all moves in ordered sequence. After some optimizing I have found following average timings:

presort : sort : dequeuing = 1/2 : 1 : 3/2

Supposing 1/3 of nodes would be fully expanded, the remaining 2/3 only partially with an (optional) average of 1/4 dequeuing time would lead to the following time calculation:

time(sort) = 1/1 * 1 = 1, time(combi) = 1/1*1/2 + 1/3*3/2 + 2/3*3/2*1/4 = 5/4

That means that even when the not completly expanded nodes would (not realistic) not need any time to dequeue the few best moves, the time consumed would be not less than a complete early sort for all the moves. The consequence from that is:

Sorting moves is better than splitting into priorizing moves first and dequeuing moves later.

Any comments to that calculation? Any other strategies with timings?

Reinhard.

by **Zach Wegner** » 24 Oct 2004, 19:39

Hello Reinhard,

I am not quite sure what this calculation represents. What is presort and why is it only performed in the dequeuing? I also am not sure about the 1/4. It is close because in 90% of the cases the ratio will be n to n log n, which for chess, is around 1 to log 35, so just under 1/5. This is only for the ~90% where the first move fails high. So it is probably at 1/4 or a little less. The only thing I want to say is that you should test this out after you have a working engine, because that is the only way to tell which is faster.

by **Reinhard Scharnagl** » 24 Oct 2004, 20:12

Hello Zach,

What is presort ...

well I will try again to explain my two different approaches:

a) sorting all generated moves immediately after creation,
b) presorting the generated moves by building a priority queue and later dequeuing each move on demand in sorted order.

The time consumption (applied on all moves from one node) is relativly: presort : sort : dequeuing = 1/2 : 1 : 3/2 (measured at my own algorithms).

The 1/4 is measuring the time consumption of dequeuing for the optimal moves when not fully expanded. Because the first to be dequeued moves would need much more time than the last moves. That is an estimation for a situation where only less then 1/8 of moves would be needed. But you are right, when you point to a test of that in practise.

But for me (I have to decide what variant to prefer in Smirf) the decision is clear: back again to a complete and unconditional sorting of all moves en block.

Naturally I have thought over a third alternative c), to do neither sort nor presort, but instead perform a time consuming search (for some moves) comparable to a dequeuing. Here I have following estimation: presort : sort : dequeuing : opt.-picking = 1/2 : 1 : 3/2 : 3

That could give 3/4 (opt.-picking) to 1 (complete search), but only under the very irreal assumption, that the fully expanded nodes would not have used any sorting effort at all. But there hardly would be such gut razoring criteria. And if there would be some that good, I still would prefer variant b) then, but never c).

Reinhard.

by **Zach Wegner** » 24 Oct 2004, 20:22

Hello all,
I would like to add a bit of information to the discussion. I tested the sorting techniques to 10 ply from the opening position. Here is the relevant data:

Code: Select all: Best move selected from remaining moves: nodes=1283412 q=77.2% time=11.127 NPS=115342 Full selection sort performed at every node: nodes=1283412 q=77.2% time=11.628 NPS=110372 Full quicksort performed at every node: nodes=1584249 q=77.1% time=14.453 NPS=109613

I attribute the poor performance of quicksort to the fact that the order of elements that are equal is unspecified combined with the low resolution of my move scores (8 bits). I am surprised that it caused so many more nodes though.

Regards,
Zach

by **Reinhard Scharnagl** » 24 Oct 2004, 20:30

Hi Zach,

I do not understand the different node count at c). Would you please describe more detailled what you did? Thank you!

Reinhard.

by **Zach Wegner** » 24 Oct 2004, 20:51

Hello Reinhard,

I replaced from the second variant the selection sort with a call to the stdlib qsort. I think that because the way elements with the same sort value are handled is different in this function is the cause for the disparity, especially because it is more likely to have moves with the same score in my program.

by **Reinhard Scharnagl** » 24 Oct 2004, 20:52

Hi Zach,

an O(n*log(n)) search should perform better than a O(n^2) sort. Thus I cannot understand your results. See for comparing reasons of sort performances following examples:

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 24 2004) 7 |::: ::: ::: | Testscenario (sorted, O(n^2)): 6 | [k] ::: :::| Move generation 5 |::: ::: [n][p]::: | 4 | <N><K> [r]:::| Smirf Test No.: 00 3 |:::<R>::: ::: ::: | 2 | <N> <Q> :::| Move Count: 37*750000 1 |::: :::[q]::: [b] | per Second: 16294773 =>+-a--b--c--d--e--f--g--h-+ Time: 1.703 sec +-a--b--c--d--e--f--g--h-+ MS Vis. Studio C++ Vers. 13.10 8 | ::: [q] :::<R>:::| (Compilation: Oct 24 2004) 7 |::: ::: ::: | Testscenario (sorted, O(n*log(n)): 6 | [k] ::: :::| Move generation 5 |::: ::: [n][p]::: | 4 | <N><K> [r]:::| Smirf Test No.: 00 3 |:::<R>::: ::: ::: | 2 | <N> <Q> :::| Move Count: 37*750000 1 |::: :::[q]::: [b] | per Second: 18125408 =>+-a--b--c--d--e--f--g--h-+ Time: 1.531 sec +-a--b--c--d--e--f--g--h-+ MS Vis. Studio C++ Vers. 13.10 8 | ::: [q] :::<R>:::| (Compilation: Oct 22 2004) 7 |::: ::: ::: | Testscenario (unsorted): 6 | [k] ::: :::| Move generation 5 |::: ::: [n][p]::: | 4 | <N><K> [r]:::| Smirf Test No.: 00 3 |:::<R>::: ::: ::: | 2 | <N> <Q> :::| Move Count: 37*750000 1 |::: :::[q]::: [b] | per Second: 29584221 =>+-a--b--c--d--e--f--g--h-+ Time: 0.938 sec 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 24 2004) 7 |[b] <N> <Q> ::: | Testscenario (sorted, O(n^2)): 6 | :::::: ::: <K>| Move generation 5 |[r] :::::: :::[b]| 4 |[p] [k] :::[p]:::| Smirf Test No.: 01 3 |:::[q]<R> [p] ::: | 2 | <N>[n]::: ::: :::| Move Count: 54*750000 1 |::: ::: ::: [n] | per Second: 15340909 =>+-a--b--c--d--e--f--g--h-+ Time: 2.640 sec +-a--b--c--d--e--f--g--h-+ MS Vis. Studio C++ Vers. 13.10 8 | ::: <R> ::: :::| (Compilation: Oct 24 2004) 7 |[b] <N> <Q> ::: | Testscenario (sorted, O(n*log(n)): 6 | :::::: ::: <K>| Move generation 5 |[r] :::::: :::[b]| 4 |[p] [k] :::[p]:::| Smirf Test No.: 01 3 |:::[q]<R> [p] ::: | 2 | <N>[n]::: ::: :::| Move Count: 54*750000 1 |::: ::: ::: [n] | per Second: 19203413 =>+-a--b--c--d--e--f--g--h-+ Time: 2.109 sec +-a--b--c--d--e--f--g--h-+ MS Vis. Studio C++ Vers. 13.10 8 | ::: <R> ::: :::| (Compilation: Oct 22 2004) 7 |[b] <N> <Q> ::: | Testscenario (unsorted): 6 | :::::: ::: <K>| Move generation 5 |[r] :::::: :::[b]| 4 |[p] [k] :::[p]:::| Smirf Test No.: 01 3 |:::[q]<R> [p] ::: | 2 | <N>[n]::: ::: :::| Move Count: 54*750000 1 |::: ::: ::: [n] | per Second: 43926247 =>+-a--b--c--d--e--f--g--h-+ Time: 0.922 sec 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 24 2004) 7 |::: :::<Q>::: ::: | Testscenario (sorted, O(n^2)): 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]<N><N>:::<K> | per Second: 8890701 =>+-a--b--c--d--e--f--g--h-+ Time: 18.390 sec +-a--b--c--d--e--f--g--h-+ MS Vis. Studio C++ Vers. 13.10 8 |<R>::: ::: ::: <R>| (Compilation: Oct 24 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]<N><N>:::<K> | per Second: 13330615 =>+-a--b--c--d--e--f--g--h-+ Time: 12.265 sec +-a--b--c--d--e--f--g--h-+ MS Vis. Studio C++ Vers. 13.10 8 |<R>::: ::: ::: <R>| (Compilation: Oct 22 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*750000 1 |[k]<N><N>:::<K> | per Second: 44526143 =>+-a--b--c--d--e--f--g--h-+ Time: 3.672 sec

Regards, Reinhard.

by **Zach Wegner** » 24 Oct 2004, 21:00

Reinhard Scharnagl wrote:an O(n*log(n)) search should perform better than a O(n^2) sort. Thus I cannot understand your results.

Indeed, it is strange. I think the difference is because:
1. Statistical error
2. A call to a library function (the selection sort was coded inline)
3. The extra nodes searched
4. I think different applications were running

I will rerun each test 3 times with no other applications running, and report the results back shortly.

Regards,
Zach

by **Uri Blass** » 24 Oct 2004, 21:01

Hi Reinhard

I am not sure about it.

After you search the first move and failed low you have more information
so you may have better order of moves for the rest of the moves.

If you decide about the order of all moves in one step you may lose information so your order may be worse when you pick the secong and the third move.

This may be a reason to prefer only sorting the best move every time
you need to decide which move to searh next.

Uri

by **Reinhard Scharnagl** » 24 Oct 2004, 21:04

Hi Uri,

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

Regards, Reinhard.

by **Zach Wegner** » 24 Oct 2004, 21:20

Hello all,

I have rerun the tests, and the results are just about the same:

Code: Select all: Best move selected from remaining moves: nodes=1167009 q=74.3% time=9.816 NPS=118888 nodes=1167009 q=74.3% time=9.797 NPS=119119 nodes=1167009 q=74.3% time=9.833 NPS=118682 average time=9.815 NPS=118896 Full selection sort performed at every node: nodes=1167009 q=74.3% time=9.929 NPS=117535 nodes=1167009 q=74.3% time=9.922 NPS=117618 nodes=1167009 q=74.3% time=9.990 NPS=116817 average time=9.947 NPS=117323 Full quicksort performed at every node: nodes=1517045 q=74.8% time=13.022 NPS=116498 nodes=1517045 q=74.8% time=12.979 NPS=116884 nodes=1517045 q=74.8% time=13.046 NPS=116284 average time=13.016 NPS=116555

Regards,
Zach

Winboard Forum

Move Generation Speed

Re: Move Generation Speed

Re: Move Generation Speed

Re: Move Generation Speed

Re: Move Generation Speed

Re: Move Generation Speed

Re: Move Generation Speed

Re: Move Generation Speed

Re: Move Generation Speed

Re: Move Generation Speed

Re: Move Generation Speed

Re: Move Generation Speed

Re: Move Generation Speed

Re: Move Generation Speed

Re: Move Generation Speed

Re: Move Generation Speed

Re: Move Generation Speed

Re: Move Generation Speed

Re: Move Generation Speed

Who is online