Re:I agree... no time soon..
on
Cracking Go
·
· Score: 1
As for the math.. I am curious to see how he explains the following statement:
"Put it all together and you should be able to build a machine that searches more than 100 trillion positions per second--easily a million times as fast as Deep Blue.
That would be enough to build a tree of analysis for Go as big as Deep Blue's was for chess and to evaluate all its end positions properly. If we assume the top Go players calculate about as deeply as the top chess players do, the result should be a machine that plays Go as well as Deep Blue played chess.
Well enough, that is, to beat any human player."
According to http://en.wikipedia.org/wiki/Go_complexity (I know.. not the end all of sources but fairly reliable), the game-tree complexity of go is 10^360. According to wikipedia John Tromp and Gunnar Farnebäck showed that of those moves.. only 10^172 are legal. These estimates seem to be on the lower end of other views of its complexity. So anyway.. the paper states two methods to trim this huge tree... 1) If you find a move that is not as good as another, don't go further down that path. 2) I don't really understand the details (he doesn't give them) but he would cache results already decided and wouldn't have to recalculate those paths until something interfered with it.
So for (1) It seems really hard to decide which move is better than another as mentioned earlier (2) Things are jumping around quite a lot on a board and I think the caching would lose its effectiveness. If we isolate only the right third of the board and there is a corner group on each side and a group in the middle... as these groups take form they will influence how the other groups form and will need to be recalculated often. A human does this with visualization and intuition.
So let's say there are 10^172 moves that may need to be traversed. Let's say that by a miracle of branching tactics mentioned in (1) the computer decides that one trillionth of a percent of these moves are viable. That leaves us with 10^158. Okay.. still have a huge number. Since (2) above seems pretty fuzzy... lets just go ahead and cut the exponent into a fourth(thats a big feat I think). That leaves us with about 10^40 board positions to evaluate. So 10^40 boards * 1 seconds/10^14 boards = 10^26 seconds. So how long is this? 10^26 seconds / 60 / 60 / 24 / 365 = about 10^18 years.
Now I know that there are complications that could make this math not exactly accurate. I don't really know how to guestimate how many trees his two methods could cut off. I do feel however that my guesses were not on the light side.. they were on the heavy side. I don't know much about complexity theory.. but it seems to me that his statement shown above seems very optimistic. He says that a computer like this would have a depth tree as deep as Deep Blue's was for chess. Does he mean depth of moves? We already know that there is a much greater depth of moves in go than chess.. what does he mean by that?
Anyway.. it seems very optimistic and he might be a very bright guy.. but his success with Deep Blue may have clouded his logic.
Re:I agree... no time soon..
on
Cracking Go
·
· Score: 1
Another two points..
Toward the endgame.. a computer would do well.. it can calculate ahead since the available paths are dying out. There are a limited number of positions and life and death of final groups is something a computer can handle.
The opening also has some promise for the computer. There are joseki patterns (corner play) that in some cases have fairly well diagrammed lines of play. Versus a low level player.. the computer could probably trap the human opponent. However.. when pros or even upper-intermediate players play.. they often get into positions that are not better for either person. You can often read that joseki xyz leaves black in a fair position for moving along the bottom edge while white is in a fair position for moving into the left center. It's not really cut and dry who wins a joseki unless one of the players makes a mistake.. and there are multiple paths in joseki that lead to "even".
This leads us to the middle game and this is where I feel the modern computer is quite hopeless. There are still a huge number of available spaces to move.. at this point the corners are starting to take shape.. there may be some groups that are pushing against each other around the sides... the question is.. where to move now? Which of the groups have the best tactical and strategic options? How should you balance territory and influence? How many moves should you dedicate to this group before you move into that group over there? Should you sacrifice this medium sized group to gain a positional advantage? If you are fighting over a group and the opponent starts pushing you back.. will you pieces lie in a position that is favorable? There are so many questions like this and the game is all about balance. I think the algorithms that come out of such research are interesting.. but how do you decide which of these 100 factors is most influential to your next move? I think the algorithms will be very narrowly focused and would prove weak vs. another player.
Pattern recognition is very important in the game and I just don't think computer algorithms (maybe even our view of hardware) are up to the task of making decisions like this now. Deep Blue vs. Kasparov is a much simpler case. The lines of what is good and bad are much more clearly drawn (maybe not black and white.. but not the flat gray of go).
I did think that the article had a very optimistic tone. I am curious how much the researcher has played go.
I agree... no time soon..
on
Cracking Go
·
· Score: 5, Interesting
I have played a lot of go and am a programmer. This will not be solved anytime soon unless there is a very big breakthrough in AI.
Go is challenging to program for many reasons:
1) There is a ridiculous number of moves. As mentioned in the article.. there are 361 factorial moves as the game progresses. Many of these would never be done (a player would not move on the outer most edge of the board in the early stages). Some extra moves can happen as you kill groups and move new pieces into their positions. And of course.. both players pass well before the game is over.. so the board will never be filled up. So there are some limits on this huge number.. but whatever it turns out to be... it is crazy bigger than chess's possible moves.
2) The rule set is much less restricted. In chess... you are very restricted.. each of the 6 types of pieces have very specific rules. All except the knight is blocked by other pieces. In go.. you can move almost anywhere you want (it may not be the best idea but there are no rules about not moving to an empty spot). I say almost because you cannot actually kill you piece by placing it into a spot that would immediately kill it. These spots however are small in number to the number of spots you can move.
3) It is extremely difficult to decide the current state of the game with regards to one position being better than another. In the article he mentioned being able to shorten the move search tree by neglecting paths that led to worse positions. The earlier parts of the game are extremely difficult to decide. In fact.. there is probably no correct answer. This is probably one of this biggest issues with getting a computer to play effectively. There are probably spots that the computer with proper algorithms could deem as not so good.. but what about the 500,000 other positions that may turn out good.. may turn out bad. I think it would have a difficult choice when it has so many positions that it cannot grade as good or bad.
4) The delicate balance between whole board and small area (strategy vs. tactics). He mentions in the article that the computer could focus on a small subsection of the board at a time. This is fine and dandy when the computer can magically know which of the small subsections is vital. As a 19x19 game progresses (especially earlier in the game) there are for example 20 zones of the board that could become hot very fast. If one player takes initiative in a section.. they may only play 3-8 moves there and then jump to a completely different section of the board. These to positions (potentially) will collide.. and the way that the player built these two sections and the way they collide is very important.. this will greatly hinder the computer simply focusing on a subset on the board... that would be to focus on tactics.. and strategy and tactics are constantly balancing back and forth in the human players mind.
5) The human player makes new algorithms as they learn more about the game. One of the trickiest things about go is that there are no sets of rules that define a good move. There are "proverbs" which sometimes are philosophical about the game. Sometimes these are even contradictory. I doubt very much that people will find the golden set of algorithms that describe good play.. at least in a way that a modern computer interprets language.
In the end... I think one day we will have a computer that will be better than people at go. The only thing is.. I am very sure that it will be a very long time from now.. or after a breakthrough happens in AI. Anyone who has played the game for at least 20 games on a 19x19 will see the amazing explosion of possible moves. They will feel how sometimes there are 10 hotspots that you just wish you could move, but you only have one. They have felt what it feels like to be focused on an area of the board and suddenly, due to their opponents craftiness, jump to a whole different area of the board and suddenly.. that area becomes vital. A single move can make a relatively safe area dreadfully
Slashdot Mirror
As for the math.. I am curious to see how he explains the following statement: "Put it all together and you should be able to build a machine that searches more than 100 trillion positions per second--easily a million times as fast as Deep Blue. That would be enough to build a tree of analysis for Go as big as Deep Blue's was for chess and to evaluate all its end positions properly. If we assume the top Go players calculate about as deeply as the top chess players do, the result should be a machine that plays Go as well as Deep Blue played chess. Well enough, that is, to beat any human player." According to http://en.wikipedia.org/wiki/Go_complexity (I know.. not the end all of sources but fairly reliable), the game-tree complexity of go is 10^360. According to wikipedia John Tromp and Gunnar Farnebäck showed that of those moves.. only 10^172 are legal. These estimates seem to be on the lower end of other views of its complexity. So anyway.. the paper states two methods to trim this huge tree... 1) If you find a move that is not as good as another, don't go further down that path. 2) I don't really understand the details (he doesn't give them) but he would cache results already decided and wouldn't have to recalculate those paths until something interfered with it. So for (1) It seems really hard to decide which move is better than another as mentioned earlier (2) Things are jumping around quite a lot on a board and I think the caching would lose its effectiveness. If we isolate only the right third of the board and there is a corner group on each side and a group in the middle... as these groups take form they will influence how the other groups form and will need to be recalculated often. A human does this with visualization and intuition. So let's say there are 10^172 moves that may need to be traversed. Let's say that by a miracle of branching tactics mentioned in (1) the computer decides that one trillionth of a percent of these moves are viable. That leaves us with 10^158. Okay.. still have a huge number. Since (2) above seems pretty fuzzy... lets just go ahead and cut the exponent into a fourth(thats a big feat I think). That leaves us with about 10^40 board positions to evaluate. So 10^40 boards * 1 seconds/10^14 boards = 10^26 seconds. So how long is this? 10^26 seconds / 60 / 60 / 24 / 365 = about 10^18 years. Now I know that there are complications that could make this math not exactly accurate. I don't really know how to guestimate how many trees his two methods could cut off. I do feel however that my guesses were not on the light side.. they were on the heavy side. I don't know much about complexity theory.. but it seems to me that his statement shown above seems very optimistic. He says that a computer like this would have a depth tree as deep as Deep Blue's was for chess. Does he mean depth of moves? We already know that there is a much greater depth of moves in go than chess.. what does he mean by that? Anyway.. it seems very optimistic and he might be a very bright guy.. but his success with Deep Blue may have clouded his logic.
Another two points..
Toward the endgame.. a computer would do well.. it can calculate ahead since the available paths are dying out. There are a limited number of positions and life and death of final groups is something a computer can handle.
The opening also has some promise for the computer. There are joseki patterns (corner play) that in some cases have fairly well diagrammed lines of play. Versus a low level player.. the computer could probably trap the human opponent. However.. when pros or even upper-intermediate players play.. they often get into positions that are not better for either person. You can often read that joseki xyz leaves black in a fair position for moving along the bottom edge while white is in a fair position for moving into the left center. It's not really cut and dry who wins a joseki unless one of the players makes a mistake.. and there are multiple paths in joseki that lead to "even".
This leads us to the middle game and this is where I feel the modern computer is quite hopeless. There are still a huge number of available spaces to move.. at this point the corners are starting to take shape.. there may be some groups that are pushing against each other around the sides... the question is.. where to move now? Which of the groups have the best tactical and strategic options? How should you balance territory and influence? How many moves should you dedicate to this group before you move into that group over there? Should you sacrifice this medium sized group to gain a positional advantage? If you are fighting over a group and the opponent starts pushing you back.. will you pieces lie in a position that is favorable? There are so many questions like this and the game is all about balance. I think the algorithms that come out of such research are interesting.. but how do you decide which of these 100 factors is most influential to your next move? I think the algorithms will be very narrowly focused and would prove weak vs. another player.
Pattern recognition is very important in the game and I just don't think computer algorithms (maybe even our view of hardware) are up to the task of making decisions like this now. Deep Blue vs. Kasparov is a much simpler case. The lines of what is good and bad are much more clearly drawn (maybe not black and white.. but not the flat gray of go).
I did think that the article had a very optimistic tone. I am curious how much the researcher has played go.
I have played a lot of go and am a programmer. This will not be solved anytime soon unless there is a very big breakthrough in AI.
Go is challenging to program for many reasons:
1) There is a ridiculous number of moves. As mentioned in the article.. there are 361 factorial moves as the game progresses. Many of these would never be done (a player would not move on the outer most edge of the board in the early stages). Some extra moves can happen as you kill groups and move new pieces into their positions. And of course.. both players pass well before the game is over.. so the board will never be filled up. So there are some limits on this huge number.. but whatever it turns out to be... it is crazy bigger than chess's possible moves.
2) The rule set is much less restricted. In chess... you are very restricted.. each of the 6 types of pieces have very specific rules. All except the knight is blocked by other pieces. In go.. you can move almost anywhere you want (it may not be the best idea but there are no rules about not moving to an empty spot). I say almost because you cannot actually kill you piece by placing it into a spot that would immediately kill it. These spots however are small in number to the number of spots you can move.
3) It is extremely difficult to decide the current state of the game with regards to one position being better than another. In the article he mentioned being able to shorten the move search tree by neglecting paths that led to worse positions. The earlier parts of the game are extremely difficult to decide. In fact.. there is probably no correct answer. This is probably one of this biggest issues with getting a computer to play effectively. There are probably spots that the computer with proper algorithms could deem as not so good.. but what about the 500,000 other positions that may turn out good.. may turn out bad. I think it would have a difficult choice when it has so many positions that it cannot grade as good or bad.
4) The delicate balance between whole board and small area (strategy vs. tactics). He mentions in the article that the computer could focus on a small subsection of the board at a time. This is fine and dandy when the computer can magically know which of the small subsections is vital. As a 19x19 game progresses (especially earlier in the game) there are for example 20 zones of the board that could become hot very fast. If one player takes initiative in a section.. they may only play 3-8 moves there and then jump to a completely different section of the board. These to positions (potentially) will collide.. and the way that the player built these two sections and the way they collide is very important.. this will greatly hinder the computer simply focusing on a subset on the board... that would be to focus on tactics.. and strategy and tactics are constantly balancing back and forth in the human players mind.
5) The human player makes new algorithms as they learn more about the game. One of the trickiest things about go is that there are no sets of rules that define a good move. There are "proverbs" which sometimes are philosophical about the game. Sometimes these are even contradictory. I doubt very much that people will find the golden set of algorithms that describe good play.. at least in a way that a modern computer interprets language.
In the end... I think one day we will have a computer that will be better than people at go. The only thing is.. I am very sure that it will be a very long time from now.. or after a breakthrough happens in AI. Anyone who has played the game for at least 20 games on a 19x19 will see the amazing explosion of possible moves. They will feel how sometimes there are 10 hotspots that you just wish you could move, but you only have one. They have felt what it feels like to be focused on an area of the board and suddenly, due to their opponents craftiness, jump to a whole different area of the board and suddenly.. that area becomes vital. A single move can make a relatively safe area dreadfully