On Jun 26, 2008, at 6:03 PM, [EMAIL PROTECTED] wrote:
> -----Original Message-----
> From: Jason House <[EMAIL PROTECTED]>
> On Jun 26, 2008, at 3:23 PM, [EMAIL PROTECTED] wrote:
Cool! Now for the cases where I'd want a Kalman filter, I'd need it
to predict the future state of a non-stationary, multimodal
distribution. A typical pattern is for a node to start out with
optimistic scores but to experience a strong pessimistic trend
later as UCT starts to focus more on effective enemy counter moves.
Or the reverse, or sometimes a see-saw.
> The drift term is intended to take care of that kind of behavior.
My limited experience is with objects moving in space, so please
bear with me. The win rate is a 1 dimensional value analogous to a
car moving on a road. If it has a constant velocity, we can model
that with a Kalman filter having a drift rate. But if we assume a
constant drift rate, we'll wind up with win rates greater than 1 or
less than zero, right?
No.
Math geeks would call drift a zero-mean, stationary, random process.
The assumption isn't constant drift but rather that the chances of a
shft in winning rate of 5% at move 432 is the same as at move 2375.
The usual/average case is that there is no drift.
When a car is at point A, for a while, then moves to a final
destination point B, it has to (at least) accelerate for a while,
then decelerate.
Think of a piece of driftwood floating in the middle of the ocean. It
will jostle around, sometimes staying put, and other times traveling
quite far when the currents are right.
I hope that helps...
In UCT, a new node will start with an initial win rate reflecting
the fact that UCT is exploring moves fairly randomly, then settle
eventually at a "final" win rate where UCT would put it if it ran
for a very long while.
Closer to the root, we are seeing a superposition of many such
distributions. My gut feeling is that the UCT tree is already doing
a better job of what I'm asking the Kalman filter to do. But it's a
nagging question for me.
> There's no way for a single floating point value to capture deeper
structure.
Well, yes and no. There is more available than a single floating
point number. You can, in fact, look at Monte Carlo go as a source
separation problem. The sources are the values of the moves at the
root, and the signals, the playouts, are mixtures of those sources.
AMAF is a model that assumes very simple mixing of the sources in
the playouts. But, maybe, this is a discussion for another day.
- Dave Hillis
Get the Moviefone Toolbar. Showtimes, theaters, movie news, & more!
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
