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

October 2002

[fembots]

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 the day before 5X5 Go is solved.

Re:October 2002

[Xzzy]

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

[onash]

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.

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

[PetWolverine]

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

Re:Some slashdot lore.

[Deadstick]

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

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.

[msaulters]

"I fully expect someone to breathlessly explain the Great Goodness that is Chess."

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)

Size?

[Anonymous Coward]

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

Re:Size?

[Doctor Ian]

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

Go...

[BicycloHexane]

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.

Re:How is this surprising?

[Haydn Fenton]

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?

[legLess]

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 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:2X2 Chess?

[nacturation]

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

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.

The mathematical rules

[Eunuch]

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

[__aaijsn7246]

AFAIK, the current state of the art of Go on computers is Goemate and Go4++.

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

Re:How long till they solve chess?

[cnettel]

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

Ridiculous.

[stonecypher]

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

[stonecypher]

When you're dealing with a ply tree, it's relatively straightforward: the score is positive infinity if the board wins, negative infinity if the board loses, 0 if no path to a win is possible (tie boards or unknown boards,) and +-inf +-epsilon/ply for any board whose path towards a solution/solutions are known.

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:How is this surprising?

[greppling]

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

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.

A couple of errors

[Flyboy Connor]

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,

His name is Eric van der Werf.

a professor at the University of Maastricht

He is not a professor. He was a Ph.D. student. He received his Ph.D. title January 27 of this year.

in Holland.

That should be "The Netherlands". Holland is part of The Netherlands, but Maastricht is not located in Holland.

At about a quarter of the full-board version, 5x5 go

That's about 1/14th of a full board (25 points as opposed to 361 points).

is miniscule, similar in scale to "solving" 2X2 chess.

It is similar to solving 5x5 or 6x6 chess.

The fact that a programmer

Calling Van der Werf a "professor" is a bit too much, but calling him a "programmer" is not enough.

would even consider this a noteworthy challenge is itself a remarkable testament to the game's complexity.

Basically, it was not done before, and could be done with a couple of weeks computation time. That's not to belittle Eric's work; it is only a small part of his work. Read his thesis to see what he has done for the field of Go research.

Van Der Werk's

Again, it is "Van der Werf".

approach is described in detail in an article at the Netherlands Organization for Scientific Research (NOSR).

That should be NWO, not NOSR, and the approach is not described in detail in the article. For details, visit Eric's website.