Playing computers finally good for your game?

CarlJung · **#41**

amnal wrote:

CarlJung wrote:

I'm with topazg here. I'm talking from a human's perspective when I say that MC bots is unsuitable for endgame analysis. Humans are generally interested in the best order of moves assuming perfect play. For a human it would make sense to go back and review a 10.5pt loss and improve it to a 0.5pt loss. He would be happy to have found a better endgame, maybe even leant something. Same reasoning when you are ahead, trying to maximize your win.

But MC bots only care about winning or losing. This is what makes them unsuitable for the task of endgame analysis in the human sense. Their algorithm just doesn't work that way.

This is what I don't understand. Naively, the only problem here is that the bot doesn't distinguish between winning lines. Wouldn't just allowing them to distinguish this to aim for the best endgame possible change this completely?

I'm well aware that I'm probably missing something, but I can't see what it is...

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.

tj86430 · **#42**

zinger wrote:

In short, they abandoned "thinking" in favor of brute force calculation, and it worked, thanks to Moore's law. Can this happen to Go?

I'd say "no" with computers as they are today, but "yes" when we have quantum computers.

padic · **#43**

dfan wrote:

padic wrote:

The way I see it, Monte Carlo bots can absolutely become "skilled". They will, however, always play in a style that is not natural to any human, and so their play won't in general resemble that of a skilled human player. The situation we're seeing is one where the strongest computers are not strong because they're imitating strong humans (with opening books etc.), but because they (or their programmers) are actually developing a new style that works very well with the way computers think. That's just the way humans make sense of the game, by thinking of it in terms that work well with the way humans think -- for instance, "good shape" or "influence".

I actually find that an extremely interesting development in the ongoing mind sports human vs. machine rivalry. To the best of my knowledge that's not the way it went with chess?

It is actually pretty much the way it went with chess (maybe to a less extreme degree).

For decades people tried to make chess programs that mimicked the thought processes of human players. This is one reason that creating a strong chess-playing program was considered really important in the field of AI.

In the 1970s, people basically abandoned the idea of making a chess program that thought like a human and switched to exploring the tree of variations as fast as possible. Of course they still try to discard obviously bad branches and look at interesting branches more closely, as a human does, but the whole concept of making a plan and implementing it, which had been seen as the interesting part of chess AI, was thrown out the window. Now it's mostly a question of having an static evaluation function that is both fast and high-quality, and of exploring the tree in the most efficient manner possible.

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.

CarlJung · **#44**

padic wrote:

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.

Tryphon · **#45**

CarlJung wrote:

padic wrote:

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.

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.

I must have the game somewhere... Ah, here it is :

CarlJung · **#46**

Tryphon wrote:

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 · **#47**

CarlJung wrote:

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 · **#48**

amnal wrote:

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 · **#49**

CarlJung wrote:

padic wrote:

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 · **#50**

padic wrote:

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 · **#51**

CarlJung wrote:

padic wrote:

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 · **#52**

topazg wrote:

amnal wrote:

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 · **#53**

amnal wrote:

topazg wrote:

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 · **#54**

amnal wrote:

CarlJung wrote:

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 · **#55**

topazg wrote:

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 · **#56**

topazg wrote:

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 · **#57**

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.

Playing computers finally good for your game?

Who is online