Playing computers finally good for your game?

[CarlJung]

I played recently Fuego with an opening library. It was very fun : he played solid moves until we reached a position when I replied like the 10k I am. From this stage, he played stupid moves and I had an easy win.

It sure have problems with ladders.

[amnal]

It does distinguish between winning lines. It just chooses the one that has highest winning probability. I'm not 100% sure, but I think it gets the winning probability from playing out a lot of random lines and seing how many that wins compared to how many that loses. This is something completely different than choosing the one that gives the biggest win. The biggest win would be to kill everything (or everything that possibly could be killed). But that isn't very probable to happen. But it's possible that one of the many random playouts result in this. Choosing that line would just be wishful thinking.

Perhaps it is the monte carlo method I'm misunderstanding. I still don't see why monte carlo should not be an excellent way to computer endgame values, but maybe there's something inherent to how these bots work that means they just can't do it.

[topazg]

Perhaps it is the monte carlo method I'm misunderstanding. I still don't see why monte carlo should not be an excellent way to computer endgame values, but maybe there's something inherent to how these bots work that means they just can't do it.

Because it works by throwing 1000s of lines at a given possibility, and picking the one that wins with the highest probability, if there are a few insanely complex lines that are technically perfect play but spell disaster if you make an error in the sequence, they will score particularly badly and never get chosen.

[padic]

I thought high-level programs still relied on extensive opening books, and so played very "correct" openings? MC go bots do exactly the opposite, playing openings that look completely ridiculous to a human, relying on computation during the game rather than pregame calculations almost immediately, which is the difference I meant to emphasise.

I just like to point out that there is nothing inherent in MC bots that prevent them from playing from an opening book. It is perfectly possible to combine an opening book with a MC bot.

But I think there's something in go that prevents the opening book approach from being as successful as it is in chess; the board is larger and the book becomes unmanageably large quicker. Actually I believe the version of MoGo I generally play when I play a bot does use an opening book, it just begins deviating from that book very, very quickly and so the book is not really an important part of how the bot plays. The things that really shape its style are direct results of the Monte Carlo approach: seemingly random moves in the center in the beginning, defensive moves at the end when ahead to secure a small-margin win, and crazy overplays at the end before resigning.

The way it plays is not a mediocre imitation, but a mediocre innovation, which is what I find interesting and why I look forward to seeing even better MC bots in the future.

[CarlJung]

But I think there's something in go that prevents the opening book approach from being as successful as it is in chess; the board is larger and the book becomes unmanageably large quicker.

Absolutely. You can have the biggest opening book in existence, compiled from all the pro games and strong amateurs you could possibly find. But when a 10k human player makes a move that's not in the book, which will happen very soon, the bot can't play from the book anymore and has to rely on it's own abilities.

[padic]

But I think there's something in go that prevents the opening book approach from being as successful as it is in chess; the board is larger and the book becomes unmanageably large quicker.

Absolutely. You can have the biggest opening book in existence, compiled from all the pro games and strong amateurs you could possibly find. But when a 10k human player makes a move that's not in the book, which will happen very soon, the bot can't play from the book anymore and has to rely on it's own abilities.

Naturally. What I was trying to assert, though, is that even the number of possible correct whole-board sequences (for some fuzzy definition of "correct" weaker than actual perfect play; say pro-level) is likely to get out of hand quickly, quicker than in chess, and for this reason the opening book approach is not as viable in go as it is in chess.

[amnal]

Perhaps it is the monte carlo method I'm misunderstanding. I still don't see why monte carlo should not be an excellent way to computer endgame values, but maybe there's something inherent to how these bots work that means they just can't do it.

Because it works by throwing 1000s of lines at a given possibility, and picking the one that wins with the highest probability, if there are a few insanely complex lines that are technically perfect play but spell disaster if you make an error in the sequence, they will score particularly badly and never get chosen.

But that's what I mean, this is nothing to do with monte carlo in general, but the evaluation function alone. And it isn't obvious to me that creating an endgame-analysis evaluation function should be inherently far more difficult than anything done so far. But maybe I'm just too optimistic

[topazg]

Because it works by throwing 1000s of lines at a given possibility, and picking the one that wins with the highest probability, if there are a few insanely complex lines that are technically perfect play but spell disaster if you make an error in the sequence, they will score particularly badly and never get chosen.

But that's what I mean, this is nothing to do with monte carlo in general, but the evaluation function alone. And it isn't obvious to me that creating an endgame-analysis evaluation function should be inherently far more difficult than anything done so far. But maybe I'm just too optimistic

You mean have it play MC heuristics until it gets to recognised endgame stages, and actually evaluate individual endgame sequences to design a way through the endgame perfectly? So it can open out of a book, rip the middle open with complicated MC tailored fighting, and then finish with a machine-like precise endgame?

If so, yeah, I agree, that's exactly what I'd like to see them do too

[CarlJung]

It does distinguish between winning lines. It just chooses the one that has highest winning probability. I'm not 100% sure, but I think it gets the winning probability from playing out a lot of random lines and seing how many that wins compared to how many that loses. This is something completely different than choosing the one that gives the biggest win. The biggest win would be to kill everything (or everything that possibly could be killed). But that isn't very probable to happen. But it's possible that one of the many random playouts result in this. Choosing that line would just be wishful thinking.

Perhaps it is the monte carlo method I'm misunderstanding. I still don't see why monte carlo should not be an excellent way to computer endgame values, but maybe there's something inherent to how these bots work that means they just can't do it.

Suppose the bot chooses between two positions A and B.

A. gives a 50 pt win 10 moves down the line.
B. gives a 1 pt win 10 moves down the line.

If we only consider those facts, A is the biggest move. But what are the odds that the whole A line will be played? What if it involves self atari and filling own eyes from the opponent. The lines are generated more or less randomly so those crazy lines will come up. We can't just choose the move with the biggest win and hope that the opponent plays like that. How do we choose more wisely?

Suppose that starting with A:
1 line result in a 50pt win 10 moves down the line.
1000 lines result in a loss 10 moves down the line.

Also suppose that starting with B:
1000 lines result in a 1pt win 10 moves down the line.
1 line result in a loss 10 moves down the line.

How do we know which line the opponent will play, or even if he plays any of these, and which are totally useless lines? We don't. So we have to rely on probability. Given the probability of winning for A is 1 to 1000 and for B it's 1000 to 1, which do you choose?

Do you see that finding the biggest endgame move (maximizing win or minimizing loss) is a question that can't be answered with these data?

[amnal]

You mean have it play MC heuristics until it gets to recognised endgame stages, and actually evaluate individual endgame sequences to design a way through the endgame perfectly? So it can open out of a book, rip the middle open with complicated MC tailored fighting, and then finish with a machine-like precise endgame?

If so, yeah, I agree, that's exactly what I'd like to see them do too

Actually I meant almost the opposite. I wasn't thinking about bots, or even entire endgames, but just the application of monte carlo techniques to evaluating the values of moves in a provided position. Maybe this isn't even worth considering.

[quantumf]

You mean have it play MC heuristics until it gets to recognised endgame stages, and actually evaluate individual endgame sequences to design a way through the endgame perfectly? So it can open out of a book, rip the middle open with complicated MC tailored fighting, and then finish with a machine-like precise endgame?

If so, yeah, I agree, that's exactly what I'd like to see them do too

Me too. Actually, what might be feasible is switching over to traditional alpha beta searching at some suitably late stage of the game, when it's actually possible to evaluate every line to the end of the game. Then your evaluation function could be margin of victory (or defeat). I don't know how late this would have to be, and it would still be complicated by ko's, but I wonder if this has actually been tried?

[Cassandra]

Supposingly this would mean the reintroduction of "locality".

Finding the answer to "What is the border of local context ?" has been one of the main problems in computer Go.

The Monte-Carlo-algorithm has proven to be a very elegant by-pass to some extend. Computer programs grew stronger without answering the question above.

But sooner or later in a game finding a 0.5 point win may not be possible any more. Then you must switch to find the best sequences in several areas of the board.