Questions on SMP search

[Milos]

How big a field do you think computer games are, compared to all the other research that is ongoing?

I already wrote about that couple of times. And what do you think, that "huge" size is a measure of quality or the measure of lack of the same?

[bob]

How big a field do you think computer games are, compared to all the other research that is ongoing?

I already wrote about that couple of times. And what do you think, that "huge" size is a measure of quality or the measure of lack of the same?

Didn't think you understood the "impact". No surprise there...

[Milos]

Please cite _any_ source that claims that somehow, magically, LMR invalidates the concept of diminishing returns. Of course you can't, because there isn't one.

Ofc I can't since the most recent paper on it still uses that data from Crafty 19.6, how ridiculous is that???
Diminishing return is not about how often I change best move at different depth. It is about if I speed up my processor from 1x to 2x and get 50 elo increase will I also get 50 elo increase if I speed it up from 512x to 1024x.
The simple answer is without LMR no, with LMR (more aggressive Null Move Pruning and other stuff from 2005 onwards) most probably yes.

[Karlo Bala]

And on topic, Houdini 1.5 parallelization _practically_ works better than Crafty's

Data?

Don't have right now, but I did the following:
NPS and time to depth are useless.

In other words, you have no data. Time to depth is the _only_ way to measure SMP performance. and I do mean the _ONLY_ way.

A little silly from you. You must know that the ELO gain and time to solution are MUCH more reliable. Depth "8 core" is not the same as Depth "1 core" (maybe in Crafty it's the same, that would be pretty unusual).

Kai

You do realize that for _most_ positions, time to depth and time to solution are _identical_? Only those odd positions where a program changes its mind due to pure non-determinism will be different. Choose enough positions and those won't be a problem. If there is a clear best move, a program should find that move at the same depth, same PV, same score, most of the time. Hence a lot of runs to wash out the sampling error.

What I started doing recently, and I'm not claiming it is sound yet but it looks promising, is measuring score difference with as oracle an insanely long search of say 60 minutes.

I take this oracle reference and then measure the difference with, say, a 3 minute search on 1 core. I square these errors, average them and square root at the end. That is the 'performance indicator for the 3 minute single core search. Closer to 0 is better.

I compare that then with what 30 second searches on a 6-core give. This would be a larger number because a single thread search is more effective. But at some longer interval, say 60 seconds, the indicators are the same. Then I say that I have a 'speedup equivalent' of 3.0 on 6 cores.

The idea is that I get more than 1 bit of information out of every position search, and thus need fewer positions to get a good indicator. The downside is the need for long oracle searches. I had a few computers calculate those while I was traveling for a few weeks.

What about the positions where there is really a "right" score and everything else is wrong? Mate-in-N as one example. But any position where you can win material, or win a positional concession, or whatever. I am not so interested in the variance of the score, because one can produce enough of that by just playing the same game N times, ponder=on, and just taking a different amount of time before entering each move.

The only goal of SMP is to search faster. You can use time to complete a specific depth, or time to find the best move, but you do need a "time" measurement since the SMP performance metric is "speedup". Defined as

speedup = 1-cpu-time / N-cpu-time.

Normally N-cpu-time is smaller so the speedup is a number > 1.0, hopefully.

I have selected the test positions to have no scores outside abs(score)>2.5 I don't care too much what the engine does outside that range.

It is not just for SMP testing, that is a special case. I judge any search change with it at the moment.

To do a full validation of the method takes me some more time, but I'm setting it up, hopefully some data by this summer. A similar method works for me for judging evaluation changes, but that is a simpler problem.

I don't use positions for anything other than very quick evaluation of a search change, or for measuring changes to the SMP code. Everything else I do is game-based. The problem with Elo and SMP is this.

Program A gains +50 Elo from using 4 cpus.
Program B gains +70 Elo from using 4 cpus.

Which one has the better SMP algorithm?

You can't answer that. A may search much deeper than B, and we know for certain that adding a ply has a diminishing return on elo gain. If B is much slower than A, then B might have a _worse_ SMP algorithm, but the speed gain helps B more than A.

That's the problem with using Elo, until you have a direct Elo to speed gain for each program. And once you have that, you don't need the Elo stuff.... Not to compare SMP effectiveness.

Elo is a measure for the entire program not only for SMP. SMP mean nothing if the branching factor is for example 6. You can add 3 more processors without any benefit.

Sorry, but that is simply wrong. A program with a branching factor of 6 gets nothing from a CPU twice as fast? Absolutely false. Backed up by years and years of data...

I'm not an expert for sure, but this was said by Ed Schroeder:

"Mind you, if you are able to produce a chess program with an effective branch-factor of 2.0 then every doubling in processor speed will give you an extra iteration, in most cases good for an increase of +30-50 elo points in the computer-computer competition."

So, on the basis of the statements above, doubling the speed is not enough to get an extra iteration with high EBF.

[Milos]

How big a field do you think computer games are, compared to all the other research that is ongoing?

I already wrote about that couple of times. And what do you think, that "huge" size is a measure of quality or the measure of lack of the same?

Didn't think you understood the "impact". No surprise there...

"Impact" is the measure of quality, whether you like it or not...

[bob]

How big a field do you think computer games are, compared to all the other research that is ongoing?

I already wrote about that couple of times. And what do you think, that "huge" size is a measure of quality or the measure of lack of the same?

Didn't think you understood the "impact". No surprise there...

"Impact" is the measure of quality, whether you like it or not...

No, it is the measure of "frequency of citation."

[bob]

Please cite _any_ source that claims that somehow, magically, LMR invalidates the concept of diminishing returns. Of course you can't, because there isn't one.

Ofc I can't since the most recent paper on it still uses that data from Crafty 19.6, how ridiculous is that???
Diminishing return is not about how often I change best move at different depth. It is about if I speed up my processor from 1x to 2x and get 50 elo increase will I also get 50 elo increase if I speed it up from 512x to 1024x.
The simple answer is without LMR no, with LMR (more aggressive Null Move Pruning and other stuff from 2005 onwards) most probably yes.

I don't know where you get this crap, but the simple answer is NO in _both_ cases. LMR doesn't suddenly allow us to escape diminishing returns, or go faster than the speed of light, or anything else.

The simplest refutation of your nonsense is "what happens when the hardware is fast enough to search to a forced mate from the initial position?" What will _another_ ply get you then?

think about it, rather than writing about it, until in sinks in...

[bob]

And on topic, Houdini 1.5 parallelization _practically_ works better than Crafty's

Data?

Don't have right now, but I did the following:
NPS and time to depth are useless.

In other words, you have no data. Time to depth is the _only_ way to measure SMP performance. and I do mean the _ONLY_ way.

A little silly from you. You must know that the ELO gain and time to solution are MUCH more reliable. Depth "8 core" is not the same as Depth "1 core" (maybe in Crafty it's the same, that would be pretty unusual).

Kai

You do realize that for _most_ positions, time to depth and time to solution are _identical_? Only those odd positions where a program changes its mind due to pure non-determinism will be different. Choose enough positions and those won't be a problem. If there is a clear best move, a program should find that move at the same depth, same PV, same score, most of the time. Hence a lot of runs to wash out the sampling error.

What I started doing recently, and I'm not claiming it is sound yet but it looks promising, is measuring score difference with as oracle an insanely long search of say 60 minutes.

I take this oracle reference and then measure the difference with, say, a 3 minute search on 1 core. I square these errors, average them and square root at the end. That is the 'performance indicator for the 3 minute single core search. Closer to 0 is better.

I compare that then with what 30 second searches on a 6-core give. This would be a larger number because a single thread search is more effective. But at some longer interval, say 60 seconds, the indicators are the same. Then I say that I have a 'speedup equivalent' of 3.0 on 6 cores.

The idea is that I get more than 1 bit of information out of every position search, and thus need fewer positions to get a good indicator. The downside is the need for long oracle searches. I had a few computers calculate those while I was traveling for a few weeks.

What about the positions where there is really a "right" score and everything else is wrong? Mate-in-N as one example. But any position where you can win material, or win a positional concession, or whatever. I am not so interested in the variance of the score, because one can produce enough of that by just playing the same game N times, ponder=on, and just taking a different amount of time before entering each move.

The only goal of SMP is to search faster. You can use time to complete a specific depth, or time to find the best move, but you do need a "time" measurement since the SMP performance metric is "speedup". Defined as

speedup = 1-cpu-time / N-cpu-time.

Normally N-cpu-time is smaller so the speedup is a number > 1.0, hopefully.

I have selected the test positions to have no scores outside abs(score)>2.5 I don't care too much what the engine does outside that range.

It is not just for SMP testing, that is a special case. I judge any search change with it at the moment.

To do a full validation of the method takes me some more time, but I'm setting it up, hopefully some data by this summer. A similar method works for me for judging evaluation changes, but that is a simpler problem.

I don't use positions for anything other than very quick evaluation of a search change, or for measuring changes to the SMP code. Everything else I do is game-based. The problem with Elo and SMP is this.

Program A gains +50 Elo from using 4 cpus.
Program B gains +70 Elo from using 4 cpus.

Which one has the better SMP algorithm?

You can't answer that. A may search much deeper than B, and we know for certain that adding a ply has a diminishing return on elo gain. If B is much slower than A, then B might have a _worse_ SMP algorithm, but the speed gain helps B more than A.

That's the problem with using Elo, until you have a direct Elo to speed gain for each program. And once you have that, you don't need the Elo stuff.... Not to compare SMP effectiveness.

Elo is a measure for the entire program not only for SMP. SMP mean nothing if the branching factor is for example 6. You can add 3 more processors without any benefit.

Sorry, but that is simply wrong. A program with a branching factor of 6 gets nothing from a CPU twice as fast? Absolutely false. Backed up by years and years of data...

I'm not an expert for sure, but this was said by Ed Schroeder:

"Mind you, if you are able to produce a chess program with an effective branch-factor of 2.0 then every doubling in processor speed will give you an extra iteration, in most cases good for an increase of +30-50 elo points in the computer-computer competition."

So, on the basis of the statements above, doubling the speed is not enough to get an extra iteration with high EBF.

Think about what you are saying for a minute. Say your EBF is 2.0. And your new hardware only goes 1.9x faster. You get _nothing_??? You don't think you might get an extra ply on one move, not on the next, then again on the next? And that doesn't help? If I go 1.999999999x faster, I get nothing? The only improvement occurs when my speedup _exactly_ matches the EBF?

that is an argument that is flawed in so many ways I don't know where to start. I'd hope it is simply obvious...

[Milos]

The simplest refutation of your nonsense is "what happens when the hardware is fast enough to search to a forced mate from the initial position?" What will _another_ ply get you then?

Nope, your refutation is wrong as usual. You don't know the rating of "perfect play"=forced mate from the initial position (if there is a forced mate, high probability is that chess is a draw game from the initial position).
Because chess is a finite game, final rating (which is of course just relative to your starting rating) must also be finite so when you reach it you reach a discontinuity point. There is absolutely no reason why elo vs. speed curve must have a derivative in that point.

[Evert]

Diminishing return is not about how often I change best move at different depth.

How can it not be?
Searching to greater depth can only ever be an elo boost if it means that every once in a while it causes you to change your mind. If there is any diminishing return from greater search depth, then it has to be that you're less likely to change the root move.
Even if there's no immediate causal relationship, then one must surely be a proxy for the other, right? Or am I missing something?

The simple answer is without LMR no, with LMR (more aggressive Null Move Pruning and other stuff from 2005 onwards) most probably yes.

Why would that be the case?
Not saying it's right or wrong, I don't know, but I don't understand why that would be true.