[computer-go] State of the art of pattern matching

[Mark Boon]

On 31-mrt-08, at 12:36, Don Dailey wrote:
>
> Are these fixed patterns or wildcard patterns?      I'm interested in
> wildcard patterns too and how to automatically generate them.
>
> A wildcard pattern is exactly the same as a decision tree (it can be
> represented perfectly by a decision tree.)    There are several  
> methods
> in AI that have similar function and performance to decision trees  
> - and
> that's why these methods are interesting to me.   They are different
> ways of looking at wildcard pattern generation.
>

These are wild-card patterns. And I do indeed represent them as a  
decision tree.

>>
>> 2) When I used these patterns during simulation the playouts suddenly
>> look surprisingly like normal Go compared to random playouts.  
>> However,
>> the program started to play worse. Much worse. Even when I let it
>> compute as many playouts as a program without patterns.
> This of course is now a well known phenomenon.

Aha, well sometimes reinventing a few wheels is inevitable :-) It did  
surprise me.

>
>>
>> The first observation made me wary to rely on harvested patterns. I
>> think it shows at least it needs to be used in combination with
>> hand-crafted patterns. Also it means that the fact you harvest a  
>> large
>> number of patterns isn't necessarily meaningful.
> It isn't  necessarily the quality of the moves that is important it
> seems.    All playouts, including uniformly random playouts, set up
> certain type of bias.   Uniformly random playouts have the
> characteristic that stupid errors are compensated by stupid errors by
> the opponent and so tend to weakly balance out and return a  
> "reasonable"
> evaluation.

They balance, but tend to have a large deviation from the norm.  
'Better' play during playouts should, in theory, reduce the size of  
the deviation.

>
> Heavier playouts have been shown to be far superior,  but just placing
> stronger moves in the playouts does not seem to be the right
> formula.     My guess is that if you place arbitrary knowledge into  
> the
> playouts, you create terrible imbalances.   Perhaps the secret (I'm
> entering uncharted territory here)  is that it's ok to create  
> imbalance
> if it's the type the tree is easily able to correct.    This is my
> working theory,  let's call it "maximum information gain."      The
> early Mogo paper showed that it's good to look at defending opponents
> atari.    Defending an atari tends to be either one of the better  
> or one
> of the worst moves on the board.    It's a horrible move if it  
> cannot be
> defended.    HOWEVER,  what you can say is that Mogo's playout  
> strategy
> pushes the search right away in the direction of  "finding out for
> sure"   so this appears to cause the playouts to create a hypothesis
> that is either quickly refuted or quickly confirmed.    I really think
> you want to push towards positions that "work out" what is really  
> going
> on, even if you have to insert bias into the the playouts to get this
> (which you probably do.)
>

I don't know about this. I'm pretty sure MoGo checks if the stone can  
make at least two liberties (ladder problem) in which case it can  
still be horrible but very seldomly worse than random. It seems to me  
that in principle whenever you have a 'pattern' that has a higher  
success-rate than a random move over a large number of games, then it  
should always be preferred over the random choice. I think it's the  
lack of randomness that's the problem. The large number of playouts  
tend to converge to a mistake if it's deterministic. It doesn't even  
have to be totally deterministic I think.

>>
>> The second observation I think may have been caused by not enough
>> randomness. But that means I first have to find an answer to how much
>> randomness I need to put into the patterns. I'm first looking at this
>> question with some hand-crafted patterns to get a better handle on
>> this issue.
> Let us know.   The whole issue is pretty interesting.    I think
> randomness is required only to counteract systematic biases because
> obviously if you playouts played perfectly,  there would be no need  
> for
> randonmess.   And yet better than random playouts can also lead to  
> worse
> play in general.
>
>
> - Don