> Winning a tactical battle is something computers are okay at now. MPP is a > useful optimization for analyzing a tactical situation. However, winning a > particular battle may lead to you losing the game (and frequently it > does), so the key problem is choosing the battles to fight. If there are > three fights on the board, how do you choose among them? Right now we > cannot answer that question, so we don't know if MPP will help or not. I > was honestly just conjecturing on the topic.
Actually, in Go, computers aren't even very good at tactics. Very basic tactics yes, but at a high, or even middling amateur level, issues that have yet to be successfully quanitified, become as important as raw territory in evaluating tactical success. Capturing 5 stones while letting your opponent get an outside wall is nearly always a tactical loss.
The other problem is that Go computers don't have great life and death engines, so the ultimate tactical issue of "If I let this group get cut off, will it live or die" is not something a computer is able to answer without reading the tree out to its most bitter end, or having a very specific pattern to match.
There's a sense in which computers are *weaker* at tactics in go than in strategy. If I play a very strategic, "peaceful" game with a computer, I will often still win, even giving 9 stones, but the better programs will appear to play at a 9-10kyu level. OTOH, I or players of my level can play all of these programs at 9 stones and win by well over 100 points, if we don't play "peacefully" but start lots of complicated tactical fights.
The real key to the weakness is the intersection of tactics and strategy -- the evaluation of *what* constitutes a tactical "win". A pro player has an excellent but hardly perfect sense of this. As a low amateur dan, I have a decent but very fuzzy sense of this. Weak players have little to no sense about it beyond the most obvious question of who has more completed territory. This is the position the computer is in. This is in contrast to chess where 95%+ of what can be considered tactical success can be well defined mathematically. So when the computer goes searching through the move tree in a chess game, it will recognize any clearly advantageous positions within its search depth. In go, existing evaluation functions are likely to grossly mischaracterize the value of various positions in the same way that rank beginners do.
So maybe you're right that this is essentially a strategic weakness, but oddly it shows up most strongly in what go players would consider "tactical fighting.
It's not as simple as just a larger search space. I've heard this before, but the fact remains that good chess playing algorithms are relatively simple and no similarly simple algorithms work well for Go.
The evaluation function is the critical problem. In Chess, you get a half decent evaluation function by looking *only* at material (and obviously checkmate). Assume the player who has more material is ahead. In conjunction with a standard minimax search, this alone probably gets the computer to around 12-300 Elo (good enough to beat me half the time).
Add in a few fairly easily encoded bits about the total number of squares attacked by each player, and the proponderance of center control (again, a very easy to code algorithm produces excellent, if not perfect results: just look at who has more attacks on a square as "control", and see who controls more of the key central squares. Add in a factor to judge what various amounts of center control are worth relative to material). To this general structure, add some pattern matching for a few thousand standard opening positions, and now you've got an algorithm that can play close to master level on an everyday PC.
In go, it's a whole different ballgame, because no one has *any idea* how to code an evaluation function that's remotely close to an accurate picture of who is ahead in the game. You can count territory, but unless you have a high level understanding of tactics, it's often not at all clear just what is really territory. Same for which groups are alive and which are dead, or which are connected and which are cut.
Oddly, the fact that the pieces move in chess makes it *more* tractable, not less. Because pieces move, positional advantages are transient and less valuable than material advantages in general. Which means that apart from the most fundamental ones (center control, file and diagonal control) they can be safely ignored, as long as your tactical reading is just a little bit better than your opponents.
In go, this is not the case. Because stones don't move, a positional advantage can last for most of the important part of the game. it's a standard style to let the opponent take territory and develop influence (and "thickness") with little firm territory in the early part of the game, then use these later to start fights on better terms and eventually close the territory gap, either by making a large territory yourself, or destroying through invasion what looked like territory for the opponent. Even players who use a "territorial" style, taking territory early and giving up influence, usually do so with a keen eye towards limiting the value of that influence, and great concern for their groups' "strength", meaning the ability resist later invasions/fights. They worry about this, their influence gathering opponent may be able to overwhelm them as the game progresses.
Clearly in order to execute these strategies, or keep from falling victim to them, a player needs to have some understanding of the value of various kinds of positional influence. Worse yet, all this valuation *depends* on tactical understanding. The difference between a beatiful powerful thickness and a problem group can be a single key cutting point that you don't have time to protect. People have been trying for 30 years to find algorithms which give accurate enough results to successfully end a search tree, and they haven't been able to do so. The obvious and simple versions (analagous to central square and file/diagonal control in chess) have all been tried and found wanting. Consider Bruce Wilcox's sector line concept, which was a great idea, but not good enough to make his program remotely strong.
The overall point here, is that while more time has probably been spent on chess, the search for a strong go program is not new, and a lot of brilliant people have been working on it for years. Getting a whole lot of masters in a room to encode openings, and Kasparov style into Deep Blue made a difference, because the basic, very simple, underlying brute force algorithm was already quite strong.
You could do all the same things with Go, and you would only improve go programs by a similar amount, maybe 500 elo points (the difference between Deep Blue, and a program that any decent software jockey could write after reading a paper on minimax and alpha/beta). But starting from a position of around 15kyu, that doesn't even get you close to amateur dan level, let alone world class.
The other thing to note is that a lot of this improvement is already in the best programs today. This kind of knowledge encoding is what's responsible for the difference between the best programs of today and the best of 10-15 years ago. The unstated assumption of your question is that there's been a whole lot more work done on computer chess than computer go in the last 30-40 years, and I'm not sure that's actually the case. Go has been a much hotter AI topic for at least the last 15 years. There are a lot of people producing chess programs because, being decent, they are much more marketable, but how many people are actually working on pushing the envelope of how well a computer can play chess? Nearly every writer of computer go software is seriously doing this. None of these folks is just throwing together known algorithms to get a computer player. They are doing research, and trying totally new approaches. Talk to some of them sometime.
BTW, I'd love to see these chess algorithms that are good which don't use minimax (brute force), or at least do so no more deeply or broadly than a typical human player. I don't think there are any programs like that stronger than a fairly weak amateur.
I think Bob might be right that it will take a general purpose AI to play Go, but I am nowhere near as sanguine as you or he about when that will come about.
I'll say flatly that there is almost *no* chance of a professional level computer Go program in the next 20 years.
I will be very impressed if computer opponents play at amateur dan level by that time, and I don't really expect it.
The problem is extremely hard and there just isn't a lot of energy being devoted to AI research. Unless that culture changes, and there starts being remarkable progress in the general state of AI research, I don't see the major breakthroughs happening in the near term (i.e. the next 50 years). If you look at the state of general AI, we're not really much further than we were 25 years ago.
There's a lot more polish, and incremental improvement, and a lot of field specific knowledge encoding, but not a great deal of general progress in the mental landscape since the AI winter of the 80s. AI is still very much out of fashion. I'm hoping it will become less so as we start to hit the wall of what faster and faster computers can do to make bad algorithms marginally acceptable, but that remains to be seen.
Of course, there's always the possibility of some crazy genius advancing things by leaps and bounds out of the blue, but I don't think you can count on that sort of thing, and without either that or a major chance in the research landscape, I'd say world class Go is at *least* a hundred year problem.
A note: There are no go programs that are actually 10 kyu measured by the same standards as humans. Computer programs get their rankings based on new opponents. Once people figure out how the computer plays, it's results get a lot worse (and certain people who tend to know how to beat computers can do this even on their first game with a program). The best programs around can only realistically play around 15-18kyu with people who know how to play them, or computers in general.
The biggest weakness of computers is in large whole board fights. They simply don't have the processing power to read them through to a conclusion, thus, the difference in a human's ability to evaluate a board position and the computer's becomes telling.
A few programs have been given fairly high ratings (like 3-5kyu) by Japanese federations based on watching a couple games and seeing that they do a lot of good normal things in their play. What is not seen is that most of those good things are just hard coded pattern matches and openings. If you draw them out of standard joseki and into big fights, they become ridiculously weak.
Slashdot Mirror
> Winning a tactical battle is something computers are okay at now. MPP is a
> useful optimization for analyzing a tactical situation. However, winning a
> particular battle may lead to you losing the game (and frequently it
> does), so the key problem is choosing the battles to fight. If there are
> three fights on the board, how do you choose among them? Right now we
> cannot answer that question, so we don't know if MPP will help or not. I
> was honestly just conjecturing on the topic.
Actually, in Go, computers aren't even very good at tactics. Very basic tactics yes, but at a high, or even middling amateur level, issues that have yet to be successfully quanitified, become as important as raw territory in evaluating tactical success. Capturing 5 stones while letting your opponent get an outside wall is nearly always a tactical loss.
The other problem is that Go computers don't have great life and death engines, so the ultimate tactical issue of "If I let this group get cut off, will it live or die" is not something a computer is able to answer without reading the tree out to its most bitter end, or having a very specific pattern to match.
There's a sense in which computers are *weaker* at tactics in go than in strategy. If I play a very strategic, "peaceful" game with a computer, I will often still win, even giving 9 stones, but the better programs will appear to play at a 9-10kyu level. OTOH, I or players of my level can play all of these programs at 9 stones and win by well over 100 points, if we don't play "peacefully" but start lots of complicated tactical fights.
The real key to the weakness is the intersection of tactics and strategy -- the evaluation of *what* constitutes a tactical "win". A pro player has an excellent but hardly perfect sense of this. As a low amateur dan, I have a decent but very fuzzy sense of this. Weak players have little to no sense about it beyond the most obvious question of who has more completed territory. This is the position the computer is in. This is in contrast to chess where 95%+ of what can be considered tactical success can be well defined mathematically. So when the computer goes searching through the move tree in a chess game, it will recognize any clearly advantageous positions within its search depth. In go, existing evaluation functions are likely to grossly mischaracterize the value of various positions in the same way that rank beginners do.
So maybe you're right that this is essentially a strategic weakness, but oddly it shows up most strongly in what go players would consider "tactical fighting.
Michael
It's not as simple as just a larger search space. I've heard this before, but the fact remains that good chess playing algorithms are relatively simple and no similarly simple algorithms work well for Go.
The evaluation function is the critical problem. In Chess, you get a half decent evaluation function by looking *only* at material (and obviously checkmate). Assume the player who has more material is ahead. In conjunction with a standard minimax search, this alone probably gets the computer to around 12-300 Elo (good enough to beat me half the time).
Add in a few fairly easily encoded bits about the total number of squares attacked by each player, and the proponderance of center control (again, a very easy to code algorithm produces excellent, if not perfect results: just look at who has more attacks on a square as "control", and see who controls more of the key central squares. Add in a factor to judge what various amounts of center control are worth relative to material). To this general structure, add some pattern matching for a few thousand standard opening positions, and now you've got an algorithm that can play close to master level on an everyday PC.
In go, it's a whole different ballgame, because no one has *any idea* how to code an evaluation function that's remotely close to an accurate picture of who is ahead in the game. You can count territory, but unless you have a high level understanding of tactics, it's often not at all clear just what is really territory. Same for which groups are alive and which are dead, or which are connected and which are cut.
Oddly, the fact that the pieces move in chess makes it *more* tractable, not less. Because pieces move, positional advantages are transient and less valuable than material advantages in general. Which means that apart from the most fundamental ones (center control, file and diagonal control) they can be safely ignored, as long as your tactical reading is just a little bit better than your opponents.
In go, this is not the case. Because stones don't move, a positional advantage can last for most of the important part of the game. it's a standard style to let the opponent take territory and develop influence (and "thickness") with little firm territory in the early part of the game, then use these later to start fights on better terms and eventually close the territory gap, either by making a large territory yourself, or destroying through invasion what looked like territory for the opponent. Even players who use a "territorial" style, taking territory early and giving up influence, usually do so with a keen eye towards limiting the value of that influence, and great concern for their groups' "strength", meaning the ability resist later invasions/fights. They worry about this, their influence gathering opponent may be able to overwhelm them as the game progresses.
Clearly in order to execute these strategies, or keep from falling victim to them, a player needs to have some understanding of the value of various kinds of positional influence. Worse yet, all this valuation *depends* on tactical understanding. The difference between a beatiful powerful thickness and a problem group can be a single key cutting point that you don't have time to protect. People have been trying for 30 years to find algorithms which give accurate enough results to successfully end a search tree, and they haven't been able to do so. The obvious and simple versions (analagous to central square and file/diagonal control in chess) have all been tried and found wanting. Consider Bruce Wilcox's sector line concept, which was a great idea, but not good enough to make his program remotely strong.
The overall point here, is that while more time has probably been spent on chess, the search for a strong go program is not new, and a lot of brilliant people have been working on it for years. Getting a whole lot of masters in a room to encode openings, and Kasparov style into Deep Blue made a difference, because the basic, very simple, underlying brute force algorithm was already quite strong.
You could do all the same things with Go, and you would only improve go programs by a similar amount, maybe 500 elo points (the difference between Deep Blue, and a program that any decent software jockey could write after reading a paper on minimax and alpha/beta). But starting from a position of around 15kyu, that doesn't even get you close to amateur dan level, let alone world class.
The other thing to note is that a lot of this improvement is already in the best programs today. This kind of knowledge encoding is what's responsible for the difference between the best programs of today and the best of 10-15 years ago. The unstated assumption of your question is that there's been a whole lot more work done on computer chess than computer go in the last 30-40 years, and I'm not sure that's actually the case. Go has been a much hotter AI topic for at least the last 15 years. There are a lot of people producing chess programs because, being decent, they are much more marketable, but how many people are actually working on pushing the envelope of how well a computer can play chess? Nearly every writer of computer go software is seriously doing this. None of these folks is just throwing together known algorithms to get a computer player. They are doing research, and trying totally new approaches. Talk to some of them sometime.
BTW, I'd love to see these chess algorithms that are good which don't use minimax (brute force), or at least do so no more deeply or broadly than a typical human player. I don't think there are any programs like that stronger than a fairly weak amateur.
Michael
I think Bob might be right that it will take a general purpose AI to play Go, but I am nowhere near as sanguine as you or he about when that will come about.
I'll say flatly that there is almost *no* chance of a professional level computer Go program in the next 20 years.
I will be very impressed if computer opponents play at amateur dan level by that time, and I don't really expect it.
The problem is extremely hard and there just isn't a lot of energy being devoted to AI research. Unless that culture changes, and there starts being remarkable progress in the general state of AI research, I don't see the major breakthroughs happening in the near term (i.e. the next 50 years). If you look at the state of general AI, we're not really much further than we were 25 years ago.
There's a lot more polish, and incremental improvement, and a lot of field specific knowledge encoding, but not a great deal of general progress in the mental landscape since the AI winter of the 80s. AI is still very much out of fashion. I'm hoping it will become less so as we start to hit the wall of what faster and faster computers can do to make bad algorithms marginally acceptable, but that remains to be seen.
Of course, there's always the possibility of some crazy genius advancing things by leaps and bounds out of the blue, but I don't think you can count on that sort of thing, and without either that or a major chance in the research landscape, I'd say world class Go is at *least* a hundred year problem.
A note: There are no go programs that are actually 10 kyu measured by the same standards as humans. Computer programs get their rankings based on new opponents. Once people figure out how the computer plays, it's results get a lot worse (and certain people who tend to know how to beat computers can do this even on their first game with a program). The best programs around can only realistically play around 15-18kyu with people who know how to play them, or computers in general.
The biggest weakness of computers is in large whole board fights. They simply don't have the processing power to read them through to a conclusion, thus, the difference in a human's ability to evaluate a board position and the computer's becomes telling.
A few programs have been given fairly high ratings (like 3-5kyu) by Japanese federations based on watching a couple games and seeing that they do a lot of good normal things in their play. What is not seen is that most of those good things are just hard coded pattern matches and openings. If you draw them out of standard joseki and into big fights, they become ridiculously weak.
Michael