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
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
