| |
Main
Date: 10 Jan 2007 19:57:24
From: Thomas T. Veldhouse
Subject: 64-bit chess engines
|
So, I see that Deep Shredder 9 and 10 are available as 64-bit UCI engines [and
chessbase may be packaging a 64-bit version in Chessbase protocol as well].
Has anybody tried these and has there been any notable performance [i.e. ELO]
increase?
Thanks in advance.
--
Thomas T. Veldhouse
Key Fingerprint: D281 77A5 63EE 82C5 5E68 00E4 7868 0ADC 4EFB 39F0
|
|
| |
One possible way to improve chess engine performance is to shape the
search tree in a probabilistic way, using statistical information from
a large database of games between strong players and/or strong engines
(I think Rybka does something like this). For example one could have a
table lookup of all possible knight moves (like Na1-b3, Na1-c2,
Nb1-a3,Nb1-c3,Nb1-d2 ...) with a probability weight assigned to each
such move depending on how frequently it occured in the database. Say
if the choice is between Nb1-a3, Nb1-c3, Nb1-d2 for example, and you
see Nb1-c3 occurs 60% of the time when a knight on b1 moves, Nb1-d2
occurs 30%, and Nb1-a3 occurs 10%, you look first at Nb1-c3, then at
Nb1-d2, last at Nb1-a3 (this is just a trivial example to try to
illustrate the point). So you might look deeper in the search tree at
lines starting with Nb1-c3 than with Nb1-d2, and deeper at lines
starting with Nb1-d2 than Nb1-a3. But it is still an exhaustive search,
however it is more of a depth first search algorithm looking at the
lines most likely to be best (based on database statistics) then a
breadth first search algorithm.
Then you can look at other factors which occur frequently in the
database. Say an enemy pawn is covering the square the knight might
move to. That factor (pawn covering the square, or lower valued piece
covering a square a higher valued piece might move to, to generalize)
might then modify the weight that is assigned to a possible move.
So all moves end up with a statistical weight based on frequently
occuring situations identified in the database. That orders your move
search so that the most likely moves are looked at first, and the
search goes deeper in those lines, but it is still an exhaustive
search, since given enough time even the least likely lines will be
looked at. So you don't miss anything if the engine runs long enough,
but computing resources are used more efficiently since the most likely
moves are looked at more deeply.
That is kind of the middle-game analogue of an opening book, you don't
get information as specific as with an opening book, but you squeeze
the database as hard as you can for statistical information about
various frequently occuring scenarios, to speed up the search in the
most likely lines.
For the endgame, one could kind of do the reverse, start with the
Nalimov tablebases and try to see if there are frequently occuring
scenarios that might generalize to endgames with more than 6 pieces,
and try to make an endgame database that would assign probabilities to
various possible moves.
One might end up with several statistical databases, one for positions
with queens on the board, one with positions with queens off but rooks
still on, one for positions with minor pieces only. You just look for
situations that occur the most frequently so you can do a table lookup
for ordering the moves to be looked at first, and thus speed up the
search in the most important lines.
|
| |
Date:
From: Martin Brown
Subject: Re: 64-bit chess engines
|
|
| |
Date: 11 Jan 2007 20:18:10
From: Ruud
Subject: Re: 64-bit chess engines
|
"Thomas T. Veldhouse" <[email protected] > schreef in bericht
news:[email protected]...
> So, I see that Deep Shredder 9 and 10 are available as 64-bit UCI engines
> [and
> chessbase may be packaging a 64-bit version in Chessbase protocol as
> well].
> Has anybody tried these and has there been any notable performance [i.e.
> ELO]
> increase?
>
> Thanks in advance.
Chessbase has not yet released a 64-bit version of any of their engines,
Fritz and Junior.
Engines like HIARCS and Shredder also released a seperate, 64-bit version.
Several of the keted engines have 64-bit versions, and also run on
Chessbase software.
For instance, Rybka gets about 50 to 60 % increase in search-power with the
64-bit version.
In engine-games of 10 minutes or so, this means that an increase of
searchdepth of maybe 2 or 3 ply, a total of 12 ply -- > 14 ply, in a regular
middlegame.
This is not the same 60% increase, logically, because of search-trees/
increasing deviations.
In ELO, this meant an increase of about 30 to 50 points.
|
| |
Date: 11 Jan 2007 10:51:02
From: Johnny T
Subject: Re: 64-bit chess engines
|
Thomas T. Veldhouse wrote:
> So, I see that Deep Shredder 9 and 10 are available as 64-bit UCI engines [and
> chessbase may be packaging a 64-bit version in Chessbase protocol as well].
> Has anybody tried these and has there been any notable performance [i.e. ELO]
> increase?
>
> Thanks in advance.
>
64 bittedness isn't anything special in and of itself. But in
combination with the right amount of cache and enough stacks, then you
should be able to get a significant search boost at a given processor
speed.
You may also need to write some custom in-line assembler because the
current compilers may not be "chessie" enough to take advantage.
But ultimately, something like Shredder may not take the full advantage.
We may very well be in the middle of the "last ply" problem. In that
there are no real improvements available (either in hardware or
software) to the top programs to generate enough searches to get to
another ply (hydra and deep blue as exceptions). But that there is a
lot of headroom that can be utilized for ster searches (which is
where Rybka seems to be excelling).
So, I think there is a new race underway. It used to be he who thought
deepest beat he who thought best. But now that everyone is the same
depth, and you just can't see deeper, it will again become a contest of
he who thinks best. It's a fun time for engine to engine matches.
|
| | |
Date: 11 Jan 2007 20:55:58
From: Thomas T. Veldhouse
Subject: Re: 64-bit chess engines
|
Johnny T <[email protected] > wrote:
> 64 bittedness isn't anything special in and of itself. But in
> combination with the right amount of cache and enough stacks, then you
> should be able to get a significant search boost at a given processor
> speed.
>
So, doesn't bitboard manipulation significantly faster on 64-bit processors
due to the fact that a bitboard is a 64-bit word? Certainly that should
increase performance by a factor of two for such manipulations.
> You may also need to write some custom in-line assembler because the
> current compilers may not be "chessie" enough to take advantage.
>
> But ultimately, something like Shredder may not take the full advantage.
> We may very well be in the middle of the "last ply" problem. In that
> there are no real improvements available (either in hardware or
> software) to the top programs to generate enough searches to get to
> another ply (hydra and deep blue as exceptions). But that there is a
> lot of headroom that can be utilized for ster searches (which is
> where Rybka seems to be excelling).
>
> So, I think there is a new race underway. It used to be he who thought
> deepest beat he who thought best. But now that everyone is the same
> depth, and you just can't see deeper, it will again become a contest of
> he who thinks best. It's a fun time for engine to engine matches.
So do you have experience with the 64-bit engines available to indicate
whether they perform better? Or not?
--
Thomas T. Veldhouse
Key Fingerprint: D281 77A5 63EE 82C5 5E68 00E4 7868 0ADC 4EFB 39F0
|
| | | |
Date: 11 Jan 2007 15:22:48
From: Johnny T
Subject: Re: 64-bit chess engines
|
Thomas T. Veldhouse wrote:
>
> So, doesn't bitboard manipulation significantly faster on 64-bit processors
> due to the fact that a bitboard is a 64-bit word? Certainly that should
> increase performance by a factor of two for such manipulations.
Often, no, because the compilers don't do anything special enough for
you here. It is more a question of cache size, speed to the stacks,
qty of stacks, and of course speed of the processor.
Yes, given a good "chessie" architecture you may see a speed advantage,
but we are WAY less than 2x away from the next ply. So 2x gives you,
essentially, nothing. It can improve speed chess, but essentially you
are just lowering and lowering the amount of time that it takes to get
to xply.
Unfortunately it is not going to improve the quality of either normal
controls, or overnight analysis. Because you are still too far away
that 2x isn't going to make such a difference. Nor 4x, like with the
transmeta processors. And other unix processors.
Hydra and deep blue work/worked well because they were 2+ MAGNITUDES
deeper, not 2x deeper. And today computers and engines are essentially
all at the same level, about 8 moves, 16 ply (i think those are the
right numbers, we may actually be slightly deeper than that, but it
doesn't matter, because the limit is there whatever the actual number
is). That works out to about world class good move level, and no real
"mistakes". And every ply added more points and deeper (faster) was
better than ster. But each ply is EXPONENTIALLY farther away.
Computers are not getting exponentially faster anytime soon, and for
awhile there was bunches and bucket loads of programming cleverness that
wrung every cycle of the processor in the quest for deepness. This was
hugely important while computers were slow, and it is the current state
of the art.
These discoveries defined chess engines for awhile. And ELO was to be
gained by furthering the horizon. More so than being st. As a
matter of fact if st dropped you a ply, you would lose more ELO than
you would gain. It may not have had to been that way, but programmers
were probably better programmers than chess players, and could provide
better code than sts.
And then the stagnation started. About fritz 9. Computers engines
are world class. Faster processors have help make all the engines as
good as they can be. There aren't any more tricks to get to that next
horizon level. It may take 10 years to get there, but it looks like
moore's law is actually maxing out as well.
But, we are starting to gain headroom towards that next ply. And it is
further to the next ply than all the previous plys before it PUT
TOGETHER. There is a lot of headroom available and it is growing.
Then comes along a really good engine that leaves it's source code to be
found (better than crafty), I think it was fruit, but I don't remember
now. But it screamed. Commercial quality screaming. This let a
programmer, who had not dedicated his life to the tricks, but who is
ALSO an extremely good chess player, to add chess knowledge. And it
works, sts adds ELO, lots of ELO. It hadn't worked for years, but it
really works now, because of the rest of the environment falling into place.
And now, there is a new target to program against. Something beyond
Kasparov and Kramnik. Sort of world class plus. And that is Rybka. It
is just first, I have no doubt he will not be last, nor do I think it
will necessarily win this next race. But it has helped define it. I
think that there are a lot of sts that there is going to be room for
in the new computers. And it will be the quality of those sts, that
go from world-class no mistakes, to world-class plus chess players.
> So do you have experience with the 64-bit engines available to indicate
> whether they perform better? Or not?
Yes, when the 64 bit architectures, and the Transmeta long word
processors came about I worked with some friends of mine modeling how a
chess program may improve in these. And we came to all of the above
conclusions, way prior to Rybka. I was not privileged to all of the
chess base knowledge to even come close to overcoming their advantages
in programming, and it was clear that the merely long words was going to
be enough to just get 2x programming speed (for a variety of reasons),
or that even given all the tricks, and 2x improvement, that at the end
of the day it would matter.
It was fun to model, but at the end of the day, not worth doing. We had
neither the deep programming experience, or the deep chess experience to
do provide anything useful here. But it doesn't mean, that I don't
understand the space. I do. Very well.
|
| | | | |
Date: 18 Jan 2007 14:41:21
From: David Richerby
Subject: Re: 64-bit chess engines
|
Johnny T <[email protected] > wrote:
> Thomas T. Veldhouse wrote:
>> So, doesn't bitboard manipulation significantly faster on 64-bit
>> processors due to the fact that a bitboard is a 64-bit word?
>> Certainly that should increase performance by a factor of two for
>> such manipulations.
>
> Often, no, because the compilers don't do anything special enough for
> you here.
Um. All the compiler needs to do is to compile a 64-bit operation as
a single operation on two 64-bit registers, rather than as two
operations on two 32-bit registers. Now, on a super-scalar processor,
that might not be much faster because a good compiler (and, even
without a good compiler, a good instruction scheduler in the CPU)
would probably do the two 32-bit ops in parallel.
> It is more a question of cache size, speed to the stacks, qty of
> stacks, and of course speed of the processor.
Cache is almost irrelevant to chess programs because they hit almost
all the memory in an essentially random pattern. Processors don't
have `stacks'. (Well, some SPARC processors had context stacks but
they're horrible and only used internally.)
> Yes, given a good "chessie" architecture you may see a speed
> advantage, but we are WAY less than 2x away from the next ply. So 2x
> gives you, essentially, nothing. It can improve speed chess, but
> essentially you are just lowering and lowering the amount of time
> that it takes to get to xply.
2x does not give you `essentially nothing'. Doubling the speed of
your program lets you do the same analysis in half the time it used to
take. Yes, that won't get you a whole extra ply but it still lets you
see more.
> Unfortunately it is not going to improve the quality of either
> normal controls, or overnight analysis. Because you are still too
> far away that 2x isn't going to make such a difference. Nor 4x,
> like with the transmeta processors. And other unix processors.
Unix is an operating system. ``Unix processors'' makes no more sense
than ``Windows processors.''
> It was fun to model, but at the end of the day, not worth doing. We
> had neither the deep programming experience, or the deep chess
> experience to do provide anything useful here. But it doesn't mean,
> that I don't understand the space. I do. Very well.
No disrespect, but various things you've said imply to me that you
don't really understand this at all.
Dave.
--
David Richerby Disposable Pickled Chainsaw (TM):
www.chiark.greenend.org.uk/~davidr/ it's like a lethal weapon but it's
preserved in vinegar and you never
have to clean it!
|
| | | | |
Date: 12 Jan 2007 15:22:46
From: Dr A. N. Walker
Subject: Re: 64-bit chess engines
|
In article <[email protected] >,
Johnny T <[email protected] > wrote:
>Yes, given a good "chessie" architecture you may see a speed advantage,
>but we are WAY less than 2x away from the next ply. So 2x gives you,
>essentially, nothing. [...]
Can you explain what you actually meant here, please? Your
*particular* program may just have crept over [eg] a 16-ply boundary
for a *particular* position on a *particular* computer; *mine* may
be just below or well above, depending on the computer [inc, eg, the
available hash storage, as well as the CPU speed/type and cache], on
the program [which may have different pruning strategies as well as
more or fewer "sts"], even for the same position. And your program
and computer combination will surely see further in simple or forcing
positions than in complex or subtle positions. So a factor 2x in speed
may not get you to the next ply *uniformly*, but it could mean that
instead of [eg] 40% 15-ply, 50% 16-ply, 10% 17-ply, you see 10% 15-ply,
50% 16-ply and 40% 17-ply. That would be an extra ply in 60% of the
positions your program meets.
How much that buys you in Elo points is another matter.
--
Andy Walker, School of MathSci., Univ. of Nott'm, UK.
[email protected]
|
| | | | | |
Date: 12 Jan 2007 12:44:13
From: Johnny T
Subject: Re: 64-bit chess engines
|
It is just not as close as you think.
A quick review. Imagine a given chess engine and it runs on a 1 Mhz
machine, a commodore 64 for instance. If you played lets say 1000
games on it you would find that the computers move choice would both
change at predictable intervals, and that the quality of the move,
measured against human opponents, would get better over time.
Those predictable points are the ply levels. At every ply the horizon
for the computer goes farther and farther out, and as it goes farther
out the quality of the move improves, merely by eliminating mistakes.
----
As an aside in the very beginning, it was an open issue whether better
moves would lead to a stronger program, than one that made fewer
mistakes. Chess was largely found to be a game of mistakes (as many
are). And it was easier for computer programmers to make less mistakes
than better chess moves.
----
That was fine, but each ply was exponentially further away. And so the
problem is ultimately not solvable in this direction. But the world
wanted to see what would happen.
Well, 2 things happened, we created very clever representations and
implementations of the game that dramatically sped up its processing,
(by orders of magnitudes), and moores law increased the power of our
machines by 3 orders of magnitude, from 1mhz to 1000mhz.
But just as we think that most if not all magnitude class programming
optimizations have been discovered and implements, it is just a lot less
likely to get out to 10000mhz on a given machine, much less 1000000mhz.
And just as it is starting to slow down, since ply is exponential, a
single magnitude improvement from here, may not include a single ply in
depth. Which means even if my computer is 10 times better, at normal
time controls, the chess gets no better at all.
But in the beginning. Performance was everything. Getting the
additional ply was possible. And those fewer mistakes meant my computer
was getting stronger, the analysis was better, and we were passing IM's
and then GM's and then the super gm's and finally world championship
caliber, over a match.
And then....
We had achieved the last ply and we look out, and the gulf between here
and the next one, is beyond nearly everytrick in the book. (except
customized massively parallel hardware, hydra and deep blue). And even
then our current laptops, just a little ster than the hydra or deep
blue in it's understanding, and only 1 ply less deep, maybe... Still
world class.
Here we sit. Nowhere to go predictably but sideways. Will the programs
change much? Will the be objectively better? Does it matter? THESE
ARE IMPORTANT QUESTIONS, and really, very st, very clever people have
been thinking about this for a very long time, and if 64 bit was the end
all be all, or if it really mattered at all, we would have already been
there. The fact is, it doesn't get us ANYWHERE near close enough to
the next ply to even matter. As a matter of fact, there is good reason
to believe it provides nearly nothing. Since deeper doesn't matter, and
we have passed that threshold a while ago. And what use to take a full
machine to be world class, now takes a half a machine. And it doesn't
matter, the second half doesn't change the answer of the first half.
So, what happens now. Well what happened is fritz 10, and Rybka. And
Rybka is probably the most important. A young good programmer, and a
young very good chess player got a hold of modern chess code. (not
crafty, but fruit?!?). And he got to mold it with his more profound
chess knowledge. This meant that instead of just making the least
mistakes at a given ply, his program could make MUCH better positive
contributions to each move. And the reason this was even possible was
due to the large amount of excess computing power available between this
ply and the next ply. And that this combination, between world class
depth, and world class depth+1, with ever more powerful chess knowledge,
means that at this point we have a much different way to program that
computer, and play the game. And at this point computers will
dramatically impact how the game is played.
So, in sum. No, we are not anywhere close enough to the next ply that
64 bit or long addressing matters with current engines.
But, newer engines that utilize the overhead for sts instead of
depth. Twice as much room, may be still quite useful. We are in the
adolescent stage of this type of optimization. (We had thought we had
been here before, in the Rebel and early Hiarcs days, but a few
breakthroughs later we won a couple more ply and the "st" programs
were being beat. And we also learned/believed that the sts were
only worth xply.) There were other interesting political issues.
Breakthroughs were no longer being shared. It was assumed that the
st programs would get faster at the same rate as everyone else
because the techniques would be revealed. But many or the chess
optimization techniques became VERY proprietary and secret. The release
of fruit?! was a dramatic change to that. There is more to this story I
believe than has been fully told. But these politics help lead to the
stagnation.
But we now have different kinds of sts. Much more complicated, more
profound in affect. And... A new race. But the new race has just
started. 64 bit may be very useful to rybka (where it might have little
affect on say Junior). But expect to see an new escalation on chess
knowledge and engine to engine matches. It's exciting.
|
| | | | | | |
Date: 15 Jan 2007 17:59:59
From: Dr A. N. Walker
Subject: Re: 64-bit chess engines
|
In article <[email protected] >,
Johnny T <[email protected] > wrote:
>A quick review. Imagine a given chess engine and it runs on a 1 Mhz
>machine, a commodore 64 for instance. If you played lets say 1000
>games on it you would find that the computers move choice would both
>change at predictable intervals, and that the quality of the move,
>measured against human opponents, would get better over time.
??? Is this on the assumption that your machine is slowly
increasing in speed? Otherwise it's hard to make sense of what you
are saying. But it so, then ...
>Those predictable points are the ply levels. [...]
... you seem to have a wrong mental model of how all good
programs play. If you speed up your engine by a factor of 2, it
will, other things being equal, analyse twice as many nodes when
playing at a given rate. That won't give you an extra ply in all
positions; but it *will* give you an extra ply in those positions
where the decision not to analyse deeper was by a factor less than
two. [As a rough guide, that should be between 30% and 60% of
positions in the case of classical chess.]
>And just as it is starting to slow down, since ply is exponential, a
>single magnitude improvement from here, may not include a single ply in
>depth. Which means even if my computer is 10 times better, at normal
>time controls, the chess gets no better at all. [...]
If your computer is 10x better, then convention hath it that
you should get between 1.5 and 2 ply deeper. How much that pays off
in terms of "skill" is perhaps another matter. And you may well be
right that Moore's Law [which has been giving us exponential increases
in speed as well, so an extra ply every 3 years or so] is breaking down;
but the doomsters have been saying that for decades ....
>We had achieved the last ply and we look out, and the gulf between here
>and the next one, is beyond nearly everytrick in the book. [...]
Still just an extra factor of between three and five ....
>So, what happens now. Well what happened is fritz 10, and Rybka. And
>Rybka is probably the most important. A young good programmer, and a
>young very good chess player got a hold of modern chess code. (not
>crafty, but fruit?!?). And he got to mold it with his more profound
>chess knowledge. [...]
Well, that's a different matter. It has probably been true for
well over a decade that there was more to be gained from intelligent
static evaluation than from an extra ply or two. [And even more from
an intelligent notion of what it is that makes some moves irrelevant
and others vital, enabling more reliable pruning.]
--
Andy Walker, School of MathSci., Univ. of Nott'm, UK.
[email protected]
|
| | | | | | | |
Date: 15 Jan 2007 20:16:32
From: Johnny T
Subject: Re: 64-bit chess engines
|
Dr A. N. Walker wrote:
> In article <[email protected]>,
> Johnny T <[email protected]> wrote:
>> A quick review. Imagine a given chess engine and it runs on a 1 Mhz
>> machine, a commodore 64 for instance. If you played lets say 1000
>> games on it you would find that the computers move choice would both
>> change at predictable intervals, and that the quality of the move,
>> measured against human opponents, would get better over time.
>
> ??? Is this on the assumption that your machine is slowly
> increasing in speed? Otherwise it's hard to make sense of what you
> are saying. But it so, then ...
>
>> Those predictable points are the ply levels. [...]
>
> ... you seem to have a wrong mental model of how all good
> programs play. If you speed up your engine by a factor of 2, it
> will, other things being equal, analyse twice as many nodes when
> playing at a given rate. That won't give you an extra ply in all
> positions; but it *will* give you an extra ply in those positions
> where the decision not to analyse deeper was by a factor less than
> two. [As a rough guide, that should be between 30% and 60% of
> positions in the case of classical chess.]
Actually, I am quite sure that you have the wrong mental model. 2x will
not change the move in 50% of the cases, nor will 10x give your 1.5 to 2
ply. This is because the depth is exponential (let that word sink in
for a minute).
We are not getting there by hardware, and it is likely there are no new
huge programming breakthroughs on depth.
I will give you that on some really small number of cases that some
speed, today, may result in a change in moves. (It only matter's if the
move changes...). But that may result in 1 game change. That is going
to be difficult to see over variance. But I am not even going to give
you that soon.
It just takes too much to get to an answer that is different than the
current answer. The problem is just too deep. Beyond 1 magnitude away.
You are just wrong about that 10x and factor of 3-5. It is no longer
true. Because the depth problem is NOT linear. It is not even
geometric (as you imply), it is exponential. It is beyond our depth.
Fortunately (?) this also coincided with world class play. Even more
fortunately, was the Rybka development. This accident could have easily
not happened. They/he got depth for "free". And has been able to add
sts. Very interesting.
And skill, has been more about not making tactical errors. And gross
strategic errors. Which has depended on depth or ply to "see". Now we
are moving to a stronger player with equivelant depth.
> If your computer is 10x better, then convention hath it that
> you should get between 1.5 and 2 ply deeper. How much that pays off
> in terms of "skill" is perhaps another matter. And you may well be
> right that Moore's Law [which has been giving us exponential increases
> in speed as well, so an extra ply every 3 years or so] is breaking down;
> but the doomsters have been saying that for decades ....
>
>> We had achieved the last ply and we look out, and the gulf between here
>> and the next one, is beyond nearly everytrick in the book. [...]
>
> Still just an extra factor of between three and five ....
>
>> So, what happens now. Well what happened is fritz 10, and Rybka. And
>> Rybka is probably the most important. A young good programmer, and a
>> young very good chess player got a hold of modern chess code. (not
>> crafty, but fruit?!?). And he got to mold it with his more profound
>> chess knowledge. [...]
>
> Well, that's a different matter. It has probably been true for
> well over a decade that there was more to be gained from intelligent
> static evaluation than from an extra ply or two. [And even more from
> an intelligent notion of what it is that makes some moves irrelevant
> and others vital, enabling more reliable pruning.]
>
The decade may be right. I am sure that it is closer to 5 years. And
it is not about pruning (which has to do with depth), it has to do with
"quality" and move score which has more to do with move scoring... It
is not about finding better depth and better pruning, it is about
creating better tableaux.
Prior to this, having the deepest horizon that didn't result in tactical
failure was where all the strength was. It also terminated around world
class strength. This is fortunate only. And a bit odd. Checkers
achieved it way earlier, go may never achieve it. Chess is right on the
edge. And chess might get significantly better on the trip to the
last ply. And it will be really interesting if the last ply doesn't
result in different answers. Or at least not many.
|
| | | | | | | | |
Date: 16 Jan 2007 14:22:23
From: Dr A. N. Walker
Subject: Re: 64-bit chess engines
|
In article <[email protected] >,
Johnny T <[email protected] > wrote:
>> [...] If you speed up your engine by a factor of 2, it
>> will, other things being equal, analyse twice as many nodes when
>> playing at a given rate. That won't give you an extra ply in all
>> positions; but it *will* give you an extra ply in those positions
>> where the decision not to analyse deeper was by a factor less than
>> two. [As a rough guide, that should be between 30% and 60% of
>> positions in the case of classical chess.]
>Actually, I am quite sure that you have the wrong mental model. 2x will
>not change the move in 50% of the cases,
I didn't say "change the move"; but "give you an extra ply".
> nor will 10x give your 1.5 to 2
>ply. This is because the depth is exponential (let that word sink in
>for a minute).
I think you meant that the size of the tree grows exponentially
with depth. Sure. That means that, with a naive branching factor of
around 30 [for chess], and so an alpha-beta bf of around sqrt(30), an
extra ply needs around 5.5x as many nodes, or equivalently that a 5.5x
increase in speed gives you an extra ply in the same time. In practice,
we do better than that for various reasons.
>We are not getting there by hardware,
Perhaps. Tell us again in a decade.
> and it is likely there are no new
>huge programming breakthroughs on depth.
What matters is not "depth" but "relevant depth". Better pruning
can easily add a ply or two to the average, and more to the depth reached
in the most critical lines. Fritz [eg] commonly gets to depth 30 or 40
[reported as (eg) 14/33 if it reaches depth 33 while searching ply 14].
[...]
>You are just wrong about that 10x and factor of 3-5. It is no longer
>true. Because the depth problem is NOT linear. It is not even
>geometric (as you imply), it is exponential. [...]
Geometric growth *is* exponential: a^n = exp (n ln a).
--
Andy Walker, School of MathSci., Univ. of Nott'm, UK.
[email protected]
|
| | | | | | | | | |
Date: 16 Jan 2007 10:31:45
From: Johnny T
Subject: Re: 64-bit chess engines
|
Dr A. N. Walker wrote:
> In article <[email protected]>,
> Johnny T <[email protected]> wrote:
>>> [...] If you speed up your engine by a factor of 2, it
>>> will, other things being equal, analyse twice as many nodes when
>>> playing at a given rate. That won't give you an extra ply in all
>>> positions; but it *will* give you an extra ply in those positions
>>> where the decision not to analyse deeper was by a factor less than
>>> two. [As a rough guide, that should be between 30% and 60% of
>>> positions in the case of classical chess.]
>> Actually, I am quite sure that you have the wrong mental model. 2x will
>> not change the move in 50% of the cases,
>
> I didn't say "change the move"; but "give you an extra ply".
You do understand that unless you change the move, you are not any
stronger over time.
>
>> nor will 10x give your 1.5 to 2
>> ply. This is because the depth is exponential (let that word sink in
>> for a minute).
>
> I think you meant that the size of the tree grows exponentially
> with depth. Sure. That means that, with a naive branching factor of
> around 30 [for chess], and so an alpha-beta bf of around sqrt(30), an
> extra ply needs around 5.5x as many nodes, or equivalently that a 5.5x
> increase in speed gives you an extra ply in the same time. In practice,
> we do better than that for various reasons.
This is alot of faith that there are some magnitude quality adjustments
to be made to add to depth. I am of opposite faith, that we are
amazing, but there just isn't anything sitting out there. We have
expended the clever.
>> We are not getting there by hardware,
>
> Perhaps. Tell us again in a decade.
It is obvious. And has to do with physics. Even the Intel folks will
tell you about the moores laws problems.
>> and it is likely there are no new
>> huge programming breakthroughs on depth.
>
> What matters is not "depth" but "relevant depth". Better pruning
> can easily add a ply or two to the average, and more to the depth reached
> in the most critical lines. Fritz [eg] commonly gets to depth 30 or 40
> [reported as (eg) 14/33 if it reaches depth 33 while searching ply 14].
>
It did, but search extensions for tactical positions are already done.
By everyone. It is the next ply that makes a difference. Search
extensions are not done against strategic positions. You will note, that
even with extensions, that in some other positions, you will see
complete depth as well. This is because the engine has nothing to look
deeper at.
Depth extensions are not that hard, because the moves tend to be forced,
and it is a very very narrow tree.
It is just not true, if we improved the pruning we would get better
stronger results. It is about broad scoring differences in quiet
positions that is going to add the ELO. Now. Your view used to be
true. There were programs challenged to be discovered and implemented.
The hardware was expanding and getting significantly faster. There
was a world not too far away, approachable to be discovered. The
*next* step is WAY WAY further away than it has been.
You cannot map extensions to tree depth, they are not the same thing.
|
| | | | | | | | | | |
Date: 17 Jan 2007 14:34:37
From: Dr A. N. Walker
Subject: Re: 64-bit chess engines
|
In article <[email protected] >,
Johnny T <[email protected] > wrote:
>>> Actually, I am quite sure that you have the wrong mental model. 2x will
>>> not change the move in 50% of the cases,
>> I didn't say "change the move"; but "give you an extra ply".
>You do understand that unless you change the move, you are not any
>stronger over time.
Of course I understand that. But you don't need [or expect]
to change the move *every* time [not at depth 16, or 23, any more than
at depth 5]. A couple of times per game will suffice to give the
faster program the edge. And *you* have been telling us, both earlier
in this thread and in the article to which this is a response, that
"It is the next ply that makes a difference". The extent to which
this is true, and will remain true, is a matter for experiment rather
than bald assertion. [It's not hard to do most of the experiment, BTW
-- play at 40 moves per four hours instead of two hours, with one of
the engines running on an older, slower machine.]
>> I think you meant that the size of the tree grows exponentially
>> with depth. Sure. That means that, with a naive branching factor of
>> around 30 [for chess], and so an alpha-beta bf of around sqrt(30), an
>> extra ply needs around 5.5x as many nodes, or equivalently that a 5.5x
>> increase in speed gives you an extra ply in the same time. In practice,
>> we do better than that for various reasons.
>This is alot of faith that there are some magnitude quality adjustments
>to be made to add to depth.
No it isn't. As tin has pointed out, some programs already
seem to gain an extra ply per factor 2 in speed, thanks to aggressive
and intelligent pruning. The factor 5.5 above is *very* conservative,
and assumes no intelligence [not even transposition tables] in the
search, beyond basic alpha-beta. Any real program should do better.
>>> We are not getting there by hardware,
>> Perhaps. Tell us again in a decade.
>It is obvious. And has to do with physics. Even the Intel folks will
>tell you about the moores laws problems.
It has been "obvious" for several decades. When I started, it
was the problem of how to get cores down below 1mm or so .... Repeat,
tell us again in a decade. And bear in mind that the processing power
available to Fritz/Rybka on the PC on your desk is not just raw CPU
speed, but also numbers of processors, size of RAM, .... Some chess
engines will react better than others to such changes.
>> What matters is not "depth" but "relevant depth". Better pruning
>> can easily add a ply or two to the average, [...]
>It did, but search extensions for tactical positions are already done.
Yes, but not all that well. There is still plenty of scope for
small improvements [and a tiny improvement in efficiency makes a huge
difference out at depth 16+].
> By everyone. It is the next ply that makes a difference.
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
NB!
> Search
>extensions are not done against strategic positions. You will note, that
>even with extensions, that in some other positions, you will see
>complete depth as well. This is because the engine has nothing to look
>deeper at.
Then it needs better "irrelevance" pruning. You seem to be
assuming that all engines [other than Rybka ...] are identical. There
is much to be done before extra intelligence is the *only* way forward.
>It is just not true, if we improved the pruning we would get better
>stronger results.
That's a point of view, but it is at odds with your claim
that the "next ply" makes a difference.
> It is about broad scoring differences in quiet
>positions that is going to add the ELO. Now. Your view used to be
>true. [...]
I haven't given you "my view". I have simply pointed out to
you that the "next ply" is not interestingly further away today than
it was a decade ago. Hardware will continue to give domestic users
certainly, and supercomputer users very possibly, an extra ply every
few years for at least the next decade. So will modest improvements
in pruning techniques, transposition table techniques, and other stuff
currently being researched. What three or four more ply do for Elo
is another matter.
None of this is to deny that extra intelligence is interesting.
Most chess programmers, for as long as I have been in the field [over
30 years now], would dearly love their programs to understand chess a
lot better. If Rybka can finally show that brain can overcome brawn,
then many of us will cheer. But I doubt whether this has much, if
anything, to do with the fact that we are currently running our PCs
at 3GHz or so rather than 30MHz or 300GHz.
>You cannot map extensions to tree depth, they are not the same thing.
[Nor are tactical search extensions the only way to prune.]
--
Andy Walker, School of MathSci., Univ. of Nott'm, UK.
[email protected]
|
| | | | |
Date: 12 Jan 2007 13:59:43
From: Thomas T. Veldhouse
Subject: Re: 64-bit chess engines
|
Johnny T <[email protected] > wrote:
> Thomas T. Veldhouse wrote:
>
>>
>> So, doesn't bitboard manipulation significantly faster on 64-bit processors
>> due to the fact that a bitboard is a 64-bit word? Certainly that should
>> increase performance by a factor of two for such manipulations.
>
> Often, no, because the compilers don't do anything special enough for
> you here. It is more a question of cache size, speed to the stacks,
> qty of stacks, and of course speed of the processor.
>
It isn't the compiler [assuming it compiles 64-bit targets], it is the CPU.
Working with a 64-bit word on a 32-bit CPU requires to steps instead of one.
Any compiler that compiles 64-bit targets will do this correctly.
> Yes, given a good "chessie" architecture you may see a speed advantage,
> but we are WAY less than 2x away from the next ply. So 2x gives you,
> essentially, nothing. It can improve speed chess, but essentially you
> are just lowering and lowering the amount of time that it takes to get
> to xply.
>
I wasn't indicating a 2x performance overall, I was indicating a 2x
performance on bitboard manipulations. There is a LOT more involved in chess
programming than simple bitboard manipulations. What I want to know is how
the entire package performs; hence my question.
> Unfortunately it is not going to improve the quality of either normal
> controls, or overnight analysis. Because you are still too far away
> that 2x isn't going to make such a difference. Nor 4x, like with the
> transmeta processors. And other unix processors.
>
I have since done some reading and there is indication of increased
performance simply because the application can access more the 2G of RAM [my
box is 4G, so I am curious about testing this]. I think increasing the hash
table capability and faster bitboard processing ought to result in a
significant and measurable performance increase. I am hoping for a real-world
measurement of this.
> Hydra and deep blue work/worked well because they were 2+ MAGNITUDES
> deeper, not 2x deeper. And today computers and engines are essentially
> all at the same level, about 8 moves, 16 ply (i think those are the
> right numbers, we may actually be slightly deeper than that, but it
> doesn't matter, because the limit is there whatever the actual number
> is). That works out to about world class good move level, and no real
> "mistakes". And every ply added more points and deeper (faster) was
> better than ster. But each ply is EXPONENTIALLY farther away.
> Computers are not getting exponentially faster anytime soon, and for
> awhile there was bunches and bucket loads of programming cleverness that
> wrung every cycle of the processor in the quest for deepness. This was
> hugely important while computers were slow, and it is the current state
> of the art.
>
As I said, I didn't say anything at all about 2x deeper ... I didn't say
anything at all about ply. I said 2x increased performance in bitboard
manipulations simply because the CPU can now work with a 64-bit word natively
in one call instead of two [working with two 32-bit words instead for a 32-bit
processor].
<snip >
You still haven't answered my question. I am looking for real performance
measurements ... what are people seeing? Even engine versus engine match
results on Playchess would be an interested statistic for me if I knew the
hardware configuration behind it.
Thanks!
--
Thomas T. Veldhouse
Key Fingerprint: D281 77A5 63EE 82C5 5E68 00E4 7868 0ADC 4EFB 39F0
|
|
