landman%hanami@Sun.COM (Howard A. Landman) (04/21/89)
In article <3724@sdsu.UUCP> wintermute@tr.wrld (Wintermute) writes: >Now that Taiwan's Acer Group and the Ing Chang-Ki Wei-Ch'i Educational >Foundation have offered a prize of 40 million Taiwanese dollars >(about $1.3 million US) to anyone who can by the year 2000 program a >version of the game that can beat a professional Go player, are there >any takers out there? Where have you been? Why do you think Bruce Wilcox, David Fotland, Lynn Beus, and I were in Taipei last November? (Not to mention a host of Europeans and Japanese and others). >Looks like it's time to start using some AI techniques.) :-D No, that's been tried already (Wilcox, Nemesis). It seems to be being left in the dust by other approaches. My territory estimator (Poka) is nearly as strong as Wilcox's entire program, for example, and neither of them have a prayer against the better programs like Codan. These were around 12 kyu last November, and the general expectation is that November 1989 will see programs around 9 to 10 kyu battling it out for the top prize. Current programs are running on <2 MIP machines and take about an hour per game. In 2000 they'll be running on 100 MIP machines, and have 7 hours or more per game. So we should be aiming at about 4 MIP-hours per move, that is, an algorithm that can productively use 2 hours of Mac II time (or 20 minutes of SparcStation 1 time) average per move. Expanding the depth and width of tactical search is one way to use more time, but I don't think it will give the maximal improvement. Pro class programs will have to do EVERYTHING well; openings, tactics, life & death, positional judgement, and endgame. On the other hand, some studies of my pro game database indicate that pros routinely make hundreds of points of errors per game; so the possibility that a program might someday beat them is quite real. And the exploding development of a solid mathematical theory of the endgame, based on Conway and Berlekamp's work, promises programs that play rapid and accurate yose. It's a very exciting time in computer Go this year. Howard A. Landman landman@hanami.sun.com
vu0112@bingvaxu.cc.binghamton.edu (Cliff Joslyn) (04/21/89)
In article <100234@sun.Eng.Sun.COM> landman@sun.UUCP (Howard A. Landman) writes: >On the other hand, some studies of my pro game database indicate that pros >routinely make hundreds of points of errors per game; so the possibility >that a program might someday beat them is quite real. And the exploding >development of a solid mathematical theory of the endgame, based on Conway >and Berlekamp's work, promises programs that play rapid and accurate yose. Fascinating, I thought as much! Could you explicate on the above reference, and any theory you have about how to measure sente, point value vs. threat value, ko involvement, etc. In my games I try to be sensitive to these issues, but usually end up just confusing myself. -- O----------------------------------------------------------------------> | Cliff Joslyn, Cybernetician at Large | Systems Science, SUNY Binghamton, vu0112@bingvaxu.cc.binghamton.edu V All the world is biscuit shaped. . .
jf@cci632.UUCP (Jens Fiederer) (04/22/89)
In article <100234@sun.Eng.Sun.COM> landman@sun.UUCP (Howard A. Landman) writes: >On the other hand, some studies of my pro game database indicate that pros >routinely make hundreds of points of errors per game; so the possibility >that a program might someday beat them is quite real. And the exploding >development of a solid mathematical theory of the endgame, based on Conway >and Berlekamp's work, promises programs that play rapid and accurate yose. >It's a very exciting time in computer Go this year. > > Howard A. Landman > landman@hanami.sun.com Apparently, at least one pro disagrees: Kato Masao has stated (boasted?) that God (to avoid religious disagreements here, assume that hypothetical entity/process that makes no mistakes at Go could give him ONE handicap stone That would put the figure for Kato at about 10 points of errors per game. Is Kato lying, or are the other pros really that much worse? Jens
landman%hanami@Sun.COM (Howard A. Landman) (04/22/89)
>In article <100234@sun.Eng.Sun.COM> landman@sun.UUCP (Howard A. Landman) writes: >>On the other hand, some studies of my pro game database indicate that pros >>routinely make hundreds of points of errors per game; so the possibility >>that a program might someday beat them is quite real. And the exploding >>development of a solid mathematical theory of the endgame, based on Conway >>and Berlekamp's work, promises programs that play rapid and accurate yose. In article <2089@bingvaxu.cc.binghamton.edu> vu0112@bingvaxu.cc.binghamton.edu.cc.binghamton.edu (Cliff Joslyn) writes: >Fascinating, I thought as much! Could you explicate on the above >reference, and any theory you have about how to measure sente, point >value vs. threat value, ko involvement, etc. None of the above work is published. I've been in email correspondence with Berlekamp and a couple of other people, and I spent 6 hours at Berlekamp's house one evening. He's making progress at a tremendous rate - most of the results are less than 3 months old. Before talking to him, I was able to apply Conway's theory to find the temperature of a move. This is useful because the simple greedy algorithm of playing the move with the highest temperature can be proved to be asymptotically correct; that is, if you have multiple copies of the game, and either player is allowed to play in any copy, then the highest temperature move is best in the limit of a large number of copies of the game. However, on a single board, there can be situations where there is a large gap in temperatures where the correct strategy is to play so as to get the last large move. For example, suppose there are three large moves left: 100 points in gote (A, temperature 50), 49 points in reverse sente (B, temperature 49), and 96 points in gote (C, temperature 48), plus a bunch of small moves (all temp <= 10). Then the correct strategy is not to grab the highest temperature move, because that leads to you getting A, but your opponent grabs B in sente and then takes C. Instead, you should take B, your opponent takes A, and you take C. This way you get 2 out of 3 big points instead of 1 out of 3. This is what professionals mean when they talk about getting the last big point in the opening. And they do this kind of analysis all the time in the endgame. Note that the addition of another large gote move, say 94 points in gote (D, temperature 47), means that A might be the best move again. Please work this out for yourself My application of the theory gives a precise mathematical (and graphical!) meaning to "sente", "gote", "double sente", and even vague concepts like exactly when something "becomes" sente or double sente. But the explanation is rather complicated and requires an understanding of the basic theory in On Numbers And Games or Winning Ways v.1. I hope to publish something eventually, but right now it's all I can do to keep up with Berlekamp's progress, and try to look at how this applies in real games. Berlekamp has gone beyond mere temperature, to expressing games as "overheated" simpler games, and playing in the simpler games. This allows him to distinguish (for example) some temperature 1 moves as being infinitesimally better than other temperature 1 moves. He can construct problems in which this difference is the margin between winning and losing. I think even pro 9 dans would have trouble solving these problems. Howard A. Landman landman@hanami.sun.com
landman%hanami@Sun.COM (Howard A. Landman) (04/23/89)
In article <28044@cci632.UUCP> jf@ccird3.UUCP (Jens Fiederer) writes: >In article <100234@sun.Eng.Sun.COM> landman@sun.UUCP (Howard A. Landman) writes: >>On the other hand, some studies of my pro game database indicate that pros >>routinely make hundreds of points of errors per game; so the possibility >>that a program might someday beat them is quite real. >Apparently, at least one pro disagrees: Kato Masao has stated (boasted?) >that God (to avoid religious disagreements here, assume that hypothetical >entity/process that makes no mistakes at Go could give him ONE handicap >stone That would put the figure for Kato at about 10 points of errors >per game. Is Kato lying, or are the other pros really that much worse? Obviously, I think Kato is either lying or deluded. I vaguely recall one game (I think between Sakata and Shuko) where there was a big running fight worth about 75 points. Post-game analysis showed that both players had made blunders that SHOULD, with correct play, have given the battle to the other player. I think there were about 6 such errors in the space of 20 moves or so. That's 225 points of errors per player. Not counting all the other moves in the game. More typically, it's easy to imagine that many moves in the opening could be small errors. At a couple of points per move, it doesn't take very long to exceed 10 points. I strongly doubt that Kato could get 50 moves into a game without making 20 points of errors. Howard A. Landman landman@hanami.sun.com
jansteen@cwi.nl (Jan van der Steen) (04/27/89)
In the Dutch Go magazine 16-6 (august 1979) an article was
published which amongst other dealing with the classification
of Go players. The author of this article is Prof. Dr. K. Heine
(Wilhelmshaven, Germany).
= Quote start =
In the next graph, different results of Go games is measured against
the strength of the players involved:
spread in results
|
50| .
| .
40| .
| . *
30| *
| . *
20| *
| * *
10| .*
|. *
_.___|_______________________________ strength (Japanese system)
| | | | | |
0 5D 1k 5k 10k 15k
Some conclusions:
- Perfect Go is played by someone who is able to give a
9 Dan professional a four stone handicap.
- The average size of the result is proportional to the
quality of the game.
- ...
= Quote end =
Interesting, isn't it?
--
-=-=-=-=-=-=-=-=-=-=-=-=-=--=-=-=-=-=-=-=-=-=-=-=-=-
Jan van der Steen, CWI the Netherlands
jansteen@cwi.nl (or uunet!mcvax!jansteen)
-=-=-=-=-=-=-=-=-=-=-=-=-=--=-=-=-=-=-=-=-=-=-=-=-=-