The conversations backstage at computer Go tournaments

Date:July 2, 2007 / year-entry #238
Tags:other
Orig Link:https://blogs.msdn.microsoft.com/oldnewthing/20070702-01/?p=26183
Comments:    7
Summary:Steve Rowe linked to an essay on why computers can't play Go well even though they've mastered other "difficult" games like chess. I was reminded of a description I received of what happens backstage at computer Go tournaments (i.e., tournaments that pit Go-playing computers against each other). ("Backstage" is a bit of a misnomer, of...

Steve Rowe linked to an essay on why computers can't play Go well even though they've mastered other "difficult" games like chess. I was reminded of a description I received of what happens backstage at computer Go tournaments (i.e., tournaments that pit Go-playing computers against each other). ("Backstage" is a bit of a misnomer, of course; since the contestants are computers, you can talk all you want as loud as you want without worrying about distracting the players.)

At computer Go tournaments, the programmers are like parents watching their children compete in a hockey game where they've only just barely learned how to skate. It's not so much a matter of who plays better as it is a matter of who sucks less. One programmer will lean over to the other and say something like "I hope my program realizes its left-hand-side is vulnerable before your program takes advantage of it."


Comments (7)
  1. Amblis says:

    What Go needs is a team of programmers versed in multi-threaded programming techniques. Unleash them on the next-generation super-computers; http://www.vnunet.com/vnunet/news/2192893/ibm-sun-microsystems-show

    And maybe they can do something impressive using neural-networks and all of that storage space;

    http://blogs.guardian.co.uk/technology/archives/2007/06/26/supercomputer_wars_kick_off_again.html

  2. Alan De Smet says:

    Amblis: The problem isn’t lack of knowledge of multi-threaded programming, or lack of access to high end machines.  Deep Blue (the Chess computer that became the first machine to beat the world champion human player) did its work in a massively parallel way.  The problem is that most computer game AI tries to solve the problem through a brute force search of the game space (and indeed, Deep Blue did just that).  With Chess, the search space is approachable.

    Given the numbers in the article, we’ll assume that a Chess player has about 35 moves at any given moment.  A typical game will last 40 or fewer moves.  So a computer is looking at about 40^35 moves to consider.  That’s about 10^56 moves.  A Go player has, on average, about 250 possible moves to consider.  And a typical Go game can easily go 200 moves.  So now we’re fasting 200^250 moves to consider.  That’s about 10^575.  That’s insanely harder than Chess.  Even assuming computer power doubles yearly, we’re talking thousands of years before a computer can brute force Go in the same way they brute force Chess.

    As a result, Go playing programs have to be more clever.  That have to look for an identify patterns and also determine how the sub-board patterns will interact as they grow.  Generally speaking, this means that the program play in a much more "human" way.   But that’s really hard.  A true Go master is the sum of all of his knowledge, and getting that knowledge out of his head is difficult, if not impossible.

    As for neural-networks, maybe.  They’re not a magical ability to can toss in and everything works.  You need to train them.  For a game as complex as Go, we’re probably talking a training set of millions, if not billions of games.  And who is going to play those millions of games against the system as it trains?  You might have some luck online, but now you’re paying for a hugely powerful computer, hoping people will play it, despite the fact that it will play terrible, random, pointless games for a long, long time.

    We might eventually develop a computer that can play Go on the level of the masters, but if we do my money is on the basis being programmers teaching it one concept and pattern at a time.  It’s slow going, but progress is being made.  And the answer isn’t going to be "just throw more processor power at it."

  3. A Tykhyy says:

    Most people point out the difference in search space size between chess and Go, but few mention the difficulties in constructing a tolerably good evaluation function for Go. In chess, the evaluation function is quite simple, essentially weighted sum of pieces owned with some tactical considerations (like doubled pawns, isolated pawns, center control etc) thrown in, and very fast to calculate. In Go, evaluation is much more complex, and this is much harder on computer Go programmers than mere size of search space, because efficient minimax pruning algorithms on which Deep Blue relies become practically useless.

    The victory condition in chess (checkmate) is also simple to evaluate. Meanwhile, even writing a program which *scores* finished Go games accurately is quite a challenge, never mind determining whether a given game is actually finished.

    As concerns master-level (or even strong amateur-level) computer Go programs, being both a programmer and a 2 dan amateur, I’m not holding my breath. Anecdotal evidence suggests that there is a "curse" on this problem, i.e. those programmers whose programs begin to approach about 6-7 kyu level, abandon their projects. By the way, the ranks awarded to programs are a joke, commonly 4-5 ranks stronger than the program actually plays.

  4. Anonymous Coward says:

    Wow, now I know why Raymond considers giving up blogging.

    Amblis: seriously dude, did you read the article?  Alan has responded to your post, but everything he has said is pretty much directly from the article.  Your first comment shows that you know nothing about AI, game strategy, and simple mathematics (you really think multithreading is the solution to the brute force problem).

    Now I see exactly what a Win32 poser is like.  Raymond writes the article and Win32 poser doesn’t really bother to read it.  But, that won’t stop Win32 poser from writing the oh-so-simple solution for what needs to be done.

  5. Amblis says:

    My post above was made in jest. Thank you for pointing out the obvious.

    You two should be ashamed for even having replied to me (and not the original post).

    To Raymond I apologize for having been lead into doing the same (and having turned this once depressingly empty space into a toxic bath because of my failed attempt to lighten the mood).

  6. alex.r. says:

    From the first article Amblis linked :

    "Supercomputers target scientific and modelling applications such as weather forecasting, drug testing and gnome mapping."

    Surely, a computer that can accomplish the incredibly complex task of "gnome mapping" ought to be able to play a decent game of Go?

  7. A_me! says:

    @alex.r

    Sorry for the facetiousness, but I think computers with those skills would be more apt to become great masters of the game of Gno.

Comments are closed.


*DISCLAIMER: I DO NOT OWN THIS CONTENT. If you are the owner and would like it removed, please contact me. The content herein is an archived reproduction of entries from Raymond Chen's "Old New Thing" Blog (most recent link is here). It may have slight formatting modifications for consistency and to improve readability.

WHY DID I DUPLICATE THIS CONTENT HERE? Let me first say this site has never had anything to sell and has never shown ads of any kind. I have nothing monetarily to gain by duplicating content here. Because I had made my own local copy of this content throughout the years, for ease of using tools like grep, I decided to put it online after I discovered some of the original content previously and publicly available, had disappeared approximately early to mid 2019. At the same time, I present the content in an easily accessible theme-agnostic way.

The information provided by Raymond's blog is, for all practical purposes, more authoritative on Windows Development than Microsoft's own MSDN documentation and should be considered supplemental reading to that documentation. The wealth of missing details provided by this blog that Microsoft could not or did not document about Windows over the years is vital enough, many would agree an online "backup" of these details is a necessary endeavor. Specifics include:

<-- Back to Old New Thing Archive Index