Re: computer-go: A problem with understanding lookahead

[William Harold Newman <william.newman@xxxxxxxxxxx>]

On Tue, Jan 23, 2001 at 08:13:33PM -0500, Don Dailey wrote:
> 
>    X-Sender: ddyer@xxxxxxxxxxxxxxxxx
>    X-Mailer: QUALCOMM Windows Eudora Version 5.0.2
>    Date: Tue, 23 Jan 2001 16:02:46 -0800
>    From: Dave Dyer <ddyer@xxxxxxxxxxxxxxxxx>
>    References: <20010123160847.E8740@xxxxxxxxxxxxxxxxx>
>     <I1JHLB.A.i_E.Qegb6@xxxxxxxxxxxxxxxxx>
>    Mime-Version: 1.0
>    Sender: owner-computer-go@xxxxxxxxxxxxxxxxx
>    Precedence: bulk
>    Reply-To: computer-go@xxxxxxxxxxxxxxxxx
>    Content-Type: text/plain; charset="us-ascii"
>    Content-Length: 756
> 
>    At 02:59 PM 1/23/01, Heikki Levanto wrote:
>    >Dave Dyer <ddyer@xxxxxxxxxxxxxxxxx> wrote:
>    >> In go, there are no such metrics.
>    >
>    >Ok, idle speculation: What sort of metrics could be useful in go? Never
>    >mindthe branching facor, just speculate on what we could possibly use for
>    >determining if we like one position better than another?
> 
>    My point is precisely that there are no known metrics which are
>    both useful and computable, and not even a theoretical
>    framework exists that could lead to such metrics.
> 
>    Go has metrics "thickness" "influence" "alive" "dead" "heavy"
>    "overconcentrated" etc, but they are all essentially uncomputable.
>    Conversely, lots of computable things have been tried as proxies
>    for the real metrics, and none has been shown to be much use.
> 
> 
> All of the metrics in chess  are proxies for  the real things too.  In
> chess,  the goal is  to checkmate  the king, being   up in material is
> roughly corelated with the ability to do  this.  How much material you
> have is computable but  doesn't have to  do  with being  in checkmate.
> Being computable doesn't   mean much, 4+4  is computable  but probably
> won't help my chess program.   
> 
> I'm telling you, we  have the same exact problems  in Go and in chess,
> the  issue is just  clouded by the  fact that chess programs search so
> deeply that people think intelligent evaluation is going on.
> 
> Don

Chess has a useful exact metric -- forced win! -- which is useful in a
significant fraction of the game space. 

It's relatively straightforward to write a computer program which
reads out forcing sequences close to checkmate (at least all sequences
of checks, plus perhaps some search extension bonus for other kinds of
moves, e.g. moves which clobber king safety). It's also
straightforward to put together a database of won endgames. And you
can afford to do an N-ply search on top of that evaluation, for N=8 or
more. Just on that alone, you'll ambush amateur players from time to
time. Simply avoiding game states which aren't lost immediately by
these analyses is a nontrivial challenge for the club players I've
watched and played. Computers do it easily.

In Chess, once you're out of your opening book, you have a significant
chance of finding a forced win in, say, 8-12 plies of full-width
search. In Go at the same point in the game, even if you searched
80-120 plies, you'd have zero chance of finding a forced win, unless
you can make a huge breakthrough in position evaluation. So "searching
so deeply that people think intelligent evaluation is going on" ends
up means something hugely different in Chess than in Go.

Even if a Chess program is relatively clueless about where to go
within the safe subspace of the full game space, perhaps because of
the enormous difficulty of writing a useful approximate evaluation
function for Chess, the program still gains a lot from the way that
this relatively safe subspace (no provable win in N moves) is a twisty
maze through the full space, and it's a continuous challenge to stay
inside it. (It's a challenge for me at N=8 or so, and a challenge for
Kasparov at N=14 or so:-). Chess programs are sufficiently good at
dealing with this challenge that their advantage here helps them win a
fair number of games, both directly, and also indirectly by
constraining their opponents to avoid sharp situations where this
advantage would be telling. Go programs have no such advantage.

It's also interesting that writing a program to solve most Chess
problems I've seen (mate in N, or small endgame problems) is pretty
straightforward, while writing a program to solve Go problems
(tsume-go) seems to be quite a bit trickier. I'm not sure where that
fits into this, though.

-- 
William Harold Newman <william.newman@xxxxxxxxxxxxxxxxx>
software consultant
PGP key fingerprint 85 CE 1C BA 79 8D 51 8C  B9 25 FB EE E0 C3 E5 7C