Slashdot Log In
Computer Cracks 5x5 Go
Posted by
timothy
on Mon Feb 21, 2005 07:24 PM
from the figure-go dept.
from the figure-go dept.
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)."
This discussion has been archived.
No new comments can be posted.
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
October 2002 (Score:5, Funny)
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 (Score:4, Informative)
Maybe the results came out just now.
Parent
Re:October 2002 (Score:5, Interesting)
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!
Parent
Re:October 2002 (Score:5, Funny)
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.
Parent
Re:October 2002 (Score:5, Insightful)
Parent
Some slashdot lore. (Score:5, Insightful)
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. (Score:5, Interesting)
Parent
Re:Some slashdot lore. (Score:4, Informative)
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.
Parent
Re:Some slashdot lore. (Score:4, Insightful)
Parent
Re:Some slashdot lore. (Score:5, Insightful)
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.
Parent
Re:Some slashdot lore. (Score:5, Insightful)
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.
Parent
Re:Some slashdot lore. (Score:3, Insightful)
Re:Some slashdot lore. (Score:5, Informative)
Parent
Re:Some slashdot lore. (Score:5, Funny)
Arm yourself against spelling flames first, Grasshopper. Only then will your math flames stand up to the foe.
rj
Parent
Re:Some slashdot lore. (Score:5, Interesting)
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)
Parent
GREAT SCOTT! (Score:3, Funny)
2002? (Score:5, Funny)
2X2 Chess? (Score:4, Insightful)
Re:2X2 Chess? (Score:5, Funny)
Parent
Re:2X2 Chess? (Score:5, Insightful)
Parent
In Other News (Score:4, Funny)
Size? (Score:5, Informative)
Re:Size? (Score:5, Informative)
Parent
Re:Size? (Score:3, Informative)
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.
Go... (Score:5, Informative)
yep (Score:5, Informative)
Also, dig my sig biotches.
"a quarter of a full scale board"? (Score:5, Insightful)
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? (Score:5, Interesting)
Re:How long till they solve chess? (Score:5, Interesting)
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...
Parent
The mathematical rules (Score:5, Interesting)
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.
arthur c clarke story (Score:3, Interesting)
If we solve Go, will it still be fun? (Score:4, Insightful)
GNU Go and future AI research (Score:5, Informative)
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? (Score:4, Informative)
http://swag.uwaterloo.ca/~jchampaign/goapplet.html [uwaterloo.ca]
Re:Want to play? (Score:5, Informative)
Parent
Ridiculous. (Score:5, Informative)
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. (Score:5, Interesting)
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
Parent
To put this in perspective for non-go players... (Score:5, Interesting)
Presently, if a typical geek started playing Go, they would get their ass kicked by the weakest computer for a week or two.
After a month, they would be winning the odd game, if the computer gave them a 3-stone headstart. (Like 3 free moves to start in chess).
After three months, they would win some games in an even match against the weaker programs (Turbo-go)
After six months, they would be winning against a 3-stone or higher handicap for the computer.
Then they find a stronger Go program.
They start to lose every match again.
After another month or so, they start to win on the weaker levels.
Take it six months ahead, and they are smashing the computer in an even match with no handicap, playing white (white moves second) or at lower levels against a 3 or 4 stone handicap.
The only thing that makes the game playable against a computer is that Go has an incredible handicapping system that lets uneven players play against each other.
So what makes this story interesting? Aside from the brute strength issue?
The first moves of the game, often in the corners in roughly a five-by-five area (Joseki) are only recently being evaluated for best move potential...
That can affect the outcome of professional matches played for big $$$$.
But more importantly for people like me, I can't play humans much... Kids, wife and home environment mean I can't spend 30 minutes undisturbed, so playing against human opponents is out for me.
Any technology that makes computer programs stronger, improves algorythms or makes me play harder will keep my morning bus trips interesting.
Because Go programs have got a long way to go if they are easily defeated against a human opponent with just 1 year experience.... Who would be easily classed as a novice let alone just a weak player.
GrpA
Even more perspective. (Score:4, Informative)
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,
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.
Parent
I wrote the first commercial Go playing program (Score:5, Interesting)
Go is such a great game. In the 1970s, I got to play exhibition games with Miss Kobyoshi (women's world champion) and Mr. Lee (national champion of South Korea). The high level of their play really blew me away - getting slaughtered was a surprisingly great experience.
The Gnu Go program plays a good game, BTW. It is best to play against human opponents, but give Gnu Go a try also. Just like studying chess, if you get into playing Go, make sure you study complete master games: studying opening, middle game, and end games in isolation just does not cut it.
A couple of errors (Score:5, Informative)
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:How is this surprising? (Score:5, Interesting)
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.
Parent
Re:How is this surprising? (Score:5, Informative)
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.
Parent
Re:How is this surprising? (Score:4, Informative)
Parent
Re:How is this surprising? (Score:5, Interesting)
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.
Parent
Re:What the hell? (Score:5, Funny)
distributed network to explore all paths in real-time.
Parent
Re:Chess vs Go (Score:5, Interesting)
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.
Parent
Re:Uh... (Score:5, Funny)
Parent
Re:Connect 4 Solvable As Well (Score:4, Informative)
Parent
Re:Posted AC to avoid karma whoring (Score:4, Informative)
Parent