back to the Komodo SMP issue

[Henk]

It may easily happen that while searching N times faster the perhaps small error in the value of the best move in the root is still too big.

This causes the better moves in the root to be rejected.

The player that makes the smallest errors in important positions wins the game.

All parameters that have any effect on basic evaluation or pruning should be 're-tuned'. Or basic evaluation should be rewritten. Or more accurate pruning methods should be invented and implemented.

Of course if it is only one parameter that causes the error bottleneck only that parameter needs to be changed.

If the algorithm is optimal, it might also be that not N times more nodes need the searched, but 100 times N times to overcome the error bottleneck. But this is perhaps theoretic non sense.

[duncan]

If it does scale well, additional depth almost certainly pays off more than increased width, else the serial search would go for the increased width as well...

there is something basic I do not understand.

if twice the time used searching additional depth in a single core gives 70 extra elo, but searching extra width gives 80% of that ie 56 elo.

then when using 2 cores which scales at 80% efficiency, you could either go for additional depth to get the 56 elo or extra width at 100% efficiency to get the 56 elo, which is why serial search does not go for the increased width but a parallel can without losing elo.

duncan

[Jesse Gersenson]

As a teenager my father gave me a summer-job on a house-building project he was orchestrating. There were three of us building the house. After a few days my old man asked me how it was going. "It's hard on my body and boring. A lot of times I don't know what I'm supposed to be doing," i told him.

He explained my job to me, "Well, I've got two guys who I'm paying $25/hr and you who I'm paying $10/hr. Your job is to do anything you can to make the $25/hr guys work faster."

[FlavusSnow]

It's a good question. I don't have the answer. In my pea-brain I conceptualize it as the engine being tuned to be too aggressive at pruning/reducing. For a single thread this means it needs higher depths before it exposes incorrect prunes/reductions, but on SMP some of the "search inefficiency" can fill the gaps sooner, and at lower depths.

[syzygy]

If it does scale well, additional depth almost certainly pays off more than increased width, else the serial search would go for the increased width as well...

there is something basic I do not understand.

if twice the time used searching additional depth in a single core gives 70 extra elo, but searching extra width gives 80% of that ie 56 elo.

then when using 2 cores which scales at 80% efficiency, you could either go for additional depth to get the 56 elo or extra width at 100% efficiency to get the 56 elo, which is why serial search does not go for the increased width but a parallel can without losing elo.

Bob's argument is logically flawed in more than one way.

[duncan]

Bob's argument is logically flawed in more than one way.

to avoid what bob will call handwaving perhaps you could spell it out or reference it if you have already done so, so bob can respond.

duncan

[bob]

It's a good question. I don't have the answer. In my pea-brain I conceptualize it as the engine being tuned to be too aggressive at pruning/reducing. For a single thread this means it needs higher depths before it exposes incorrect prunes/reductions, but on SMP some of the "search inefficiency" can fill the gaps sooner, and at lower depths.

It is not quite that easy. You can't redirect the "effort" within a parallel search. There are two distinct components of a parallel chess engine:

(1) the basic alpha/beta search, along with all the usual selectivity stuff like null-move, reductions, forward-pruning and such. You generally tune these so that they provide the max Elo on a single CPU box.

(2) the parallel search, which simply traverses the tree above, but in parallel to complete it faster (to the same depth). This introduces some overhead since move ordering is not perfect, yet alpha/beta depends on it being good. Unfortunately, a parallel search has to split the search at various points, and that DOES require perfect ordering, else you introduce search overhead in the form of extra nodes searched when you split at a CUT node.

To increase width, you just tighten up the reductions and pruning rules so that they are activated less frequently. This penalizes depth. Then you use a parallel search to hopefully gain that speed back through search efficiency.

I don't see the gain at the present, given a reasonable parallel search implementation that can produce a speedup > 3x for 4 cpus, unless the pruning rules are too liberal to begin with, and tightened up to increase the size of the tree. At the cost of search depth. And that would seem to be something that should work on the single cpu version equally well.

All this chatter about 128 cores and such is irrelevant when we are specifically talking about 4 cpu examples. Diminishing returns doesn't become a serious problem with just 4 cores.

At the moment, I seem to be missing the point...

[bob]

If it does scale well, additional depth almost certainly pays off more than increased width, else the serial search would go for the increased width as well...

there is something basic I do not understand.

if twice the time used searching additional depth in a single core gives 70 extra elo, but searching extra width gives 80% of that ie 56 elo.

then when using 2 cores which scales at 80% efficiency, you could either go for additional depth to get the 56 elo or extra width at 100% efficiency to get the 56 elo, which is why serial search does not go for the increased width but a parallel can without losing elo.

duncan

How do you go for extra width at 100% efficiency? You STILL have to search that extra width in parallel, and the parallel search overhead doesn't go away. That is EXACTLY the issue I have been addressing.

[bob]

If it does scale well, additional depth almost certainly pays off more than increased width, else the serial search would go for the increased width as well...

there is something basic I do not understand.

if twice the time used searching additional depth in a single core gives 70 extra elo, but searching extra width gives 80% of that ie 56 elo.

then when using 2 cores which scales at 80% efficiency, you could either go for additional depth to get the 56 elo or extra width at 100% efficiency to get the 56 elo, which is why serial search does not go for the increased width but a parallel can without losing elo.

Bob's argument is logically flawed in more than one way.

And you have yet to point out a single one. Just hand-waving and such. Not one scintilla of technical discussion to address this issue. And yet you keep posting.

Whatever you do to the shape of the tree, you STILL have to run it through the parallel search and lose the overhead cost..

[bob]

Bob's argument is logically flawed in more than one way.

to avoid what bob will call handwaving perhaps you could spell it out or reference it if you have already done so, so bob can respond.

duncan

Do NOT hold your breath...