Results of the 1992 World Computer Go Championship, held in Tokyo, Japan on November 11 and 12. 1 - Go Intellect, Ken Chen USA 5-1 2 - Handtalk ZhiXing Cheng China 4-2 3 - Goliath Mark Boon Netherlands 4-2 4 - GOG 5th gen project? Japan? 4-2 5 - Star of Poland Januz Kraszek Poland 4-2 6 - Many Faces of Go David Fotland USA 3-3 7 - Nemesis Bruce Wilcox USA 2-4 8 - Great Hon-in-bow Takeshiro Yoshikawa Japan 2-4 9 - Rex 2-4 10 - Go Congress 0-6 Go Intellect lost to Handtalk. Handtalk lost to GOG and Goliath Goliath lost to Go Intellect and Star of Poland GOG lost to Go Intellect and Many Faces of Go Star of Poland lost to Go Intellect and Handtalk Many Faces of Go lost to Go Intellect, Goliath, and Star of Poland The top programs were very well matched this year. The top 6 finishers each beat at least one program that finished above them. Star of Poland had the bad luck to be paired with Rex and Great Hon-in-bow in early rounds, which hurt it in the tie breaker. Any of the top 5 finishers could have taken first place, but Go Intellect has been among the top programs for several years and deserves the title. The three top programs earned the right to challenge 6-dan amateur human opponents at 15-stone handicaps. The humans, age 11-13, won all three games. _Computer_Go_ magazine $15/year (U.S. dollars outside Canada) 71 Brixford Crescent Winnipeg Manitoba R2N 1E1 Canada (204) 256-2537 and (204) 946-7461 (office) Results from the 1991 World computer Go Congress: Main Computer Tournament: Place Program Author Country Wins 1 6 Goliath Mark Boon Netherlands 2 5 Go Intellect Ken Chen USA (lost to Goliath) 3 4 Dragon Tung-Yueh Liu Taiwan 4 4 Weiki III Sanechika Japan 5 4 Star of Poland Kraszek Poland 6 3 Handtalk ZhiXing Cheng China 7 3 Stone Kuo-Yuan Kao Taiwan 8 3 Modgo Knoffle Germany 9 3 Mac Won-Ho Jee Korea 10 3 Many Faces David Fotland USA 11 2 Nemesis Bruce Wilcox USA 12 2 Hirartsuka Shigyou Japan 13 1 Explorer Martin Muller Switzerland 14 1 Daihoninbo Yoshikawa Japan (Win was due to a bye) 15 0 Go Yuzhi Yang China (crashed every round) "Best Design" prize for the program with the overall best combination of ease of use, features, look, and playing strength, went to Many Faces of Go. Goliath went on to challange the 3 human players (young 5 dans), at a 16 play handicap and won all 3 games. It challenged at the next level (14 play handicap), and lost all three games. Next year the human challenge will be at a 14 play handicap. --------------------------------------------------------------------- Results of 1991 North American Computer Go Tournament, held at the 1991 Go Congress in Rochester, New York. 1st: Many Faces of Go, By David Fotland 2nd: Go Intellect, by Ken Chen 3rd: Stone, by Kao 4th: Contender, by Lynn Beus and Jim Logan 5th: Nemesis, by Bruce Wilcox 6th: Swiss Explorer, by Martin Mueller and Anders Kierulf Swiss Explorer forfeited two games, to Many faces and Nemesis, because it was late and missed two rounds. Swiss explorer lost to Contender due to an unrecoverable crash, but Contender was ahead at the time. Nemesis lost two games, to Contender and Stone, due to unrecoverable crashes. Nemesis was ahead in the game against Contender, and about even with Stone when it crashed. Stone is a rewrite of a program that has done well in Taiwan in the past. Swiss Explorer was rewritten for this year. The game between Many Faces and Go Intellect was exciting - both programs killed large enemy groups, and the score swung over 100 points each way in the middle game, then the programs left a very large ko on the board until the last dame was filled. Many Faces beat Stone by about 20 points and Nemesis and Contender by about 140 points each. Con Exp MFGO INT NEMESIS Stone Wins Place Contender x 1C 0 0 1C 0 2 4th Explorer 0C x 0F 0 0F 0 0 6th Many Faces 1 1F x 1 1 1 5 1st Intellect 1 1 0 x 1 1 4 2nd NEMESIS 0C 1F 0 0 x 0C 1 5th Stone 1 1 0 0 1C x 3 3rd -David Fotland (3 Dan, author of Many Faces of Go) ----------------------------------------------------------------------- Here are the reults of the 1989 World Computer Go Championship held in Taipei, R.O.C. on November 11th and 12th. Place Programmer Program Country R1 R2 R3 R4 1 (3) Mark Boon Goliath Holland +14 +10 +6 +2 2 (11) Bruce Wilcox Nemesis USA +12 +3 +8 -1 3 (5) Ken Chen Go Intellect USA +5 -2 +11 +6 4 (5) Anders Kierulf Swiss Explorer Switzerland +7 -6 +10 +8 5 Noriaki Sanechika Igo 2.24 Japan -3 +13 +7 +12 6 (4) Janusz Kraszek Star of Poland Poland +9 +4 -1 -3 7 (8) David Fotland Cosmos USA -4 +9 -5 +10 8 Yen Chi Lin Go ROC +13 +12 -2 -4 9 Tadashi Takamoto AISYS King Japan -6 -7 +13 +11 10 (7) Gao Guo Yuan Stone 2.0 ROC +11 -1 -4 -7 11 Lin Guang Jiue Life ROC -10 +14 -3 -9 12 (2) Liu Dong Yue Dragon ROC -2 -8 +14 -5 13 (12) Chang Sheng Shu Magic Go ROC -8 -5 -7 +14 14 Wu Jeng Ru WCR II ROC -1 -11 -12 -13 () shows place from last year's world championship. This year there were large improvements in most of the programs. Dragon was the winning program until last year, when it came in second. Most of last year Liu Dong Yue has been in military service so he hasn't had much time to improve his program and this year it came in 12th. Last year's top program, Codan, could not be at the championship this year, but it did not finish first in the Japanese preliminary, and the other Japanese programs came in 5th and 9th. The most improved program was Nemesis, which came in 11th last year and 3rd in the USA preliminary, but took 2nd place. Swiss Explorer and Go intellect are both derivatives of Go Explorer, which took 5th place last year. I think that all of the top 9 programs are stronger than last year's top finisher was. The final game between Goliath and Nemesis was won by 1 point by Goliath, and the game between Go Intellect and Nemesis was won by 3 points. If Goliath had lost it would have been 5th place because it played relatively weaker opponents than the other top programs. The top programs are close enough in strength that 4 rounds is not really enough to accurately determine which is best. Next year the contest may be played on 3 days with 8 rounds to solve this problem. Goliath had the opportunity to play a 16 play handicap game against a 12 year old 6 dan. (Under Ing rules, Black makes 16 plays, then plays first so there are actually 17 black stones on the board when white makes his first play.) Goliath lost, but only by about 15 points, so maybe next year the computer will be able to win. -------------------------------------------------------------------- Though it is difficult to obtain a precise estimate of the abilities of these GO programs, their strengths are close to the 9-12 kyu range. Each program may have certain anomalous vulnerabilities which can be discovered after a few games and subsequently exploited. From: David Fotland From: jansteen@cwi.nl (Jan van der Steen) 9x9 TOURNAMENT PLAYER PROGRAM MACHINE I II III IV TOT a b ======================================================================== 1 D. Y. Lui (Taiwan) Dragon 3.0 Mac +14 +5 +6 +2 4 8 8 2 D. Fotland (USA) Cosmos 1100 +13 +12 +3 -1 3 5 9 3 B. Wilcox (USA) Nemesis 910 +8 +13 -2 +6 3 5 8 4 M. Boon (NL) Goliath II 1100 -6 +9 +12 +7 3 5 7 5 F. C. Tang (Taiwan) Long Feather 910 +7 -1 +10 +12 3 4 8 6 R. Rehm (NL) Goliath I 910 +4 +11 -1 -3 2 4 8 7 A. Scarff (GB) MicroGo 910 -5 +14 +11 -4 2 1 7 8 K. S. Chen (USA) Explorer Mac -3 -10 +13 +11 2 1 6 9 K. Y. Chen (Taiwan) Jester 910 -11 -4 +14 +10 2 1 5 10 C. S. Chang (Taiwan) Magic Go 910 -12 +8 -5 -9 1 2 8 11 J. Kraszek (P) SOP 910 +9 -6 -7 -8 1 2 8 12 C. W. Shuie (Taiwan) Stone 1.0 1100 +10 -2 -4 -5 1 1 10 13 S. S. Yu (Taiwan) Dragon 2.0 910 -2 -3 -8 +14 1 0 8 14 H. Landman (USA) Poka Sun -1 -7 -9 -13 0 0 9 a = SOSB and b = SOS. 910 is an Acer computer running on a 80286 Intel processor. 1100 is an Acer computer running on a 80386 Intel processor. Mac is a MacIntosh II. Sun is a Sun 4. 19x19 TOURNAMENT PLAYER PROGRAM MACHINE I II III IV TOT a b ======================================================================== 1 K. Hayashi (J) Codan Toshiba +16 +6 +3 +2 4 8 8 2 D. Y. Liu (Taiwan) Dragon 3.0 Mac +9 +4 +7 -1 3 7 11 3 M. Boon (NL) Goliath II 1100 +14 +8 -1 +6 3 5 9 4 J. Kraszek (P) SOP 910 +12 -2 +9 +7 3 5 8 5 K. S. Chen (USA) Explorer Mac -6 +16 +13 +8 3 3 8 6 J. Sakai (J) Igo II 910 +5 -1 +11 -3 2 5 12 7 G. Y. Gao (Taiwan) Stone 1.0 910 +10 +11 -2 -4 2 4 10 8 D. Fotland (USA) Cosmos 1100 +13 -3 +10 -5 2 3 9 9 R. Rehm (NL) Goliath I 910 -2 +12 -4 +14 2 2 8 10 N. Sanechika (J) Go V. 1.3 910 -7 +15 -8 +12 2 2 6 11 B. Wilcox (USA) Nemesis 910 +15 -7 -6 +13 2 2 6 12 C. S. Chang (Taiwan) Magic Go 910 -4 -9 +15 -10 1 1 8 13 A. Scarff (GB) MicroGo 910 -8 +14 -5 -11 1 1 8 14 F. C. Tang (Taiwan) Long Feather 910 -3 -13 +16 -9 1 0 6 15 Huang (Taiwan) Logos 910 -11 -10 -12 +16 1 0 5 16 S. S. Yu (Taiwan) Dragon 2.0 910 -1 -5 -14 -15 0 0 9 Toshiba is a Toshiba 3100, a PC compatible running a 80386 Intel processor. -- Jan van der Steen, CWI the Netherlands jansteen@cwi.nl (or uunet!mcvax!jansteen) From fotland@hpda.hp.com Tue Feb 13 15:39:07 1990 ------------------ 10 programs participated in this year's (89) United States Championship. There weren't too many surprises in the finishing order. Two strong European programs entered but were not eligible to qualify for the international tournament in Taiwan. Place N.A.Place Program Author Record 1 1 Go Intellect K. Chen 4-0 2 - MicroGo 2 A. Scarff 3-1 3 2 Cosmos D. Fotland 3-1 4 - Star of Poland J. Kraszek 3-1 5 3 Nemesis B. Wilcox 2-2 6 4 Poka H. Landman 2-2 7 5 Golem H. Enderton 1-3 8 6 Contender L. Beus 1-3 9 7 Go Guru K. Schatten 1-3 10 8 Tsunami B. Ladendorf 0-4 Go Intellect is the next generation of Go Explorer. It is much stronger. Opinions of GI's strength ranged from 12 kyu to 5 kyu, with most people saying 8 to 10. Go Explorer is generally considered to be 12 to 14 kyu, so this is a large improvement in one year. MicroGo 2 finally did fairly well, surprising many observers. Alan Scarff was the only person who thought it had a reasonable chance against Go Intellect in their 4th round match. Alan has said that the program uses cellular automaton techniques, but he hasn't explained how yet. Cosmos qualified as expected, beating Nemesis as expected. There was a little excitement in the 4th round, when Poka got paired with Cosmos, which should have been a sure win for Cosmos. However, due to some kind of bug, Cosmos started moving slower and slower, and got into serious time trouble. Dave Fotland finally had to kill it and re-enter the moves by hand. (Maybe he'll implement auto-save or a trickle file now?) Eventually he got Cosmos back in sync and completed the game, but another 5 minutes and it would have been disqualified. Star Of Poland placed about as expected. The 2nd round game between MicroGo and SOP was very difficult, with a large capturing race that MicroGo won. Nemesis lost to the stronger programs and beat the weaker programs. So did Poka. It is unfortunate that Nemesis and Poka were never paired, since it would have been an interesting game. As it turned out, the 4th round match between the two worst programs (Go Guru and Tsunami) decided the 3rd place by tie-breaker (sum-of-defeated-opponent's-scores). Golem is basically the same program that competed in the USENIX tournament in 1987. It is tactically very strong, but weak elsewhere. Contender is a several-rank improvement of Infinity Go, but that still leaves it around 23 to 25 kyu. Go Guru and Tsunami are very young programs, and were not able to stand up to any of the more mature ones. I expect that these could improve dramatically in a year. Except for the Cosmos time problem and one glitch in another program, there were no crashes this year. All games were considered completed. This contrasts with last year, where only 5 programs were entered and the two that didn't qualify both crashed alot. Howard A. Landman landman@sun.com From: David Fotland From: jan@mathrt0.math.chalmers.se. (Jan Stein) Subject: 1st Computer Olympiad GO tournament I havn't seen any results from the GO tournament in the 1st Computer Olympiad, so I have taken time to post the results. It's interesting to notice that Go Intellect which placed 1st in North American tournament only came fourth. The first three program in the 19x19 tournament are also this years European entries in the Taiwan tournament. 19 x 19 GO 1 2 3 4 5 6 7 8 9 10 score position ------------------------------------------------------------------------------ 1. Swiss Explorer (Switzerland) x 0 1 1 1 1 1 1 1 1 8 1 2. Goliath (Netherlands) 1 x 0 0 1 1 1 1 1 1 7 2 3. Star of Poland (Poland) 0 1 x 1 0 1 0 1 1 1 6 3 4. Go Intellect (USA) 0 1 0 x 1 1 0 1 1 1 6 4 5. Stone (Taiwan) 0 0 1 0 x 0 1 1 1 1 5 5 6. Modgo (W. Germany) 0 0 0 0 1 x 1 1 1 1 5 5 7. Microgo 2 (England) 0 0 1 1 0 0 x 0 1 1 4 7 8. Dragon (Taiwan) 0 0 0 0 0 0 1 x 1 1 3 8 9. Tango (W. Germany) 0 0 0 0 0 0 0 0 x 1 1 9 10. Cingo (England) 0 0 0 0 0 0 0 0 0 x 0 10 9 x 9 GO 1 2 3 4 5 6 7 8 9 10 score position ------------------------------------------------------------------------------ 1. Dragon (Taiwan) x 1 1 0 1 1 1 1 1 1 8 1 2. Go Intellect (USA) 0 x 1 1 0 1 1 1 1 1 7 2 3. Goliath (Netherlands) 0 0 x 1 1 1 1 1 1 1 7 3 4. Go 4 (England) 1 0 0 x 1 1 0 1 1 1 6 4 5. Microgo 2 (England) 0 1 0 0 x 1 1 0 1 1 5 5 6. Modgo (W. Germany) 0 0 0 0 0 x 1 1 1 1 4 6 7. Swiss Explorer (Switzerland) 0 0 0 1 0 0 x 1 1 1 4 6 8. Star of Poland (Poland) 0 0 0 0 1 0 0 x 1 1 3 8 9. Tango (W. Germany) 0 0 0 0 0 0 0 0 x 1 1 9 10. Cingo (England) 0 0 0 0 0 0 0 0 0 x 0 10 -- Jan Stein, Chalmers Computer Society, E-mail: jan@cd.chalmers.se Disclaimer: afs: Lost contact with server 129.16.38.2 From: fotland@hpihoah.cup.hp.com (David Fotland) Subject: X11 Go program available (includes two player mode) Date: 26 Nov 91 19:38:16 GMT Documentation for "The Many Faces of Go", Cosmos, IGO, and xgo, a program that plays Go, by David Fotland. (11/26/91) "The Many Faces of Go" is a GO program for the IBM-PC that includes an extensive tutorial on the rules and strategy, a set of introductory problems (from Graded Go Problems For Beginners), several professional games with commentary (and the ability to present additional games available from Ishi Press), a Joseki tutor with about 15,000 moves, and one of the strongest Go playing computer opponents available. MFGO was introduced in January, 1991, and currently holds the title of "North American Computer Go Champion". Cosmos was the previous version of this program, introduced in September, 1988, and is no longer available, since MFGO is a stronger player and has a much better user interface. IGO is a 9 line only introductory version of Many Faces of Go for the IBM-PC that is available from the American Go Association or Ishi Press. It is free (except for shipping and handling), and may be freely copied and given away to friends. Xgo is a port of Many Faces of Go to X11 release 4 on the Hewlett Packard HP9000 3xx, 4xx, 6xx, 7xx, and 8xx computers. It emulates the VGA graphics interface from MFGO, and has a two player, two screen mode for playing games with friends over the net. The most recent Cosmos is Rev 6.11. The most recent Many Faces of Go is Rev 7.03. The most recent xgo is Rev 7.34. The most recent rev of IGO is 7.5. All programs share the same source code. MFGO plays the oriental game of Go, a 2 player board game where the object is to surround territory. Players take turns putting pieces (called stones) on a board. Once played a piece does not move, although it may be captured. Play continues until both players pass and the score is the number of points surrounded plus the number of prisoners. Highest score wins. Tournament Results: "Best Design" award 1991 World Computer Go Championship 1st place 1991 North American Computer Go Championship 10th place 1991 World Computer Go Congress 5th Place 1990 USA Computer Go Championship 2nd place 1989 USA 19 line computer Go championship 7th place 1989 World 19 line computer Go championship 1st place 1988 Usenix 19 line computer Go tournament 1st place 1988 USA 19 line Computer Go championship 8th place 1988 World 19 line computer Go championship 2nd place 1988 World 9 line Computer Go championship 4th place 1987 World 19 line computer Go championship 4th place 1987 World 9 line Computer Go championship MFGO is about 15 Kyu strength. Xgo is about 13 Kyu strength. Beginners are about 25 to 30 kyu. Smaller numbers are stronger players. The difference in rank is the number of handicap stones given on a 19 line board. Most serious players get to 6 to 10 kyu within a year or two if they have stronger people to play. After one kyu, the next rank is one dan and ranks go up to 9 dan with the strongest amateur players at 7 or 8 dan. My rank is 3 Dan. How to get it: If you are inside HP, xgo is ninstallable from hpihoah. The package is called "go" and includes a man page. It puts "xgo" in /usr/local/games, the man page "xgo.6" in /usr/local/man/man6, and the data files and graphic bitmaps in /usr/local/games/lib/xgo. It also installs an old X10 and curses version as /usr/local/games/go. From outside HP you can get Xgo from uunet.uu.net via anonymous FTP. Look in games/hp-xgo.shar.Z. This shar file contains binary executables for both HP9000 68000 based machines (3xx and 4xx) and RISC based machines (6xx, 7xx, 8xx), as well as documentation and data files. The file is about 2.75 Mbytes, and uncompresses to about 6 Mbytes. Transfer it in binary mode, then use 'uncompress hp-xgo.shar.Z' to uncompress it, then 'sh hp-xgo.shar' to split out the separate files. Xgo is available free on Hewlett Packard 9000 series computers. MFGO is available for IBM PC or compatibles with at least 512 Kb of memory as "The Many Faces of Go", for $59.95 (plus $3.00 postage and handling) in many computer and game stores or from: Ishi Press 76 Bonaventura Dr. San Jose CA 95134 (408)944-9900 I do not distribute source since this is one of the stronger programs in the world and I want to win the world championship. I have no plans to port this program to any other Unix based machines, especially not to Sun workstations. I may port it to the Macintosh, Amiga, or NeXt machines. Usage (for Xgo X11 version): xgo [-sSIZE] [-lLEVEL] [-hHANDICAP] [-display FOO:0.0] [-display2 BAR:0.0] SIZE is size of board (7 to 19). Default is 19. LEVEL is the playing level (0-20). Default is 10 HANDICAP is number of handicap stones -display FOO:0.0 use FOO for display -display2 BAR:0.0 use BAR for the second player MFGO and xgo have a setup screen that allows setting of playing level, handicap, rules, color played, and some user interface parameters. The playing level controls the number of nodes visited in each tactical search and the number of moves considered on the full board. Higher numbers are slower, but allow the program to read out more difficult tactical situations and find less obvious moves. MFGO/Xgo has 20 playing levels, which cover the same range as the 100 playing levels in Cosmos. MFGO/Xgo allows black to start with handicap stones on the board to make up for a difference in strength between the players. Japanese rules are commonly used in the US and Japan. The Ing Chinese rules are used in Taiwan and are the official rules of the Ing computer Go championship (the one with the $1.5 Million prize). Many Faces of Go Info: MFGO will run on any IBM PC, XT, AT, PS/2 system, Tandy 1000, or clone. The machine should have at least 512Kb of RAM (Cosmos is about 450K) and a 5 1/4 inch or 3 1/2 inch floppy drive. MFGO is distributed on two 362Kb floppy disks and one 3 1/2 inch disk. It is not copy protected. To run it, just type go. It allows you to set up a configuration for the game where you can specify board size, handicap, computer to play black, white, both or neither, beep for Atari, playing level, archive all games to disk, randomize moves (so it doesn't always play the same game), etc. You can save the configuration on the disk. MFGO supports Hercules, CGA, EGA, VGA (Color or Mono), Tandy, and Laptop graphics modes. In each mode it uses the highest resolution available and has shaded stones. In VGA the board has a realistic wood grain. The VGA graphics are use for the X11 version. The rules and strategy of Go are on line and there is extensive on line help for the configurations, playing, and scoring, including a 90 screen on line tutorial presented in question/answer format (using the text from the AGA book "The Way to Go") with two commented small board games. Games can be saved and restored, or reviewed move by move. MFGO can explain its reasons for picking a move and can give you a hint as to where you should move next (and explain the reasons for the hint). MFGO includes a joseki tutor that allows you to browse the 15,000 move joseki library. MFGO is designed to be very easy to use for the Go and or computer novice and is a good way to introduce someone new to Go. It can play games on small boards. It supports any odd size from 9x9 to 19x19. Igo information: Igo is MFGO restricted to a 9 line board, and it includes a new, improved on line tutorial presented in problem/answer format (using the text from the AGA book "The Way to Go"). Igo has 4 levels, which control the playing strength and the handicap, so an improving player will move up in levels. Igo is intended primarily to introduce new players to the game. How it Works: Go is a very difficult problem. There is no single idea that can generate strong moves (like searching in chess). Strong programs are strong because they have lots of go knowledge. The most important thing is a way to organize lots of go knowledge so it can be used quickly. MFGO has 250 major move suggesting rules (and most of them are results of several subrules). It has a 26,000 move annotated joseki library. It has 320 patterns in a pattern library. It has maybe 50 rules each hardcoded into the tactical analyzer, connection evaluator, eye evaluator, and life and death evaluator. It has 3 different territory evaluators which are used in different circumstances. (One for secure eye space, one for liberties, and one for influence.) The move suggesting rules suggest moves to try and probable values. These are sorted and the "playing level" top moves are further considered. Each of these moves are made on the board and the position evaluated and scored (using the tactical analyzer, eye evaluator, etc.) The move which leads to the best score is played. Details There are three parts of a Go program; the data structures for representing go knowledge, the evaluation function for determining the score, and the move selection expert system. Data structures: My most basic data structure is a sorted list of integers. I use it for things like lists of liberties, lists of neighboring groups, and lists of eyepoints. I keep track of local structures like liberty lists incrementally. Some global structures like the amount of influence on each square are completely recalculated every move. For some things like the value of an eye I only recalculate ones that change. Most data structures are attached to strings or groups rather than squares on the board. Important data structures: Per point (intersection): Color (black, white, or empty) String number Number of adjacent black, white, empty points List of adjacent empty points White and black influence Which eye is this point part of List of connections through this point List of patterns that match here Per string (set of adjacent stones of same color, unit of capture): Number of liberties List of liberties List of adjacent enemy strings Group number List of connections from this string Aliveness Tactically threatened flag Per Group (set of unbreakably connected strings): List of component strings Aliveness Number of liberties List of liberties List of eyes Number of eyes List of eye potentials List of running points Per connection: Two string numbers Status of connection (unbreakable, cuttable, etc) Type of connection (hane, knights, one point jump, etc) List of points in connection Per eye: List of points in eye How many eyes if I move first How many eyes if enemy moves first How many eyes if enemy gets two moves in a row List of vital points Type of eye (one_point, dead_group, line, etc.) Per eye potential Type of potential (eye vital point, extend, connect, etc) Amount of potential Per running point Type of point (toward friend, toward enemy, etc) Evaluating a position: First, figure out where the strings of stones, liberties, liberties of liberties, stones next to empty squares, and connections are (I do this incrementally). A string of stones is the unit of capture in Go. For each string, see if it is tactically captured if it moves first. If so, mark it DEAD. For each string, see if it is tactically captured if it moves second. If so, mark it THREATENED. Find all of the connections between strings. Check tactically if they are cuttable or not. (Knowing which strings are DEAD or THREATENED is a big help here.) Collect all of the strings that are unbreakably connected into groups. Analyze all the eyes on the board and assign them to groups. An eye is a small space mostly surrounded by stones or a small DEAD group. MFGO knows the dead shapes and vital points. It checks the diagonals of small eyes to see if they are false. Figure out the value and potential of each eye. (For example, 3 in a row has a value of one eye and potential of two eyes). Find all of the territory completely controlled by each group which was not already counted as eyes. This is the army's EYESPACE. For each group, if it has eyes plus EYESPACE for two eyes, mark it ALIVE. Radiate influence from the ALIVE groups (and negative influence from DEAD ones), and slight influence from the other stones. For each group that is not ALIVE or DEAD, figure out how strong it is. Take into account potential connections, potential extensions along the edge, potential eyes. If it has two independent moves that could make two eyes, mark it MIAI-ALIVE. If it has one move that can make it alive, mark it UNSETTLED. The remaining groups are WEAK. Look for two adjacent WEAK groups to find semeais and sekis. See if the radiated influence from a friendly live group hits a weak group. If so it is not surrounded. Separate the WEAK groups that can run or fight from the ones that are hopeless. Generally a WEAK group that can't run and has ALIVE neighbors and few liberties is hopeless. Each point with a stone on it or adjacent to a stone or between a stone and the edge is scored according to how alive the stone is. Other points are scored based on the radiated influence. Unsettled groups are scored differently depending on who has the move. The guts of the evaluation function is based almost entirely on life and death considerations. My feeling is that you can make 20 kyu moves based on shape alone, but you can't get to 10 kyu unless you can tell which groups are strong and which are weak, and especially which are unsettled. MFGO classifies groups according by how strong they are into the following classes: HERE DOWN ARE DEAD 25 - tactically captured unconditionally 24 - presumed dead because surrounded without any eyes (smothered small group) 23 - Temp used for weak groups undecided yet 22 - No eyespace or potential and nbrs all alive 21 - probably dead. some eye space or potential, nbrs alive 20 - in semeai loses HERE DOWN ARE WEAK - PROBABLY WILL DIE 19 - no running ability, weak nbrs and some eye potential 18 - can't run, lots of eye potential, only one eye has aji to live, or can be used as ko threats 17 - in a semeai. behind - aji for later 16 - poor running ability - can't live in one move HERE DOWN ARE UNSETTLED 15 - in a semeai. unsettled 14 - Running fight (can run and there are adjacent weak groups) 13 - surrounded, can live or die in one move 13 - would be alive, but tactically threatened 12 - in a semeai. Ahead or temporary seki 11 - unsettled - can live in one move or limp away HERE DOWN ARE ALIVE (or settled for now) 10 - can run away easily, no eyes 9 - can run away easily, one eye needs two moves to make second eye 8 - can live in one move or run easily 7 - Alive because wins semeai 6 - alive in seki 5 - miai for barely space for two eyes (dangerous) 4 - barely territory for two eyes (dangerous) HERE DOWN ARE VERY ALIVE 3 - miai for lots of eye space - 3 or more ways to make second eye 2 - absolutely unconditionally alive - two small eyes or lots of territory The influence function: Once we know the strength of groups we can radiate influence to determine where the territory is. Influence is radiated independently from each stone and summed at each point. The influence function falls off as 1/distance, and does not go through stones or connections. A function that falls off as 1/distance will create a constant field inside any fully enclosed area, no matter how big it is, which is what we want for territory. Dead stones radiate negative influence. The tactician: The tactician does a single tactical search with the goal of capturing a string. It gets passed the maximum liberty count, maximum depth, and maximum size of the search. When seeing if strings are DEAD or THREATENED the maximum liberty count is 4. If a string gets 5 liberties it is assumed to escape. The maximum depth is about 100 which allows a ladder across the board to be read out. The size of the search is the playing level, which controls the number of decisions made. Forcing moves don't count, so a ladder can be read out even at low levels. Eye and connection evaluations use much smaller values for the size of the search since for a solid eye or unbreakable connection you want to capture quickly. The tactician does about 200 nodes per second per MIP. Move Selection: I used to just try every move and score the board. This worked OK, but was very slow. Now I have a bunch of move suggestion code organized as a set of experts which suggest moves along with the reason for making them. There are over 250 reasons for making a move. Each reason comes with a bonus value, a guess value, a minimum aliveness, and an indication of which group is being attacked or defended (if any one is). The moves are sorted by the guess value and some number of them are tried (controlled by the playing level). After a move is tried we check if the rule applied. For example, if the rule is "Make an eye to save an unsettled group" and after the move is made the group is still unsettled, then the rule did not work and the move is rejected. If the move is an attacking move, the attacked group must end up weaker. If the move is a defending move, the defended group must end up stronger. If the rule applied, we check to see if the move is sente, and add a bonus if it is. The position is evaluated (as described above) and the rule bonus and sente bonus are added. If there is a move tree associated with this move (from a joseki or a pattern match) the moves in the tree are placed on the board and evaluated (as above), then the scores are backed up using minimax. After trying each move, the one which led to the highest score (counting bonuses) is made. In evaluating the position a local quiescence search is made. Move Suggestion: The move suggestion experts are: Fuseki Playing in empty corner Shimari and kakari Joseki moves Big moves on edge Towards enemy Invasions Between friendly stones Playing in the center (reducing moves and junction lines) Playing safe when ahead Respond when enemy adds stone to dead group Squirming around when behind Make a bogus invasion try to make a hopeless group live Pattern matching patterns for cutting and connecting patterns for surrounding and avoiding getting surrounded endgame patterns killing/saving groups patterns Shape moves Saving a weak group making eyes running fighting semeais Save threatened string Capture threatened string Killing a weak group surrounding taking eyes Cutting and connecting Contact fights Blocking extending for liberties hane Ko threats make a big atari Filling dame There is a Joseki library which can suggest joseki moves. It's organized as an directed acyclic graph (not a tree). Moves are marked as normal, urgent, bad (these moves are ignored but the response is in the library in case the opponent makes one), followup, etc. The Joseki database is encoded in about 1.2 bytes per move. There is a pattern matcher with over 300 patterns in it. Each pattern is 8x8, where each point is specified as black, white, empty, don't care, white or empty, black or empty, or black or white. Each pattern has a set of attributes with it that must also match. For example, the stone at (4,2) must be alive, or the stone at (2,5) must have at least 2 liberties. Each pattern has a move tree attached that is used for full board lookahead. There are about 1600 moves in all the move trees. The move suggestion code is easily extensible by adding more patterns or firing rules based on other criteria. The program has text associated with each rule so it can "explain" its reasons for making moves. This makes it easy to debug. Program Size: Many Faces of Go is about 41,000 lines of code with about 15,000 of those lines in the user interface and the rest in the playing algorithm. It is written entirely in C except for a small amount of PC video graphic interface code which is in 80x86 assembler. On the PC, MFGO occupies about 440 Kbytes in memory, about 2/3 code and 1/3 data. -David Fotland >From: bdp@ely.cl.cam.ac.uk (Barney Pell) Subject: (LONG) Computer GO people and INFO Date: 7 Jun 90 17:29:26 GMT I still haven't completed the paper I promised long ago. But at last, I've compiled the numerous responses I got. Thanks to everyone who replied. I hope we can once again use this newsgroup as a place to exchange ideas about COMPUTER GO. I didn't make an address book below, instead I pretty much just included the relevant parts of the responses I received. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%% %%% Computer GO People and INFORMATION %%% %%% Information compiled by Barney Pell %%% Thanks to everyone in NETLAND who replied. %%% %%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% ---------------------------------------- >From: Barney Pell ---------------------------------------- I'm working on Machine Learning in the Game of GO. I currently have two areas of research: 1. Probabilistic evaluation function learning 1.1. Given some features, learn which ones are good, and in what combinations, based on statistical experience). 1.2. Supervised learning (from master games) 1.3. Unsupervised (program plays against itself, experiments). 2. Dependency-based learning: 2.1. Given: a dependency structure (i.e., this group is safe because it can kill that group, because it has only 2 liberties. 2.2. Given: some change which undermines a previous conclusion 2.2.1. (Like: enemy protected the 2-liberty group, so now my group is no longer safe. 2.3. Learn: General Concept of undermining this type of conclusion. 2.3.1. (In this example: "defend to attack"). ================================================== Barney Pell Computer Laboratory University of Cambridge phone: (0223) 334622 e-mail: bdp@cl.cam.ac.uk Life is a metaphor for GO! ================================================== ---------------------------------------- >From: Fred Hansen ---------------------------------------- Here's some stuff recently posted to the net by Jeff Boscole ( aesop@milton.u.washington.edu ). You should especially get in touch with the Computer Go journal. Anders Kierulf is studying with Jurg Nievergelt at: ETH-Zentrum/ETL CH-8092 Zurich Switzerland Fred Hansen ---------------------------------------- >From: Tim Duncan ---------------------------------------- I'm interested in building a Go playing program too, though haven't been able to devote much time to it yet. However, you might be interested in several papers on Go in: Max Bramer (ed) Computer game-playing: theory and practice. Ellis Horwood, Chichester, 1983 (ISBN: 0853124884) -------------------- >From Kaihu Chen -------------------- I have been working on computer Go for about 3 years. My program won the 3rd place in the 1987 Go tournament at Taipei. No, the K. Chen who won last year was not me (I was not there). I did my Ph.D. thesis with R. S. Michalski on Machin Learning, and I have been trying to apply it to computer Go. Personally I believe that's the only way for a program to reach 3-dan or higher. I would be happy to open up a channle of discussion so that we can benefit from each other. I am hoping to use inductive learning to generalize results derived from minimaxing into reliable declarative forms, in order to reduce the need for minimaxing at the time of competition. This is my way to make a Go program play faster and better with practice and time. Kaihu Chen MS: DLB5-3/E7 290 Donald Lynch Blvd Marlboro, MA 01752 U. S. A. (FAX)508-840-3494 email: kchen@aisg.enet.dec.com -------------------- >From Jens-Peter Haack -------------------- Im working on a GO-Programm for one year, it's written in C an runns on an ATARI ST and SUN's under X-Windows. It's the thema of my diplom in Informatik on the technical University of Berlin, to be finnished 21. Feb 90. With an old (and very clumsy) Version i got the 9th place of 10 in London last year (Computer Olymiad) in 19x19 GO. If you are interessted, ill send you a copy of my work after the 21. Feb. Addresses: Anders Kierulf, ETH Zuerich, CH-8092 Zurich, Switzerland e-mail: kierulf@inf.ethz.ch Ken Chen, Dept. of Computer Science University of North Carolina Charlotte, NC 28223, USA e-mal: chen@unccvax.uncc.edu Christian Haider, Ohsuga-Lab. The University of Tokyo 4-6-1 Komaba, Meguro-Ku, Tokyo 153 e-mail: haider%kaus1.ohsuga.u-tokyo.junet%utokyo-relay.csnet@RELAY.CS.NET Me (Jens-Peter Haack), Sedanstr. 25, 1000 Berlin 41, West-Germany e-mail: pyramid!tub!peter unido!tub!peter peter@tub.bitnet Christian Haider will be back in germany in 3 month's Do you know about the "Computer Go", DIN-A5 Magazin. Printed and edited in Canada, Editor: David Erbach, 71 Brixford Crescent, Winnipeg Manitoba R2N 1E1 There are 4 issues a year. The latest paper from A.Kierulf, K.Chen, J.Nievergelt i have, is dated May 1989: "Smart Game Board and Go Explorer: A case study in software and knowledge engineering" Christian Haider just finnished his report desribing his one year in Japan, working on his Programm LeGo, using Machine Learning. (Automatic Rule Creation and Improving). It should also be possible to order his Diplom-Work on the technical University of berlin: "Anwendung von Verfahren des Maschinellen Lernens auf das japanische Brettspiel Go" September 1988, (in german) -------------------- >From David Fotland -------------------- I wrote Cosmos, the strongest program commercially available (about 15 Kyu), which came in second place last year in the U.S. For recent information on computer Go, contact David Erbach 71 Brixford Cr Winnipeg Manitoba R2N 1E1 Canada (204) 256-2537 or (204) 946-7461 He publishes "Computer Go" which has many recent articles on algorithms. Noriaki Sanechika's address is AI language research institute Sakurai building 15-15, Shiba 3-Chome; Minato-Ku Tokyo 105, Japan Herbert Enderton is a graduate student at CMU doing work on Go and neural nets. Here are the names from last years US championships: K Chen D Fotland B Wilcox H Landman H Enderton L Beus K Schatten B Landendorf H Landman is reachable at sun!landman. Bruce Wilcox's address and phone is: Toyogo Inc 34 Oak St. Lexington, MA 02173 (617) 863-1454 -------------------- >From David Stoutamire -------------------- I am doing an MS on computer go. -- daves@alpha.ces.cwru.edu | David Stoutamire, | gradual student in computer engineering (216) 368-5038 | at Case Western Reserve University -------------------- >From Niek van Diepen (niekd@cs.kun.nl) -------------------- 1. Mark Boon (author of Goliath II, the current world champion, and C.S.-student at the University of Amsterdam). His address is: Tasmanstraat 43-I, NL-1013 PX Amsterdam, The Netherlands. He might be able to point out the others to you. 2. Jan Wielemaker (working at the University of Amsterdam on some AI techniques, and a go player who has considered using some of these techniques for programming go -- an aborted attempt, I think.) I do have an e-mail address of him: jan@swivax.uucp. -------------------- >From Howard A. Landman -------------------- I wrote a program Poka which is about 19 kyu - weaker than the good programs, but stronger than pretenders like Contender and GnuGo. It has the world's best (only?) full-board opening library, and excellent fast routines for calculating influence, but it's very stupid about tactics and living. It uses cellular-automaton-like algorithms for the influence stuff. I also have a huge amount of Go game data (over 200,000 moves), most of which I've typed in myself. I presume a good learning program needs a lot of data to train on? -- Howard A. Landman landman@eng.sun.com -or- sun!landman --------- From: landman@hanami.Sun.COM (Howard A. Landman) Elwyn Berlekamp at U.C. Berkeley taught a class this year on the Conway-Berlekamp-Guy theory of games, using Go for many of the examples. He's proved many interesting results, including for example that the temperature of a simple ko is 1/3 the number of points at risk. Lynn Beus at Brigham Young University is still actively developing the BYU Go -> Infinity Go -> Contender line of Go programs. Laura Yedwab, working at MIT under Ron Rivest, did a thesis called something like "On Playing Well In A Sum Of Games", which more-or-less proves that even the endgame of Go is PSPACE-hard by itself. (That the entire game of Go is PSPACE-hard was established a few years back by Sipser at Berkeley, who proved that the cut-vs-connect subproblems of Go are already PSPACE-hard.) I don't know whether Rivest is still interested in such matters. Danny Hillis at Thinking Machines Inc., designer of the Connection Machine, has expressed interest in computer Go as a good, hard theoretical problem. (See for instance the interview in Stewart Brand's "The Media Lab: Inventing the Future at MIT".) At least one person (myself) is experimenting with massively parallel algorithms for Go using Connection Machines. It might be possible for people with similar interests to get guest accounts on such machines. Hans Berliner at CMU could be a force to contend with if he ever turned his attention to computer Go, but I've heard rumors that he considers it too hard. Still, it might be worth contacting him. Judeah Pearl (at UCLA?) has done outstanding basic research in game theory, some of which is applicable to Go. -------------------- >From: Larry Watanabe -------------------- I am about 4-dan, and am studying machine learning under Larry Rendell at the University of Illinois. I have been thinking about doing a go program, but it seems to me that it would take up too much time. I already have a thesis topic, and it is not go. However, I might choose GO as a domain, but I don't think that I will write something that learns GO. To do so, you have to address a number of machine learning issues, and I may only address some of them in my learning system -- so there would be a large gap between what my system learns and what is needed to have a GO performance element. Larry Watanabe 154 Paddock Dr. E. Savoy IL 61874 USA e-mail: watanabe@thucydides.cs.uiuc.edu ---------------------------------------- >From: Herbert.Enderton@edu.cmu.cs.gp.a ---------------------------------------- I'm a graduate student at Carnegie Mellon and am also trying to do a PhD thesis on computer go. Machine learning may or may not be central to my research depending on how successful the various methods I'm trying turn out to be. ... The working title [of my thesis] is "The Use of Lemmas in Computer Go", where a lemma is a chunk of cached knowledge obtained through tactical search. -- Bert Enderton School of Computer Science Carnegie Mellon Pittsburgh, PA 15213-3890 U.S.A. (412) 268-7571 ---------------------------------------- >From: Richard Lorentz ---------------------------------------- I am responding to your posting from rec.games.go. First of all, David B. Benson was my Ph.D advisor and can probably be reached at: benson@wsu.edu. Based on your request for references I assume you have the Hamann paper and are having trouble finding anything after that. I am in the same boat and would like to hear about any newer references you may have turned up. I am thinking of starting up a go project of sorts. I am just learning the game (about 15 kyu) and figure I may be in a unique position to watch how I learn and program those ideas into a go player. I haven't written any code yet, and, in fact, have no algorithms in mind yet. I just applied for a local grant to get support to work on a go program The success or failure of that proposal will probably determine how quickly I start on mine. ================================================== Barney Pell Computer Laboratory University of Cambridge phone: (0223) 334622 e-mail: bdp@cl.cam.ac.uk ================================================== * Gerry Tesauro, who is at IBM Watson, created the winner of the Computer Games Olympiad Backgammon competition in 1989. This is the first time a learning program won over hand-crafted programs. A brief report is in Neural Computation vol 1 no. 3 (Fall 1989). The initial work was reported at NIPS 1 in 1988 and is in the proceedings (Neural Information Processing Systems vol 1, Touretzky, Ed., Morgan Kaufmann 1989) Other papers are Tesauro & Sejnowski, "A parallel network that learns to play backgammon", Artificial Intelligence 39, 357 (1989), and Tesauro, "Neural Network defeats creator in backgammon match" T.R. CCSR-88-6, U. of Illinois at Urbana-Champagne Center for Complex Research. * From: Dave Stoutamire "My thesis is on machine learning applied to go: it is not trivial, mainly for computatinal reasons. I ended up not using NNs for go because I didn't want to wait years for them to converge. Herbert Enderton at CMU (andrew.cmu.edu) has been doing some NNs for go for his PhD work." * From: Barney.Pell@computer-lab.cambridge.ac.uk "The following people (certainly the first) have done some work on NNs and GO: % Herbert.Enderton Herbert.Enderton@moriarty.theory.cs.cmu.edu %Howard Landman landman@sun.com I do work on Machine Learning and GO, but using logic and/or probability, not NNs." * From: landman@Eng.Sun.COM (Howard A. Landman) "...papers dealing with the computational complexity of GO Lichtenstein & Sipser, "Go is PSPACE-hard" (don't have the date or journal in front of me but they were posted to the net a couple of months ago) Yedwab, Laura, "On Playing Well In A Sum Of Games", MIT Masters thesis under Ron Rivest, available by sending email to (I think) publications@lcs.mit.edu" * From: heidi@ucthpx.uct.ac.za (Heidi de Wet) "...On a related topic, I saw a reference once to a ... Go program which reportedly played to 10 kyu (the Nemesis Go programs play to 20 and 15 kyu). The heart of the program was a so-called cellular automaton - a sort of one-layer NN with feedback. Each cell was one location on the board, and 'vacant' cells could take on one of 15 or so states. At each move, the net would cycle about 5 times before reaching a stable state, and picking its move. * unknown ...It comes from a collection of articles from the "Over the Horizon" column in the British weekly newspaper "Computing", by one Tony Durham. The book is entitled "Computing Horizons", by Tony Durham, published by Addison- Wesly, 1988. ISBN 0-201-18046-4." From: ddemers@UCSD.EDU (David E Demers) Newsgroups: comp.ai.neural-nets Organization: CSE Dept., UC San Diego I worked on this problem as a course project for a grad AI class. I am pretty much an expert with NNs, and a novice with GO. I used an approach similar to Tesauro's Neurogammon - trained a net to pick one position over another. Because of the network architecture, 19 x 19 GO was infeasible, so I used 9 x 9. However, finding data for 9 x 9 GO was difficult. I used DRAGON, a GO program for the Macintosh, to get some data. The result was a crude position evaluation function. The game player then had higher level routines to find all possible legal moves, and presented each to the evaluation function, and chose the highest scoring move. It didn't play very well at all, but DID actually play legal GO. I have corresponded with a few other people working on this, but know of no published research. You might post to rec.games.go. There is a newsletter or some other communication for Computer GO enthusiasts, but I don't recall the e-mail or surface address. There may in fact be a magazine... Good luck, -- Dave DeMers demers@cs.ucsd.edu Computer Science & Engineering C-014 demers%cs@ucsd.bitnet UC San Diego ...!ucsd!cs!demers La Jolla, CA 92093-0114 (619) 534-8187,-0688 ddemers@UCSD =========== From: Chris Chisolm Newsgroups: comp.ai.neural-nets Organization: University of New Mexico, Albuquerque I have also been interested in the aplication of neural nets to go. I have so far been just rying to teach myself about neural nets. I would like it if you would mail me the responses you get. BTW Howard Landman might be a good person to contact for this. I have not yet because I do not even know the right questions to ask yet. His address is landman@sun.com I believe. good luck. chris ============= From: Chris Chisolm That message reminds me of a few things you might be interested in. David Erbach publishes a computer go magazine. I have not seen anything in it yet on neural nets though. there are two sites where you can find go information. ftp scam.berkeley.edu in /src/local I think blake.u.washington.edu who knows where. if you can't find david erbachs address there talk to wjh+@andrew.cmu.edu he is the American GO Assc. net contact chris ============ From: ddemers@UCSD.EDU (David Demers) Gerry Tesauro, who is at IBM Watson, created the winner of the Computer Games Olympiad Backgammon competition in 1989. This is the first time a learning program won over hand-crafted programs. A brief report is in Neural Computation vol 1 no. 3 (Fall 1989). The initial work was reported at NIPS 1 in 1988 and is in the proceedings (Neural Information Processing Systems vol 1, Touretzky, Ed., Morgan Kaufmann 1989) Other papers are Tesauro & Sejnowski, "A parallel network that learns to play backgammon", Artificial Intelligence 39, 357 (1989), and Tesauro, "Neural Network defeats creator in backgammon match" T.R. CCSR-88-6, U. of Illinois at Urbana-Champagne Center for Complex Research. Note that one major problem with GO is that there is a large symmetry group, and no known canonical representation to choose among the members of the equivalence classes. NNs are notoriously poor at handling symmetries. My solution was to train on all members of the equivalence class, which inflates the number of training patterns by a factor of 16 with no true additional information. I'm sure a better solution is possible. Backgammon is much easier since it is linear and all positions are unique. Chess has only a right/left symmetry, but it is rare for the king and queen to end up switched, so for all practical purposes again has unique positions. There is someone at SUN Microsystems with a huge database of games available, in the form of C structs. He will probably give it away for free. I didn't think they would be useful, since my approach required annotations of some sort - that is, some expert decision that a particular move was superior to another. I STRONGLY suggest that 19 x 19 GO not be attempted as a first project. Tic-tac-toe (naughts & crosses) might be a good initial project, since it has the same symmetries as GO but all games can be exhaustively enumerated in a small space. If you can learn this game with say a 9-4-9 network (to keep the number of parameters at least on the order of the number of training patterns), the next step might be 9 x 9 GO. dave ========== From: heidi@ucthpx.uct.ac.za (Heidi de Wet) Newsgroups: comp.ai.neural-nets Hi, I'm afraid there's no help from here. However, as a) a keen Go player, and b) someone who's going to do an MSc in neural nets sometime soon, I'd _LOVE_ you to pass on any information you get. I've actually been wondering if I could get a thesis out of application of NN to Go... On a related topic, I saw a reference once to a chap in England who built a Go program which reportedly played to 10 kyu (the Nemesis Go programs play to 20 and 15 kyu). The heart of the program was a so-called cellular automaton - a sort of one-layer NN with feedback. Each cell was one location on the board, and 'vacant' cells could take on one of 15 or so states. At each move, the net would cycle about 5 times before reaching a stable state, and picking its move. The chap who wrote it said he doesn't actually understand its rule base - he set it up initially and then tinkered with it until he couldn't improve it any more. If you like, I'll track down the reference. Good luck! Heidi de Wet University of Cape Town, South Africa heidi@ucthpx.uct.ac.za or ..!ddsw1!proxima!ucteeu!heidi ========== From: Barney.Pell@computer-lab.cambridge.ac.uk The following people (certainly the first) have done some work on NNs and GO: % Herbert.Enderton Herbert.Enderton@moriarty.theory.cs.cmu.edu %Howard Landman landman@sun.com I do work on Machine Learning and GO, but using logic and/or probability, not NNs. If your interested, I'd be happy to send a paper to you. Also you should read the newsgroup rec.games.go -- Barney ========== From: "Bruce Reeler: Breeler%uctvax%quagga@uunet.uu.net" Hi Guszti I saw your posting on the Net re Go and NNs. We have a Go boffin here at UCT, and he recommends "Go for beginners" by Kauro (sp.?) Iwamoto. This is THE book on Go. I have played a bit, and it seems a good candidate for a NN. More so than chess, because the patterns in Go are more static, in the sense that when a stone is laid down in Go, it doesn't move. (Except capture, of course). Hope things go well! Where are you, by the way? Cheers Bruce Reeler ========= From: landman@Eng.Sun.COM (Howard A. Landman) In article <1991Feb26.195333.3972@comp.vuw.ac.nz> you write: >I'd appreciate if you could help me find out what the difficulties are, That's easy to explain. Go is PSPACE-hard. In fact, there's purported to be a recent unpublished proof that Go is EXPTIME-complete. That makes it a couple of quantum jumps more difficult than merely NP-complete problems like traveling salesman. >and how programs try to address them. Most use one sort of stupid heuristic or another. Go ahead and try to devise one; you might get lucky and find one that works better than anyone else's. -- Howard A. Landman landman@eng.sun.com -or- sun!landman ========= From: Alexandre Wallyn I tried to post the same question about NNs and chess 3 weeks ago, but I have a lot of difficulties to post news. We told about such a project here at Cap Gemini Innovation. We have 2 good Go players, and I am specialised in neural networks, (and also internationnally rated in Chess). Our project was to try to learn first with a mini-Go and then try to extend it. I believe it has not been already done. I wrote a proposition of such a project (Go or Chess, and Neural Networks), and I can send you, but it is in French. Anyway, I am interested to keep contact with you. If it is possible, we can even set up a collaboration (official between our organisations). But anyway, if your project is unformal, I would be interested to know it and may be exchange ideas. Alexandre WALLYN CAP GEMINI INNOVATION 118, rue de Tocqueville 75017 PARIS wallyn@crp.capsogeti.fr ========== From: landman@Eng.Sun.COM (Howard A. Landman) >papers dealing with the computational complexity of GO Lichtenstein & Sipser, "Go is PSPACE-hard" (don't have the date or journal in front of me but they were posted to the net a couple of months ago) Yedwab, Laura, "On Playing Well In A Sum Of Games", MIT Masters thesis under Ron Rivest, available by sending email to (I think) publications@lcs.mit.edu The EXPTIME-complete result is somewhat startling, and I haven't seen the proof yet, but it apparently relies on complicated multiple ko situations. >I'd rather have the computer work them out Well, no one's really tried Genetic Algorithms yet, so you might have something there. The difficulty for me is that each test takes a couple of hours of human intervention, since I test my algorithms against other people's Go programs, and you have to play all the way through the endgame to weed out bad bugs there (filling in own eyes, etc.). If EVERYONE followed a common protocol, things might be easier. But with programs running on different hardware (IBM-PC, Mac, Sun, H-P, Amiga), it gets a little hairy establishing ANY kind of communication. Howard ========== From: xpoint!landman@uunet.UU.NET (Howard Landman) To: uunet!cleveland.Freenet.Edu!as666@uunet.UU.NET Subject: Re: Poka Date: Tue, 07 Jan >Do you use a neural network for Poka's move choices? No. It's closer to a cellular automaton in spirit, but augmented by a few "global" operations like counting up 1 cells, finding the first one, etc. Howard P.S. However, I have done some NN work for Go. It just hasn't been good enough to include in a competitive program yet.