| |
Main
Date: 20 Jul 2007 05:40:50
From: Beliavsky
Subject: strength of chess computer programs vs. time
|
Deep Fritz defeated Kramnik in a match by 4-2 and plays at least at a
2800 level at classical time controls. Can someone estimate how much
stronger it would be if it had much more thinking time, say 1 day per
move?
I think it would be interesting to have a correspondence computer-
assisted match between two top players. That ought to produce the
highest quality of play.
|
|
| |
Date: 24 Jul 2007 16:11:17
From: Neo
Subject: Re: strength of chess computer programs vs. time
|
On Jul 21, 12:41 pm, David Richerby <[email protected] >
wrote:
> Neo <[email protected]> wrote:
> > 4-2 and DF10 won that is 2/3 (66%) winning. If we run the logic
> > backwards which doesn't really apply like this after the fact. In
> > other words predicting chances of winning with the winning/losing
> > numbers is not what you want. You first say 66% chance of winning
> > and see if it matches. Also there is info missing. It could be a
> > little less than 66% to 75%(+a little more).
>
> I'm sorry but I really have no idea what you're talking about. I
> don't think it's a language thing: your sentences make sense
> individually but they don't come together in any coherent way.
Sorry Dave. The answer is quite long so I tried to shorten it giving
the most significant info. My response was in terms of the question
and I thought the person asking had already the necessary background.
Therefore I could skip over the boring part which I understood we all
knew.
I was responding to how much stronger would a computer become after
thinking for 1 day.
What I was saying was if one works out the math to estimate a computer
chess strength. Given: 4-2 win for DF10, one may be wanting to take
the math and run it backwards to figure out the elo. I am saying you
get many answers to give the same 4-2 results. Therefore the strength
of a computer will give you a statistical range not a singleton.
So taking a single game of 4-2 DF10 winning, we cannot find a single
value for our starting point. If Kramnik is 2800, and the computer
wins 4-2. We find a range of elos. I was giving a high-low range.
So if that is the best the computer does to win 4-2 against a player
with 2800.
Now the question was how strong would it be if it thought for 1 day.
To know this we need a starting elo which is what I was trying to
explain and give some basic idea. That idea was a range of elos. So
I picked a conversative number. Again I was just trying to explain
it is a little involved or complex.
So to simplify there is a linear relationship. I understand some do
not think so. However the case in reality is a non-linear curve.
However we can gather lots of data and find that the exponent change
is linear... not really but there are a collection of points that
gather along a line. Any curve or random data points can be expressed
as a line. The best line that fits. Basic stat math.
As far as I know... There is a linear relationship which has not
changed when you look over lots of programs. Up til today it is
valid. What we find is 1 move deeper yields 100 elo points. That is
an estimate. That estimate does not tell you much about a specific
computer program. That part is important to understand which is what
I tried to convey.
However statistically as we go a move deeper the exponential growth in
nodes to search increases greatly. The elo increases by 100 per move
deep.
Therefore we can estimate how strong a computer would be if it thought
for 1 day. Some believe it'd not change much or by about 100. That I
do not believe to be true for programs in general. It must be much
more because the program is thinking much deeper in 1 day vs 3
mins(tournament play.. mins per move on average... understand it's not
exact but it's an estimate to begin with to make math simpler...at
least for me:)
Sorry Dave for the confusion. I hope I was clearer. If not, I am
happy to discuss more.
>
> Dave.
>
> --
> David Richerby Hungry Erotic Puzzle (TM): it's likewww.chiark.greenend.org.uk/~davidr/ an intriguing conundrum but it's
> genuinely erotic and it'll eat you!
|
| |
Date: 20 Jul 2007 14:37:31
From: Hello
Subject: Re: strength of chess computer programs vs. time
|
"Beliavsky" <[email protected] > wrote in message
news:[email protected]...
> Deep Fritz defeated Kramnik in a match by 4-2 and plays at least at a
> 2800 level at classical time controls. Can someone estimate how much
> stronger it would be if it had much more thinking time, say 1 day per
> move?
There wont be much increase. Not like what you'd want.
Do a google search for: computer chess "technology curve"
In the old days (70's & 80's) an increase in search depth (by extra time,
faster system, whatever) mean a straight increase in play strength. Linear
growth.
Roughly 100 elo for every extra ply.
However, that quickly changed. By the late 80s onward, it was fairly
obvious it was a curve and not linear.
The more powerful the computers got, and the better the programs, the slower
the strength improvements came.
There was a 'deminishing returns' to the growth of the machine power /
search time.
It didn't really flatten out, but it definetly went from a straight line
(linear) to a much more of a curve with progressively slower growth.
Probably one of the better papers on this in the early days is Szabo &
Szabo: "The Technology Curve Revisited" in ICJA v11#1 (ch 1988). Later
tests were done, of course, but this is probably one of the first better
ones to show a curve instead of a linear growth.
Not everybody can agree on the exact shape of the curve, but these days,
nobody in their right mind would expect a linear or even near linear growth.
There has been way too much research showing diminishing returns.
So, to answer your question....
Since the program is strong on its own, and assuming the system it runs on
is powerful, that gets us firmly away from the linear growth and into the
curve.
I would guess probably 100-150 elo, but that's a guess that I have no data
to actually back it up with. Realistically you'd have to try it and find
out. And you'd have to turn off "thinking on oppoent's time". And play
hundreds of games. Considering the time limits, that's not practical unless
you have a few hundred spare identical systems and are willing to wait half
a year for the results.
(And no, you can't reduce the time limits to get approximate results. 3
minutes to 24 hours is 480x. You can't go 1 second and 480 seconds. That
would put the weaker program into a much different part of the curve and it
wouldn't be able to play like it has been tuned to play.)
(Also note that parallel chess programs follow a similar growth. The first
few processors help a lot and as you add more, they help less and less.
Modern search algorithms are better than they used to be, but using 64
processors instead of 8 is not going to make the program vastly stronger.)
----== Posted via Newsfeeds.Com - Unlimited-Unrestricted-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----
|
| | |
Date: 20 Jul 2007 20:56:02
From: Guy Macon
Subject: Re: strength of chess computer programs vs. time
|
Hello wrote:
>In the old days (70's & 80's) an increase in search depth (by extra time,
>faster system, whatever) mean a straight increase in play strength. Linear
>growth.
>
>Roughly 100 elo for every extra ply.
>
>However, that quickly changed. By the late 80s onward, it was fairly
>obvious it was a curve and not linear.
>
>The more powerful the computers got, and the better the programs, the slower
>the strength improvements came.
>
>There was a 'deminishing returns' to the growth of the machine power /
>search time.
>
>It didn't really flatten out, but it definetly went from a straight line
>(linear) to a much more of a curve with progressively slower growth.
That makes sense. How often does a computer end up in a position
where the position is even after 20 plies but won after 30 plies?
How often is it even after 30 plies but won after 40?
--
Guy Macon
<http://www.guymacon.com/ >
|
| |
Date: 20 Jul 2007 18:39:05
From: Neo
Subject: Re: strength of chess computer programs vs. time
|
On Jul 20, 8:40 am, Beliavsky <[email protected] > wrote:
> Deep Fritz defeated Kramnik in a match by 4-2 and plays at least at a
> 2800 level at classical time controls.
Well as memory serves.. could be wrong but I think it's in this
ballpark. 4-2 and DF10 won that is 2/3 (66%) winning. If we run the
logic backwards which doesn't really apply like this after the fact.
In other words predicting chances of winning with the winning/losing
numbers is not what you want. You first say 66% chance of winning and
see if it matches. Also there is info missing. It could be a little
less than 66% to 75%(+a little more). Chances of winning based on
this one match gives you an idea. Do this with many games for a more
reliable number of % winning.
Also more games than 6 helps much more
So DF10 is about an 100elo(66%) to 200(75%) higher than Kramnik based
on this one tournament with a low number of sample sets of 6 games.
>Can someone estimate how much
> stronger it would be if it had much more thinking time, say 1 day per
> move?
1 day(1440 mins = 1day) per move in theory would give the computer:
Let's say an average game is average 3 mins per move. If we triple
that number(a bit more than 3x but it's close enough for this
example). 3 comes from the alpha-beta pruning. It'll take time to
explain, please post if anyone is curious). 3x longer gets you approx
1 move deeper. 1 move deeper is approx 100elo.
mins +elo
3 0 (add 0 to the original elo ranking of the computer---ex:
2800)
9 100
27 200
81 300
243 400
729(1/2day) 500
2187(1.5day) 600
This linear relationship shows up with many chess computers of varying
types. It's fairly close but I don't know if anyone has done this for
a single computer algorithm. It may vary but statistically when
averaging pcs this is what we get.
So about 550 elo point more. If we started with 2800 + 550 then one
day in theory 3350.
How ever I've seen with my chess engine that I've been working on
follows a different relationship over very long periods. If I let it
think 1 day per move sometime it needs to think 5 days longer to find
a better move(at least one that it thinks). So there is sorta a wall
that appears that you really need something faster or diff algorithm.
You may have a lot of hash cache etc but searching through memory etc
can wind up taking too much time and when trying to add so much memory
and enhance HW things that were insignificant for speed when computing
a total of a billion moves in a few mins really hits another issue
when thinking for very long periods. So those insignificant HW issues
previously worked very well and fast become a factor to slow things
down. As time goes up other factors become more apparent. So for
smaller increases in time, I think it's more significant but over days
I don't think it necessarily will help unless it's planned.
Either way this is the theory as I recall. There might be some errors
but the general principle is there.
>
> I think it would be interesting to have a correspondence computer-
> assisted match between two top players. That ought to produce the
> highest quality of play.
|
| | |
Date: 21 Jul 2007 17:41:00
From: David Richerby
Subject: Re: strength of chess computer programs vs. time
|
Neo <[email protected] > wrote:
> 4-2 and DF10 won that is 2/3 (66%) winning. If we run the logic
> backwards which doesn't really apply like this after the fact. In
> other words predicting chances of winning with the winning/losing
> numbers is not what you want. You first say 66% chance of winning
> and see if it matches. Also there is info missing. It could be a
> little less than 66% to 75%(+a little more).
I'm sorry but I really have no idea what you're talking about. I
don't think it's a language thing: your sentences make sense
individually but they don't come together in any coherent way.
Dave.
--
David Richerby Hungry Erotic Puzzle (TM): it's like
www.chiark.greenend.org.uk/~davidr/ an intriguing conundrum but it's
genuinely erotic and it'll eat you!
|
|
