Computer Cracks 5x5 Go

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)."

Comments

Some slashdot lore.

[Eunuch]

Slashdot has a longstanding joke that with every chess article, some wide-eyed enthusiast will blurt out a quick description of Go like he's first to discover it in all the West. Speed is essential! There may be some pasty white guy who does not know the wonder that is Go.

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.

Re:Some slashdot lore.

[Anonymous Coward]

I find it most amusing that they describe a 5x5 Go board as a quarter of the size of a full-sized go board... a full size go board is 20x20, so 5x5 is a sixteenth-sized go board. It's only a quarter sized if you only measure linearally, rather than spacially.

Re:Some slashdot lore.

[cgenman]

A Go board is 19x19. This solution was for 5x5. Saying that it is a quarter of the size of the full board is incorrect, it's actually one fourteenth the size.

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.

[igrek]

I disagree completely. Completely.

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.

[Asmodai]

Of course, kyu is the rating from Japan. If using Korean rules you use gup.

Re:Some slashdot lore.

[yodhe]

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.

2X2 Chess?

[tritone]

Go scales downwards in a logical way, but 2X2 chess is either absurd or trivial depending on what pieces you decide to place there. The "equivalent" chess problem is probably more along the lines of 4x4 or 5x5.

Oh a fanatic

[Eunuch]

You notice there's no chess players proclaiming its superiority to Go. What is this, frustration from the fact that Go doesn't help with getting an Asian girlfriend?

"a quarter of a full scale board"?

[Speare]

A 5x5 go board is not a quarter of a full scale board. It is only roughly a quarter in each dimension. A full go board, if I recall, at the size most people play, is 19 by 19 intersections. That's 361 positions. A 5x5 only has 25 positions. Each intersection can theoretically contain three states.

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?

[_Pablo]

In my opinion, for it to be chess, it would have to have two kings otherwise no one could win. Therefore 2x2 chess would start with checkmate and is absurd.

If we solve Go, will it still be fun?

[Eunuch]

I think it will. We still have weightlifting competitions even though we have forklifts at our disposal.

Re:In the interest of fairness...

[maino82]

Go may have simpler rules than chess, but it by no means a simple game. When I tell my friends about Go they laugh at me, but after explaining the game to them and giving them a 9 stone handicap and thoroughly trouncing them (I'm only around 12kyu... practically a beginner) they begin to see the game is much more complex and subtle than they anticipated. A computer program playing Go would have to be much more adaptive than a program playing chess, or have a much quicker algorithm to process the insane number of possible moves and responses. In either case, research into a computer that can play Go and can beat a human is something that is extremely worthwhile and applicable not just in Go, but in other AI applications as well. Don't get me wrong, research into chess playing programs is just as worthwhile, but any advance in Go will be orders of magnitude more impressive than any advance in playing chess.

Re:October 2002

[Xzzy]

Obviously their control extends deeper than any of us can imagine, for they conspired to mod my post insightful instead of the coveted +5 funny.

Re:How is this surprising?

[legLess]

But couldn't one turn chess into a 'spectacularly complex' game by increasing the number of squares say... to 16*16? Or even into 3D :-)

Yes, but then it wouldn't be chess anymore. You'd need more pieces, for one thing. Go, on the other hand, requires no rule changes at all to scale to any size. There are only four rules, none of which depend on board size.

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.

For chess to be 'solved', would a computer have to know definite answers to the best moves...

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.