Re: [computer-go] Pattern matching - example play

[Vincent Diepeveen <diep@xxxxxxxxx>]

At 20:07 2-12-2004 +0100, Heikki Levanto wrote:
>On Thu, Dec 02, 2004 at 03:33:10PM +0100, Vincent Diepeveen wrote:
>> 
>> A deeper brute force search is an absolute necessity to make it into the
>> dan levels with go software. Without that, the weakest chain is and will be
>> just some life&death tactics.
>
>Some searching is obviously necessary, but I am not at all convinced
>that we need a global full-board search. Unlike chess, go has many
>fairly (but usually not completely) localized problems, that IMHO need
>to be analyzed locally. 

In the 80s there were several dedicated computers splittin gbetween
localized search and 1 global search.

Let me first show the problem of a global search in go:

A global search in go has just 1 disadvantage and that's that you get less
nodes a second. So basically it requires you to implement a lot of go
knowledge near the leafs in order to figure out what moves to try further on.

So the problem of a global search is very clear: it is a lot of
professional effort to make it and requires go knowledge. At least dan level.

The disadvantage of a localized search is also trivial: it will play
forever at a very weak level.

It is not true that in go problems can get solved locally easily because if
you just search whether you can save this certain group X, i could perhaps
create threats elsewhere which occupy an entire corner suddenly as i have
played a move at that spot which takes care i can win the fight elsewhere.

There is another 100 trivial examples possible why local search sucks.

Basically the advantage is that it is much easier to program it.

So in the end the local search will get slowly extinct and everyone will do
a global board search.

Now the only question is: "WHEN".

Because there is break even considerations. Like that most of you play at a
dead slow P4 whereas an A64 is already 2 times faster. And a dual opteron
is another 2 times faster than an A64 and so on. So a free factor 4, or in
short 1 ply extra which could for some of you already break even.

>It may be possible to combine the local results into a global full-board
>search tree, but it is not (yet?) obvious how that should be done.

It is impossible to let a localized search which runs without using the
evaluation function, to let it see the same like a global search. A global
search always will outgun it of course bigtime.

>I would not completely write off higher-level planning and neural nets,
>and other fancy theories. Many of them have shown their values in

I have written them off after i learned a lot about them and experimented
with them myself. Additional it won't be a surprise to you that worlds
biggest ANN experts are chatting to the programmers so also to me and they
can exactly define the problem for you.

The problem is that game playing programs each time play an unique game. So
they should train in order to recognize something they didn't train at!

That's a contradiction and therefore it is not possible.

So that is completely in contradiction to recognizing voice. In theory a
voice is always the same. Has the same pattern, so a neural net is capable
of recognizing that. Because it can train for a voice X and then you later
try to recognize it, you *exactly* try to find voice X.

So again, in go if you train it to see that in position P the white side is
 better and therefore winning, it will recognize P if it sees P again.

However the problem in go is that the chance you get position P on the
board is zero as every game is unique, so it will not recognize suddenly
that what it has at the board is bad.

We can have lengthy discussions, but the majority of ANN top researchers
agree with me here that for game playing ANN is completely useless.

And believe me, nearly all of them really TRIED it. They weren't convinced
that easily that their black box isn't working for game playing.

Yet no one is stopping you believing in a black box that can solve the game
without much calculation. A formula X based upon a few artificial neurons.

However if such a formula F would exist and if you take into account that a
manual implementation of such an evaluation function is pretty
straightforward, then why didn't some clever go programmer create that
function manual yet?

Vincent

>other games. Perhaps some features of go are closer to some other game
>than chess...

Good news for us all there. Go, Chess, Chinese Chess and Shogi are very
related games. Checkers is far away from that (nullmove isn't working as
the start position is pretty close to ideal and making a nullmove is
therefore real good, additionally the game is not symmetric but asymmetric,
so there is in fact a first move that is LOSING for white amazingly)

>But of course, unless and until we see really strong programs, we can
>only speculate. From my part it is quite idle speculation, as I am not
>even writing a go program.

That's what mailing lists are for. Note i do have a go program but soon
halted programming at it after i played a few games against it :) 

>Best regards
>  Heikki

_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/