Go-ing Monte Carlo

Go is much more intuitive than chess , even dan players make a lot of random (or intuitive) moves in a game.Specially in the opening.
It makes a lot of sense to be crushed by a machine that fights for territory based on statistics.
When i started playing Go (2001), my teacher told me that (unlike chess) machines will never beat humans , i was fascinated .
:(

Go players were always saying "hey, in go we, humans, still prevail over silicon, in chess they are doomed" And now... the machines start wining also there!

Very interesting article, indeed in quantum mechanics they use probabilities to determine the outcome of experiments, and surprisingly their results are very accurate. I wonder if the "go" method could be used in chess to navigate the amazing maze of possible moves.

Truly astonishing!

Hold on a second! - the computer beat the professionals _with a handicap of six stones_!

http://www.ireport.com/docs/DOC-214010

This is like a chess game at, say, knight odds.

No question, it's really exciting that computers are improving so fast; and the new Monte Carlo techniques are a revolution. But the computers are not at the level of beating the best humans in even games, even occasionally.

(On large boards anyway. On a 9x9 board, the computers are more formidable - the game is shorter, more tactical and less strategic.)

I read the article at the Chssbase link, but it doesn't really explain how a Monte Carlo analysis is used to carry out a search. Rather it talks about how to run one within the software. Where and how exactly does the Monte Carlo methodology apply? Does the engine pick random moves in games that are used to populate the search?? Or is there an ordered hierarchy of moves it goes through when playing these games?

Andy: you sound like you think we disagree but note I did describe it as a "revolution" too! Whatever the appropriate analogy to chess is, 6 stones is certainly nothing like an even game (which is the impression one would get from reading Mig's post or the Wired article). Computers are improving very fast and in an exciting way, but they are not near to professional standard yet. Maybe in a decade? That's the timescale that the programmer talks of in the interview at the ireport.com link above.

D_Tal, you can look at http://zaphod.aml.sztaki.hu/papers/ecml06.pdf
for an explanation of the techniques. (Or google for 'UCT go', or something. There are lots of references out there now). The basic idea is called "UCT". Very loosely: the programme runs lots of trial games from the current position to the end of the game. At first the trials are completely random. In later trials, whenever the program reaches a position it's considered before, it has a bias in favour of moves that have fared well in previous trials and a bias against moves that have fared badly. The idea is that gradually it converges to the best line.

james, thanks, that makes sense.

Computers know the truth in chess, or a reliable approximation thereof.

So the only interest in human chess, between GMs, lies in the slippage or distance between a GM's moves and those of Rybka.

The truth is now easily accessible: the only fun part is in watching GMs stray from it. When they come too close to Rybka's truth, we accuse the humans of cheating.

For me, the most interesting thing about Rybka's Monte Carlo simulation is that it provides an estimate of the "drawishness" of various move alternatives. This can be an important factor depending on one's standing in a match or tournament. So for instance if you are losing near the end of a match, you might decide on a slightly weaker alternative because it actually gives you a somewhat higher chance to win the game (but significantly less chance to draw).

I haven't seen this point made anywhere else, but in my opinion it could be a significant step forward in computer strategy, as it potentially allows the program to integrate match strategy along with the evaluation of positions.

That also has implications for using Monte Carlo methods as a guide to "practical chances," a major weakness, or at least difference, in how computers play. That is, they would rather go into simplified Position A with absolutely no counterchances if it's evaluated 0.04 higher than Position B, which leads to incredible complications. That may occasionally make sense against another computer, but it's simply bad against a human.

And even against another comp, Monte Carlo could curb the limitations of the horizon effect -- as I had in mind for endgames. So that 0.04 might be downgraded if the scoring percentage after that choice is significantly worse than in the other, complex line. E.g. Position A leads to 30 losses, 70 draws and Position B leads to 40 losses, 20 draws, and 40 wins. That result could also employ the contempt factor as Jeff indicates, so draws could count as less than .5 in the contempt calculation.

Btw, regarding the ChessBase article, I don't think Monte Carlo is used in chess search right now. Too slow, would hurt playing strength against comps, all the usual reasons for not abandoning straightforward search. They're just using it as an analysis tool to create quick stats from a certain position. This sort of thing is essentially what some engines already do with extremely deep extensions in search, really. Narrow, deep branching. But I don't think they use it for practical chances and statistical relevance a la Monte Carlo, just more minimax eval fodder.

I would not have thought that Monte Carlo techniques would have been an intutitive choice in Chess, because random moves would result in some (many) games that clearly have no value. However if a probability distribution for candidate moves are constructed from a quick regular search (or a heuristic perhaps in the opening phase) that reduces the available choice and also accords a probability to each move, and moves are picked with a probablity dictated by this distribution, I can see how it might work. The endgame does seem like the phase most likely to benefit from Monte Carlo techniques.

The main problem for writing software to play go is the lack of an evaluation algorithm.

I remember that, years ago, someone once defined a chess software as "a 1600 player who sees everything". Commercial chess programs only got really strong, and capable of beating GMs, when they stopped focusing on "seeing even more", and starting incorporating positional knowledge in their algorithms. In other words, instead of being "a 1600 player who sees even more", they started being "a 2000 player who sees nearly everything".

But in Go, due to the nature of the game (and it is difficult to explain, unless you are familiar with that game), and algotithm for positional evaluation is much harder to implement. That's why engines are still not beating professionals in even games, and will probably still take many years to do so.

As said above, the engines beat profissionls when they recieve a handicap of six stones. And six stones in go is a lot.

------------------------------

Completely out of topic, but I don't resist.
Jeff, do you intent to update your chessmetrics site? I don't know how much traffic it gets nowadays, but I still check it regularly.

Six stones in go is something like giving a rook in chess.