Number of Nodes Visited

FeikeBoomstra · Post by **FeikeBoomstra** » Sun Nov 16, 2008 13:59

After weeks of working getting my parallel implementation hopefully error free, I am again trying to have a look at the performance.

This is what I like to share:

Code: Select all

   dur:   0.00, k= 2 avg= 2.0 max= 5 s= 210 11-17  (410)
   dur:   0.00, k= 4 avg= 6.0 max=10 s=1615 19-24  (360)
   dur:   0.02, k= 6 avg=10.0 max=15 s=2077 19-24  (375)
   dur:   0.36, k= 8 avg=14.0 max=22 s=2589 19-24  (445)
   dur:   5.86, k=10 avg=18.0 max=29 s=2999 19-24  (410)

the counters for the last run:
nodes visited  :	   17.564.624
evaluated:	          6.370.600
hash hits:	          1.872.551

Can you please comment on it. What are your figures if you run for the best move in about 6 seconds in the given position:
[FEN B:B1,3,4,7,8,9,11,12,13,15,16,18,19,20,W27,29,32,34,35,36,37,38,39,42,45,46,47,48]

11-17 gives the same score as 19-24, it is just an exchange of the moves.

Ed Gilbert · Post by **Ed Gilbert** » Sun Nov 16, 2008 17:23

Hi Feike,

I'm not sure what you wanted to compare. What do all your numbers mean? I assume k means nominal search depth, and then avg and max are also search depths in plies? What is 's', and the numbers in parentheses after the moves?

I don't think it is possible to compare node counts between different engines. There are just too many ways to count nodes, and what is depth when every engine has its own unique algorithm for extensions and truncations?

Comparing node counts is only useful between two versions of the same engine, e.g. to evaluate some change to the search. Even then I do this by averaging the results over many searches, because any one search is too much affected by random things like fortuitous move ordering, etc.

Your ratio of hash hits to nodes looks low to me. In kingsrow this is typically around 17% in the opening and increases to about 25% when half the pieces are off the board. Were you using a very small hashtable?

Below is the search log from kingsrow on this position using 4 search threads.

Code: Select all

best 20-24, value 10, depth 1/3.7/8, nodes 134, time 0.00, 134 kN/s
best 11-17, value 10, depth 3/7.2/14, nodes 1409, time 0.00, 1409 kN/s
best 11-17, value 14, depth 5/9.1/19, nodes 28315, time 0.00, 28315 kN/s
best 19-24, value 24, depth 7/10.7/23, nodes 89202, time 0.03, 2788 kN/s
best 19-24, value 20, depth 9/12.3/26, nodes 283177, time 0.06, 4495 kN/s
best 19-24, value 20, depth 11/14.4/28, nodes 1142574, time 0.22, 5217 kN/s
best 19-24, value 20, depth 13/16.4/32, nodes 4986050, time 0.84, 5908 kN/s
best 19-24, value 18, depth 15/18.6/36, nodes 25515247, time 4.08, 6257 kN/s
best 19-24, value 18, depth 17/20.7/38, nodes 103982111, time 16.64, 6249 kN/s

-- Ed

FeikeBoomstra · Post by **FeikeBoomstra** » Sat Dec 27, 2008 13:04

From the game (gorredijk) BoomstraDam - Sjende Blyn move 32. for white, I computed, just for curiosity, for both programs the relation between average depth (= average distance from the root to all visited leaf-nodes) and the number of visited nodes.

In my opinion this is an important relation, because it tells you something about how efficient you are throwing away unwanted search paths. Of course, it doesn't measure if you throw away too many paths, missing important positions.

This is the realtion:
Kingsrow: visited kNodes (depth) = 10^(0.26*depth - 1.16)
BoomstraDam: 10^(0.27*depth - 1.22)

It looks like a small difference, but at average depth = 26 it means that Kingsrow will have to examine 400.000 kNodes and BoomstraDam 630.000 kNodes. In other words, if all other elements were the same, than Kingrow can go on average one ply deeper.

My cutoff strategy is material loss only. I have build a finite state machine in the search to recognize a possible combination, otherwise I end the search at material loss ( a little bit simplified)

TAILLE · Post by **TAILLE** » Sat Dec 27, 2008 16:16

HI Feike,

I do not quite understand what importance you see in the ratio
average distance from the root to all visited leaf-nodes/number of visited nodes.
When looking at Damy implementation, this ratio do not depend on how efficient you are throwing away unwanted search paths. This ratio depend on the Q-search algorithm.

Let's take an exemple.
Starting from the following position under discussion

consider now the following sequence
32-27?? 21x43 25-20 14x25 33-28 22x33 29x49

black to play
Black has here a very great material advantage. You can see that the number of visited leaf-nodes will not depend on the way you will reduce the analysis of the first move 32-27?? but rather it will depend on the way you will finish the exploration of this bad move.
If in the above diagram it remains only one ply available for exploration then you will try the first black move generated and you will immediatly discover a cutoff. As a consequence you will visit only one leaf node.
If now it remains 2 plies available then you will play the first black move and then you will generate 11 white moves and visit these 11 leaves in order to demonstrate that black last move was an obvious cutoff in this position.

Gérard

FeikeBoomstra · Post by **FeikeBoomstra** » Sat Dec 27, 2008 19:44

Hi Gerard,

my general assumption is that, the lesser nodes you visit to explore a certain depth, the stronger your program will play (as long as you don't miss interesting positions).

I agree that this is depended on your search strategy and your increase and decrease search depth algorithms.

I didn't mention this here, but from earlier post I did know that Kingrow and me are using the same alpha-beta (zero-window) algorithm. So the difference has to be in the increase / decrease routines.

FeikeBoomstra · Post by **FeikeBoomstra** » Sat Dec 27, 2008 19:45

By the way, what is your best move in this position after around 20 sec searching?

TAILLE · Post by **TAILLE** » Sat Dec 27, 2008 20:17

Hi Feike,

FeikeBoomstra wrote:By the way, what is your best move in this position after around 20 sec searching?

Damy begins by chosing 24-20 but after 7 seconds it changes its move for 48-42.

Gérard

BertTuyt · Post by **BertTuyt** » Sat Dec 27, 2008 20:55

Damage also prefers 48-42

Bert

FeikeBoomstra · Post by **FeikeBoomstra** » Sat Dec 27, 2008 22:20

I can't get rid of 24-20. But the origin of my loss is move 29. 36-31.

That;s too aggressive, as it create the foundation for the threat: black on 16 & 21. After this move, the only thing I can do it every time try to remove the black piece from 22, and at the moment of playing 24-20 I can't see that eventually I will not be able to exchange 22 enough times.

I am thinking about renaming my program: Horizon , a much better name than the name I just put in my email, when I joined the first tournament.

Lost Horizon comes in my mind, but also the fact that I always want to know what is behind the horizon. In a way you can also say that draught programs are fighting the horizon. If you have a perfect evaluation function, you have no problems with the horizon.

This also brings me to another topic I want to investigate in the future, the frequency of changes on the best move between the last two depths.