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

Re:October 2002

[Anonymous Coward]

The doctoral thesis was defended on 27 January 2005

Maybe the results came out just now.

Size?

[Anonymous Coward]

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

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.

yep

[St. Arbirix]

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.

Re:Some slashdot lore.

[usefool]

When we told him, his reply was, "Go? I thought that was a card game."

I had a similar experience except that guy said "Go? I thought that was the monkey from outerspace."

Posted AC to avoid karma whoring

[Anonymous Coward]

Seeing as so many karma whores are saying that this was solved 3 years ago, here's a hint: RTFFA (Read The Full Fucking Article). If you do you'll realise that it was just solved recently. [www.nwo.nl]

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 [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:Some slashdot lore.

[PetWolverine]

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

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?

Re:Size?

[wmshub]

Uh, no.

It's 19x19. There are 18 squares on a side when you look at the board, but as you point out, the stones are placed on the vertices, so the playable positions form a 19x19 grid.

Re:How is this surprising?

[STrinity]

In chess, there are approximately 71,000 possible board possitions after four moves, compared to over 16.7 billion in full board Go. Even on a simplified 5x5 board, there are more than 300,000 combos after four moves.

Re:October 2002

[Anonymous Coward]

Before trolling read the full fucking article [www.nwo.nl]

And as one had already stated, the thesis was defended just a few days ago...

The actual details

[Anonymous Coward]

The actual details are available at Erik van der Werf's homepage [unimaas.nl] at the Universiteit Maastricht, and in particular on his publication list. [unimaas.nl]

Re:Oh a fanatic

[Anonymous Coward]

What is this, frustration from the fact that Go doesn't help with getting an Asian girlfriend?

Hey, that's every Geek's concern---except you, obviously, since you are Eunuch [slashdot.org].

GNU Go and future AI research

[__aaijsn7246]

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.

Want to play?

[Champaign]

A variant of Go (Atari or first capture Go) can be played at:

http://swag.uwaterloo.ca/~jchampaign/goapplet.html [uwaterloo.ca]

Re:Um, who wins?

[Anonymous Coward]

Sorry, it is not what you think. Black is *not* allowed to pass the first move.

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.

I'll try to enlighten you...

[hummassa]

exp-time-complete: the time to solve one particular problem for an input of size N is no less than O(2^N) time units.
exp-space-complete: you can solve one particular problem in less then O(2^N) if you calculate all the solutions and try to keep all the O(2^N) results around, wasting an enormous amount of storage.

Re:Go...

[Dogun]

I would also like to point out the increased computational challenge for RANKING a move.

A Go player has a significantly harder time judging whether groups of pieces are alive or dead than a chess player has deciding if he has killed a queen or not.

Similarly, Go is very much about more abstract qualities like territory and influence, thickness and lightness of play, good shape and bad. Although similarly abstract concepts exist in chess, my understanding is that at least in chess ai's aimed more at defeating the average player, these concepts don't even need to be explored. Those crazy machines they use to play against grandmasters are another story, I imagine.

I ramble. But suffice it to say the problem isn't entirely the exponentiality. There are significant challenges unrelated to alpha-beta pruning the search space before picking a decent move.

Re:Connect 4 Solvable As Well

[emurphy42]

The canonical game (7 columns, 6 rows) has been solved. [rec-puzzles.org]

Re:Want to play?

[UserGoogol]

And real Go can be played at KGS [kiseido.com].

Re:In the interest of fairness...

[Council]

He was joking; it's a slashdot cliche to say what you just said about Go when someone posts about chess.

Re:Isn't Go solveable?

[Anonymous Coward]

[...] tic-tac-toe [...] whoever goes first always wins, so long as they go right in the middle.

Alright, you played "O" in the middle. Here's my move:

X . .
. O .
. . .

Go ahead and beat me in a tic-tac-toe correspondence game through slashdot.

Re:Posted AC to avoid karma whoring

[Kippesoep]

The other posters are correct. If you really RTFFA, you'll find that it was solved October 20th 2002, well over two years ago. Even the link you provide only mentions the corresponding doctoral thesis beind defended recently (January 27th 2005). Perhaps you should RYOFL (Read Your Own Frelling Links).

Re:To put this in perspective for non-go players..

[Anonymous Coward]

Hi

Sorry to hear you can't really play undisturbed as much as you like. I'm in a similar position at times and hence I've started playing go at http://www.dragongoserver.net wich is a sort of korespondance go. You play long lasting games at perhpas as little as one move per day or less (logging on and off in between).

I tend to play a few moves at breaks or inbetween idleing on the net.

Hope to see you there... :)

Re:Size?

[PetWolverine]

90, I think...

Each one has to be 8x9, if the specs you give are right. So along one side there are 18-8=10 squares, along the other side 18-9=9.

Re:Some slashdot lore.

[OldAndSlow]

Go is needlessly complex to start up playing on reasonable level and as consequence you're going to be having a lot of uneven matches between random players

It seems you know next to nothing about go. Stronger players give weaker players a handicap. The handicap is a number of stones placed on the board before as the game begins. The number of stones is simply the difference is ranking. Beginners start at around 13 Kyu, progressing to 1 Kyu. From 1 Kyu, progress is to 1 Dan up to 9 Dan. When a 4 Dan plays a 1 Kyu, the 1 Kyu should get a 4 stone handicap. (I know about the professional Dan scale, and I'm ignoring it).

If two folks who do not know their ratings play, the handicap can be determined after the first game by dividing the winning margin by 10. Now was that hard?

A handicap game of go is a lot more interesting than a game of chess between a master and a class A player.

All this assumes that you are serious about your games and are willing to work on getting good. If all you want to do is kill time, go still has simpler rules, and you can use the set to play gomoku.

Even more perspective.

[cwills]

To put this into even more perspective

In go, players can be given a rank on how strong they are compared to others. It's a fairly simple method.

Everyone starts out at about 30 kyu. As they get stronger, their kyu number decreases till it gets to 1 kyu. At which point starts a new number system that goes upward, starting at 1 dan and goes to 9 dan.

So..

30 Kyu, is weaker then a 29 kyu,... 2 kyu, 1 kyu, 1 dan, 2 dan, ..., 9 dan.

Now that is for amateur rankings. There is a professional ranking system that starts at 1 dan pro and goes to 9 dan pro. I have heard that a 1 dan pro is roughly the same strength as a 7 dan amateur.

There is a handicap system where if you take the rankings of two players and subtract them, it determines the number of handicap stones given to the weaker player. Thus a 10 kyu playing against an 8 kyu, the 10 kyu player gets to play first by placing 2 stones on the board (one set of rules allows black to place the stones anywhere on the board, another set of rules, the stones must be played at specific spots). The rule of thumb is that each handicap stone is worth about 10 points. Another rule of thumb is that each handicap stone "erases" one mistake by the weaker player.

Normally one doesn't play with more then a 9 stone handicap. Mainly because beyond 9 stones, black really isn't "learning" much

To prevent ties, a half point is awarded to white in handicap games, in an even game (where both players are of equal strength), white is given 6.5 points (this has been changing around some -- depending on the rules you are playing with).

Usually after the 1st game or so a 30 kyu player learns enough to drop to around 28 kyu or there abouts.

I have heard that the amount of time and study to go from a 10 kyu to a 1 kyu rank is about the same as going from a 1 dan to a 2 dan.

A game between two weaker players can result in scores of anywhere from just a few points to 100's of points going to the winner. As one gets stronger, the wins are usually only a few points, or someone resigns.

I have seen strong dan and pro players when playing weaker players their goal is to try to get the score within a half point (always in their favor).

In Go, the game really doesn't start to get interesting till about 30 to 50 moves into the game (in chess, the game is usually over at that point).

Currently on one of the online go playing servers, GNU Go (among the top go playing programs -- though not the strongest) is roughly around 11 kyu in strength, A weak dan player can give gnugo a 9 stone handicap and the dan player will still win.

Several years ago, Janice Kim gave the top go playing program a 28 stone handicap and she still won the game (I believe it was a 28 stone game).

To get to a professional level player, it is best to start playing when you are very young. Expect to dedicate your life to the game. To get to a strong amateur dan level, also expect to dedicate a good chunk of your life to the game.

Re:How is this surprising?

[eidechse]

The main issue is distiguishing between shapes that are "alive" and shapes that are "dead" (a shape that is alive can't be captured). This is difficult for humans to do, sometimes even for skilled players.

Due to this, it can be much more difficult to tell when a game is over in Go. All this makes for a set of problems that don't submit well to brute force analysis and are very difficult to develop other types of algorithms for.

Lastly, the above problems can/do occur in multiple areas of the board. Unlike chess where a single material or structural advantage typically ends up deciding the game, a single Go game can produce multiple smaller "battles" that in themselves won't be enough to decide the overall game.

Strength ref : Gnugo is within a 6 month reach

[tototitui]

I started to play from scratch 5 months ago dedicating around 1 hour per day for go.

Now I beat gnugo with no handicap more then 50% of the time.

On KGS (http://kgs.kiseido.com/) I'm 14 kyus only.
Gnogo is around 12-11kyus on the same scale but I think the last stones are compensated by the fact I subconsciouly know which patterns gnugo are unable to handle.

Re:An Idea

[Flyboy Connor]

Markus Enzenberger's NeuroGo [markus-enzenberger.de] implements a neural network to play 9x9 Go. The program is reasonably strong, but no match for the more traditionally designed programs.

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. [unimaas.nl]

Re:A couple of errors

[ControlFreal]

His name is Eric van der Werf

That would be Erik van der Werf, but ok ;) It's amazing how our puny Windows department webserver stood up to the slashdotting...

So, how to begin playing go?

[GozzoMan]

Some time ago I tried to pick up go, basing on the faq of a dedicated usenet group (sorry, I don't remember which one right now).

I found it all rather confusing, since it went immediately through the different sets of rules (some rather complex), while I had made the opinion that the power of Go is that it can be played with a very small rule set but still offering a lot of possibilities during play (which imho is what make great games, well, great). Am I wrong?

So, how (I mean basing on which document, tool or else), oh sage ./ers-goers, do you suggest I begin again?

Thank you.

obligatory emacs link

[10am-bedtime]

i wrote some elisp [glug.org] to play GNU Go [gnu.org] in an Emacs [gnu.org] buffer. check it out! (fishing for bug reports; patches welcome.)

see also: GoMode [emacswiki.org] (emacswiki [emacswiki.org])

"Go Blip"

[Anonymous Coward]

A variation on Go for players with vastly different skills is to play Go by all the regular rules except the following: The weaker player instead of placing enough stones on the board to make it an even game places enough stones on the board to prevent the better player from creating any viable territory whatsoever. So the strong player's first 20 moves or so are all around the board using his better sense of strategy, while the weaker player responds tacticly to each move and doesn't have a feeling of being overwhelmed. I played this "Go Blip" thousands of times, and it's unsymmetrical play helps the weaker player from being embarrassed at losing since he's trying to beat his own best score of how few initial handicap stones are needed to stop the other from ending up with any viable territory.

Re:October 2002

[zero_offset]

(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

More than 310000 nodes per second is quite a lot of work.

Go and Chess compared

[^DA]

http://users.eniinternet.com/bradleym/Compare.html

Scroll down to see a point by point comparation.

Re:Some slashdot lore.

[hyphz]

I think more the problem is that playing Go actually requires you to look ahead.

What's the aim of the game? To take more territory than the opponent. So, what makes an area "territory"? Basically, if an opponent's stone would inevitably be captured eventually if played there, that area is your territory.

So as a beginner it's terribly frustrating. You don't know which areas are your enemy's territory, so you waste moves playing into them. Even if the other player warns you, which most good players will do, to be really good you need to know when a given area is NOT the enemy's territory now, but will become it if they place one more stone there - and THAT'S damn hard to spot and I've yet to met a teacher who could point it out.

Worse yet, you can't count your own territory, because even if you learn the standard territory counting rules, they don't apply to you because as a novice you might screw up and fail to capture the enemy's stones before they trash your territory even though, by all rights, you should have been able to. Aaaarrgh!

Although I don't think that the "Chess vs. Go" argument is useful, I do agree with the first poster on the basic point - Go is a very steep uphill struggle when you're starting, and doesn't obviously offer any extra entertainment over any other board game, so unless you want to play competitively you're liable to drop out.

Funny sort of quarter

[Anonymous Coward]

Right so they've solved go for a 5x5 board wonderful, nice to know it has a solution.

However it does make me wonder how good your maths is as if a 'standard' board is 19x19 then this small board is approximately 1/15 of the size (a 5x5 has 25 possible places where as a 19x19 has 361 possibilities which is clearly about 15 times bigger.

so if you are going to say its 4 times bigger be more specific as the area is not just 4 times...

enjoy

Re:So, how to begin playing go?

[dh5fbr]

Hi,

try to be able to count liberties (remember you are sitting on the stone with your bicycle and only can leave it along the lines). Then finding out what a group is and when it has 0 liberties should be doable. After that you are basically set and can play.

There is, however, one "confusing" additional rule, the ko-rule, which basically states that I can not do a move so that the whole board (meaning every spot of it!) looks the same like two moves ahead. If there would be no ko-rule a (ko-)fight over one important spot would go on forever. (One would take out a stone, the other back, etc.).

People will want to explain you about Josekis, Empty triangle (DO NOT PLAY THEM!), Influence, Aggressive, Defensive play, Ladders etc. Listen (to be polite) but don't worry about not understanding.

Keep on playing your game by counting liberties and trying to figure out your personal strategy. It is proven, that all the other "rule-sets" can be discovered naturally. (Better start playing on a 9x9 board!)

Well, the previous said, I have to speak about he rule set as how to decide, who won the game. On a 19x19 board the one moving first (black) has an advantage, with makes a komi (points added to whites score at the end,6.5 is a good value). The amount of komi differs in the different countries rules, so does if only the empty spaces or also the stones itself are counted. BTW in 99% the cases neither difference matters for your (beginner) games - the same person would win. By the time it matters you will understand it easily ;)

The opligatory link: http://gobase.org/ [gobase.org]

Re:Some slashdot lore.

[atlacatl]

You are wrong! Everyone knows it It originated in China. [samsloan.com]