Giorgio Bellegotti wrote:
Hi!
[...]
> this article couldn't be more interesting for me.
Fine. :)
> Above all, I find very intriguing the new Monte Carlo
> search method, even if I have a lot of doubts about it (if
> I have correctly understood it).
Well, I admit that I did not really understand it nor can
judge its value at all. Just some thoughts how I understood
it.
> I mean: trusting in statistical results can be very
> dangerous in chess (especially in endgames), very often
> there can be only one winning line, but it is enough to
> win the game, instead the Monte Carlo method could
> consider it as a draw line.
I'm not sure about that. I think the point is, that Monte
Carlo simulation is successfull for _large_ numbers of
samples. One would probably say the number of samples was
large enough if the effect you mention has vanished by
averaging over the number of samples. Plus, in Monte Carlo
you actually have a numerical way to estimate the error in
your calculation.
The only thing I used Monte Carlo simulation for, is
integration of some real valued functions in multiple
dimensions. (I had to integrate f(a,b,c,d,w,x,y,z) over da
db dc dd dw dx dy dz.) There the efficiency of Monte Carlo
rises with the number of dimensions. You gain nothing in say
up to 2 or maybe 3 dimensions, here the classical Gauss is
much faster and more accurate in the same ammount of CPU
cycles. "Taking advantage" means faster convergence at
the same ammount of CPU time admitting for the same
numerical error. Convergence is defined by reaching a
certian error interval in your calculation.
The point here is, that the stochastic alorigthm just needs
to calculate less points for this compared to the other ones
if you have a large number of dimension. Ie. you have to
use a much finer grid plus you need this grid along each of
your axis in Gauss to reach the same error interval compared
to the numbers of throws of your virtual dice in Monte Carlo
and as each point in the grid needs the complete evaluation
of the complex function you want to integrate... So if you
need to evaluate your function at 16 points for the Gauss
and at 16 points for MC you gain nothing. But if you
increase the dimension by one your Gauss might need 32
points while your MC stays at 16 or maybe increases to 24.
This is the sort of gain you get. Ie. you calculate the same
but at less grid points.
> Maybe, I'm missing something... maybe Monte Carlo search
> is only an addition to the normal evaluation, not a
> replacement.
If I take the analogon, without knowing how the do it, I'd
think that searching the correct move in chess is a pretty
high dimensional problem. The classical approach of weeding
the search tree starting by a line that might get high
evalutiation for the frist moves but then drops to a loss
might converge slower (ie. needs more grid poitns) than just
using a large ammount of random moves and play out the
position at a fast evaluation level. Plus, maybe you find
large error bars in bad moves (you just get everything from
a loss over a draw to a win) compared to very small ones for
the forcing win (there is only one move or you are lost).
To me it sounds a bit like the triple brain idea of
Shredder's win-GUI. There you take several engines to
evaluate the postion. For forcing lines they may give the
same evaluation. For unclear position however, they differ.
Then you take these different lines from the different
engines and use them as input for a "master mind" that looks
at exactly these lines and takes the one it evalutates best.
This would be statistics with small numbers. The MC approach
sounds a bit like taking 10000 different engines (simulated
by using random moves) and then ...
But I'm really not an expert at all, I just think in this
analogy to my integration problem. Maybe you could draw some
conclusion from this.
--
Kind regards, / War is Peace.
| Freedom is Slavery.
Alexander Wagner | Ignorance is Strength.
|
| Theory : G. Orwell, "1984"
/ In practice: USA, since 2001
-------------------------------------------------------------------------
This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
Build the coolest Linux based applications with Moblin SDK & win great prizes
Grand prize is a trip for two to an Open Source event anywhere in the world
http://moblin-contest.org/redirect.php?banner_id=100&url=/
_______________________________________________
Scid-users mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/scid-users
