Computer Cracks 5x5 Go 442
gustgr writes "The American Go Association is reporting that Go for the 5x5 board has been solved by the computer program MIGOS, reports the program's creator, Erik Van Der Werk, a professor at the University of Maastricht in Holland. At about a quarter of the full-board version, 5x5 go is miniscule, similar in scale to "solving" 2X2 chess. The fact that a programmer would even consider this a noteworthy challenge is itself a remarkable testament to the game's complexity. Van Der Werk's approach is described in detail in an
article at the Netherlands Organization for Scientific Research (NOSR)."
How is this surprising? (Score:2, Interesting)
Re:Some slashdot lore. (Score:5, Interesting)
Re:How is this surprising? (Score:2, Interesting)
Re:How is this surprising? (Score:5, Interesting)
Or so I would assume, I've never actually tried to make a program for either, but it would appear so to anyone who has played more than a few games of each.
How long till they solve chess? (Score:5, Interesting)
Re:2x2 chess? (Score:2, Interesting)
The mathematical rules (Score:5, Interesting)
The Alternating Rule:
Two players, called Black and white, keep alternating moves till the end of the game. Black plays first. A move by a player begins by his placing a stone on an empty intersection of the go board. The first player who cannot put down a stone without breaking a rule loses the game.
The Rule of Capture:
After a stone is placed on the board, all enemy stones which have no liberties are removed. A player's move is not finished until this phase has been completed.
The Rule for Suicide:
Suicide is illegal. Precisely, after a stone has been played, and after the rule of capture has been applied to his enemy stones, if the stone has no liberty, then the move was illegal.
The SuperKo Rule:
A player is not allowed to place down a stone if, after the rule of capture has been applied, the resulting Board position has appeared previously in the game.
arthur c clarke story (Score:3, Interesting)
Re:Um, who wins? (Score:1, Interesting)
What?? (Score:3, Interesting)
Sorry, but that's like a full chess board with the pawns removed (if even that much).
5x5 Go is still fairly complex. Although the article is old (2002), I'd still like to see a caltulation time comparison.
2x2 chess can be solved in a manner of seconds/microseconds. 5x5 Go might take a few days to brute force it.
Re:How long till they solve chess? (Score:5, Interesting)
The number of chess positions is, very naively and as a significant underestimation, something like C(8, 64) * C(8,56) * C(8, 48) * C(8,40).
Even this severe underestimation gives 1.8E35, or about 2^117.
Let's say that 2^80 problems are crackable today and that we wouldn't have the non-locality problems of chess (a move consists of computing another position and then you have to see if that is already in the database of computed moves, not as parallel as just trying encryption keys 'til it works). The added 2^37 is on the scale of 13 billions. If 2^80 is done in a year now, this would require the age of the universe.
We can guess that we, if lucky, get to trust Moore for our lifetimes. Hoping that it will get better than that is a long shot, in my mind. The development of computing speed for computing machines in the Turing sense will probably rather slow down. Even if the current speed of increasing computation capacity was maintained and chess would be as simple as encryption testing (calculating moves is simpler, coordinating the effort and addressing the memory isn't), it would taket 56 years to get to the point where a run would take a year -- based on extremely optimistic assumptions.
Finally, we haven't even got to the point about how to store all that information. 6E23 hydrogen atoms weigh about a gram (Avogadro and all that). Let's say we store one bit for each atom. We would need one billion kilograms of storage to store one bit for each of the possible chess positions. To reach less than 1 bit/position seems quite hard...
Versus people or computers? (Score:2, Interesting)
Re:Go... (Score:2, Interesting)
Re:Chess vs Go (Score:5, Interesting)
It should be noted that even on a 9x9 board (let alone 19x19), competent amateurs can beat any computer program.
19x19, 13x13, and 9x9 (the "standard" sizes, though 7x7 is fun sometimes), require totally different strategies. 9x9 is pure life and death, 13x13 is mostly fighting, and 19x19 requires a good understanding of balancing influence for defined territory (don't spread your stones too thin while not letting them get bunched up).
For all who don't play go or are new to go, the biggest problem with the 19x19 and even 9x9 computer programs is that the computer can't see the dual threat someone might play with a sequence of moves. For example, you can start to attack a specific section of the board, and use what you played to grab hold of an even larger section of territory, or even kill a large portion of their stones. It's easy to fool the computer in Go.
Re:October 2002 (Score:5, Interesting)
4-hours is on a single p4 machine is just a joke.. but good point though, solving a game takes alot of time. University of Alberta (Canada) have been working on solving checkers (which is a much simpler game) for years. I think they are about half done with that. They are just using search, as checkers has low branching factor compared to Go
Van der Werf also investigated learning techniques, which are used in games such as backgammon
I belivie this is the way to be able to create a decent Go program, by learning (Reinforcement Learning, because Backgammon techniques). Brute force search gets boring, no matter how advanced it is!
To put this in perspective for non-go players... (Score:5, Interesting)
Presently, if a typical geek started playing Go, they would get their ass kicked by the weakest computer for a week or two.
After a month, they would be winning the odd game, if the computer gave them a 3-stone headstart. (Like 3 free moves to start in chess).
After three months, they would win some games in an even match against the weaker programs (Turbo-go)
After six months, they would be winning against a 3-stone or higher handicap for the computer.
Then they find a stronger Go program.
They start to lose every match again.
After another month or so, they start to win on the weaker levels.
Take it six months ahead, and they are smashing the computer in an even match with no handicap, playing white (white moves second) or at lower levels against a 3 or 4 stone handicap.
The only thing that makes the game playable against a computer is that Go has an incredible handicapping system that lets uneven players play against each other.
So what makes this story interesting? Aside from the brute strength issue?
The first moves of the game, often in the corners in roughly a five-by-five area (Joseki) are only recently being evaluated for best move potential...
That can affect the outcome of professional matches played for big $$$$.
But more importantly for people like me, I can't play humans much... Kids, wife and home environment mean I can't spend 30 minutes undisturbed, so playing against human opponents is out for me.
Any technology that makes computer programs stronger, improves algorythms or makes me play harder will keep my morning bus trips interesting.
Because Go programs have got a long way to go if they are easily defeated against a human opponent with just 1 year experience.... Who would be easily classed as a novice let alone just a weak player.
GrpA
Re:How is this surprising? (Score:5, Interesting)
Well, on the one hand go is much harder, etc. etc., other people have explained this already. On the other hand, I don't think it surprised anyone seriously interested in computer go, that 5x5 can be done by brute force. Every serious go player can read out quickly that it is a full-board win for black. If Black's starting move is restricted, it takes a little more care to read it out, but I would be confident to read the out the correct play for both sides in a couple of minutes. Further, the essential key algorithm (position evaluation according to so-called "unconditional territory") used by Erik has long been known.
This is not to belittle Erik van der Werf's achievements. In fact to the contrary. His more interesting program is MAGOG, which plays 9x9 go. AFAIK, in the end of the game, it uses the same algorithm as MIGOS, and thus plays perfectly (given enough time, and not too complicated a position). Before that, it combines traditional goal-directed search (tactical search, "life-and-death-search") with a lot of brute force global search. Although his program is pretty young by computer go standards (ALL the top programs started to get developed in the 80's), it has shown to be a serious competitor in recent computer go tournaments.
Pattern recognition (Score:1, Interesting)
Seems kinda obvious so there must be something wrong with it but I'm not sure what it is.
Re:Ridiculous. (Score:1, Interesting)
An Idea (Score:2, Interesting)
One approach I have always wanted to try is this:
set up a massive neural net that takes the state of the entire board as input, goes through way too many intermediate layers, and spits out a preference for spots to play. The state of the neural net could be exhaustively described with a few tens of thousands of [0,1] doubles.
Then set up "breeding" algorithm, make a few hundred instances of the program, each with its own neural net, and then have them pretend to be users on an internet Go site. Don't try to understand how they play, just let them figure it out. You could even, on occasion, let them play eachother...
I don't know if this would produce a good genome ever, but I'd be interested to see where it went regardless.
Does anybody know if this sort of thing has been tried before?
Re:How long till they solve chess? (Score:1, Interesting)
Um. That only works in connect 4 and other systems which decrease the possible number of states the board is in. Chess does not require each play to decrease the possible number of sucessive plays.
" A quantum computer could just solve the problem from any state. It would just calculate the answer right then and there, you wouldn't need to store all possible answers."
Er.. that's more of what we'd call a "magic computer". A quantum computer still would need to calculate the data and store the data that it is calculating.
Re:Some slashdot lore. (Score:5, Interesting)
You asked for it...
Each game of chess means there's one less variation left to be played. Each day got through means one, or two, less mistakes remain to be made.
Not much is known of early days of chess beyond a fairly vague report, that 1500 years ago two princes fought though brothers for a Hindu throne. Their mother cried, for noone really likes her offspring fighting to the death. She begged them stop the slaughter with her every breath, but sure enough one brother died.
Sad beyond belief, she told the winning son "You have caused such grief, I can't forgive this evil thing you've done." He tried to explain how things had really been, but he tried in vain; no words of his would satisfy the queen.
And so he asked the wisest men he knew the way to lessen her distress. They told him he'd be pretty certain to impress by using model soldiers on a checkered board to show it was his brother's fault.
They thus invented... Chess!
(now there's some REAL Slashdot lore for ya)
I wrote the first commercial Go playing program (Score:5, Interesting)
Go is such a great game. In the 1970s, I got to play exhibition games with Miss Kobyoshi (women's world champion) and Mr. Lee (national champion of South Korea). The high level of their play really blew me away - getting slaughtered was a surprisingly great experience.
The Gnu Go program plays a good game, BTW. It is best to play against human opponents, but give Gnu Go a try also. Just like studying chess, if you get into playing Go, make sure you study complete master games: studying opening, middle game, and end games in isolation just does not cut it.
Re:Ridiculous. (Score:5, Interesting)
How do you know what a move is worth without knowing its effect?
Uh, when you're solving a game, there's no such thing as a move. You consider only board states, not the moves which lead to them, except in determining in which order to evaluate states. In this way it's trivial to understand how the value of a board in an infinite cycle between two paired positions - say, two kings moving back and forth between their same two cells each turn on a chess board - have up to four board scores through which they oscillate (unless there's a terminate-at-N-moves rule like in chess, but whatever.)
The only true way to "solve" is not to consider all game states, but to consider all possible paths
Game theory 101: the board states are the only thing there is. There are no "paths" - there is no difference between a board which has had a cyclic move applied to it ten thousand times than one which hasn't gone through them at all.
Solve has a very specific mathematical definition here - that the perfect response is known for every move. For games of no chance and perfect information such as go, chess and so forth, the traditional way to handle this is to create the entire move ply tree and then follow through the paths of least risk. When that tree is completed, you know for every possible board state every possible result of every move, and therefore know what exactly the best move is.
In this way you can find out that some games are balanced (tic tac toe, for example, is always a tie with perfect play with both sides) whereas other games are unbalanced (with perfect play by both sides, the second player will always win at connect-4; there is nothing player 1 can do.)
The reason chess remains unsolved is that its solution tree is so preposterously huge that even by modern computing standards it's just an absurd thing to want to attack, even given twenty years and positing 20 years' hardware development.
By the way, what I described above is not the only way to sove a game; if you'd like to find out how the branch of mathematics called Game Theory works, I recommend the primers "The Compleat Strategyst" (yes, it's spelled like that) and "Game Theory: a Nontechnical Introduction."
Common sense as what you're saying may seem, John von Neumann proved you quite wrong in the early 50s. I suggest you read up before challenging these terms; they're very well defined.
(note: the board never gets completely full, game stops before, when no more territory can be made, and playing into enemy territory would be suicide inviting a pass from the opponent while the invasion stones still being dead, increasing the enemies points.)
Er, yes, I know how Go works, and that's what I was referring to when mentioning that I was counting impossible boards. The number I quoted is the mathematically-derived high end cap on possible board definitions as a simple string of radix-3 digits. Observing that you can reduce the solution space here does you no good: you're only making my job easier.
Now take those 847,288,609,443 possible states, and consider all the sequences through which you can travel
That's a giant waste of time. Watching the ko cycle doesn't change the board, and since Go is scored not on held piece count but rather difference in held piece counts, the scores aren't changing either. It really doesn't matter how you got to a board - if you play squares a,b,c,d,e,f in order then the next game you play f,a,b,e,c,d, nothing has changed; your opportunities are still exactly the same.
because you can't just look at a position and "evaluate it" without knowing the "future" it holds
Re:Go... (Score:3, Interesting)
Which is a problem, but not the main one. The real advantage of computer chess over computer go is the relative ease with which the leaves of the search tree (e.g. all positions after n moves) can be evaluated statically. In chess you can perform excellent static evaluation by counting material, mobility, king safety and maybe a few other features. In Go, static evaluation is considered difficult for an expert, let alone a computer.
Re:Go... (Score:2, Interesting)
There are 20 potential moves in the first iteration for chess, and exactly 361 (19*19) for Go.
There are around 10^120 possible chess games, and around 10^760 possible Go games. That's why the milion-dollar prize for the first program to beat 1-dan Go player is still not taken.
Re:October 2002 (Score:3, Interesting)
Funny how it was the American Go Association [usgo.org] who reported this...
They were always a bit slow compared to the Dutch in mathematics.
I've read about this and 6x6 being solved a *long* time ago already here:
http://senseis.xmp.net/?SmallBoardGo
Re:Go... (Score:3, Interesting)
http://jhubert.club.fr/Go/Parties/Takagawa_GoSe
I'm not sure what you're saying about the result is correct. I advise you to read the page i've linked above and google around for other information related to the situation.