Re: [DISCUSSION] Game Tree vs. Pattern Matching

[Antti Huima <huima@xxxxxx>]

On Wed, 28 Oct 1998, Mousheng Xu wrote:

> Dear Smart Guys,
> 
> 	I am having a hard time in deciding whether I need to build a
> game tree or a pattern matching database. Here are the comparisions of
> a few aspects between game tree (assume min-max) & pattern matching.
>
> 		GAME TREE		PATTERN MATCHING
> Space:	much smaller		much bigger
> Efficiency:	log(n)			log(n)
> History:	sensitive		insensitive
> Time:		dynamic		static
> 
> 	As you can see from the above, a game tree is smaller, but
> you've got to know the play history. Otherwise you don't know how to
> traverse your tree. Pattern matching does not care about the play
> history, it only cares about the current board configuration. The
> board configuration, theoretically, is the only informatjion you need
> to make your decisions about the next step. So, it seems pattern
> matching is more natural. But the problem is that it takes a lot more
> space.
> 	What is your strategy and how do you think about the pros and
> cons?
> 	Thanks a lot.
> 
> -- Mousheng Xu

It is not clear what do you mean by log(n), I mean, what 'n' does measure.
Ignoring that, I think you cannot make a choice between game tree search
and pattern matching. A program playing using only local and relatively
static pattern matching will not become strong. By 'local' and 'relatively
static' I mean that in principle a 'pattern matcher' can incorporate
arbitrary tactical searches as a part of the matching process; it's just
about how you defined your 'patterns'. But with 'conventional' patterns
alone, success will not be achieved, because non-local properties as well
as all move continuations are ignored.

On the other hand, game tree search itself cannot play any interesting
game, because some heuristics are always needed. If you want to use the
traditional min-max approach, you probably need a static evaluation
function, which is the real problem with go programs. You might use
pattern matching for performing forward pruning during the min-max search
(i.e. consider only moves that match with a pattern in your pattern
database) but that isn't an evaluation function which you still need.
Pattern matching combined with otherwise dumb min-max search does not
work; the min-max search is meaningless because there are no
game-theoretic values found for the leaves of the generated trees.

-- 
Antti Huima
SSH Communications Security Oy