Deep Thought
Thorsten Heedt
Thorsten Heedt
Hello computer fans,
has anybody heard something new about DEEP BLUE or DEEP THOUGHT ? Some
years ago, they wrote in SCIENTIFIC AMERICAN, that they would construct a
super chess chip and connect one thousand of them to a parallel super
computer that would perhaps be able to beat Kasparov. But somehow they
had some problems with the hardware and nothing happened. I talked to the
constructor of that powerful hardware, Mr Feng Hsiung-Hsu, but perhaps by
commercial reasons, he didn't say anything rich of information.
I told him why they didn't 'buy' the programmer of Genius 3.0, Richard
Lang, who should do the program. Perhaps they could show him how to
program that super computer. That would surely be a ingenious machine
because even that microcomputer program by him has on a pentium a
strenght of about 2440 ELO !. DEEP THOUGHT has 'only' 2550 ELO,not much
for a super computer, I think, and their program has powerful tactics,
but it doesn't know even the simpliest things as for example the rule of
the bishops of different colour. (See the awful games against GM Bent
Larsen, some years ago.)
But Mr Hsu replied that there would remain some gaps which Kasparov could
pass easily, it wouldn't be enought to transfer a micro program to a
super computer (for some obscure reasons he didn't really precise.)
If anyone knows, please tell me
1) Some News about Deep Thought
2) What do you think about trying to transfer a micro program to a super
computer
Do you know any tries to do that and what increase in playing strenghth
did it cause ?
Many greetings
Thorsten
I want to hear many different ideas and propositions, please !
Answer me as fast as you can !!
Noshir Patel
: Do you know any tries to do that and what increase in playing strenghth
: did it cause ?
This has problems. The big one is that the heuristics of a chess program
are tuned for best results with the combination of speed and time it has.
All of that tuning (much of which is experimental) goes pretty much out the
door as soon as the search depth increases much.
So, when you move a program to a faster machine, the results are often
quite a bit less than you might expect.
--
Noshir Patel
"I got 7000 channels of shit on the usenet to choose from (choose from...
choose from...)" - if RW was on internet...
engelkes
>has anybody heard something new about DEEP BLUE or DEEP THOUGHT ? Some
>years ago, they wrote in SCIENTIFIC AMERICAN, that they would construct a
>super chess chip and connect one thousand of them to a parallel super
>computer that would perhaps be able to beat Kasparov. But somehow they
>had some problems with the hardware and nothing happened. I talked to the
>If anyone knows, please tell me
>1) Some News about Deep Thought
It will come out of the closet one year after Botvinik's Pioneer :-)
John P DeMastri
Robert Hyatt
Thorsten Heedt <a224...@athena.rrz.uni-koeln.de> wrote:
>
>Hello computer fans,
>
>has anybody heard something new about DEEP BLUE or DEEP THOUGHT ? Some
>years ago, they wrote in SCIENTIFIC AMERICAN, that they would construct a
>super chess chip and connect one thousand of them to a parallel super
>computer that would perhaps be able to beat Kasparov. But somehow they
>had some problems with the hardware and nothing happened. I talked to the
>commercial reasons, he didn't say anything rich of information.
>
>I told him why they didn't 'buy' the programmer of Genius 3.0, Richard
>Lang, who should do the program. Perhaps they could show him how to
>
>program that super computer. That would surely be a ingenious machine
>because even that microcomputer program by him has on a pentium a
>strenght of about 2440 ELO !. DEEP THOUGHT has 'only' 2550 ELO,not much
>for a super computer, I think, and their program has powerful tactics,
>but it doesn't know even the simpliest things as for example the rule of
>the bishops of different colour. (See the awful games against GM Bent
>Larsen, some years ago.)
>
>But Mr Hsu replied that there would remain some gaps which Kasparov could
>pass easily, it wouldn't be enought to transfer a micro program to a
>super computer (for some obscure reasons he didn't really precise.)
>
>1) Some News about Deep Thought
>computer
MUCH easier said than done. Deep Thought / Deep Blue is a parallel machine,
requiring a parallel search algorithm. These are *very* hard to develop,
debug, etc. The hardware can do some things that make it very fast, but, as
a result, concessions are also made... some that would break Genius completely.
This has been a "theme" for discussion for years. In general, you would have
to throw genius away and start from scratch. Lang might be good, but he would
spend years getting up to speed on parallel search strategies, while many of us
already have invested this time. While he learns to program a parallel
special-purpose piece of hardware, what does Hsu do? keep on working. No
advantage I can see to try it...
>Do you know any tries to do that and what increase in playing strenghth
>did it cause ?
Lets take the Cray C90. The typical computer chess program would probably
run two-five times faster on that machine than on the fastest pentium around.
You can get another factor of 16 if you develop a parallel search algorithm,
taking man-years to perfect, that will take you to 32-80 times faster which
is getting serious... Then, if you learn how to write vectorizable code,
you get another factor of at least 5, now your speedup is 150-400 which is
*really* serious performance. However, just dropping your "dusty deck" C
chess program onto a cray will get you 2-5 which is not a lot. The rest is
there for the asking, but the "price is high in man-hours to get it."
We've been working on Cray Blitz for about 15 years on the cray, with tons
of assembly language, etc, to get our 500K nodes per second on the C90. It
*has not* been easy. Our original chess program would probably do about 3K
nodes per second on the C90 (the 1981 version of Cray Blitz) so we've gone
from 3K to 500K with probably 5 man-years of full-time effort.
--
Robert Hyatt Computer and Information Sciences
hy...@cis.uab.edu University of Alabama at Birmingham
(205) 934-2213 115A Campbell Hall, UAB Station
(205) 934-5473 FAX Birmingham, AL 35294-1170
Vincent Diepeveen
>In article <3me9gc$4...@news.rrz.uni-koeln.de>,
>Thorsten Heedt <a224...@athena.rrz.uni-koeln.de> wrote:
>>
>>Hello computer fans,
>>I told him why they didn't 'buy' the programmer of Genius 3.0, Richard
I guess both are right;
implementing parallelism/C90 is very hard.
On the other hand, we see that incredibly fast machines are not much better
then commercial programms on hardware that is just too slow to overcome
even the so called tactical barrier using full-witdh search.
Why?
Well, i think that too much time is given to parallelism, fast evaluating
on C90: why not make the programm better?
For example take my stupid programm:
I started programming Februari 1994 on it:
However, compared to a shareware programm called Gazebo
i get a much better branching factor.
hxg6
[--------------
. . . . r q k .
. p . n . r p p
. . p b Q . p .
. . . p . . P P
p . . . . P . .
. P . P P N . B
P B P . . . . .
. . K . . . . R
white to play
--------------]
ply AB-evals total-evals time(s) move
2 130 587 1 Qg4
3 474 1256 1 Qg4
4 2790 9405 7 Qg4
5 5834 25211 16 Qg4
6 20304 57061 36 Qg4
7 65441 235663 158 Qg4
8 187243 734285 441 Qg4
9 1041679 4096953 2747 h5xg6!
AB-evals are all evaluations in alpha-beta.
I evaluate not only at the ends of search (after a n-ply variation),
but also in 'innernodes'.
Total-evals are all evaluations in alpha-beta + quiescencesearch.
The search is entirely full-with:
using PVS,Nullmove (recursive,2 ply reduction factor),Hashtables.
There is no forward pruning at all.
Why does a 1.2 year old programm that is having a MUCH worse evaluating
procedure(which decreases the branching factor) then Gazebo
(in fact it is a little worse then GNU-chess) have a
better branching factor Gazebo has?
Yes, i wrote a lot of knowledge for that sorting, taking about
15% of the total systemtime.
With 500,000 evaluations a second i'd get 15 to 18 ply brute force
in complex middlegames. No problem.
My branching factor is still not as good as it could be; there are a lot
of commercial programms which have much better full-width branching
factors, i guess. Not to mention other things like evaluating procedure...
(the only problem with evaluation routines is that it is hard to compare them;
finding combinations has nothing to do with a good evaluation of a position;
in fact sacrificing could be seen as a bug in evaluation sometimes).
>Lets take the Cray C90. The typical computer chess program would probably
>run two-five times faster on that machine than on the fastest pentium around.
>You can get another factor of 16 if you develop a parallel search algorithm,
>taking man-years to perfect, that will take you to 32-80 times faster which
>is getting serious... Then, if you learn how to write vectorizable code,
>you get another factor of at least 5, now your speedup is 150-400 which is
>*really* serious performance. However, just dropping your "dusty deck" C
>chess program onto a cray will get you 2-5 which is not a lot. The rest is
>there for the asking, but the "price is high in man-hours to get it."
Write these difficult Crays-only things yourself, and get the
chessknowledge/move ordering from a commercial programm!
I guess this solves all problems.
I wouldn't take Lang however... ...the only superior thing about Genius
is its selective search and its static knowledge(with build-in
problem-solutions). When you want to find super-GM-moves, then you
don't need static knowledge, but dynamic knowledge... ...and a very very
good branching factor.
>We've been working on Cray Blitz for about 15 years on the cray, with tons
>of assembly language, etc, to get our 500K nodes per second on the C90. It
>*has not* been easy. Our original chess program would probably do about 3K
>nodes per second on the C90 (the 1981 version of Cray Blitz) so we've gone
>from 3K to 500K with probably 5 man-years of full-time effort.
Do you get 15-18+ ply in complex middlegames?
Vincent.
Vincent Diepeveen
vdie...@cs.ruu.nl
--
+--------------------------------------+
|| email : vdie...@cs.ruu.nl ||
|| Vincent Diepeveen ||
+======================================+
Kenneth Naugle
>Richard Lang of Genius 3.0 )who could show his abilities on a super
>computer ? As far as I know, there are only patzers who can't play chess
>that program those chess programs on super computers, but they are
>perfect in those hardware matters.
You mean perhaps a FISH like Hans Berliner (I could beat him in my
sleep!) who was working on HITECH the last I heard! Where do these
weakies come from?? ;^)
Can't get a real World Champion, so we have to borrow a postal guy!? Ex.
at that!!
R/ Ken Naugle
Apologies to Mr. Berliner
Thorsten Heedt
: : 2) What do you think about trying to transfer a micro program to a super
: : computer
: : Do you know any tries to do that and what increase in playing strenghth
: : did it cause ?
:
: This has problems. The big one is that the heuristics of a chess program
: are tuned for best results with the combination of speed and time it has.
:
: All of that tuning (much of which is experimental) goes pretty much out the
: door as soon as the search depth increases much.
:
: So, when you move a program to a faster machine, the results are often
: quite a bit less than you might expect.
:
:
: --
: Noshir Patel
:
: "I got 7000 channels of shit on the usenet to choose from (choose from...
: choose from...)" - if RW was on internet...
But I'd like to know: These are all theories about how it works, but are
there any hints that this is really the case ? Is there for example a
Feng-Hsiung Hsu
>MUCH easier said than done. Deep Thought / Deep Blue is a parallel machine,
>requiring a parallel search algorithm. These are *very* hard to develop,
>debug, etc. The hardware can do some things that make it very fast, but, as
>a result, concessions are also made...
To be more precise, DT-1 or DT-2 do not support general purpose programming,
and there is no way to port other software to them. BTW, at the time that
DTs were built, they costed less than a pentium class machine would have
costed back then. DT-1, if built today, would still cost less than a
pentium machine. It was mainly a tradeoff between complexity and speed.
For the new chip, it does not make sense to port programs like Genius; the
hardware evaluation is better than what the programs are trying to approximate
in software, at least in theory. I will know for sure when the vendor
finally sends the chips back.
Joe Stella
f...@sawmill.watson.ibm.com (Feng-Hsiung Hsu) writes:
>For the new chip, it does not make sense to port programs like Genius; the
>hardware evaluation is better than what the programs are trying to approximate
>in software, at least in theory. I will know for sure when the vendor
>finally sends the chips back.
Well, I can believe that your hardware evaluator might be faster and more
accurate than any software evaluator, but what about things like forward
pruning? Genius has a very good selective search, and it seems to me that
no one else knows how this is done. Is it possible that more knowledge
in this area might be beneficial to you people?
Joe S.
Steve Kelly
Naugle) wrote:
> >computer ? As far as I know, there are only patzers who can't play chess
> >that program those chess programs on super computers, but they are
> >perfect in those hardware matters.
> You mean perhaps a FISH like Hans Berliner (I could beat him in my
> sleep!) who was working on HITECH the last I heard! Where do these
> weakies come from?? ;^)
> Can't get a real World Champion, so we have to borrow a postal guy!? Ex.
> at that!!
That Russian computer making its bouts in the 1970's had to really
scrape the bottom of the barrel for their help: Botvinnik! :^)
... "None but himself can be his parallel." - Louis Theobald
Peter Gillgasch
|> For example take my stupid programm:
|>
|> The search is entirely full-with:
^^^^^^^^^^^^^^^^^^
|> using PVS,Nullmove (recursive,2 ply reduction factor),Hashtables.
|> There is no forward pruning at all.
ROTFL... Sounds like "I shot the sheriff, but I didn't shot the deputy".
|> Do you get 15-18+ ply in complex middlegames?
With the search regime described above I easily get 12 ply on
a PowerMacintosh, so probably Bob would get your estimated 18
ply on a Cray. The fact that nearly no big iron program uses
this recursive null move pruning (I think *Socrates is the only
exception) should make you think: If you have the alternative
to get >10 ply brute force (or with *non recursive* null move
pruning) and getting >15 ply with the *highly* selective search
you are using, you are certainly better off with brute force
plus some extensions.
-- Peter
------------------------------------------------------------
Peter W. Gillgasch
Klosterweg 28/I-113 email gil...@ira.uka.de
76131 Karlsruhe/Germany Phone ++49/(0)721/6904255
Paul Rubin
Feng-Hsiung Hsu <f...@sawmill.watson.ibm.com> wrote:
>To be more precise, DT-1 or DT-2 do not support general purpose programming,
>and there is no way to port other software to them. BTW, at the time that
>DTs were built, they costed less than a pentium class machine would have
>costed back then. DT-1, if built today, would still cost less than a
>pentium machine. It was mainly a tradeoff between complexity and speed.
>hardware evaluation is better than what the programs are trying to approximate
>in software, at least in theory. I will know for sure when the vendor
>finally sends the chips back.
Vendor? You don't use an in-house fab?
Do you have any publications (internet or paper) about the DT hardware
more recent than the Scientific American article of a couple years
back? I'm interested to see how things are progressing!
Feng-Hsiung Hsu
>Well, I can believe that your hardware evaluator might be faster and more
>accurate than any software evaluator, but what about things like forward
>pruning? Genius has a very good selective search, and it seems to me that
>no one else knows how this is done. Is it possible that more knowledge
>in this area might be beneficial to you people?
Genius' selective search appears to be quite good, but not good enough.
Another consideration is that we are concerned about the worst case, not
the average case. It is more important for us to see the VERY difficult
combinations that the top players are capable of producing than getting
the average combinations fast. Not to boast, but we probably know more
about how to get the program to solve the most difficult combinations than
anyone.
Joe Stella
f...@sawmill.watson.ibm.com (Feng-Hsiung Hsu) writes:
>Genius' selective search appears to be quite good, but not good enough.
>Another consideration is that we are concerned about the worst case, not
>the average case. It is more important for us to see the VERY difficult
>combinations that the top players are capable of producing than getting
>the average combinations fast. Not to boast, but we probably know more
>about how to get the program to solve the most difficult combinations than
>anyone.
Well, I will accept the notion that you are not trying to boast, if you
will accept the notion that I am not trying to put you down. Deal?
I am trying to understand the numbers that I have seen. Genius running
on a Pentium does maybe 20,000 nodes/sec (I don't know if that is exactly
right) but the old Deep Thought was about 50 times faster, was it not?
So why are their ratings so close? There is a good deal of evidence
that Genius is about 2400 USCF, while DT was 2550. A factor of 50 in
speed should give you more than 150 points!
Joe S.
Robert Hyatt
Peter Gillgasch <gil...@i41s12.ira.uka.de> wrote:
>In article <3mjjnc$s...@krant.cs.ruu.nl>, vdie...@cs.ruu.nl (Vincent Diepeveen) writes:
>
>|>
>|> using PVS,Nullmove (recursive,2 ply reduction factor),Hashtables.
>|> There is no forward pruning at all.
>
>
>
>a PowerMacintosh, so probably Bob would get your estimated 18
>ply on a Cray. The fact that nearly no big iron program uses
>this recursive null move pruning (I think *Socrates is the only
>exception) should make you think: If you have the alternative
>to get >10 ply brute force (or with *non recursive* null move
>pruning) and getting >15 ply with the *highly* selective search
>you are using, you are certainly better off with brute force
>plus some extensions.
>
>-- Peter
>
OK, where is this taking us? We (Crafty and CB) use recursive
null-move, with r=2 in Crafty (1 in CB) and we don't see any
18 ply searches, nor even any 12's.... you must be doing some
"different.".....
Bob
Remy de Ruysscher
>In article <3mmams$k...@watnews1.watson.ibm.com>
>f...@sawmill.watson.ibm.com (Feng-Hsiung Hsu) writes:
>
the
>>hardware evaluation is better than what the programs are trying to
approximate
>>in software, at least in theory. I will know for sure when the vendor
>>finally sends the chips back.
>
more
>accurate than any software evaluator, but what about things like forward
>pruning? Genius has a very good selective search, and it seems to me
that
>no one else knows how this is done. Is it possible that more knowledge
>in this area might be beneficial to you people?
>
>
Well at that speed, selective search isn't that important anymore, since
they are computing 12-14 ply brute force anyway.
More knowlegde can help to improve there program rather than more
speed......
--
+----------------------------------------------------------------------+
| Remy de Ruysscher STUDY: Interactive Digital |
| Communication Systems |
| e-mail : re...@knoware.nl at |
| fidonet: 2:282/705.26 Hogeschool van Utrecht |
|
|
| Author of Shannon (Chess Program) |
| |
| "Chess is a beautiful mistress to whom we keep coming back, no matter|
| how many times she rejects us." -- Bent Larsen |
| |
| |
| Chess Dyer Rye Rum |
| |
|----------------------------------------------------------------------|
Feng-Hsiung Hsu
>Vendor? You don't use an in-house fab?
At the time the project was started, the in-house fabs only handled very
high volume stuff. They probably still do. Love to have those 5-layer
metal technologies though.
SheppardCo
> in complex middlegames. No problem.
This is very hard to believe.
No wait. Let me rephrase that: this is not true.
To convince me otherwise, please do the following:
1) Perform a 15-ply search using your current hardware.
2) Tell us how many nodes it searched.
3) Tell us how long it took.
We'll do the arithemetic from there.
Looking forward to hearing from you!
Regards,
Brian Sheppard
Robert Hyatt
SheppardCo <shepp...@aol.com> wrote:
>> With 500,000 evaluations a second i'd get 15 to 18 ply brute force
>> in complex middlegames. No problem.
>
>
>No wait. Let me rephrase that: this is not true.
>
>To convince me otherwise, please do the following:
>
> 1) Perform a 15-ply search using your current hardware.
> 2) Tell us how many nodes it searched.
> 3) Tell us how long it took.
>
>We'll do the arithemetic from there.
>
>Looking forward to hearing from you!
>
This looks even worse to anyone that has mathematically studied
alpha/beta.
15 plies = (roughly) .5 x (38 ^ 7.5) (1/2 branching factor to depth/2 power.)
lets try 16 plies to make it easier to compute:
16 = .5 x 38^8 = x.5= 4,347,792,138,496 nodes...
that's four *trillion* (as in national debt trillion... :^) )
at 500K nodes per second, that's a lot longer than the *normal* 3 minutes
per move!
Of course, if you use forward pruning, you can reduce this a lot, but you
will add significant errors into the search space...
How can you get 15-18 plies? from the above you need 8.6 million seconds to
do this... a tad long, even for postal? :^)
Joe Stella
f...@sawmill.watson.ibm.com (Feng-Hsiung Hsu) writes:
>Your question makes about as much sense as asking why the state of the art
>0.5 micron BICMOS Pentium is performing worse than the ancient 3 micron
>CMOS based DT in chess.
>[...]
Peace, man. Like I said, I am not trying to put anyone down, I just want
to understand.
So I guess your algorithms must have improved since you published
the paper on "singular extension"? Or maybe you just have a chance to
implement that algorithm better using larger scale integration?
Joe S.
Johannes Fuernkranz
>
> > Is there for example a programmer of a strong micro-program (perhaps
> >Richard Lang of Genius 3.0 )who could show his abilities on a super
> >that program those chess programs on super computers, but they are
> >perfect in those hardware matters.
>
> You mean perhaps a FISH like Hans Berliner (I could beat him in my
> sleep!) who was working on HITECH the last I heard! Where do these
> weakies come from?? ;^)
>
> Can't get a real World Champion, so we have to borrow a postal guy!? Ex.
> at that!!
>
> Apologies to Mr. Berliner
>
that would play world-champion chess and solve the economic problems
of Russia if he only had more computer power available.
Juffi
Feng-Hsiung Hsu
>I am trying to understand the numbers that I have seen. Genius running
>on a Pentium does maybe 20,000 nodes/sec (I don't know if that is exactly
>right) but the old Deep Thought was about 50 times faster, was it not?
>
>So why are their ratings so close? There is a good deal of evidence
>that Genius is about 2400 USCF, while DT was 2550. A factor of 50 in
>speed should give you more than 150 points!
Your question makes about as much sense as asking why the state of the art
0.5 micron BICMOS Pentium is performing worse than the ancient 3 micron
CMOS based DT in chess. One gives up something for general purpose
processing with Pentium, just as I had to give up a lot to fit the move
generator into a 3-micron process die. The move generator only supported
a quiescence search that is even more simple minded than what Shannon
described.
By the way, Genius is probably in the 50,000 nodes/sec range, and the speed
differential is around a factor of 15. DT's performance over ALL rated games
is around 2600, not 2550. The first 20 games was counted 4[?] times
in the way the USCF rating was calculated, as its first established rating
was over 2500 and it got a much reduced K factor.
Vincent Diepeveen
>In article <3muq3b$k...@newsbf02.news.aol.com>,
>SheppardCo <shepp...@aol.com> wrote:
>>> With 500,000 evaluations a second i'd get 15 to 18 ply brute force
>>> in complex middlegames. No problem.
>>
>>This is very hard to believe.
>>No wait. Let me rephrase that: this is not true.
>>To convince me otherwise, please do the following:
>> 1) Perform a 15-ply search using your current hardware.
>> 2) Tell us how many nodes it searched.
>> 3) Tell us how long it took.
>>We'll do the arithemetic from there.
>>Looking forward to hearing from you!
>This looks even worse to anyone that has mathematically studied
>alpha/beta.
You forget that with mathematically studied alpha-beta you don't
take the hashtables into account, nor nullmoves.
Especially that combination is giving you the better branching factor:
>15 plies = (roughly) .5 x (38 ^ 7.5) (1/2 branching factor to depth/2 power.)
>lets try 16 plies to make it easier to compute:
>16 = .5 x 38^8 = x.5= 4,347,792,138,496 nodes...
This is true for alpha-beta without hashtable and without nullmoves,
and with a minimal tree.
However with hashtables and with nullmove commercial guys
get a branching factor of 4.
My own programm currently gets 4.4, which has to do with the very
bad evaluating routine (a certain move is stored as best in hashtable,
but is not best when searching a ply deeper; without loosing material:
better evaluation gives you better branching factor, i guess;
in positions my evaluation routine is entirely wrong my branching
factor is just too bad to make it public).
I use bf = 4:
15 = .5 x 4^15 = 536,870,912
On 15 ply your hashtable should give you much more performance then
it gives you on 10 ply, so the deeper you get, the easier another
ply is?
May be someone who does get very deep can tell about this?
>that's four *trillion* (as in national debt trillion... :^) )
>at 500K nodes per second, that's a lot longer than the *normal* 3 minutes
>per move!
>Of course, if you use forward pruning, you can reduce this a lot, but you
>will add significant errors into the search space...
Nullmove and hashtable are only forward pruning tools i use.
No other, they just didn't give me that extra that i could use...
There is 1 huge disadvantage (besides that 'singular' extensions get
worse) with nullmove using reduction factor 2 (or bigger):
suppose you have 9 ply search:
ply: normal real-ply plydepth recursive nullmove real-ply
1 white 1 1 white 1
2 black 2 2 nullmove 2
3 white 3 4 white 3
4 black 4 5 r-nullmove 4
5 white 5 7 white 5
6 black 6 8 r-nullmove 6
7 white 7 9 white,q-search 7
8 black 8
9 white 9
10 q-search 10
white moves : 5 white moves : 4
Suppose white needs 5 moves to mate you.
Nullmove will not find it.
>How can you get 15-18 plies? from the above you need 8.6 million seconds to
>do this... a tad long, even for postal? :^)
Improve move ordering, and nullmove, and hashtables.
Or give every position score 0...
Suppose that there are more then 1 move that gives you a cutoff
in a certain position (but that doing nothing does give you a score < beta ).
I assume that a certain move ordering with a lot of knowledge
gives you a move A to be investigated first.
Less knowledge using move ordering gives you a move B, different from A,
because it misses the knowledge to know that A is better.
Both moves give a cutoff.
However, move B is using a much bigger tree to get that cutoff then A does.
After getting a cutoff from B, B is stored in hashtable.
Next plies it gives you also an cutoff, simply because position after B is
LITTLE better for you.
However, after A you get a quick cutoff on every ply, because
positions after A is MUCH better for you.
I noticed this problem in my programm (i print every second the
variation that is searched).
The only way of solving this, as far as i can see, is writing better
move ordering code.
Does anyone know a better solution to this?
Vincent.
Robert Hyatt
Wrong concept... this "branching factor" is "after" alpha/beta, which
for normal positions is sqrt(38) or about 6. null moves and the like
reduce this to 3-4, but you don't plug this back into the alpha/beta
formula again, it's already been done once.
However, this branching factor of four does not mean that you look at
an average of 4 moves per ply. What about extensions, captures, etc?
In short, this number is most commonly the time multiplication factor
to search one ply deeper. IE, 4 ply=5 secs, 5 ply=20 secs, 6 ply=80 secs,
but don't plug this in as the average branching factor for a 15 ply
search, because it doesn't hold up except for the simplest of search
algorithms.
>
> 15 = .5 x 4^15 = 536,870,912
>
You also have to drop the .5.... that's included in the alpha/beta
formula already and was accounted for in getting the BF=4, so 15
plies is back to a billion nodes.
>On 15 ply your hashtable should give you much more performance then
>it gives you on 10 ply, so the deeper you get, the easier another
>ply is?
maybe... can you store such a large hash table? Deep thought doesn't do
this as the chip can't afford the delay to go to some large multi-ported
ram...
I do the scoring trick for fun, and it doesn't make crafty run much faster.
It produces perfect ordering of course, letting it search a minimal tree,
but no 15 plies... I suspect a serious bug somewhere lurking... since that
is 5 plies deeper than Cray Blitz when it searches over a million nodes per
second...
Deep Thought was hitting 10-11 at something over a million nodes per second,
so we compare in the same ball park... 4 more plies is something I don't see
how we are missing...
>
>Suppose that there are more then 1 move that gives you a cutoff
>in a certain position (but that doing nothing does give you a score < beta ).
>
>I assume that a certain move ordering with a lot of knowledge
>gives you a move A to be investigated first.
>Less knowledge using move ordering gives you a move B, different from A,
>because it misses the knowledge to know that A is better.
>
>Both moves give a cutoff.
>However, move B is using a much bigger tree to get that cutoff then A does.
>
>After getting a cutoff from B, B is stored in hashtable.
>Next plies it gives you also an cutoff, simply because position after B is
>LITTLE better for you.
>
>However, after A you get a quick cutoff on every ply, because
>positions after A is MUCH better for you.
>
>
>I noticed this problem in my programm (i print every second the
>variation that is searched).
>
>The only way of solving this, as far as i can see, is writing better
>move ordering code.
>Does anyone know a better solution to this?
>
>
>Vincent.
Peter Gillgasch
been misinterpreted. I neither wanted to say that given a certain
search speed you have to be able search to absurd depths nor did
I want to imply that some method of pruning is "bad". I just wanted
to point out the differences of brute force vs. selective search.
<I snipped a lot and often I failed to state that, sorry>
In article <3n3mnt$7...@pelham.cis.uab.edu>, hy...@willis.cis.uab.edu (Robert Hyatt) writes:
|> In article <3n32im$o...@krant.cs.ruu.nl>,
|> Vincent Diepeveen <vdie...@cs.ruu.nl> wrote:
|> >In <3n0h4i$5...@pelham.cis.uab.edu> hy...@willis.cis.uab.edu (Robert Hyatt) writes:
|> >
|> >>In article <3muq3b$k...@newsbf02.news.aol.com>,
|> >>SheppardCo <shepp...@aol.com> wrote:
|> >>>> With 500,000 evaluations a second i'd get 15 to 18 ply brute force
|> >>>> in complex middlegames. No problem.
|> >>>
|> >>>This is very hard to believe.
|> >
|> >>>No wait. Let me rephrase that: this is not true.
|> >
|> >>>To convince me otherwise, please do the following:
|> >
|> >>> 1) Perform a 15-ply search using your current hardware.
Probably completely impossible due to hash memory limitations.
|> >>> 2) Tell us how many nodes it searched.
See above.
|> >>> 3) Tell us how long it took.
See above.
|> >>>We'll do the arithemetic from there.
|> >
|> >>>Looking forward to hearing from you!
|> >
|> >>This looks even worse to anyone that has mathematically studied
|> >>alpha/beta.
|> >
|> >You forget that with mathematically studied alpha-beta you don't
|> >take the hashtables into account, nor nullmoves.
|> >
|> >Especially that combination is giving you the better branching factor:
|> >
|> >>15 plies = (roughly) .5 x (38 ^ 7.5) (1/2 branching factor to depth/2 power.)
|> >>lets try 16 plies to make it easier to compute:
|> >>16 = .5 x 38^8 = x.5= 4,347,792,138,496 nodes...
|> >
|> >This is true for alpha-beta without hashtable and without nullmoves,
|> >and with a minimal tree.
|> >However with hashtables and with nullmove commercial guys
|> >get a branching factor of 4.
|>
|> >I use bf = 4:
<snip>
|> Wrong concept... this "branching factor" is "after" alpha/beta, which
|> for normal positions is sqrt(38) or about 6. null moves and the like
|> reduce this to 3-4, but you don't plug this back into the alpha/beta
|> formula again, it's already been done once.
|>
|> However, this branching factor of four does not mean that you look at
|> an average of 4 moves per ply. What about extensions, captures, etc?
|> In short, this number is most commonly the time multiplication factor
|> to search one ply deeper. IE, 4 ply=5 secs, 5 ply=20 secs, 6 ply=80 secs,
|> but don't plug this in as the average branching factor for a 15 ply
|> search, because it doesn't hold up except for the simplest of search
|> algorithms.
True. When I was stating that really large *nominal* search depths are doable
when doing recursive null move pruning I was talking out of experience with
a __very__ stripped down version of my chess program. This version reaches
depths that are really hard to believe. I created this version using a couple
of #define's just for the sole purpose of verifying the claims made about
some of the commercial programs - take a look at the nominal search depth
of Fritz3 for example - and to test the hypothesis that they are applying
such a search regime.
This version uses most of the cpu time for search control, so you can imagine
that the evaluation, the extension techniques and especially the quiesence
search was very simple.
|> You also have to drop the .5.... that's included in the alpha/beta
|> formula already and was accounted for in getting the BF=4, so 15
|> plies is back to a billion nodes.
Bob, did you consider the following: the "depth" parameter is selectively
reduced during the search. If you design a search algorithm in such a way
that at most frontier nodes the material balance is so loopsided that you
can simply stop the search and most of your searches approach this level
of the search tree faster than usual then I don't see how the analysis
of Knuth and Moore can hold for that algorithm ? Since the exponent is
reduced this will definitively lead to massive reduction of the search
space...
|> >On 15 ply your hashtable should give you much more performance then
|> >it gives you on 10 ply, so the deeper you get, the easier another
|> >ply is?
|>
|> maybe... can you store such a large hash table? Deep thought doesn't do
|> this as the chip can't afford the delay to go to some large multi-ported
|> ram...
The size of the hash table is of course a limiting factor. But when you
use techniques that forward prune the tree by null move searches and
certain mathematical properties of the evaluation function then you end
up very often with the info that the subtree can be pruned without having
any "refutation move" information. Hence you cannot create a hash entry.
|> >>Of course, if you use forward pruning, you can reduce this a lot, but you
|> >>will add significant errors into the search space...
That's the price you pay for scaring the other player to death when he
looks at the display (^8 Which is probably not helpful when playing against
a classical CHESS 4.x clone...
|> >Nullmove and hashtable are only forward pruning tools i use.
|> >No other, they just didn't give me that extra that i could use...
That was the reason for my laughter... The techniques Vincent uses *are*
forward pruning (introducing errors into the search) yet he claimed the
search to be "full width" and comparable with programs that do a lot of
work to extend critical lines.
|> I do the scoring trick for fun, and it doesn't make crafty run much faster.
|> It produces perfect ordering of course, letting it search a minimal tree,
|> but no 15 plies... I suspect a serious bug somewhere lurking... since that
|> is 5 plies deeper than Cray Blitz when it searches over a million nodes per
|> second...
Assigning the same score to all positions and looking at the depth then is
probably not a good experiment. Change it to the following: use material
balance and a purely piece/square table based positional component. This
alone will yield big savings ("better" futility pruning).
|> Deep Thought was hitting 10-11 at something over a million nodes per second,
|> so we compare in the same ball park... 4 more plies is something I don't see
|> how we are missing...
I don't think that you miss them. First 15 ply is of course
**big** if you look at the algorithm you are using now. But if
you change the algorithm the notion of "ply" changes as well,
especially if you can reduce the quiesence search to close to
nothing.
Paul Hsieh
that F. Hsu and R. Hyatt seem really big on their parallel algorithms and try
to explain away the fact that Socrates can draw them or that Chess Genius
beats Kasparov while neither of them has by opening books or fluke.
Fact is, those PC programs are pretty damn good and they can't simply throw
ridiculuosly expensive hardware at them, and yet they have achieved very good
results (at their paltry 8 or 9 ply per move.) My understanding of search
algorithms is that good ordering and judicious pruning is where the biggest
gains are to be made. Clearly these good PC programmers MUST have made major
breakthroughs in these areas. I just don't buy the line that these achieve-
ments cannot be somehow incorporated into these parallel search algorithms.
As far as I know nobody has had success with *singular extensions* except
for Hsu's team. (I have tried them myself in another game playing field;
Othello with 0 success) I am somewhat suspicious as to how much they really
help DT. DT has always outsearched its competition by a factor of 10 or
more. Any reasonable algorithm would probably be successful with that
amount of fire power behind it. R. Hyatt has described his algorithms in
a couple papers (one of which I have a copy of somewhere) and there really
didn't seem to be anything clever in it at all. I'm sure even the most
basic chess programs out there are using all those techniques.
I'm sure your skill with parallel algorithms are unmatched. But what about
the search algorithms themselves? I guess I didn't mean to come down that
hard, but you guys just gotta know that you're not very convincing.
I would be more apt to believe that if you took some of Lang's ideas and
incorporated them into your (either of you guys) hardware/programs you could
make it substantially stronger and dethrown Kasparov almost immediately.
Anyhow, enough ranting. On the subject of evaluators, have you looked at
the field of Othello? Very recently three very strong Othello playing
programs have been developed: Logistello, Kitty, and Eclipse (they make
"BILL" look like MS Windows Reversi). They have varying degrees of search
capabilities but the common theme is that they all have very good evaluators.
Their methods are based on regression analysis, logarithmic regression (?),
and genetic algorithms (I believe).
Their methods are proven and worth a look see. I remember some mention of
the evaluator for DT in the first scientific american article, but I could
not gleen enough details from how it was described. It sounded to me like
it was a programmable polynomial calculator of some kind?
Anyhow if you are interested in more evaluator tidbits from Othello you guys
can contact me.
Paul Hsieh
Robert Hyatt
>I have been watching computer chess for quite a while now and it seems to me
>that F. Hsu and R. Hyatt seem really big on their parallel algorithms and try
>to explain away the fact that Socrates can draw them or that Chess Genius
>beats Kasparov while neither of them has by opening books or fluke.
>
>Fact is, those PC programs are pretty damn good and they can't simply throw
>ridiculuosly expensive hardware at them, and yet they have achieved very good
>results (at their paltry 8 or 9 ply per move.) My understanding of search
>algorithms is that good ordering and judicious pruning is where the biggest
>gains are to be made. Clearly these good PC programmers MUST have made major
>breakthroughs in these areas. I just don't buy the line that these achieve-
>ments cannot be somehow incorporated into these parallel search algorithms.
1. You "assume" that deep thought doesn't use any of these ideas. Where does
this assumption come from? You will notice that the Deep Thought team has
published "tons" of "inside information" on their selective search strategies,
test results, and the like. How much info do you have on Genius 3?
2. No one (least of all myself) will argue with your point that these commercial
programs are absolutely astounding chess players. However, it's highly improbable
that such programs can climb to the top... defeating the last few hundred GM
players is a formidable task...
3. If either Deep Thought or Cray Blitz plays Kasparov in a match of blitz games,
neither will end up with a score of 0 wins. I've personally played too many GM's,
IM's, etc at blitz (using Cray Blitz of course). These programs are simply too
strong tactically to lose over and over. In fact, I would suspect that they would
have a reasonable chance of winning such a match. Note: 5 mins on the clock type
blitz games are the subject here.
4. "judicious" pruning does pay off, until you aspire to reach the top. Suddenly,
you begin to prune away moves that are actually very important. Deep Thought doesn't
have to "prune" and therefore is not subject to these fatal mistakes.
>
>As far as I know nobody has had success with *singular extensions* except
>for Hsu's team. (I have tried them myself in another game playing field;
>Othello with 0 success) I am somewhat suspicious as to how much they really
>help DT. DT has always outsearched its competition by a factor of 10 or
>more. Any reasonable algorithm would probably be successful with that
>amount of fire power behind it. R. Hyatt has described his algorithms in
>a couple papers (one of which I have a copy of somewhere) and there really
>didn't seem to be anything clever in it at all. I'm sure even the most
>basic chess programs out there are using all those techniques.
Quite possible, and the main reason is that I (and others) did, in fact, publish
what we do and how it works. Do you think that the new group of PC programmers
simply "started from scratch" and came up with these amazing programs? Granted
that they have their own tricks of the trade, but 90% comes from prior work...
the "standing on the shoulders of giants..." Most current programs can be traced
directly back to Slate and Atkin's Chess 4.x... improvements, of course, have been
made, but the similarities are there.
The latest Spracklen program uses singular extensions. The problem with the
algorithm is that is is relatively expensive. For argument, suppose it costs
one ply of search depth. If you are only searching 6 plies deep, then dropping
to 5 is probably going to more than offset the gain of singular extensions.
However, if you are searching 10-11, then losing a ply is not nearly so
costly. One simple example: The last time deep thought and star socrates
played, deep thought found a forcing line to win material, and it saw the win
at least 5 full moves before star socrates knew it had fallen into the sewer.
A couple of years ago, we played deep thought and again they found a forcing
series of moves, that their program saw to the end, where they won a pawn.
It took us (with no singular extensions) another 6 or 7 full moves before
we saw it...
Is this important? As Hsu pointed out, these forced "deep" combinations are
probably more important than anything else when playing and competing with the
very best players. They will all fall for the occasional 10 ply combination
that computers are so good at seeing, but to compete consistently, the computer
has got to be able to follow these forcing lines 30+ plies deep. Genius nor
non of the other programs can currently do this.
>
>I'm sure your skill with parallel algorithms are unmatched. But what about
>the search algorithms themselves? I guess I didn't mean to come down that
>hard, but you guys just gotta know that you're not very convincing.
>
>I would be more apt to believe that if you took some of Lang's ideas and
>incorporated them into your (either of you guys) hardware/programs you could
>make it substantially stronger and dethrown Kasparov almost immediately.
It's hard to "take" that which is "not available." Give me Richard's selective
search algorithm, and I'll certainly look at it. However, both Deep Thought and
Cray Blitz (and now Crafty) have their own selective algorithms that are continuously
being improved...
>
>Anyhow, enough ranting. On the subject of evaluators, have you looked at
>the field of Othello? Very recently three very strong Othello playing
>programs have been developed: Logistello, Kitty, and Eclipse (they make
>"BILL" look like MS Windows Reversi). They have varying degrees of search
>capabilities but the common theme is that they all have very good evaluators.
>Their methods are based on regression analysis, logarithmic regression (?),
>and genetic algorithms (I believe).
I've even played with othello programs and modified Cray Blitz (years ago) to
play the game. They are good programs for two reasons: (1) the game is much
simpler in terms of rules than chess, so the program is faster than the
corresponding chess board; the strategies are simpler, the game is exceedingly
difficult for a human to search deeply since a single piece can affect many
others, making visualization difficult. However, the game itself bears no relation
at all to chess, other than both can be managed by typical alpha/beta searches.
>
>Their methods are proven and worth a look see. I remember some mention of
>the evaluator for DT in the first scientific american article, but I could
>not gleen enough details from how it was described. It sounded to me like
>it was a programmable polynomial calculator of some kind?
>
>Anyhow if you are interested in more evaluator tidbits from Othello you guys
>can contact me.
>
>Paul Hsieh
Joe Stella
hy...@willis.cis.uab.edu (Robert Hyatt) writes:
>Quite possible, and the main reason is that I (and others) did, in fact, publish
>what we do and how it works. Do you think that the new group of PC programmers
>simply "started from scratch" and came up with these amazing programs?
[...]
>The latest Spracklen program uses singular extensions.
The fourth quarter 1990 issue of Computer Chess Reports stated that Richard
Lang also adopted Singular Extension in his "Mephisto Lyon" program, and
that this was the principal source of improvement in his program for that
year.
Joe Stella
Feng-Hsiung Hsu
>I have been watching computer chess for quite a while now and it seems to me
>that F. Hsu and R. Hyatt seem really big on their parallel algorithms and try
>to explain away the fact that Socrates can draw them or that Chess Genius
>beats Kasparov while neither of them has by opening books or fluke.
Better check your fact again. Socrates drew Cray Blitz, not DT-2. Chess
Genius beating Kasparov IS a fluke. It is good, but not that good.
>As far as I know nobody has had success with *singular extensions* except
>for Hsu's team. (I have tried them myself in another game playing field;
>Othello with 0 success) I am somewhat suspicious as to how much they really
>help DT. DT has always outsearched its competition by a factor of 10 or
>more.
Not when we were playing *Socrates. They were "outsearching" us by two
full plies. Node counts were comparable. There are commercial programs
that do use singular extensions.
>I would be more apt to believe that if you took some of Lang's ideas and
>incorporated them into your (either of you guys) hardware/programs you could
>make it substantially stronger and dethrown Kasparov almost immediately.
If it were true, Lang would have done it by now. I don't think programming a
Cray is beyond him. Lang's program would not work on DTs' hardware. DTs'
hardware is both a boon and a bane. Speed it has, programmability it doesn't
have.
By the way, Kasparov is tougher than you think when he puts his mind to it.
Peter McKenzie
phsieh@jedi (Paul Hsieh) writes a whole lot of junk.
Paul, do you really believe all that stuff or is it just flame bait??
peter