Talk:Computer Go

From Wikipedia, the free encyclopedia

This article is within the scope of WikiProject Go, a collaborative effort to improve Wikipedia's coverage of the game of Go. If you would like to participate, you can visit the project page, where you can join the project and see a list of open tasks.
??? This article has not yet received a rating on the quality scale.
??? This article has not yet received a rating on the importance scale.


Use the + tab at top to add new comments at the end.

Contents

[edit] Initial Comments

I think this page should include a reference to the important free Go-playing program GNU Go.

In the absence of Wikipedia pages describing Go++, Many Faces of Go and GNU Go, why not provide external links to pages describing these programs? 13:31, 27 May 2003 210.8.232.5

Done. :-) Evercat 13:41 27 May 2003 (UTC)

Wow! That was fast. I'm impressed. 13:48, 27 May 2003 210.8.232.5

According to http://www.gnu.org/software/gnugo/gnugo.html, "GNU Go won the 19x19 tournament at the Computer Olympiad 2003 after winning all its 10 games!" Their site also seems to think that GNU Go is at least as strong as Many Faces. Paullusmagnus 23:16, 21 Jan 2004 (UTC)

Does it say that about MF? Anyway, I think it's true that GNU Go is quite decent these days, though I'm not sure it's quite overtaken MF or Go++. Evercat 01:22, 22 Jan 2004 (UTC)
Just an update. The 2004 Computer Olympiad was last month, and the winner for both 19X19 and 9X9 Go was Go Intellect. Many Faces of Go came in second in 19X19 after losing a play-off to Go Intellect. GNU Go took second in 9X9 but came in second to last in 19X19. You can see the complete results here: http://www.cs.unimaas.nl/olympiad2004/results.html
Greyweather 01:46, 23 Aug 2004 (UTC)

I read this "The strongest programs are as weak as players that have played the game for mere months, and are no match to a seasoned player." and was quite embarrassed. There are some 12k computer programs out there and I'm only 15k after playing for 3 years! I may not be a very good player but there are man people like me. 18:44, 4 September 2005 202.122.139.99

"Fortress" positions should be better explained. Or explained at all. I think they are positions where, despite a material advantage, winning is not possible due to the rules of play. I.e., the position is constrained somehow to nullify the material advantage. However, this is my guess at what the term means and a google search reveals articles with other different definitions that are less general, usually with specific examples. Someone who works with "fortress" positions in computer opponent programs should perhaps edit this. --Peterius 04:48, 9 October 2007 (UTC)

To the two explanations of why go is hard for computers, 1) many legal moves and 2) no eval. function, I think you should add 3) long game. If a program is computing a variation tree it's not only the breadth that makes it difficult, but the length. Things like playing for good shape in the opening can't be evaluated by going through variations, since their benefit will come 200 moves later in a fight or in having priveledge to a good endgame move. 6 July 2005 15:03 (UTC)

I don't really understand this line. "At the same time, even beginner go players are able to look about 60 moves ahead in some positions like shicho (ladder), while even a grandmaster in chess is able to look only about 10 moves ahead." I presume they mean that when playing chess, chess grandmasters only need to look 10 moves ahead, right? The way it's phrased now it sounds like they mean that chess grandmasters are so used to the style of their own game that in Go, they're much more limited than beginner Go players. The external link didn't clarify either. Weefz 20:01, 17 December 2005 (UTC)

[edit] Merge with Computer go programming? [Done]

It seems to me that this article and Computer go programming could happily live in one place (albeit, in a well-organized fashion). As an enthusiast in this field, I find myself paging between both articles to get "the whole story". Certainly the section headers of this article (Difficulties, The future, New approaches to the problem) refer to programming. Likewise, I think several of the sections in the other article (Philosophies, Problems that arise, etc.) now or soon will overlap with content here as the articles expand. Or not; just a thought. Thoughts? --Ds13 23:05, 5 January 2006 (UTC)

There does appear to be a difference in tone between the two articles. The Computer Go section could be of interest to an intelligent layman, or someone who may be interested in buying a Go program. The Computer Go programming section is much more technical and of interest to someone who is thinking of writing a Go program. I am not against this distinction, as it allows the programming section to tackle the real nitty-gritty of the technical issues. At the moment, I don't feel strongly about this, but as this articles get bigger and better, I suspect that having two articles will become more useful than now. Stephen B Streater 06:51, 1 March 2006 (UTC)

[edit] Propose to merge 2 articles together

I would like to merge both computer Go & computer Go programming.
Reasons are as follows:

  • the topics are very similar (Wikipedia policy says 2 similar topics should be merged!)
  • there're duplication between 2 articles
  • information on one article can enrich the contents on another
  • since they are highly relevant, readers are interested to read both at the same time.
  • it provides better integration if 2 articles join together
  • no linking confusion - some link to computer Go, some link to computer Go programming

Feel free to express your opinions! Thanks a lot! --Wai Wai 16:36, 17 July 2006 (UTC)

I agree with a merge. The current state is confusing and overlaps. "Computer Go" is probably the best name for the merged article, but even the section headings there already overlap with each other. Good luck and thanks for taking this on... --Ds13 18:48, 20 July 2006 (UT== Other links [Done]==

I suggest an Other links section:

  • [Ideosphere] gives current estimate of whether a Go program will be best player in the world
  • [London Open] is a short mobile video blog of the latest London Open Go Tournament

Stephen B Streater 10:53, 23 February 2006 (UTC)

Section added. Stephen B Streater 06:34, 1 March 2006 (UTC)

[edit] More Go solved

I believe a friend showed that 5x5 is a first player win even if black cannot start in the centre. Can anyone verify this independently? Stephen B Streater 21:38, 8 April 2006 (UTC)

I believe this is true. You should read over Erik van der Werf's page on his solution to 5x5 Go. There are some illustrations that show black winning even though they did not play center. Ceran 19:50, 3 March 2007 (UTC)

[edit] History?

It might be nice to have a history section, mentioning computer go in the context of other AI research and computer chess programming. Also worth mentioning: the influence of the Ing prize, tournament history, and some of the milestones achieved. --IanOsgood 19:47, 18 July 2006 (UTC)

Got bored and started filling in a History section under competitions. --IanOsgood 22:22, 23 August 2006 (UTC)

[edit] Who is "Muller"?

This article has cites for "Muller", but I don't see it listed anywhere but with inline cites. --Falcorian (talk) 04:46, 24 July 2006 (UTC)

I don't know for certain, but it is likely to be Martin Müller, a computer go researcher, author of Go Explorer. --IanOsgood 20:28, 28 July 2006 (UTC)

Whatever of his writings is being referenced needs to be put in the article then. Any idea how to find it? --Falcorian (talk) 21:12, 28 July 2006 (UTC)
It apparently is already there (the Artificial Intelligence 134 article). I went ahead and turned them into footnotes. --IanOsgood 20:31, 23 August 2006 (UTC)

[edit] Go

I have multiple Go books, and it is sometimes capitalised. I'll include some examples in a minute... Stephen B Streater 15:47, 25 July 2006 (UTC)

Cites for capital G in Go:

Cites for small g:

  • Appreciating Famous Games (1977) ISBN 4-87187-025-1
  • The 1971 Hononbo Tournament (1972) ISBN 4-906574-07-6
  • Elementary Go Series, Vol. 5: Attack and Defense (1980) ISBN 4-87287-14-9
  • Elementary Go Series, Vol. 4: Life and Death (1975) ISBN 4-8906574-013-0
  • Elementary Go Series, Vol. 3: Tesuji (1975) ISBN 4-87187-12-4
  • Elementary Go Series, Vol. 1: In the Beginning (1973) ISBN 4-87187-010-4
  • Graded Go Problems for Beginners Vol. 3: Intermediate Problems (1985) ISBN 4-906574-48-3
  • The Nihon Ki-in Handbook of Proverbs Vol. 1 (1998) ISBN 1-889554-24-3

So my random sample of books seems to prefer a small g after all. I'd take this over to Go so we can get a consensus for all the related articles and see if we can make them consistent. I think last time it was discussed, Go was preferred. Stephen B Streater 16:05, 25 July 2006 (UTC)

Yes, you are correct. Capital "Go" is prefered. It is a better convention really. Reasons have been stated in Talk:Go. Sensei's Library uses capital "Go" too --Wai Wai 17:03, 25 July 2006 (UTC).

[edit] Progressive complexity

The new section on progressive complexity was interesting but not true:

  • Chess gets more complex as the pieces develop, and only then gets easier as the pieces are removed
  • The number of legal moves in Go generally decreases as the game proceeds
  • The number of plausible Go moves also decreases at the end - until pass is the only realistic option for both players and the game ends.
  • Fewer moves or pieces doesn't make the position simpler if computers/people are expected to look more moves ahead to compensate.

Stephen B Streater 20:08, 7 August 2006 (UTC)

[edit] Language choice

I am a fan of java and all but there seems to be an off topic rant hyping up java in the language choice section... this should be removed. --Dave1g 07:53, 24 August 2006 (UTC)

Do you oppose all mention of Java, or just the focus on memory management and other internal language issues? If I was writing this section, I would focus on the accessibility to the end user. Stephen B Streater 08:20, 24 August 2006 (UTC)

As a programmer I have to say that this section better be removed. There is no information in it that is go-specific . With little changes it could be standing on the Computer_chess page. Rewrite it with more focus on go-content or remove it.

Bhaak 09:51, 24 August 2006 (UTC)

Concur. In fact, the whole section could go, considering there is already a Wikibook covering these kind of computer Go details. --IanOsgood 16:09, 24 August 2006 (UTC)

Does anyone have any objection to removing this section? --ZincBelief 15:14, 27 November 2006 (UTC)

I agree with removing anything not notably specific to computer Go. That removes most of it. However, I think maintaining a very factual, perhaps tabular, list of notable Go programs and their implementation language(s) could be valuable. No commentary or pros and cons or speculation necessary; just the facts. I think that would be encyclopedic. --Ds13 06:37, 28 November 2006 (UTC)
Yes I could see the value of this. There is a lot of inteesting history along that path. Perhaps a seperate article might be needed though? I will mention this on wikipedia Go project.--ZincBelief 10:58, 28 November 2006 (UTC)

Consensus seems to be that this in depth discussion of computer languages should not be in the go article, therefore I am removing it. --Dave1g 10:29, 17 January 2007 (UTC)

[edit] Endgame

What on earth is the following paragraph trying to say? Am I missing something, or is it incomprehensible.

In Go, to an application of the kind of game analysis pioneered by John H. Conway, who invented surreal numbers to analyze games and Go endgames in particular, an idea much further developed in application to Go by Elwyn R. Berlekamp and David Wolfe. It is outlined in their book, Mathematical Go (ISBN 1-56881-032-6). While not of general utility in most play, it greatly aids the analysis of certain classes of positions.--ZincBelief 13:34, 27 November 2006 (UTC)

Somebody has now made this paragraph comprehensible--ZincBelief 15:43, 6 February 2007 (UTC)

[edit] Remove section: 'Perhaps programs aren't really so poor'

Is this based on anything? This section at least needs a citation to someone credible discussing this theory. A citation is also needed for the comment about computer GO being superior at ishi-no-shita moves (ishi-no-shita is, I believe, just 'ko-battle' in English). williameis 15:37, 11 October 2007 (UTC)

This would benefit from a citation, yes. But so would much more of the article. Ishi-no-shita literally means 'under-the-stones'. It refers to situations where stones are captured and the points vacated are then played on again. This is something entirely different from ko. HermanHiddema 20:18, 11 October 2007 (UTC)
This view is held by David Fotland, though I can't for the moment find an article in which he states it. I can provide an example of an ishi-no-shita position which illustrates the point (actually, any ishi-no-shita position would do); but I feel this would be excessive in the context. There's an example at [1] but I can't cite that, I wrote it myself. -- Maproom (talk) 16:51, 16 November 2007 (UTC)
Interesting position! There are actually two possible lines of play there. The simpler one involves ishi-no-shita in the upper left, the more complex starts with a move just under the center point, and may involve ko. But anyway, it would certainly be a good example of how a kyu-level program finds what may be considered a dan-level sequence when ishi-no-shita is involved. HermanHiddema (talk) 15:00, 17 November 2007 (UTC)
I can't find where it was that David Fotland expressed this view; in fact I can now find very little of his writings about Go on the web. For the "OR" claim - certainly, if you read articles about computer Go in non-specialist journals, you won't find this view anywhere. Not will you find it in specialist journals, they are about programming techniques, and it wouldn't be relevant there. But I think the view stated in this section is not unusual among experienced Go programmers. Perhaps someone could ask a couple of such programmers? I would do so myself, but I am (or may be thought to be) biassed. Maproom (talk) 10:04, 17 November 2007 (UTC)
The section in question has actually been removed, but could be reinstated. However, it would probably be more productive if much of this article was rewritten, with proper sourcing. HermanHiddema (talk) 15:00, 17 November 2007 (UTC)

The section (which I created) hasn't been removed, it has been there all along. As for the request for an example of an ishi-no-shita position that illustrates the point: there's another one at [2]. But I'm not going to cite it, as I wrote it myself, around four years ago. (I am not longer connected with the Intelligent Go Foundation.) Maproom (talk) 15:46, 29 February 2008 (UTC)

[edit] Obstacles to high-level performance

I added a

 This section needs additional citations for verification.
Please help improve this article by adding reliable references. Unsourced material may be challenged and removed. (October 2007)

tag to this section. A number of subsections have no references. This is a topic for which there should be plenty of AI papers to reference.

In particular, the "Maybe computer performance isn't so poor" section smacks of OR. This section screams out to be referenced with a citation to a reliable source.

--Richard 23:39, 12 October 2007 (UTC)

[edit] Can you really get that far that quick?

"Currently, even average players can beat the best Go programs (after about 6 months of dedicated training)."

The best Go programs on KGS are rated between 1 and 3 kyu. Can just anyone get that good in six months? I've looked at some match transcripts with high-ranked players, and they vary between "wow, this bot plays really strong!" and "This program is completely idiotic!". A great deal of the latter reaction may be due to how the Monte Carlo algorithms deal with a game they think they will lose - they choose the moves with the highest uncertainty.

Go programs have progressed enough that it's time to let go of the patronizing tone. Only six months of dedicated training, huh?

Vintermann (talk) 22:35, 8 December 2007 (UTC)

This quote may be old, perhaps predating the succes of UCT Monte Carlo programs, please feel free to fix it. The current wording in the main Go article is: ...the best Go programs only manage to reach an average amateur level. On the small 9×9 board, the computer fares better, and some programs have reached a strong amateur level. Human players generally achieve an average amateur level by studying and playing regularly for a few years
In the section on ranks and ratings average amateur is roughly equaled to SDK (single digit kyu), and strong amateur is roughly dan level. (This will always be "roughly" until there is a unified grading system that is consistent around the world).
On a further note, I've seen talented players reach 1 kyu in about a year. Talented children may reach that even quicker. Generally however, it will take a player several years to get there, so 6 months of dedicated training is definitely an overstatement. In 6 months (dedicated) many players can reach 7-10 kyu, so the statement is more appropriate when applied to pre monte carlo programs (eg: GnuGo is estimated at 8-9 kyu) HermanHiddema (talk) 23:15, 8 December 2007 (UTC)

[edit] Citation?

"these crushing defeats were due to successful exploitation of known weaknesses in the programs.[citation needed]"

An article about this is cited on Jean-loup's Go page, the link to the actual article [3] is broken as I write this. Maproom (talk) 12:34, 21 December 2007 (UTC)

Thanks, I didn't doubt this to be true myself, but I believed it needed a reference for others.--ZincBelief (talk) 15:27, 21 December 2007 (UTC)

[edit] Wikipedia is not a forum for speculation and philosophizing.

The only choice a program needs to make is where to place its next stone.

This isn't even remotely true; it must first decide whether to place a next stone. Otherwise it can never recognize when a game has ended and it will merrily fill the board with stones, in some order that it considers "best". --75.63.48.18 (talk) 06:52, 28 January 2008 (UTC)

Please take your trolling elsewhere. HermanHiddema (talk) 11:08, 28 January 2008 (UTC)
I think what Herman means, is that "whether" to place a stone is a trivial exception to "where to place a stone"; in fact, passing (which happens usually no more than twice in a game) could be considered as placing the stone vacuously (e.g., back in the bowl). So the "not remotely true" comment is incorrect, making the comment sound more like splitting hairs than advancing the quality of the article. Pete St.John (talk) 20:14, 30 January 2008 (UTC)
Not exactly, I was in fact referring to the internet practice of trolling. As you said, "not remotely true" is incorrect. I would go further and call it a "gross overstatement". Combining this with the usage of the foul language in the title and with a bit of research into other contributions made by the same user on wikipedia, has led me to conclude that his comment was merely an attempt at trolling, not an attempt at improving the article. HermanHiddema (talk) 13:21, 31 January 2008 (UTC)

[edit] The meme that Go is harder than Chess because Go programs are weak

Consider this introductory line from the article:

  • Go has long been considered a difficult challenge in the field of AI and has not yielded as easily as Chess. The first Go program was written by Albert Zobrist in 1968...

Certainly Go is a difficult challenge in AI. However, the first chess machine was built in the forties (I'm thinking of von Neuman's machine, which played with limited pieces on a smaller board). Chess was used as a model for AI research from the very beginning of modern electronic computing. So part of the reason that Go programs don't play (nearly!) as well as Chess programs, is the huge head start chess programming got. Botvinnik, world champion and a SciD in EE, worked on computer chess after the war. Ken Thompson, the guy who wrote Unix, built a chess machine in the late 70's. That's very high level attention from top-notch people. When Sony spends the money that IBM did then you can call me a fool :-) but part of the reason Go is behind, is that it just started later and didn't have the position chess had as a model; AI referenced chess as a standard, the way psychologists and physiologists reference white mice. Pete St.John (talk) 20:14, 30 January 2008 (UTC)

A "huge head start", from the days when a powerful computer ran at 1MHz and had 64Kb of memory, may not be that significant. Maproom (talk) 15:51, 29 February 2008 (UTC)

[edit] 9x9 win against a pro

I don't know if this is worth adding to the article -
In April 2008, the Go-playing program MoGo, running on a cluster, won an even 9x9 game against 5-dan pro Catalin Taranu [4]. (A 19x19 win against a pro is still a long way off, imho.) Maproom (talk) 13:58, 18 April 2008 (UTC)

Maybe he had a bad day (sick?). Before you go tooting MoGo's horn, this experiment should be replicated several times. What is its winning percentage against professional players? JRSpriggs (talk) 15:39, 18 April 2008 (UTC)

He showed no signs of being sick, and made no complaint. He went on to play against it again.

This was a three-game series, the pro won the other two games, though in the first game MoGo lost its connection with the cluster and played most of the game on an ordinary PC.

The only other 9x9 games I know of between MoGo and a pro were on KGS last June, against Guo Juan 5p. It won 12 games, she won 7. But it is not clear that she was trying to win, she may just have been experimenting with it. Whereas the series against Catalin Taranu was widely publicised and had a large audience, he was definitely trying to win. Maproom (talk) 16:44, 18 April 2008 (UTC)

I heard that the games against Guo Juan were with Guo taking white without komi? HermanHiddema (talk) 19:22, 18 April 2008 (UTC)
Sorry, you are right. Most of these games were played with only half a point komi. Of the three played with 7.5 points komi, Guo Juan won two, MoGo won one. (For anyone who wants to check, look for the 9x9 games on this page: [5].) Maproom (talk) 10:04, 19 April 2008 (UTC)

[edit] "People think"

I see that Kibiusa has deleted the section "Why Humans are successful at Go", with the reasons "weasel words ("people think"); POV; original research".

I don't accept the "weasel words" argument at all. Yes, those words can be used as weasel words, but they aren't in this case. There is indeed a widespread belief that computers are bad at Go compared with humans, as expressed in the article itself by the section heading (of which this was a subsection) "Obstacles to high level performance".

The POV/Original research argument carries more weight. But as David Fotland has expressed this view, I think it should be accepted. I wish I could find where he stated it; his web pages about Go programming no longer exist. Maproom (talk) 09:16, 11 May 2008 (UTC)