Heinz, Hyatt and Newborn next best move paradox
Jesper Antonsson
<7col44$9uo$3...@juniper.cis.uab.edu>:
>Remember that everyone is interested in the "top" of the curve. IE we
>know that going from 1 to 2 plies is significant. and that going from 2
>to 3 is significant. The big question is, what about going from 13 to
>14? There has been a lot of speculation that programs have reached
>'tactical sufficiency' already. IE another ply won't help at all. And
>based on what Monty, and then Ernst discovered, an extra ply on the top
>of the search _does_ make a difference in skill. And that was what we
>wanted to know.
I have a hard time understanding how anyone could propose that greater
search depth doesn't matter. It seems easy to conduct a comp-comp
experiment that would give rapid evidence to the contrary. Nevertheless,
the tests conducted by you and Ernst are very interesting, as they say
something about how far we have come, how much we can expect in the
future and so on.
To me it seems like it would be good to conduct the same experiments with
a larger set of positions, since the standard deviation is much larger
than what you can expect the difference from ply to ply to be. Until the
standard deviation is brought down a bit, it doesn't seem to be much use
to extend the experiment to greater ply depths than 16.
Jesper
Henri H. Arsenault
<8A709382003A4D24.D52A740B...@library-proxy.airnews.net>,
Jesper Antonsson <jes...@ctrl-c.liu.se> wrote:
> I have a hard time understanding how anyone could propose that greater
> search depth doesn't matter. It seems easy to conduct a comp-comp
> experiment that would give rapid evidence to the contrary. Nevertheless,
> the tests conducted by you and Ernst are very interesting, as they say
> something about how far we have come, how much we can expect in the
> future and so on.
>
As far as I know, no one proposes that search depth doesn't matter for low
depths (say less than 14); the question is does this continue and if so
how far?
Consider the following: let us suppose that search depth DOES always make
a difference, say all the way up to say, 25 plies ahead. And let us assume
for simplicity that the probability of "new best moves" remains the same
for each additional ply. By this I mean that whatever depth one searches
at, if one goes just one more ply deeper, there is a fixed probability
that a "better" move would be found.
If this were true, it would mean that there is no such thing as a "best
move" for any search depth less than 25! Indeed, this would imply that
what one is doing when playing chess is not to look for the best move, but
to look for a move that gives the opponent the maximum chance to make a
mistake that can be spotted within the search depth that is being used, or
to exploit such a mistake that has just been made. In other words, a "bad"
move would be a move that does not yield an advantage to the opponent at a
depth of N, but one that DOES yield such an advantage at depth N+1.
But our assumption that the probability that there is a better move at ply
N+2 is the same as that for ply N+1 means that if the two computers are
looking at the same ply depth, it is just as likely that there is an even
"better" move for the opponent at ply N+2.
This means finally that a game of chess would be nothing more than a game
of chance, with the loser being the one that falls by chance into a "hole"
which happens to be a "bad" move for a large number of successive plies!
So there is good reason to believe that there is a horizon beyond which
looking deeper does not significantly increase the probability of finding
a better move.
Henri
Henri H. Arsenault
<Ev...@nym.alias.net> wrote:
> You miss the point that there is no competitive program searching to a
> fixed depth. In so far your arguments are useless.
>
Every competitive program searches to a LIMITED depth because of time
limits, so the discussion about fixed depth is relevant. But my arguement
is not so much directed towards the question of how to make a competitive
engine as towards the question of the practical solvabioity of chess
assuming speeds high enough to reach 20 plies or more (not feasible now).
> Computers don't look at a fixed ply depth. If they did, the deeper
> searcher would win the tournament. No doubt.
Everything else being equal, the deeper searcher will win by definition,
if there is no horizon beyond which searching deeper yields no better move
(but results by Hyatt, Heinz and others suggest that there is no horizon,
at least not before 15-ply). My whole point deals with the consequences of
whether this is true or not for deeper searches.
>
> >This means finally that a game of chess would be nothing more than a game
> >of chance, with the loser being the one that falls by chance into a "hole"
> >which happens to be a "bad" move for a large number of successive plies!
>
> Why?
>
Because searching one ply deeper would always have the same probability of
finding a better move for either side, so that the winner could suddenly
become the loser.
> >So there is good reason to believe that there is a horizon beyond which
> >looking deeper does not significantly increase the probability of finding
> >a better move.
>
> Not convincing.
>
What can I say? If my reasoning is wrong, there must be a logical flaw in
it somewhere. Please show me where it is.
Henri
Robert Hyatt
: In article
: This means finally that a game of chess would be nothing more than a game
: of chance, with the loser being the one that falls by chance into a "hole"
: which happens to be a "bad" move for a large number of successive plies!
: So there is good reason to believe that there is a horizon beyond which
: looking deeper does not significantly increase the probability of finding
: a better move.
: Henri
This is what many think. But at least thru depth 14/15 it doesn't seem
to be true. A few years ago, we were seeing "going beyond 12 is not going
to help any". Now it is going beyond 15 won't help. And we have just about
disproved that. _IS_ there a limit? I don't know. But so far, I don't see
anything that suggests yes, and a bit of data that suggests no, since at
least we know going to 14/15 still improves the search accuracy.
--
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
Dann Corbit
So there is a limit.
;-)
Until programs get to this point from the opening (read "never") deeper will
be better. The real question is how to get there. Clever application of
fast & forceful or intensive knowledge based or both? Could something like
Otter be brought to bear on the problem, or is there an application of AI
that might prove fruitful?
But the deeper the better.
--
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
C.A.P. FAQ: ftp://38.168.214.175/pub/Chess%20Analysis%20Project%20FAQ.htm
Henri H. Arsenault
<dco...@solutionsiq.com> wrote:
> Once you have found win, lose, or draw, there is no point searching deeper.
> So there is a limit.
True, but unless there is a forced mate in sight or not enough material to
mate, there is always the possibility that just beyond the horizon is a
killer move that will turn the game around (if the hypothesis that the
"next best move" phenomenon goes on for almost any depth and for almost
any position).
Henri
Jesper Antonsson
>Consider the following: let us suppose that search depth DOES always make
>a difference, say all the way up to say, 25 plies ahead. And let us assume
>for simplicity that the probability of "new best moves" remains the same
>for each additional ply. By this I mean that whatever depth one searches
>at, if one goes just one more ply deeper, there is a fixed probability
>that a "better" move would be found.
I think it so intuitive that more search depth will give better results
until at least 80 ply, and that the probability of "new best moves"
will decrease with each new ply, that I really don't need any proofs.
What I am interested in is more data to establish if these probabilities
follow an exponential curve, and if so, what the parameters are (to
make good extrapolations).
When you have established this, it would be really interesting to see
the same experiments with programs that uses different heuristics. If
my assumption of an exponential curve holds, this experiment would tell
how large a percentage the different programs find the objectively
best move. (I wrote more on this in another post a few weeks ago.)
Perhaps we would find that enough reliability in determining the
parameters can be obtained by doing the Hyatt/Ernst experiment at low
plies. If so, this would provide an *excellent* objective method of
optimizing and testing chess programs heuristics automatically!
Opinions, anyone?
Jesper Antonsson
Steffen A. Jakob
[...]
> Take a random function to evaluate the final positions.
> Search one ply deeper.
> You will win.
> (Don Beal some years ago in the ICCA-Journal).
I don't understand this. What do you mean by random function?
Greetings,
Steffen.
--
Steffen A. Jakob | "Victory goes to the player who makes the
ste...@jakob.at | second-to-last mistake."
http://www.jakob.at/ | (Savielly Grigorievitch Tartakower)
Henri H. Arsenault
<C64119ED8CF3FD15.502AB324...@library-proxy.airnews.net>,
Jesper Antonsson <jes...@ctrl-c.liu.se> wrote:
> I think it so intuitive that more search depth will give better results
> until at least 80 ply, and that the probability of "new best moves"
> will decrease with each new ply, that I really don't need any proofs.
> What I am interested in is more data to establish if these probabilities
> follow an exponential curve, and if so, what the parameters are (to
> make good extrapolations).
>
That is what I like to think too, but so far there is no evidence that the
probability decreases with each additional ply. That is at the nub of the
whole question of whether chess is solvable in principle without going all
the way through.
My point of the previous message was to investigate the consequences of
the hypothesis that the probability does NOT decrease.
Of course I also would like to see the numbers that you suggest...
Henri
Robert Hyatt
: Elisabeth van Aaring <Ev...@nym.alias.net> writes:
: [...]
:> Take a random function to evaluate the final positions.
:> Search one ply deeper.
:> You will win.
:> (Don Beal some years ago in the ICCA-Journal).
: I don't understand this. What do you mean by random function?
Don Beal wrote an article about a program with a pure random number
generator for the eval. And he found that deeper depth still helped,
because of an unexpected property of uniform random numbers:
say you search a node with two branches. the probability for getting a
high eval is lower than when you search a node with 30 branches, because
30 calls to the RNG will likely produce a bigger number. So that this
'random number' evaluation actually turns into a form of mobility.
And it worked, amazingly...
: Greetings,
: Steffen.
: --
: Steffen A. Jakob | "Victory goes to the player who makes the
: ste...@jakob.at | second-to-last mistake."
: http://www.jakob.at/ | (Savielly Grigorievitch Tartakower)
--
Henri H. Arsenault
<Ev...@nym.alias.net> wrote:
> Use a random function to "evaluate" the positions in the chess program.
>
>
> value = rand();
>
> Now take your program, do a fixed depth search, e.g. 4 plies. The other
> program, everything else being equal, searches 5 plies. This
> 5-ply-searcher will outperform the 4-ply-searcher in a match. Just with
> a random evaluation!
> Funny, but true. And it can be explained (mobility).
>
If this is true, it would justify my suspicion that a narrow but deeper
search (what I called the 2/2/2 strategy) yields better results than a
full-width search, because what you are saying is that it is better to
choose at random one ply deeper than to take the "best" evaluation one ply
less deep.
Of course most serious researchers on this forum believe that this is not
the case. So what evidence do you have to justify your statement?
Henri
Dann Corbit
news:arseno-1903...@descartes.phy.ulaval.ca...
I have a notion along these lines:
The number of positions examined should be a function of distance from the
root. For instance, we might brute force everything out to 8 plies. Then
normal null move and the like out to 10 ply. Then explore the three or four
most promising lines out to 12 ply. Then explore the 2 best out to 13
plies. Something like that. I have observed that while "changing its mind"
does continue to happen about 15% of the time with each new ply, it becomes
less and less probable that it will be a move that has not been chosen as
the best in one of the previous plies. It is "all over the board" at first,
but then it usually settles down to a few good options.
RDavis101
>
><C64119ED8CF3FD15.502AB324...@library-proxy.airnews
Some time ago someone on this group mentioned that there are openings in which
a particular move that doesn't look especially relevant given the current
position has massive consequences that aren't known for something like 40 ply.
I forget which opening they mentioned. However, these are the kinds of moves
that computers can't yet see because of the horizon effect. If such openings
are common, then I would think that you can expect continued returns on the
search up to at least 40 ply. If they are uncommon, then maybe not. So maybe
someone with a broad knowledge about openings would be in a position to shed
some light on the question.
Roger
Robert Hyatt
: In article <10O3LN-0...@drule.org>, Elisabeth van Aaring
: <Ev...@nym.alias.net> wrote:
:> Use a random function to "evaluate" the positions in the chess program.
:>
:>
:> value = rand();
:>
:> Now take your program, do a fixed depth search, e.g. 4 plies. The other
:> program, everything else being equal, searches 5 plies. This
:> 5-ply-searcher will outperform the 4-ply-searcher in a match. Just with
:> a random evaluation!
:> Funny, but true. And it can be explained (mobility).
:>
: If this is true, it would justify my suspicion that a narrow but deeper
: search (what I called the 2/2/2 strategy) yields better results than a
: full-width search, because what you are saying is that it is better to
: choose at random one ply deeper than to take the "best" evaluation one ply
: less deep.
: Of course most serious researchers on this forum believe that this is not
: the case. So what evidence do you have to justify your statement?
: Henri
I don't think he said that... the experiment simply showed that even with
a 100% random evaluation, no material, no mobility, no pawn structure, just
eval=Random();, that a N ply search would lose to an N+1 ply search, simply
because the N+1 ply search sees 'more'. "more" is a bizarre thing here, but
lots of random numbers will produce some big ones, while a few won't. And if
you gave up your queen, positions below that will get smaller numbers since
there will be far fewer moves.
It was an interesting experiment.
But I don't think _anyone_ thinks that normal_crafty(N) would lose to Random(N+1)
where N=depth.
But that would be interesting to see what the 'increment' needs to be before that
_does_ happen. IE normal_crafty(N) may lose to Random(2N) or something like
that... totally unknown at present.
Robert Hyatt
:>In article
: Roger
If you look at any of the 'cute' openings... KGA, Latvian, Evans,
Marshal, to name but a few, there are _always_ a few of these lines
that have been calculated way out. And a few of those are 'tough'
lines that might look (to a computer) as a win for white (in the
Latvian) until the search finally gets deep enough to expose the kicker
at the end that breaks the position for white badly. I don't think they
are very common, and I combat these by (a) randomness in book line
selection from a big book, so that getting crafty to follow such a line
is _very_ difficult; (b) automatic learning so that once I lose such a
game I won't play it again. Although that one loss might be _the_ loss
you don't want...
j...@yktvmv.watson.ibm.com
on 19 Mar 1999 16:45:07 GMT,
Robert Hyatt <hy...@crafty.cis.uab.edu> writes:
>Steffen A. Jakob <sp...@jakob.at> wrote:
>: Elisabeth van Aaring <Ev...@nym.alias.net> writes:
>
>: [...]
>
>:> Take a random function to evaluate the final positions.
>:> Search one ply deeper.
>:> You will win.
>:> (Don Beal some years ago in the ICCA-Journal).
>
>: I don't understand this. What do you mean by random function?
>
>Don Beal wrote an article about a program with a pure random number
>generator for the eval. And he found that deeper depth still helped,
>because of an unexpected property of uniform random numbers:
>
>say you search a node with two branches. the probability for getting a
>high eval is lower than when you search a node with 30 branches, because
>30 calls to the RNG will likely produce a bigger number. So that this
>'random number' evaluation actually turns into a form of mobility.
>
>And it worked, amazingly...
Similarly adding a small amount of random noise to a real
evaluation function might improve things since it will tend to bias
the search towards parts of the tree where you have a lot of
reasonable choices and your opponent does not. This is good since
as the game progresses and the programs see deeper the program with
more choices is less likely to find itself trapped in unfavorable
lines. Has anyone tried this?
James B. Shearer
Robert Hyatt
: In article <7ctuuj$qar$3...@juniper.cis.uab.edu>,
Dang... I was hoping you were volunteering. It would be an
interesting experiment...
:)
Steffen A. Jakob
> Steffen A. Jakob <sp...@jakob.at> wrote:
> : Elisabeth van Aaring <Ev...@nym.alias.net> writes:
>
> : [...]
>
> :> Take a random function to evaluate the final positions.
> :> Search one ply deeper.
> :> You will win.
> :> (Don Beal some years ago in the ICCA-Journal).
>
> : I don't understand this. What do you mean by random function?
>
> Don Beal wrote an article about a program with a pure random number
> generator for the eval. And he found that deeper depth still helped,
> because of an unexpected property of uniform random numbers:
>
> say you search a node with two branches. the probability for getting a
> high eval is lower than when you search a node with 30 branches, because
> 30 calls to the RNG will likely produce a bigger number. So that this
> 'random number' evaluation actually turns into a form of mobility.
>
> And it worked, amazingly...
Cool! :-)
Ernst A. Heinz
> I have observed that while "changing its mind"
> does continue to happen about 15% of the time with each new ply, it becomes
> less and less probable that it will be a move that has not been chosen as
> the best in one of the previous plies.
Dear Dann,
Please read my article "DarkThought Goes Deep" as published in the
ICCA Journal 21(4) and you will see that my quantitative data does
*not* support your observation above.
About 30%-50% of all new best moves of "Crafty" and "DarkThought"
represented "fresh ideas" (never chosen as best before!) even at
high search depths of 9 plies onwards.
An electronic preprint of my article is available from the WWW pages
of "DarkThought" 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
<hy...@crafty.cis.uab.edu> wrote:
>
> I don't think he said that... the experiment simply showed that even with
> a 100% random evaluation, no material, no mobility, no pawn structure, just
> eval=Random();, that a N ply search would lose to an N+1 ply search, simply
> because the N+1 ply search sees 'more'. "more" is a bizarre thing here, but
> lots of random numbers will produce some big ones, while a few won't. And if
> you gave up your queen, positions below that will get smaller numbers since
> there will be far fewer moves.
>
Hmm, ok, maybe I misunderstood; I thought he said that N+1 plies with a
random choice would beat a full-search N ply search. Still, what you say
would imply that the ratio of good moves is higher for n+1 than for N. Why
that should be is not clear to me. If there was a higher probability of
choosing more higly rated moves, then of course it would be true.
Henri
Steffen A. Jakob
The point is that in positions with many possible moves, the prob. is
higher to get a large value (we compute max of all random values) then
in positions with few legal moves. Therefore positions with more legal
moves will be prefered, which leads to the concept of mobility. This
is very surprising, isn't it?! :-)
Greetings,
Steffen.
Robert Hyatt
: <hy...@crafty.cis.uab.edu> wrote:
:>
:> I don't think he said that... the experiment simply showed that even with
:> a 100% random evaluation, no material, no mobility, no pawn structure, just
:> eval=Random();, that a N ply search would lose to an N+1 ply search, simply
:> because the N+1 ply search sees 'more'. "more" is a bizarre thing here, but
:> lots of random numbers will produce some big ones, while a few won't. And if
:> you gave up your queen, positions below that will get smaller numbers since
:> there will be far fewer moves.
:>
: Hmm, ok, maybe I misunderstood; I thought he said that N+1 plies with a
: random choice would beat a full-search N ply search. Still, what you say
: would imply that the ratio of good moves is higher for n+1 than for N. Why
: that should be is not clear to me. If there was a higher probability of
: choosing more higly rated moves, then of course it would be true.
: Henri
The idea is this: the 'random' eval simply leads the program toward
positions with the most 'moves', because move moves == more positions to
evaluate, giving that random number generator a chance to produce a big
number in the group.
If A searches to 5 plies, while B searches to 6, both using this approach,
basically B sees deeper ways to produce more mobility, while A sees one
ply less and will overlook some things that can be done.
IE the basic finding is that one more ply is better. Whether you have a
great eval or a purely random one.
bruce moreland
wrote:
Material balance is also being maximized.
You have a reduced chance of creating a large random value if you
don't get the dozen or so extra chances that you get by having your
queen on the board.
bruce
Steffen A. Jakob
Just for fun I added a random evaluation (with values in the range
[-250..250]) method to Hossa (I must not forget to remove it before
the next ICC login! ;-). As you can see white and black develop their
queen very fast to maximize the mobility. Here is the evaluation in
the initial position:
depth value time nodes pv
1 -232 0.02 2 1.c4
2/1 -18 0.03 4 1.h4
5/1 214 0.04 9 1.b1c3
? 2 -172 0.04 120 1.b1c3 a5
! 4 15 0.06 1466 1.b1c3 b6 2.a1b1
! 2/4 29 0.08 2055 1.a3 b8c6 2.h4
! 5/4 82 0.10 3358 1.e4 g8f6 2.f1c4 f6xe4 3.c4xf7 e8xf7
! 18/4 150 0.13 7549 1.f4 c6 2.a3
? 5 -180 0.30 28887 1.f4 a5 2.b4 a4
4/5 -170 0.36 35829 1.b3 e6 2.c1b2 f8d6
6/5 -58 0.47 49694 1.c3 b8c6 2.d1b3 e6 3.b3xe6 d7xe6
! 6 79 0.80 91270 1.b3 e6 2.a4 c6 3.c3
! 10/6 113 1.65 190172 1.e4 b8c6 2.a4 e6 3.d3
? 7 -13 6.14 683894 1.e4 b8c6 2.d1h5 g6 3.h5xg6 e6 4.g6xe6 f7xe6
10/7 45 7.89 853323 1.e3 c6 2.d1h5 g6 3.h5xh7 d8b6 4.h7xh8
8 38 20.40 2022853 1.e3 e6 2.d1h5 d8f6 3.e1e2 g8e7 4.h5xf7 e8xf7
5.a3 f6xb2
? 9 -25 5:17 29266406 1.e3 e6 2.d1h5 d8f6 3.f1b5 g6 4.g1f3 b6
Best wishes,
Robert Hyatt
: On 20 Mar 1999 17:56:17 GMT, Robert Hyatt <hy...@crafty.cis.uab.edu>
: wrote:
: bruce
I thought I mentioned that somewhere along the way... but you are
right.
and the idea is still 'cute'. Don's had his share of good ideas over
the years, and is often forgotten. Just remember "Selective search without
tears" which is the basis for the null-move search, among other things.
Thanks, Don. :)
Although I don't think I'll be doing a random eval until the hardware gets
better. Say 10^10 times faster or something. :)
Bob
Henri H. Arsenault
Jakob) wrote:
> The point is that in positions with many possible moves, the prob. is
> higher to get a large value (we compute max of all random values) then
> in positions with few legal moves. Therefore positions with more legal
> moves will be prefered, which leads to the concept of mobility. This
> is very surprising, isn't it?! :-)
>
Maybe, but you could call it "keeping your options open". Assuming that
the ratio of good moves to bad moves is about the same, then clearly
choosing a position with more mobility gives the opponent more
opportunities to make mistakes, especially if you are looking one ply
deeper than him.
Henri
Dr A. N. Walker
> Looking one ply deeper implies an implicite mobility evaluation... At
> zero costs... astonishing...
Well, it's not *zero* cost, as you have to go that one
ply deeper and call a random-number generator. You could probably
get better results by saving a ply and returning a move count.
You don't need to generate all the moves, in general, just enough
to cause a beta-cutoff. All the usual null-move, killer moves,
transposition table, principal variation, etc stuff still works
just fine!
Perhaps more interestingly, though, this is a very
asymmetric evaluation function, as effectively you're just
counting mobility for one side. With White to move, you're
alternately trying to maximise White's mobility and, at the
next depth, minimise Black's. So, at one depth you'll be
trying, say, to centralise your queen, no matter what Black
is doing, and at the next you're trying to capture his queen,
no matter what happens to your pieces. This is not a good
way to exploit iterative deepening! Don's "random" program
might play even better if the depth is increased by two at
each iteration.
Oh, and note that actual [stale]mates are rather drastic
examples of mobility evaluation. Even with a random evaluation,
the program will still find forced mates -- and these will occur
quite frequently if both sides are playing semi-random moves.
--
Andy Walker, School of MathSci., Univ. of Nott'm, UK.
a...@maths.nott.ac.uk