Re: [DISCUSSION] Game Tree vs. Pattern Matching

[David Fotland <fotland@xxxxxxxxxxxxx>]

If you are talking about a Joseki or Fuseki database, I use game trees for
both to save space.  I think most of the chess programs use large hash tables
so they can recognize any position no matter what the history.  A hash table
using zobrist hashing is not so big.  I use a hash table to record positions
from past game in the learning feature in Igowin.

In any case you will need some kind of pattern matcher to do move generation.
This can be bit mapped, or a description language, or just thousands of
"if" statements :)

David

At 05:35 PM 10/28/98 -0800, 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
>	
>	
>
>
>