Forgot your password?
typodupeerror
Puzzle Games (Games) Science

Computer Cracks 5x5 Go 442

Posted by timothy
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.

Computer Cracks 5x5 Go

Comments Filter:
  • by fembots (753724) on Monday February 21, 2005 @08:25PM (#11740416) Homepage
    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 (Score:4, Informative)

      by Anonymous Coward on Monday February 21, 2005 @08:28PM (#11740434)
      The doctoral thesis was defended on 27 January 2005

      Maybe the results came out just now.
      • Re:October 2002 (Score:5, Interesting)

        by onash (599976) on Monday February 21, 2005 @09:28PM (#11740870)
        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!
        • Re:October 2002 (Score:3, Informative)

          by zero_offset (200586)
          (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.
    • by Xzzy (111297) <sether@t[ ]h.org ['ru7' in gap]> on Monday February 21, 2005 @08:36PM (#11740503) Homepage
      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.
    • by hdparm (575302)
      Can you imagine the level of hilarity (this is the correct word?) produced tomorrow after dupe of this story appears on Slashdot front page?
    • Re:October 2002 (Score:3, Interesting)

      by Domini (103836)
      He-he...

      Funny how it was the American Go Association [usgo.org] who reported this...

      They were always a bit slow compared to the Dutch in mathematics. ;)

      I've read about this and 6x6 being solved a *long* time ago already here:

      http://senseis.xmp.net/?SmallBoardGo
  • by Eunuch (844280) * on Monday February 21, 2005 @08:25PM (#11740418)
    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.
    • by Ayaress (662020) on Monday February 21, 2005 @08:29PM (#11740447) Journal
      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."
      • by usefool (798755)
        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."
    • by 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.
    • Chess is fun

      Bah, chess [uchicago.edu]...
    • by msaulters (130992) on Tuesday February 22, 2005 @01:18AM (#11742040) Homepage
      "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)
  • by agildehaus (112245) on Monday February 21, 2005 @08:28PM (#11740432)
    Marty, this story once mattered, back in 2002, when it happened.
  • by idono (858850)
    If computers can beat chess grandmasters and similar feats, how is this anything special?
    • Because computers can't beat 10 year olds in Go. It's kinda amusing really.
    • by Haydn Fenton (752330) <no.spam.for.haydn@gmail.com> on Monday February 21, 2005 @08:40PM (#11740524)
      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.
    • by legLess (127550) on Monday February 21, 2005 @08:43PM (#11740549) Journal
      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.
    • by STrinity (723872) on Monday February 21, 2005 @08:48PM (#11740586) Homepage
      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.
    • by greppling (601175) on Monday February 21, 2005 @09:38PM (#11740938)
      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.

    • 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. Unli
  • 2002? (Score:5, Funny)

    by porcupine8 (816071) on Monday February 21, 2005 @08:29PM (#11740448) Journal
    What is this, Classic Slashdot? Next do we get a story on the impending end of the dot-com bubble?
  • by Anonymous Coward
    It said 6x6 go is solved.
  • 2X2 Chess? (Score:4, Insightful)

    by tritone (189506) on Monday February 21, 2005 @08:30PM (#11740456) Homepage
    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.
  • by froodiantherapy (858964) on Monday February 21, 2005 @08:31PM (#11740458)
    Sony has released a new devixe, tentatively dubbed the "CD Burner," capable of burning the first second of any of your music CDs! Programmers hope some day to move to the entire first track.
  • Size? (Score:5, Informative)

    by Anonymous Coward on Monday February 21, 2005 @08:32PM (#11740463)
    5x5 is 1/4 the size of 19x19??? More like 1/14th.
    • IIRC, traditionally computer approaches to solving Go have used a 10x10 board. Maybe that is what the poster was thinking about.
  • Go... (Score:5, Informative)

    by BicycloHexane (819192) on Monday February 21, 2005 @08:32PM (#11740470)
    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:Go... (Score:2, Interesting)

      by Sir_Real (179104)
      An initial dig [uci.edu] brings up terms like "EXPTIME-complete" which doesn't match anything I remember from my undergrad algo class. Apparently, there is a rule modification that makes EXPTIME-complete games EXPSPACE-complete. This makes even less sense to me. Explanations in lay speak are appreciated.
      • 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... (Score:3, Informative)

      by Dogun (7502)
      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 defeat
    • Re:Go... (Score:3, Interesting)

      by Cryogenes (324121)
      The number of potential moves grows way faster then in chess

      Which is a problem, but not the main one. The real advantage of computer chess over computer go is the relative ease with which the leaves of the search tree (e.g. all positions after n moves) can be evaluated statically. In chess you can perform excellent static evaluation by counting material, mobility, king safety and maybe a few other features. In Go, static evaluation is considered difficult for an expert, let alone a computer.
  • yep (Score:5, Informative)

    by St. Arbirix (218306) <matthew...townsend@@@gmail...com> on Monday February 21, 2005 @08:34PM (#11740482) Homepage Journal
    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.
    • Oh a fanatic (Score:2, Insightful)

      by Eunuch (844280) *
      You notice there's no chess players proclaiming its superiority to Go. What is this, frustration from the fact that Go doesn't help with getting an Asian girlfriend?
  • by Speare (84249) on Monday February 21, 2005 @08:38PM (#11740514) Homepage Journal
    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.

  • by jaylee7877 (665673) on Monday February 21, 2005 @08:40PM (#11740527) Homepage
    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.
    • by cnettel (836611) on Monday February 21, 2005 @09:05PM (#11740695)
      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...

    • Congratulations on a quality troll. Too bad you didn't get any bites. Has the makings of a classic slashdot flamefest.
    • I've always believed within my lifetime, chess would be solved.

      For all practical purposes, it already has. Opening books are dozens of moves deep and many endgames have been completely solved and loaded into databases. I doubt that more than a couple dozen of the best Grandmasters could beat the best computer program out there - Kasparov had a heck of a time with Deep Blue.

      The days when an average person could walk up to a chess program and beat it are long in the past. For me, that's close enough to ca

  • It's nice that AI and computer science research is going into popular and well-known games like go, but a lot more complexity and interesting research can be found in a less-known game called chess [chess.net]

    • Go may have simpler rules than chess, but it by no means a simple game. When I tell my friends about Go they laugh at me, but after explaining the game to them and giving them a 9 stone handicap and thoroughly trouncing them (I'm only around 12kyu... practically a beginner) they begin to see the game is much more complex and subtle than they anticipated. A computer program playing Go would have to be much more adaptive than a program playing chess, or have a much quicker algorithm to process the insane numb
  • by 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]
  • by Eunuch (844280) * on Monday February 21, 2005 @08:47PM (#11740583)
    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.

  • by Sark666 (756464) on Monday February 21, 2005 @08:54PM (#11740622)
    Everytime chess gets mentioned on /. (ok I know it's a go story but you know the comparisons will start) I like to post a link to this short story written by Arthur C. Clarke. I originally found the story through someone else's /. post http://www.research.ibm.com/deepblue/learn/html/e. 8.2.shtml [ibm.com]
  • Isn't this in the realm of possibility for Checkers now. I know checkers has been solved with up to like 9 pieces a side. But with the limited moves, it should be able to create a database of all moves in only a couple terrabytes or so. Yeah I know "only" is relative, but it should be in the realm of possibilities.
  • by Eunuch (844280) * on Monday February 21, 2005 @09:02PM (#11740677)
    I think it will. We still have weightlifting competitions even though we have forklifts at our disposal.
  • by keen (86192) on Monday February 21, 2005 @09:04PM (#11740684)
    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.
    • It would seem that it could be very different. There are a lot of these computer-only competitions and tuning for that will be very different from tuning for humans online.
  • What?? (Score:3, Interesting)

    by Transcendent (204992) on Monday February 21, 2005 @09:04PM (#11740686)
    5x5 go is miniscule, similar in scale to "solving" 2X2 chess

    Sorry, but that's like a full chess board with the pawns removed (if even that much).

    5x5 Go is still fairly complex. Although the article is old (2002), I'd still like to see a caltulation time comparison.

    2x2 chess can be solved in a manner of seconds/microseconds. 5x5 Go might take a few days to brute force it.
  • Want to play? (Score:4, Informative)

    by Champaign (307086) on Monday February 21, 2005 @09:12PM (#11740740) Homepage Journal
    A variant of Go (Atari or first capture Go) can be played at:

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

  • by Comatose51 (687974) on Monday February 21, 2005 @09:15PM (#11740770) Homepage
    My friends and I once made a connect 4 game but the AI wasn't very good against other AIs. It occured to me that perhaps Connect 4 is solvable. Each hole has 3 possible states and there are 42 holes. So it's 3^42 possible board states. However, there is a very large number of board states that cannot happen, such as having a piece in row 2 but not row 1, etc. Someone with better math skills can calculate what the actual number of possible board states. My intuition is that it should greatly reduces the number of states enough that we can solve the entire game. The rules are simple and the AI for it is simple as well. We used a tree to represent moves and applied alpha-beta pruning to it.
  • Ridiculous. (Score:5, Informative)

    by stonecypher (118140) * <stonecypherNO@SPAMgmail.com> on Monday February 21, 2005 @09:17PM (#11740778) Homepage Journal
    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.
  • by GrpA (691294) on Monday February 21, 2005 @09:29PM (#11740871)
    Since computers have started to beat strong chess players, it *is* taken for granted by many that computers can beat reasonably strong people with today's processing power.

    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

    • by cwills (200262) on Tuesday February 22, 2005 @01:24AM (#11742065)
      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.
  • I don't mean in terms of computation power, I mean in a theoretical way. As in, it can be shown that Go can be solved, even if we cant='t solve it.

    I don't know much about these sorts of things... practically nothing in fact. Now, we all learned as kids that tic-tac-toe (or Naughts and Crosses if you prefer) is closed or solved or whatever the right term is... whoever goes first always wins, so long as they go right in the middle.

    It seems pretty clear to me that if the solution in the 5x5 case is to put
  • by MarkWatson (189759) on Tuesday February 22, 2005 @01:20AM (#11742049) Homepage
    Honinbo Warrior was coded in UCSD Pascal and really did not play that well, but my boss and a few friends talked me into running ads in some Apple II magazines and marketing it. Working on that program was a fun obsession that lasted about 1 1/2 years.

    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.
  • 2x2 Chess (Score:3, Funny)

    by gnovos (447128) <`ten.deppihc' `ta' `sovong'> on Tuesday February 22, 2005 @03:19AM (#11742455) Homepage Journal
    Not QUITE that scale...

    Two by two chess:

    White: Checkmate in 0, would you like to play agin?
    White: Checkmate in 0, would you like to play agin?
    White: Checkmate in 0, would you like to play agin?
    White: Checkmate in 0, would you like to play agin?
  • A couple of errors (Score:5, Informative)

    by Flyboy Connor (741764) on Tuesday February 22, 2005 @05:02AM (#11742743)
    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]

  • by 10am-bedtime (11106) on Tuesday February 22, 2005 @07:09AM (#11743081)

    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])

Neckties strangle clear thinking. -- Lin Yutang

Working...