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.

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.

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