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

October 2002

From the friendly article:

Subject: computer-go: 5x5 Go is solved
Date: Sun, 20 Oct 2002 15:27:04 -0100
From: Erik van der Werf
To: COMPUTER GO MAILING LIST

The fact that an editor would even consider this a newsworthy article is itself a remarkable testament to the site's simplicity.

Funny how the stock market crashed [greekshares.com] the day before 5X5 Go is solved.

Re:October 2002

Sometimes I wonder if there's some secret society of geeks that scour geekly websites for neat stuff, who's only flaw is being several years old.

They make a contest of it.. whoever gets an old geek story posted on slashdot, wins the round.

It's such an obvious sport to invent, considering all the heckling slashdot editors recieve. I'm not quite prepared to accept that so many old stories get submitted out of ignorance.

Someone, somewhere, is toasting themselves to a beer right about now.

Re:October 2002

from the website;The solution was found at 22 ply deep (23 for the empty board).(searching 4.472.000.000 nodes in about 4 hours on a P4 2.0Ghz)

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!

Some slashdot lore.

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.

People on Slashdot probably fall into a different demographic, but I've found that people generally haven't heard of Go. They'll recognize a chess set by site, but they see Go and if you're lucky they assume Reversi or Othello. I was in the student lounge with a friend who was teaching me how to play Go, and somebody asked what game we were playing. When we told him, his reply was, "Go? I thought that was a card game."

Re:Some slashdot lore.

A full-size Go board is 19x19, but you're right in your main point.

Re:Some slashdot lore.

It's only a quarter sized if you only measure linearally, rather than spacially.

Arm yourself against spelling flames first, Grasshopper. Only then will your math flames stand up to the foe.

rj

2002?

What is this, Classic Slashdot? Next do we get a story on the impending end of the dot-com bubble?

Size?

5x5 is 1/4 the size of 19x19??? More like 1/14th.

Re:Size?

No, 18 by 18 squares, the game is played on the vertices which is 19 by 19. There's a centre vertex, see?

Go...

The way that chess games work is they check n ammount of moves into the future. With each iteration into the next move it splits off into a massive tree of moves. As an example, the first iteration has 10 potential moves, the next has 100 and the next has 1,000 With Go as an example there may be 100 potential moves on the first iteration and then 10,000 and then 10,000,000 The number of potential moves grows way faster then in chess.

yep

Check out this [nyud.net] for a decent comparison between chess and go for those of you who have been missing out.

Also, dig my sig biotches.

"a quarter of a full scale board"?

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.

How long till they solve chess?

I've always believed within my lifetime, chess would be solved. In other words, a computer would come up with the perfect solution to chess so that no matter what moves you possible make, out of the, i dunno, billions, trillions, or higher number of possible moves, the computer knows how to beat you. The simplest comparison I can think of is tic-tac-toe. If you've played tic-tac-toe enough, you've learned that no matter who goes first, someone can always force a cat (tie game). I wonder, is it possible to always force a draw in chess or might it be that whoever goes first can always win? Sure the computing power to figure this out is beyond anything we have now, but with quantum computing and other advancements, I expect to see chess solved in my lifetime.

Re:How long till they solve chess?

Yeah, you have to rely on quantum computing to do that. Alternatively, you have to prove that lots of "possible" chess positions don't actually appear, no matter how the other player plays, on the way to the optimal win.

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

The mathematical rules

Note that a liberty is an empty spot on the board that is either next to your stone or can be reached by moving across your stones horizontally or vertically. This is great for computer scientists who don't know the game yet, http://brooklyngoclub.org/jc/rulesgo.html:

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.

GNU Go and future AI research

AFAIK, the current state of the art of Go on computers is Goemate [wulu.com] and Go4++ [infonomics.nl].

GNU Go [gnu.org] is actively developed, but it still does not match commercial Go software, ranking 1-2 stones weaker. It is rated from 8 to 9 kru, which is a weak amateur.

Computers have thus far not been too great at cracking go via the usual searching algorithms, as it has a high branching factor - starting at 361, much higher than chess! It is only recently that Go programs have even begun to achieve low levels of competence. Besides the limited searching and pattern recognition of current software, future programs may improve by decomposing Go into 'subgames', allowing it to be more readily attacked.

Ridiculous.

A 5x5 go board has only 847,288,609,443 possible game states, even including impossible boards. Assuming the relatively tame pace of scoring 100,000 boards per second towards completion, which on a board of that size is trivial, this solution takes a simple brute-force time of 98 days. That solution space can be cut down by almost two orders of magnitude with simple reflection and rotation tricks, implying a realtime tree search space of about a day and a half.

Given that my full board scorer moves faster than that, and given that the university probably has more than one PC to work with, I wonder how it is that anyone can justify this as something larger than a publicity stunt, especially given that none of go's emergent structures even fit onto a 5x5 board.

This is horseshit, in short. Mod story down.

Re:How is this surprising?

Because Go is incalcuably more complex to design a computer program for, there are only two pieces, but they can go anywhere at any time (Ok, not *anywhere at any time* but pretty much), and the number of combinations there are to a simple move is much more difficult than the moves are in chess.
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.

Re:How is this surprising?

If computers can beat chess grandmasters and similar feats, how is this anything special?

It's special for two reasons. For one thing, even though computer programs can beat most humans, chess itself has not been solved. That's a very different proposition.

For another thing, go is spectacularly more complex than chess. The very best go programs are competition only for weak amateurs. There's an archived NYT article [ishipress.com] that summarizes the problems reasonably well.

Although the standard go board is 19x19 intersections, the game scales, unlike chess. Things you learn on a small board are sometimes applicable to larger ones. A 5x5 is usually not interesting for human play; most consider 9x9 the minimum size for a worthwhile game. This means that a computer has been programmed to force a guaranteed win at a smaller size, and hopefully paves the way for further development and understanding.

Re:What the hell?

I heard rumours that there was a solution for "Tic-Tac-Toe" very close to being announced. The only hold up is finding a large enough
distributed network to explore all paths in real-time.

Re:2X2 Chess?

But what if it's 2x2 chess with all knights?

Re:2X2 Chess?

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.

Re:Chess vs Go

To have a program which has solved Go (unlike the best chess programs, which are merely at the strength of Grandmasters)

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

Actually, the fact that Go only has two pieces is why it's so much more complex. Chess pieces individual behavior is what usually limits the number of moves in Chess. Also, since Chess doesn't easily scale down, 2x2 chess doesn't work: QK QK Neither side can move, since any move they make still leaves their king in check. I guess that means that White looses by default, since White goes first and can't make a legal move. Unless you play by rules like with blitz and don't count check, only actually capturing the king, in which case White always wins (unless he's REALLY dumb).