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)."
Some slashdot lore. (Score:5, Insightful)
I fully expect someone to breathlessly explain the Great Goodness that is Chess.
Chess is fun. Go is fun. People have generally heard of both. That is all.
2X2 Chess? (Score:4, Insightful)
Re:Some slashdot lore. (Score:3, Insightful)
Oh a fanatic (Score:2, Insightful)
"a quarter of a full scale board"? (Score:5, Insightful)
In the past couple days, people have been talking about "cracking" an 80 bit hash with a 69 bit effort. It's logarithmic, people. 69 bits is not three-quarters of 80 bits, it's a factor of 0.000488 in terms of the workload to crack it.
SHA-1 is now 0.000488 (4.88*10-4) as strong as it was. And by my calculator, 5x5 go is 4.866*10-161 as hard as a brute-force solution as a 19x19 board would be.
Re:2X2 Chess? (Score:5, Insightful)
If we solve Go, will it still be fun? (Score:4, Insightful)
Re:In the interest of fairness... (Score:2, Insightful)
Re:October 2002 (Score:5, Insightful)
Re:How is this surprising? (Score:3, Insightful)
The other issue is that, regardless of search space size, go is inherently more difficult to evaluate. In chess, if the king is captured the game's over. In go, you have to count territory to determine a winner, and territory is space surrounded by stones. So to get an accurate territory count you have to know the life or death status of every stone on the board. Unless you have strong judgement this is very difficult. I'm a weak amateur myself, but I can trivially solve life/death problems that the very bext computer programs cannot. My understanding of it is that "solved" means, "one player can always force a win." IOW, you don't need to calculate moves anymore, just look up positions on a chart. Of course, given (for go) 361! positions, that's far from trivial. Even for chess the search space is enormous.
Re:Some slashdot lore. (Score:5, Insightful)
A Chess board is 8x8. One sixteenth of that is 2x2. It's a reasonable comparison, at least mathematically. The difference is that while Go at 5x5 is still strategic, if predictable, Chess at 2x2 is meaningless. One could say that Go happens to hold up well under that type of minimalist circumstance. One could also say that Go is just a physically larger game than Chess, and achieves a deeper degree of strategy through sheer insane volume.
But overall mathematically, it's a fair comparison.
Re:Some slashdot lore. (Score:5, Insightful)
I'm playing Go for long long time, and currently I'm about 1 dan. However, even when I was a novice of 20 kyu, and all these years in between, the game was always equally interesting to me. In fact, this is one of the main advantage of Go over chess. Until you're relatively good at chess, your game is very limited and there's no place for real creativity. In Go, you have planty of reasonable choices on every move, on every level.
Speaking of levels, Go has the great system of handicaps, which makes it interesting to play for players of really different strength.
Go is as complex as you want it to be. You can start playing meaningfully in 20 minutes, and you can master it all your life. It might sound like a cliche, but this is true.
Re:Some slashdot lore. (Score:4, Insightful)
Re:How long till they solve chess? (Score:1, Insightful)
(Is there something like an "algebra nazi"?
Re:Some slashdot lore. (Score:2, Insightful)
Can't completely agree with you about "the deeper degree of strategy" in Go. Larger number of playable positions perhaps, but only one type type of piece. With six different pieces, Chess has its own depths.
As other posts have observed, both games are great, as is backgammon.
"Solving" (Score:1, Insightful)
Why is this noteworthy? It's pretty straightforward, and known to be impossible for large games ( it has been calculated by 'some physics PhD in a popular book' that to 'solve' chess using a (hypothetical) maximally energy efficient cpu it would require one to convert the mass of Jupiter to pure energy just to power the cpu during the computation - Go is even worse. People do not play games by 'solving' them except maybe very simple ones like Tic Tac Toe. I'd be more impressed with a machine that could actually reason about games, forming powerful theorems and even unproved hypotheses which are improved upon when they don't pan out. For instance, you could state a theorem about chess that it is impossible for white to lose a piece in the first move, or a general unproven hypothesis like: it's good to control the board early in the game to restrict your opponent's movements and create opportunities for your self without knowing exactly what those oppertunities will be.
It's generally accepted among chess-heads that controlling the board early is a Good Thing, but maybe, in the space of chess games, more winning strategies are actually to be found where control of the board is not gained early. That has never actually been proven, it's only a hypothesis ( or maybe a theory since it seems pretty well accepted and seems to be borne out by actual chess games ) but if say, the actual 'solution to chess' were known and it happened to be a strategy that did not cease control of the board early for most sequences of opposing moves, and that player with the 'cheat sheet' for chess played some games, then that theory of chess would quickly fall out of favor to be replaced by the new stategem.
If life is a game, then maybe reasoning itself is rooted in the need for the ability to reason about games. Deception may not play much of a role in the lives of lions and tigers and bears, but for monkeys, the current battle is many times not the war. A male chimp may kowtow to the Bluto of the troop when he's around but then do the nasty with the lady chimps behind his back.
Among humans, goals are even more veiled. The road to X is rarely the direct route. You want a candy bar, you go to the store and buy it - seems direct, but it isn't. To get the 85 cents, you go to a job and earn your money. But to get that job you may have had to obtain college degrees, or certifications, and to do that you had to compete. To get hired you had to compete, and to get promoted you had to compete. The games you participated in probably had less to do with being valuable so as to make your paycheck a good deal for your employer than with gaming so as to appear that way - especially if you have been successful in getting anywhere - nobody ever got to be boss by being a good laborer, the games you have to play to be boss take too much time for someone who spends all their effort working to compete in. Some may find this amoral, but be assured that those who are successful most likely do not even know they are useless fucks who reap all the reward.
They probably assume everyone games as much as they do and when they are rewarded they are certain it is because they really *are* more valuable and they actually think they *deserve* it. To think otherwise would offend their own egos. In fact, if your desire to masturbate your own ego does not make you stupid enough to accept the top seat with a straight face, then you either accept being 'evil' to some extent and wear a poker face, or you put your nose to the grindstone to be an even more valuable resource to exploit ( a lot of currently technical people who didn't spend all their time 'gaming' for popularity in high school because they didn't enjoy it have taken this route. Then they find that labor is labor and that they can not charge more than the third world shmoe who will charge the leas