Patterns and Behavior

[rbrown@xxxxxxxxxxxxxxx]

Mousheng Xu wrote:

>         Hey, that's a good catch. :) "Ko" is the Janpanese way to say "Jie".

Ah, I thought that might be it.  A vacant point, but one you aren't permitted to
play on, at this time.  I must ask another question, does "jie" mean eternity?
That is, is it the same han zi (kanji) as "ko"?

We could spend an eternity discussing go programming, so let's get started!

>     So you guys have not discussed my original questions yet: 1. pros & cons
> of PAT, Zobrist, Silly Number, Pattern tree; 2. which do you prefer if you
> have to choose one? why? 3. Any other suggetions about patterns?

My earlier comments were meant to be general in nature; I don't think I am able
to answer Mousheng's specific questions.  But if Silly Number means what I think
it does, you'd better get some more disk drives, if you are going to use that!

There is a phase of pattern recognition called "feature extraction" during which
useless or redundant information is discarded from an observation, _before_ that
observation is encoded into a pattern.  Again, this is a rephrasing of that very
difficult question, "what information do I want to store in my patterns?"

What I am trying to say is that, if you want to use patterns, you must use
heuristics.  You have to decide what information to keep in your patterns, and
what to throw away.  The universe doesn't have enough bits, nor will it last
long enough, for you to store 1 response per 1 board state.

That said, my answer to the multiple-choice question is, "None of the above."
Instead, prototypical examples of the patterns I'm interested in are collected
as data by having the program observe professional games.  (The encoding of the
patterns that result from the observations, i.e. the database format, is a state
secret.)  Based on that data, the program emulates behaviors it has seen before.

>         Great new word -- "behavior!" Don't you just mean play history? 

Actually, no, unless history includes _style_.  By a pattern of behavior in go,
I mean the _syntax_ of the moves.  A move is not just a pair of coordinates,
which is what I take "play history" to mean.  For example, an sgf file contains
the play history of a game, but what I mean by "behavior" is much, much more
than that.

If you think of go as a language with its own grammar, then some sequence of
moves expresses some of the production rules of that grammar.  Now, some moves
speak a fighting language, threaten, demand a response, while others may speak a
more timid languange, being overly-defensive, unnecessary.  Or, Consider joseki.
In a joseki, one player's moves will often speak an explicitly territorial
language with regard to the corner, while at the same time the other player's
moves speak a language of implicit power, which will only later result in
territory.

A human expert knows at a glance whether a move is greedy, generous, ambitious,
cowardly, and so on.  He knows whether it is a steady move, or a risky one, and
can often calculate precisely the degree to which that is so (counting the score
that will be the result).  That is, he knows what type of language the move
speaks, or what its style is, or what type of behavior it embodies.

A player's _style_ is the aggregate of the the individual types of behavior in
which he indulges, and in what sorts of contexts he indulges in them, considered
over the long term.  Of course this varies from player to player, and even a
single player may use different styles in different games, so it can vary from
game to game also.  Inexperienced players will have an erratic style, varying
even within one game.  Experienced players' styles tend more toward consistency.
(For that reason, I feel that directed or supervised learning, "learning with a
teacher", using professional games as prototypical data examples, is a superior 
approach to that of letting a program learn on its own, playing against itself.)

Now, the two most fundamental behaviors in go are cutting and connecting.
Extending (a play that contacts one's own stones, as in the attach-and-EXTEND
joseki) is a kind of connecting.  Making a tiger's mouth or a bamboo joint are
other kinds of connecting but they are fundamentally still connecting behaviors.

Other, higher-order behaviors include jumping, approaching, attaching (that is,
removing foe liberties), peeping (that is, threatening to cut), making eyes,
making walls, surrounding empty space, surrounding enemy stones, playing the
eye-stealing tesuji, sacrificing two stones instead of one, capturing groups,
all the way up to the highest-order behaviors of all, namely claiming territory
and defending it.  (How do you _do_ that, anyway?)

Stupid behaviors are also possible.  Consider the common beginner's error of 
taking a stone, only to be caught in a snapback.  That's a type of behavior too.

Jumping may be thought of as virtual connecting, as yet incomplete, to become
a real connection (or not) later.  Or it may be that some jump also cuts the
opponent into two groups.  Or perhaps it threatens some followup behavior which
will so cut.  Attaching could be a precursor to some eventual cut or connection,
or it could be a sacrifice, keeping the opponent busy.  Similarly, a probe or an
invasion could become territory, or it could be a sacrifice.  With a probing 
move, the expert himself may not know what he intends to do with it, until he 
sees the foe's response.  Other higher-order behaviors include various tesuji.

Forcing the foe to take your dead stones off the board and waste moves filling 
his own territory is a specific example of a higher-order behavior that is made
up of other lower-order behaviors, like cutting and connecting and capturing.

Causing groups of various sizes of one's own stones to live, and causing groups
of various sizes of the opponent's stones to die are, again, high-order 
behaviors composed of many discrete lower-order behaviors.  Playing an
edge-territory-oriented game versus playing for a powerful moyo are likewise
both high-order behaviors, but again, they are built up from many smaller
individual behaviors.

Playing risky moves when you are behind is a type of behavior, going
hand-in-hand with playing steady moves when you are ahead.  Yet we all know
players who throw away won games by playing risky when ahead, or miss
opportunities to suddenly come from behind, because they are afraid of risk.
So those converse (perverse?) behaviors are available too; the problem is
sorting it all out and making the program choosing the _right_ behaviors.

The highest-order behavior in go is surrounding, encircling, enclosing.  It too
comprises many discrete individual behaviors protracted across space and time.
Playing an edge-territory-oriented game versus playing for a powerful moyo are
likewise high-order behaviors, but again, they are built up from many smaller
individual behaviors.

Tolstoy, speaking of all games like chess -- that is, games of no chance --
said that they embody that which is most noble in man, as well as that which is
most beastly.  And so it is in go, where -- just as in real life -- behavior
ranges from the sublime to the ridiculous.

The tricky part is getting a machine to be able to tell the difference.


Rich

-- 
Richard L. Brown              Office of Information Services
rbrown@xxxxxxxxxxxxxxxxx        University of Wisconsin System Administration
rlbrown6@xxxxxxxxxxxxxxxxx    780 Regent St., Rm. 246  /  Madison, WI  53715