Playing computers finally good for your game?

General conversations about Go belong here.
padic
Dies in gote
Posts: 43
Joined: Thu Apr 22, 2010 1:46 pm
Rank: KGS 5 kyu
GD Posts: 0
Has thanked: 21 times
Been thanked: 6 times

Re: Playing computers finally good for your game?

Post by padic »

topazg wrote:Monte Carlo code is an interesting idea, but IMHO very poor for the future of skilled playing Go engines. I await to see if I'm right or wrong I guess.

In simplest terms, MC bots take a given position, it plays out huge numbers of sequences to the end for a number of moves, and then picks the one that "wins the most times". Over enough iterations, without a great deal of skill or logic in the moves, this works very effectively, but you'll often find an MC bot play a poor endgame, turning a 7.5 point lead into a 1.5 point win - however, get it close to the wire, like 1.5 or 0.5 points, and they play very strongly indeed.

Sure, Monte Carlo bots get defensive and play moves that are suboptimal in terms of points when they are ahead, but why is this considered "unskilled"? Isn't a win by half a point as good as a win by a landslide? In a sense, the computer is just not being greedy by taking more points than it needs to win.

In a position where one player is visibly ahead, there will often be several moves that qualify as perfect play -- that is, the opponent has no sequence of responses that cannot be refuted (in terms of who wins at the end of the game). A sufficiently powerful Monte Carlo bot will choose one of these more or less at random, not caring whether or not it'll win by 7.5 points or 1.5 points at the end of the game. A practical, finite Monte Carlo bot will tend to prefer the more defensive moves, and obviously, it won't always choose perfect play. But your position seems to be one where you could even criticize actual perfect play as "unskilled" or as a "poor endgame", which seems off.

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?
User avatar
zinger
Lives in gote
Posts: 305
Joined: Wed Apr 21, 2010 5:49 am
Rank: hopeless
GD Posts: 0
Has thanked: 1 time
Been thanked: 16 times

Re: Playing computers finally good for your game?

Post by zinger »

topazg wrote:Monte Carlo code is an interesting idea, but IMHO very poor for the future of skilled playing Go engines. I await to see if I'm right or wrong I guess.

In simplest terms, MC bots take a given position, it plays out huge numbers of sequences to the end for a number of moves, and then picks the one that "wins the most times". Over enough iterations, without a great deal of skill or logic in the moves, this works very effectively, but you'll often find an MC bot play a poor endgame, turning a 7.5 point lead into a 1.5 point win - however, get it close to the wire, like 1.5 or 0.5 points, and they play very strongly indeed.

Exactly. So we just need to convince it to play this strongly, even when it knows it is behind. If the deficit is small enough - I would say anything less than 15 points - the bot will have a good chance for an endgame comeback win against middling amateurs. It just doesn't know that.
Main Entry: zing·er Pronunciation: \ˈziŋ-ər\
1 : something causing or meant to cause interest, surprise, or shock
2 : a pointed witty remark or retort
Wildclaw
Dies in gote
Posts: 29
Joined: Fri Apr 23, 2010 4:54 pm
Rank: KGS 2 kyu
GD Posts: 543
Has thanked: 3 times
Been thanked: 4 times

Re: Playing computers finally good for your game?

Post by Wildclaw »

padic wrote:Sure, Monte Carlo bots get defensive and play moves that are suboptimal in terms of points when they are ahead, but why is this considered "unskilled"? Isn't a win by half a point as good as a win by a landslide? In a sense, the computer is just not being greedy by taking more points than it needs to win.


Agreed. Go is a game of endurance. It isn't the good moves that win you the game. It is the lack of bad moves.

The only problem with Monte Carlo bots is that they generally over exaggerate the level of carefulness when they are ahead. And over exaggerate risk taking when behind. This generally doesn't cause any problems in the end game because MC bots read pretty damn good. But it does cause problems earlier in the game, and also makes them somewhat unstable in handicap games.

Now, with all this said. This is why MC bots actually makes for pretty good computer opponents. Their weakness is less in actual game play and more in maintaining risk/reward throughout the game. So I don't think you will pick up any real bad habits from them.
User avatar
topazg
Tengen
Posts: 4511
Joined: Wed Apr 21, 2010 3:08 am
Rank: Nebulous
GD Posts: 918
KGS: topazg
Location: Chatteris, UK
Has thanked: 1579 times
Been thanked: 650 times
Contact:

Re: Playing computers finally good for your game?

Post by topazg »

zinger wrote:
topazg wrote:Monte Carlo code is an interesting idea, but IMHO very poor for the future of skilled playing Go engines. I await to see if I'm right or wrong I guess.

In simplest terms, MC bots take a given position, it plays out huge numbers of sequences to the end for a number of moves, and then picks the one that "wins the most times". Over enough iterations, without a great deal of skill or logic in the moves, this works very effectively, but you'll often find an MC bot play a poor endgame, turning a 7.5 point lead into a 1.5 point win - however, get it close to the wire, like 1.5 or 0.5 points, and they play very strongly indeed.

Exactly. So we just need to convince it to play this strongly, even when it knows it is behind. If the deficit is small enough - I would say anything less than 15 points - the bot will have a good chance for an endgame comeback win against middling amateurs. It just doesn't know that.


Agreed. And, I'd like to see it do it even if it was 20 points ahead. I'm sure most to all professional Go players would frown on being casual in the end just because you don't have to be that precise to win any more.
dfan
Gosei
Posts: 1598
Joined: Wed Apr 21, 2010 8:49 am
Rank: AGA 2k Fox 3d
GD Posts: 61
KGS: dfan
Has thanked: 891 times
Been thanked: 534 times
Contact:

Re: Playing computers finally good for your game?

Post by dfan »

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.
User avatar
CarlJung
Lives in gote
Posts: 429
Joined: Wed Apr 21, 2010 1:10 pm
Rank: SDK
GD Posts: 0
KGS: CarlJung
Location: Sweden
Has thanked: 101 times
Been thanked: 73 times

Re: Playing computers finally good for your game?

Post by CarlJung »

gaius wrote:
CarlJung wrote:With the little I know about MC bots I believe they are fundamentally unsuitable for endgame analysis. The algorithm chooses moves from winning probability from it's simulations. If they are behind too much they can't rely on a strong endgame to catch up so they will have to play crazy and hope the opponent screws up. Moves that lead to a loss is discarded, even if the loss is lesser than for another move. If they are ahead they play safe. E.g. the algorithm is incapable of answering questions like "could a 10.5 pt loss be reduced to a 0.5 pt loss" or "could the 10.5 point win be stretched to a 15.5 point win". Strongest play in a given situation is something fundamentally different than winning probability.


Ummm. You are disproving your own point here. An MC program plays immensely strong endgame, because it's always looking for the best way to win, even if that's with a small margin. And in my experience, once it is a tiny bit ahead in the endgame, an MC bot is not going to let you catch up. Just try playing a few 9*9 games against any strong program and you know what I mean - the sheer number of 0.5 and 1.5 point losses becomes almost frustrating :).

Also, whether it's by 50.5 points or 0.5 points, a win is a win. Therefore, questions like "could a 10.5 pt loss be reduced to a 0.5 pt loss" or "could the 10.5 point win be stretched to a 15.5 point win" are irrelevant to strong endgame play. What matters is taking home the win; counting the value of moves is merely an imperfect tool to help the imperfect human brain work towards that goal.


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.
User avatar
topazg
Tengen
Posts: 4511
Joined: Wed Apr 21, 2010 3:08 am
Rank: Nebulous
GD Posts: 918
KGS: topazg
Location: Chatteris, UK
Has thanked: 1579 times
Been thanked: 650 times
Contact:

Re: Playing computers finally good for your game?

Post by topazg »

dfan wrote: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.


For one thing, Making a plan still just relies on static evaluative heuristics put together. Moves that naturally improve a position will automatically work towards a dynamic and flexible plan with regards to the board as it stands.

Rybka has started to reverse the process again ;)

I used to do UCI engine leagues as a hobby, and I was always amazed at the node differences. Fritz and Shredder would run between 1 and 2 million positions a second getting to about 13/14 ply per move at the time controls I used, whereas Rybka did about 30 to 40 thousand - a 500th the amount - and outperformed them.

The difficulty is that actually coding how people think is not an easy task. It helps that the Rybka author is both a programmer and a titled International Master ;)
User avatar
CarlJung
Lives in gote
Posts: 429
Joined: Wed Apr 21, 2010 1:10 pm
Rank: SDK
GD Posts: 0
KGS: CarlJung
Location: Sweden
Has thanked: 101 times
Been thanked: 73 times

Re: Playing computers finally good for your game?

Post by CarlJung »

zinger wrote:
topazg wrote:Monte Carlo code is an interesting idea, but IMHO very poor for the future of skilled playing Go engines. I await to see if I'm right or wrong I guess.

In simplest terms, MC bots take a given position, it plays out huge numbers of sequences to the end for a number of moves, and then picks the one that "wins the most times". Over enough iterations, without a great deal of skill or logic in the moves, this works very effectively, but you'll often find an MC bot play a poor endgame, turning a 7.5 point lead into a 1.5 point win - however, get it close to the wire, like 1.5 or 0.5 points, and they play very strongly indeed.

Exactly. So we just need to convince it to play this strongly, even when it knows it is behind. If the deficit is small enough - I would say anything less than 15 points - the bot will have a good chance for an endgame comeback win against middling amateurs. It just doesn't know that.


What I'm trying to say is that I think MC bots are inherently unable to play a strong endgame (in the human sense) when one side has a significant lead. I hope someone who has actually programmed an MC bot can say if this is true or not.
amnal
Lives in gote
Posts: 589
Joined: Fri Apr 23, 2010 10:42 am
Rank: 2 dan
GD Posts: 0
Been thanked: 114 times

Re: Playing computers finally good for your game?

Post by amnal »

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...
User avatar
zinger
Lives in gote
Posts: 305
Joined: Wed Apr 21, 2010 5:49 am
Rank: hopeless
GD Posts: 0
Has thanked: 1 time
Been thanked: 16 times

Re: Playing computers finally good for your game?

Post by zinger »

dfan wrote: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.

In short, they abandoned "thinking" in favor of brute force calculation, and it worked, thanks to Moore's law. Can this happen to Go?
Main Entry: zing·er Pronunciation: \ˈziŋ-ər\
1 : something causing or meant to cause interest, surprise, or shock
2 : a pointed witty remark or retort
User avatar
CarlJung
Lives in gote
Posts: 429
Joined: Wed Apr 21, 2010 1:10 pm
Rank: SDK
GD Posts: 0
KGS: CarlJung
Location: Sweden
Has thanked: 101 times
Been thanked: 73 times

Re: Playing computers finally good for your game?

Post by CarlJung »

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
Gosei
Posts: 1348
Joined: Wed Apr 28, 2010 12:42 am
Rank: FGA 7k GoR 1297
GD Posts: 0
Location: Finland
Has thanked: 49 times
Been thanked: 129 times

Re: Playing computers finally good for your game?

Post by tj86430 »

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.
Offending ad removed
padic
Dies in gote
Posts: 43
Joined: Thu Apr 22, 2010 1:46 pm
Rank: KGS 5 kyu
GD Posts: 0
Has thanked: 21 times
Been thanked: 6 times

Re: Playing computers finally good for your game?

Post by padic »

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.
User avatar
CarlJung
Lives in gote
Posts: 429
Joined: Wed Apr 21, 2010 1:10 pm
Rank: SDK
GD Posts: 0
KGS: CarlJung
Location: Sweden
Has thanked: 101 times
Been thanked: 73 times

Re: Playing computers finally good for your game?

Post by CarlJung »

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.
User avatar
Tryphon
Lives with ko
Posts: 299
Joined: Tue Apr 20, 2010 2:32 am
Rank: KGS 10k DGS 8k
GD Posts: 396
Has thanked: 49 times
Been thanked: 17 times

Re: Playing computers finally good for your game?

Post by Tryphon »

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 :

Post Reply