RE: [computer-go] Pattern matching - rectification & update

["Mark Boon" <tesuji@xxxxxxxxx>]

> -----Original Message-----
> From: computer-go-bounces@xxxxxxxxxxxxxxxxx
> [mailto:computer-go-bounces@xxxxxxxxxxxxxxxxx]On Behalf Of Frank de Groot
> Sent: Saturday, November 20, 2004 0:55
> To: computer-go
> Subject: Re: [computer-go] Pattern matching - rectification & update
>
>
> From: "Mark Boon" <tesuji@xxxxxxxxxxxxxxxxx>
> Subject: RE: [computer-go] Pattern matching - rectification & update
>
>
>
> > Do you mean inefficient in algorithm, or inefficient in implementation?
> > Do you mean tactical in terms of life-and-death or tactical like in
> ladders,
> > geta, etc...?
>
>
> I mean that I do not understand why they strive for a guaranteed way to
> solve a problem.
> Isn't it better to be a trillion trillion times faster and be
> only 90% sure
> you solved the problem?

First, I don't think you're going to be able to make a tactical module a
trillion trillion times faster than the existing ones. (Who was talking
about faster cotton-balls again?) And secondly, no I don't think 90% is good
enough either. But it depends a little on the complexity of the 'problems'
you want to solve. Ladder problems need to be solved 99.9999% correctly. For
complex life-and-death 90% is more acceptable.

>
> > I think we came a long way of making a life-and-death module that does
> what
> > you're looking for. It was based on whole-board evaluation combined with
> > proof-number search. Simple problems would be solved in
> hundreds of nodes,
> > complex ones in thousands. To 'solve' carpenter-square took maybe
> > ten-thousand, but that even stumps your average 6d amateur.
>
> Well it is interesting to work on such a thing.

It is, very interesting.

>
> > The search-algorithm is simple, the evaluation is not. But I agree it's
> > doable.
>
> I don't understand the theory behind the search algorithms (except
> Alpha-Beta with killers)
> I want to make something much simpler that does exactly what a human does.

Well, maybe time to spend a little effort in trying to understand some of
them then. I think PN-search can be tailored to do search in a very
human-like way. Basically what it does is it assigns each node in a
search-tree a number that reflects the amount of work that it estimates
still needs to be done to 'prove' or 'disprove' the problem. This 'proof'
and 'disproof' number of the leaves gets added up in the parent-node in a
minimax way, all the way up to the root. The most basic-form uses the number
of 'unproven' moves each side has. The node that needs the least work gets
expanded, after which the process repeats. ('Expanded' means play the move,
generate candidate moves for the opponent and generate the proof-numbers for
those.)

In a way it's very much like humans do search. They follow a (promising)
path, but when it gets too complicated, they back-track and try a simpler
path first. Only when the simpler path turns out to be fruitless do they
turn back to take a closer look at the complicated path(s). (This is a
simplification of matters, for the sake of argument.)

It works well if you have a way to make good estimates of 'amount of work',
based on evaluation and patterns.

As a side question: what can be simpler than alpha-beta, but be more
human-like? Seems like a contradiction to me. But to answer such question
you have to get almost philosphical and first determine 'simple' and
'human-like'.

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