Monte Carlo Theory Is it time to Update Comp-Chess Books?

[AdminX]

Just was wondering what the programmers here think about the idea of Monte Carlo Analysis. Seems new in alot of ways and yet I know that Rybka had the Randomizer 1st, which seems to pre-date Monte Carlo.

However in all the books I have read about Computer Chess, I don't ever recall reading about it. Do you think it will someday change the way computers select moves in the middle game.

[Zach Wegner]

Seems new in alot of ways and yet I know that Rybka had the Randomizer 1st, which seems to pre-date Monte Carlo.

?? Monte Carlo techniques have been around for a very long time. Monte Carlo as applied to game playouts have been around for many years as well. IIRC it was first used in about '93 for Go. Also, AFAIK, Randomizer isn't Monte Carlo but it just adds random values to the eval.

However in all the books I have read about Computer Chess, I don't ever recall reading about it. Do you think it will someday change the way computers select moves in the middle game.

No. It's way too inexact, and regular tree searching is too well suited for chess. Someday it might influence engines, but I doubt it will ever be the basis for a top engine.

[CRoberson]

Monte Carlo has been around in Mathematics and Computer Science
for several decades.

It falls under dynamic programming.

It is one of many statistical based aprroximation methods which can
and is used for solutions to many LARGE problems. If you need an
answer but it is not possible to get a perfect answer (due to size or other issues) and
an approximation is ok (no choice about that) then dynamic techniques
can be very good approximators.

The problem with these algorithms is that they consume
runtime to get accurate answers.

For instance, one might use it for tuning opening books. However, this
beggs the question of how big is the book and how many games it takes
random evaluations to cover the space with reasonable density. I've
been using this method along with other competitive methods for
sometime for book creation. I've used them for other projects since
the 1980's.

As far as re-writing text books go: no need. Monte Carlo and the like
predates me and I am older than Vasik. So, it most definitely predates
the Rybka Randomizer.

[bob]

Just was wondering what the programmers here think about the idea of Monte Carlo Analysis. Seems new in alot of ways and yet I know that Rybka had the Randomizer 1st, which seems to pre-date Monte Carlo.

However in all the books I have read about Computer Chess, I don't ever recall reading about it. Do you think it will someday change the way computers select moves in the middle game.

I don't think much of it, because of the time required. We tried to do something like this with Cray Blitz, but even with a relatively small book of 300,000 total moves/positions, we found it impossible to run such tests on the entire book, position by position, to look for blunders or novelties. Even worse, at the shallow search depths necessary to make this complete in reasonable time, the programs are more likely to overlook things than they are to find something.

The book is a _big_ problem and I don't believe this kind of analysis will do anything useful other than perhaps answer questions about a specific line/move during analysis. And even then it will be of dubious quality compared to deep human and/or computer analysis

[bob]

Monte Carlo has been around in Mathematics and Computer Science
for several decades.

It falls under dynamic programming.

It is one of many statistical based aprroximation methods which can
and is used for solutions to many LARGE problems. If you need an
answer but it is not possible to get a perfect answer (due to size or other issues) and
an approximation is ok (no choice about that) then dynamic techniques
can be very good approximators.

The problem with these algorithms is that they consume
runtime to get accurate answers.

For instance, one might use it for tuning opening books. However, this
beggs the question of how big is the book and how many games it takes
random evaluations to cover the space with reasonable density. I've
been using this method along with other competitive methods for
sometime for book creation. I've used them for other projects since
the 1980's.

As far as re-writing text books go: no need. Monte Carlo and the like
predates me and I am older than Vasik. So, it most definitely predates
the Rybka Randomizer.

We had that idea years ago although different in that there was no random evaluation. We simply took our 300,000 position book and played very fast games from each position. We tried at least a couple of approaches.

(1) just play the games from the ends of the book lines to make sure that a book line that ends in +/- is not dead lost instead. We didn't like this result because most of the blunders or potential novelties by the opponent occurs earlier in the book tree and since searches are only done from the tips, these unplayed but good moves are not found.

(2) to solve that, we tried to do the same thing at every position in the book. Problem is this is hundreds of times more difficult in terms of number of games needed.

Our "randomizer" was just a randomness introduced into the time usage code so that each game, given the same target time for the moves, would actually use different real times because the time was mangled with a random number.

We didn't find either of those very useful. Sometimes the fast games would suggest that a position was bad for the side choosing to make it, but more careful analysis would show it was actually a good position. We found that it almost always liked accepting gambits, because the shallow depth games could not discover all the tactical nuances present and would conclude that winning the pawn was tantamount to winning the game, when often the opposite was true...

The only benefit for us was that we would have the program display the overall result, and flag results that were anything other than fairly equal, so that we could then look at the line manually and decide whether to keep it or lock it out. Occasionally we would find a nice anti-computer line where the program would almost be obligated to make a capture that would lose the game to a deep horizon-type move that it could not find. But we had to do this kind of analysis by hand after the book analysis program would flag the line as "interesting - possibly good or bad".


Granted today's depths are significantly larger, but I doubt the issues are substantially different overall. Monte Carlo has been around forever. I learned about it in college in the late 60's... So while it sounds like something new and wonderful, it definitely is not a new idea, and I am not so sure it is that "wonderful" for tweaking a book or providing statistics about a line.