Suggested chess experiment
Henri H. Arsenault
not search efficiency decreases with depth still don't answer the question
of whether there is a horizon beyond which a further search will not yeild
a better move. The fact that published experiments show that up to 14 ply,
the number of new "best" moves seems constant show that if there is a
horizon, it lies deeper.
I have an idea for an experiment that could give useful information on the
effect of search depth, if not on the above question.
The idea is to pit a computer against itself in a tournament with one
engine having one more ply in its search. For example, let us say that
you play Fritz against itself with white having a fixed six-ply search and
Black having a fixed five-ply search. The number of games won, lost and
drawn are compiled and a corresponding probability that White wins is
determined with error bars.
The experiment is then repeated with White having a seven-ply search and
Black having a six-ply search. This is continued with eight, nine, ten...
and so on plies.
If the proportion of wins decreases with the number of plies, this
indicates that as the search depth increases, more plies are required in
order to win. On the other hand, if 12-ply vs 11-ply yields the same
proportion of wins as six vs five, this is an indication that going the
probability that going one ply deeper is independent of the depth of the
search. If this is true, it means that chess cannot be solved without
going all the way through the game :(
The experiment could be repeated with a two-ply difference, or with Black
having the larger number of plies.
The problem with this experiment is that Fritz does not allow engine vs
engine tournaments with fixed numbers of plies, but only with fixed
time.It is also unclear to me how many games at each level would be
required in order to ensure a statistically significant result.So unless a
special program were written, the experiment could be rather tedious.
Any ideas?
Henri
Ernst A. Heinz
> I have an idea for an experiment that could give useful information on the
> effect of search depth, if not on the above question.
Dear Henri,
Your idea is not so new -- Ken Thompson pioneered such self-play experiments
with his chess machine "Belle" back in 1982.
My article "DarkThought Goes Deep" as published in the ICCA Journal 22(4)
summarizes the results and setups of the most prominent self-play experiments
in computer chess as conducted so far (electronic preprint available at URL
<http://wwwipd.ira.uka.de/Tichy/DarkThought/>.
=Ernst=
+----------------------------------------------------------------------------+
| Ernst A. Heinz, School of CS (IPD), Univ. of Karlsruhe, P.O. Box 6980, |
| D-76128 Karlsruhe, F.R. Germany. WWW: <http://wwwipd.ira.uka.de/~heinze/> |
| Tel. / Fax: +49-(0)721-6084386 / 6087343 E-Mail: <hei...@ira.uka.de> |
+----------------------------------------------------------------------------+
"It has recently been found out that research causes cancer in rats!"
Henri H. Arsenault
(Ernst A. Heinz) wrote:
> Your idea is not so new -- Ken Thompson pioneered such self-play experiments
> with his chess machine "Belle" back in 1982.
>
> My article "DarkThought Goes Deep" as published in the ICCA Journal 22(4)
> summarizes the results and setups of the most prominent self-play experiments
> in computer chess as conducted so far (electronic preprint available at URL
> <http://wwwipd.ira.uka.de/Tichy/DarkThought/>.
>
Thanks for the info, and I have already read your fine article, but I
don't recall any results from self-play experiments along the line of what
I proposed in my message.(Should I read your article again?...). Offhand
what I remember from your article is that the number of "new best moves"
seems to remain constant with depth of analysis up to 14-ply (confirming
previous results by Hyatt), and that Hyatt's methodology for forecasting
the performance of crafty when it would go more deeply was flawed.
Anyway, if Thompson and/or someone else already did the experiments, I am
glad (since I am unlikely to do them myself), and I would appreciate
knowing what the results were - I presume that today's computers could do
a lot better than Belle in 1982.
Henri
Ernst A. Heinz
> Thanks for the info, and I have already read your fine article, but I
> don't recall any results from self-play experiments along the line of what
> I proposed in my message.(Should I read your article again?...).
Section 2 of my article summarizes the self-play results and tells you that
some of them hinted at diminishing returns for additional search in computer
chess self-play while others did not. Yet, unfortunately, none of the
experiments was conclusive in the sense that it allowed for any statistically
*confident* statements in this respect.
=Ernst=
Henri H. Arsenault
(Ernst A. Heinz) wrote:
OK, thanks. That means that it might be worthwhile to do the experiment as
I described it, given the much higher speed of today's computers. It is
not clear to me how many games in each match would be required to have a
statistically valid result. Offhand I would say about 9 games for a 90%
probability for each match or 16 games for a 95% probability (this assumes
a Poisson distribution), but this may not be enough for the validity of
the whole match.
In my view, the main problem is to automate the process, since up until
about 11-ply, today's computers could play one match reasonably fast. one
possible solution could be to break up the problem among dozens of
volunteers.
Henri
Dann Corbit
news:arseno-1702...@descartes.phy.ulaval.ca...
position and also 8 hours. It might be an interesting study to see how
often it changes its mind. Three months after the completion of any phase
of an experiment from the C.A.P. project, the public domain data is
released. We will have several more announcements shortly.
--
C-FAQ: http://www.eskimo.com/~scs/C-faq/top.html
"The C-FAQ Book" ISBN 0-201-84519-9
C.A.P. Newsgroup http://www.dejanews.com/~c_a_p
Chess Data: ftp://38.168.214.175/pub/
Robert Hyatt
: In article <7aetsb$rnt$1...@news.rz.uni-karlsruhe.de>, hei...@ira.uka.de
: (Ernst A. Heinz) wrote:
:> Your idea is not so new -- Ken Thompson pioneered such self-play experiments
:> with his chess machine "Belle" back in 1982.
:>
:> My article "DarkThought Goes Deep" as published in the ICCA Journal 22(4)
:> summarizes the results and setups of the most prominent self-play experiments
:> in computer chess as conducted so far (electronic preprint available at URL
:> <http://wwwipd.ira.uka.de/Tichy/DarkThought/>.
:>
: Thanks for the info, and I have already read your fine article, but I
: don't recall any results from self-play experiments along the line of what
: I proposed in my message.(Should I read your article again?...). Offhand
: what I remember from your article is that the number of "new best moves"
: seems to remain constant with depth of analysis up to 14-ply (confirming
: previous results by Hyatt), and that Hyatt's methodology for forecasting
: the performance of crafty when it would go more deeply was flawed.
There have been at least two such experiments. Ken Thompson did the
first one (which was published a long time back). Hans Berliner did
another, but took two versions of "hitech". one smart/dumb, the other
slower but smarter, and played them vs each other, to see what would
happen. I think that was published in one of the advances in computer
chess books. I can summarize if you don't have it handy...
: Anyway, if Thompson and/or someone else already did the experiments, I am
: glad (since I am unlikely to do them myself), and I would appreciate
: knowing what the results were - I presume that today's computers could do
: a lot better than Belle in 1982.
: Henri
--
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
Ernst A. Heinz
> It is
> not clear to me how many games in each match would be required to have a
> statistically valid result. Offhand I would say about 9 games for a 90%
> probability for each match or 16 games for a 95% probability (this assumes
> a Poisson distribution), but this may not be enough for the validity of
> the whole match.
Depending on the actual scoring rates, you need at least 500-1000 games
to quantify differences in playing strength with 95% statistical
confidence (already stated in Section 2 of my article, too).
So, maybe you should actually reread the article ... :-)
=Ernst=
Henri H. Arsenault
<hy...@crafty.cis.uab.edu> wrote:
> There have been at least two such experiments. Ken Thompson did the
> first one (which was published a long time back). Hans Berliner did
> another, but took two versions of "hitech". one smart/dumb, the other
> slower but smarter, and played them vs each other, to see what would
> happen. I think that was published in one of the advances in computer
> chess books. I can summarize if you don't have it handy...
>
I don't, so please do.
Henri
Ernst A. Heinz
>> There have been at least two such experiments. Ken Thompson did the
>> first one (which was published a long time back). Hans Berliner did
>> another, but took two versions of "hitech". one smart/dumb, the other
>> slower but smarter, and played them vs each other, to see what would
>> happen. I think that was published in one of the advances in computer
>> chess books. I can summarize if you don't have it handy...
>
>I don't, so please do.
Obviously, you have still not re-read my article because it summarizes
many more self-play experiments than the two mentioned by Bob.
The below is pasted verbatim from the preprint of my article
"DarkThought Goes Deep" as published in the ICCA Journal 22(4)
and available electronically from our WWW page at URL
<http://wwwipd.ira.uka.de/Tichy/DarkThought/>.
=Ernst=
///////////////////////////////////////////////////////////////
************
Introduction
************
Deep searches with far look-ahead continue to fascinate the whole computer-chess community
because they promise to achieve ever stronger play for all decent programs. Thompson pioneered
the scientific investigation of the general relation between search depth and playing strength in
chess programs by his famous self-play experiments with the then reigning World Computer
Chess Champion BELLE in the early 1980s [55,56,199]. His experiments led to the surprising
result that the playing strength of BELLE increased almost linearly with search depth by roughly
200 rating points per ply for full-width searches of fixed depths ranging from 3-9 plies. Several
other researchers later confirmed Thompson's findings by self-play experiments with their own
chess programs HITECH, PHOENIX, THE TURK, and ZUGZWANG [28,114,151]. In Figure 1 of their
article [114] Junghanns et al. showed that in all these cases the winning percentages of the
program versions searching one ply deeper than their direct siblings remained range-bound
between 70%-80% with no clearly visible, let alone statistically significant, average downward
trends at the end of the 9-ply data curves. We thoroughly discuss the above mentioned self-play
research and further related works in Section 1.5.3.
In 1985 Newborn [156] introduced a technique different from self-play in order to study the
general relation of search depth and playing strength in chess programs. The rationale of
Newborn's novel approach sprang from the assumption that new best moves as discovered by
chess programs at higher search depths ought to represent better choices than the best moves
preferred at shallower depths. To this end, Newborn tracked the according behaviour of BELLE
for searches to fixed depths of 11 plies on a set of 447 test positions from real games. The close
correlation of his data with Thompson's earlier self-play results made Newborn propose an
interesting hypothesis concerning the playing strength of chess programs that we elaborate on in
Section 1.5.4.
Unfortunately, Newborn's new experimental methodology of observing the behaviour of deep
searches did not gain much popularity. Nobody followed his initial example until Junghanns et al.
let PHOENIX and THE TURK search roughly 1,000 positions from self-play games to fixed depths
of 9 plies while recording all the new best moves beside other information [114]. In 1997 Hyatt and
Newborn himself then conducted another behavioural experiment with Hyatt's chess program
CRAFTY searching 347 new test positions to a fixed depth of 14 plies each [108]. This experiment
revealed the astonishing fact that the rate of new best moves as chosen by CRAFTY at high
search depths of 9-14 plies remained quite steady around 15%-17% on average and hardly
decreased anymore. In order to check whether this exceptional behaviour may actually hold for
modern chess programs in general or if it was only an artifact of the specific CRAFTY
implementation as used by Hyatt and Newborn in 1997, we repeated their experiment with our
own chess program DARKTHOUGHT [90].
[...]
*******************************************************
Relating Search Depth to the Strength of Chess Programs
*******************************************************
To the best of our knowledge, Gillogly and Newborn in 1978 independently reported the earliest
attempts at modeling the relationship between the playing strength of chess programs on one hand
and the available computing power or search depth on the other. Gillogly introduced his so-called
``technology curve'' [73] that plotted the playing strength against what he called ``machine
power'' on a logarithmic scale. Newborn related the numbers of nodes as searched by different
chess programs in three minutes (average time per move in tournament games) to the playing
strengths of the very same programs as derived from their actual performances in
tournaments [157,158]. Later on, Levy [131] and Levy and Newborn [124] refined Newborn's
initial scheme by contrasting the highest rated tournament performances of the best chess
programs with the years of their achievement. All these comparisons inevitably led to speculative
extrapolations of the graphs which Levy characterized to the point as the ``meta-science of
prediction in computer chess'' in his latest article about the subject in 1997 [123].
Self-play matches as pioneered by Thompson with his chess machine BELLE in 1982 [199]
represent a more rigorous method of investigating the relationship between available computing
power or search depth and the playing strength of chess programs. A great advantage of such
matches is that the encountered winning percentages quantify the differences in playing strength
of the various participating versions of the same program. Despite lingering doubts and questions
regarding the magnitude of self-play rating differences [28], many researchers felt and still feel
that self-play is the best of the available approaches in order to assess the expected ``diminishing
returns'' of additional search in chess. In the context of self-play matches the presence of
diminishing returns should lead to notably reduced winning percentages of the deeper or longer
searching program versions with the progression towards higher search depths and search times.
Up to now nobody proved the existence of diminishing returns for self-play in computer chess by
means of statistically significant experiments. For matches of only 20 games, even high winning
percentages of 70%-75% barely suffice to decide with good confidence that the victor is indeed
stronger than his opponent in general. Consequently, such small sample sizes do not allow for any
confident quantification of the absolute rating differences between the opponents. In order to
confidently assess rating differences of 70 points we need about 500 games per match and for
differences of 40-50 rating points the number of necessary games per match increases to 1000.
Hence, we completely agree with Mysliwietz [151] who already criticized the statistical
insignificance of many famous self-play experiments in computer chess back in 1994. Based on
these explanations it is now easy to understand why we label many experimental results as ``not
statistically significant'' while describing all prominent self-play experiments in computer chess
below.
1982: Thompson [199].
Thompson's pioneering experiment featured 100 self-play games with matches of 20
games each between versions of BELLE differing by exactly one ply in lookahead for fixed
search depths of 3-8 plies. The gain in playing strength averaged at 246 rating points per
ply of search. The experiment showed no diminishing returns at any search depth but its
results are not statistically significant anyway.
1983: Condon and Thompson [55].
In the second experiment, Condon and Thompson let BELLE self-play 300 games in
round-robin style with matches of 20 games each between all program versions for fixed
search depths of 3-9 plies. The gain in playing strength averaged at 217 rating points per
ply of search. Now the observed ratings hinted at limited diminishing returns from a fixed
search depth of 6 plies onwards. Yet the results of the experiment are not statistically
significant.
1988: Szabo and Szabo [191].
The two Szabos determined the technology curve of their chess program TECHMATE that
self-played 6882 games on two Atari ST computers linked together via their MIDI ports.
The number of games per match between longer and shorter searching versions of the
program varied strongly from a minimum of 32 to a maximum of 1367. The gain in playing
strength averaged at 156 rating point per doubling of available search time (computing
power). The experimental data indicated slight diminishing returns at longer search times.
Several results from the experiment are statistically significant. Unfortunately, however,
this does not hold for the results of the most interesting program versions with really long
search times. They simply did not play enough games to draw reliable conclusions.
1990: Berliner et al. [28].
The HITECH team made their chess machine self-play 1056 games in a round-robin
setting with matches of 16 games each between all program versions of HITECH and
LOTECH (a variant of Hitech scaled down knowledge-wise) for fixed search depths of 4-9
plies. The gain in playing strength averaged at 195 rating points per ply of search for
HITECH and at 232 rating points per ply for LOTECH. The overall ratings showed signs of
limited diminishing returns starting at a fixed search depth of 6 plies. But there was no clear
trend of diminishing returns at higher search depths and the experimental results are not
statistically significant.
1994: Mysliwietz [151].
In his own experiment, Mysliwietz let the parallel chess program ZUGZWANG self-play
450 games with 50 games per match between program versions that differed roughly by a
factor of 2 in search speed due to varying numbers of allotted processors. The gain in
playing strength averaged at 109 rating points per doubling of search speed for 9
successive doubling steps. The observed ratings do not exhibit any diminishing returns at
all. Most of the match results from this experiment are statistically significant in the sense
that they allow for the discrimination of stronger and weaker opponents with 95%
confidence. The true general rating gain for the version of ZUGZWANG used in the
experiment lay in the estimated range of 76-143 points per ply of search with 95%
confidence. Thence, Mysliwietz's experiment does neither support nor falsify the
hypothesis of diminishing returns for self-play of ZUGZWANG with good confidence.
1997: Junghanns et al. [114].
The self-play experiment with Junghanns' chess program THE TURK featured 480 games
with matches of 80 games each between program versions differing by exactly one ply in
lookahead for fixed search depths of 3-9 plies. The gain in playing strength averaged
around 200 rating points per ply of search.1.8 The winning percentages of the deeper
searching versions of THE TURK actually increased steadily from fixed search depths of 6
plies onwards, thus even hinting at additional gains in returns for higher search depths
rather than diminishing ones. The match results from this experiment are statistically
significant in the sense that they allow for the discrimination of stronger and weaker
opponents with 95% confidence. As in the case of Mysliwietz's experiment, however, the
resulting data of the THE TURK neither supports nor falsifies the hypothesis of diminishing
returns for self-play of this program with good confidence.
In their article Junghanns et al. [114] then continued to look for diminishing returns by means of
other metrics than self-play. They finally claimed to have found empirical evidence in this respect.
According to their explanations the low search quality of chess programs (i.e. their high error
probability) and the abnormally large lengths of self-play games inadvertently hide the doubtlessly
existent diminishing returns in computer chess. Although we greatly appreciate Junghanns et al.'s
new trial aimed at the better understanding of diminishing returns in computer chess, we are not
convinced that their claims hold when subjected to rigorous methodological and statistical testing.
In our opinion the quest for indisputable and statistically significant demonstrations of diminishing
returns for additional search in computer chess still remains to be concluded.
Robert Hyatt
: <hy...@crafty.cis.uab.edu> wrote:
:> There have been at least two such experiments. Ken Thompson did the
:> first one (which was published a long time back). Hans Berliner did
:> another, but took two versions of "hitech". one smart/dumb, the other
:> slower but smarter, and played them vs each other, to see what would
:> happen. I think that was published in one of the advances in computer
:> chess books. I can summarize if you don't have it handy...
:>
: I don't, so please do.
: Henri
OK... Advances in Computer Chess V, page 11, "Measuring the performance
potential of chess programs" by Berliner, Goetsch, and Campbell.
They made 6 versions of "hitech" named H4, ..., H9. Ditto for 6
versions of "lotech" named L4, ..., L9. Lotech == Hitech but the
eval in Lotech included material, piece centrality and pawn structure,
but no king safety or other specific tidbits of knowledge.
Here are the results:
L4 L5 L6 L7 L8 L9 H4 H5 H6 H7 H8 H9 tot
L4 -- 3 6 0 0 0 4 6 0 0 0 0 7.0
L5 13 -- 9 .5 0 0 8 4 0 0 0 0 28.5
L6 16 13 -- 2 1.5 0 12.5 6.5 4 1 0 0 56.5
L7 16 15.5 14 -- 2 0 12.5 9.5 5.5 3 0 0 79.0
L8 16 16 14.5 14 -- 2 15 12.5 7 5 2.5 1 105.5
L9 16 16 16 15 14 -- 15.5 14 9.5 8.5 2 2.5 129.0
H4 12 8 3.5 3.5 1 0.5 -- 2.5 1.5 .5 0 0 33.0
H5 16 12 9.5 6.5 3.5 2 13.5 -- 4 1.5 0 0 68.5
H6 16 16 12 10.5 9 6.5 14.5 12 -- 4 1 0 101.5
H7 16 16 15 13 11 6.5 15.5 14.5 12 -- 3 1 124.5
H8 16 16 16 16 13.5 14 16 16 15 13 -- 3 154.5
H9 16 16 16 16 13.5 13.5 16 16 15 15 13 -- 168.5
If you study those, first look at Ln vs Ln to see what a ply means to
a 'fast/dumb' program. ie L9 beats L8 14/20 games. Then compare Ln to
Hn, and you notice that L9 breaks even with H6. They are equal, yet
L9 searches 3 plies deeper. And then finally Hn to Hn shows that one
ply (Hn to Hn-1) is a significant advantage.
I wish the numbers included deeper depths... but that is the gist of
the paper.
Let me know if you have specific questions...
Henri H. Arsenault
(Ernst A. Heinz) wrote:
> Obviously, you have still not re-read my article because it summarizes
> many more self-play experiments than the two mentioned by Bob.
>
I guess I have a selective memory (or more probably, when I read your
article, I skipped some parts and then forgot that I had done so)...
Anyway thanks for the information. This question is a lot move difficult
that I thought, and a lot more research on the subject has been carried
out that I had imagined.
Henri
Henri H. Arsenault
<hy...@crafty.cis.uab.edu> wrote:
> I wish the numbers included deeper depths... but that is the gist of
> the paper.
>
> Let me know if you have specific questions...
>
Yes, excuse my ignorance, but is it possible for alpha-beta pruning to
exclude the best move? For example, let us say that all ply levels below
some depth, say 10, showed the move as very bad (say 50 other moves looked
better), but then an 11-ply search showed the move to yield a winning
advantage, would the move be still there to evaluate? If so, how does a
pruning algorithm eliminate moves? I realize that this example may not be
very realistic, but you get the idea...
The point is whether an algorithm that would "solve" chess (assuming a
fast enough computer) using known techniques could miss the best move in a
position, therefore NOT "solving" chess.
Henri
rpo...@netscape.net
ars...@phy.ulaval.ca (Henri H. Arsenault) wrote:
> In article <7ahcj2$ir6$1...@juniper.cis.uab.edu>, Robert Hyatt
> <hy...@crafty.cis.uab.edu> wrote:
>
> > I wish the numbers included deeper depths... but that is the gist of
> > the paper.
> >
> > Let me know if you have specific questions...
> >
> Yes, excuse my ignorance, but is it possible for alpha-beta pruning to
> exclude the best move? For example, let us say that all ply levels below
> some depth, say 10, showed the move as very bad (say 50 other moves looked
> better), but then an 11-ply search showed the move to yield a winning
> advantage, would the move be still there to evaluate? If so, how does a
> pruning algorithm eliminate moves? I realize that this example may not be
> very realistic, but you get the idea...
No, the best move won't ever be 'missing' from the 11-ply search. Alpha-beta
doesn't base the results of a depth n search on the results of an earlier,
shallower search. For each deeper search, it is starting (essentially) from
scratch, searching a single line to depth n, backing up a move and trying the
other choices, backing up two moves, making a different choice, then trying
the various possibilities, etc. until it finishes the last of the choices at
depth 1.
The only lines or positions that are eliminated are ones where the best line
from position B is guaranteed worse for the computer than the worst case
scenario from position A, _and_ the computer can force the position to A or B
at will. Then the computer rejects all positions arising from position B.
It doesn't have to check how bad the opponent can make it suffer (lose 2
pawns or 3?), as long as it knows that no matter what moves it makes, the
opponent can make _good enough_ moves to make it worse off than if it had
chosen to follow position A.
I know this last paragraph could have been worded better, but it is tricky
wording. Basically, if the best move can be recognized within a given depth,
then it will never be eliminated because the pruning happens on the way back
down to the original position, _after_ the computer knows that it would not
make a move to give the opponent a chance on that line because it knows it
would end up worse off than if it took a different line.
This analysis does not depend on the shallower searches. These searches
mainly just help us speed things up a little. For example, the best moves in
a 10-ply search are probably for the most part still the best moves. We also
can get short cuts on information about how good or bad a position is, but it
will never cause us to say that the best line is not worth examining. Other
very good moves may get junked, since we already found a better one, but the
best one will not get eliminated.
>
> The point is whether an algorithm that would "solve" chess (assuming a
> fast enough computer) using known techniques could miss the best move in a
> position, therefore NOT "solving" chess.
>
> Henri
>
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
Robert Hyatt
: In article <7ahcj2$ir6$1...@juniper.cis.uab.edu>, Robert Hyatt
: <hy...@crafty.cis.uab.edu> wrote:
:> I wish the numbers included deeper depths... but that is the gist of
:> the paper.
:>
:> Let me know if you have specific questions...
:>
: Yes, excuse my ignorance, but is it possible for alpha-beta pruning to
: exclude the best move?
No. So long as you remember the 'depth' issue. IE a 9 ply search with
minimax will take forever. A 9 ply search using alpha/beta with the same
search extensions and evaluation will take roughly sqrt(minimax) time.
And it will produce exactly the same score and PV if you ignore some minor
issues dealing with hashing and possible differences in move ordering.
: For example, let us say that all ply levels below
: some depth, say 10, showed the move as very bad (say 50 other moves looked
: better), but then an 11-ply search showed the move to yield a winning
: advantage, would the move be still there to evaluate? If so, how does a
: pruning algorithm eliminate moves? I realize that this example may not be
: very realistic, but you get the idea...
Alpha/Beta is a backward pruning idea. Try a simple example: After
carefully searching the first move I find, I discover that the position
deep in the tree is _equal_. I can't find a way to improve either white
or black assuming I make the first move. Now, when I try my second move,
the very first move I try for my opponent wins a pawn. Should I continue,
knowing that he is going to win _at least_ a pawn (since my first move
choice was _equal_) or should I continue searching all of his choices to
see if he can win more than a pawn? Alpha/beta quits on that move after
this point, because losing a pawn at the root (move 2) is worse than
an equal score. I don't care _how_ bad the score is (-pawn or -queen)
I only care that it is < 0.
That is how alpha/beta works...
: The point is whether an algorithm that would "solve" chess (assuming a
: fast enough computer) using known techniques could miss the best move in a
: position, therefore NOT "solving" chess.
it would work, but it would take a _long_ time... :)
: Henri
Jesper Antonsson
18029915...@descartes.phy.ulaval.ca>:
>In article <7ahcj2$ir6$1...@juniper.cis.uab.edu>, Robert Hyatt
><hy...@crafty.cis.uab.edu> wrote:
>
>> Let me know if you have specific questions...
>>
>Yes, excuse my ignorance, but is it possible for alpha-beta pruning to
>exclude the best move? For example, let us say that all ply levels below
>some depth, say 10, showed the move as very bad (say 50 other moves looked
>better), but then an 11-ply search showed the move to yield a winning
>advantage, would the move be still there to evaluate? If so, how does a
>pruning algorithm eliminate moves? I realize that this example may not be
>very realistic, but you get the idea...
Lets see if I get first. :-) This explanation of alpha-beta requires
knowledge of the basic mini-max algorithm. Have a piece of paper and a
pen ready and draw the following tree:
R (for root) Maximizing node
R1 R2 (children) Minimizing node
R21 R22 (children to R2) Maximizing node
1. Now, assume that you have searched R1 and found that position to be
worth 2.00 pawns, for example. Now you know that R will *at least* have
the value 2.00, right?
2. But maybe the move leading to position R2 is better? We start searching
R2, and go to R21 first. Lets assume that position is worth 1.50 pawns.
Now you know that R2 will be worth *at most* 1.50, right?
3. Since you already, without searching R22, know that R2 is inferior to
R1, you don't bother with R22, and just throw away R2. (If you decide
to search one ply deeper in the next iteration, you start from scratch,
more or less, and R1 and R2 will be considered again.)
4. Generalize to all interior nodes in the tree.
5. Be glad that you will be able to reach about double depth without
sacrificing any accuracy at all!
Hope this was clear.
Jesper
Henri H. Arsenault
<330EF4826602935F.08100E41...@library-proxy.airnews.net>,
Jesper Antonsson <jes...@ctrl-c.liu.se> wrote:
> Hope this was clear.
>
very clear, thanks.
Henri