Now that a chess program has beaten the World Chess Champion, admittedly in a one-off match, attention is increasingly turning to Go programming. The tree-searching and evaluation techniques which have been so successful with chess have had relatively little success when applied to Go, and more interesting techniques, perhaps worthy of the description "Artificial Intelligence", are needed.

Unfortunately, in the last two years, the Go programming world has been distracted by accusations of plagiarism. Evidence has been provided showing that one of the leading programs contains code copied without permission from one of its leading rivals. However no action has been taken in response to this evidence, and the plagiarised program continues to compete in international events.

A program that plays chess well has long been a goal of computer programmers. This goal was in a sense attained in 1997, when IBM's Deep Blue beat the World Chess Champion, Garry Kasparov, with two wins, three draws and one loss in a six-game match.

It is proving far harder to write a good Go program than a good chess program. The best Go programs are a long way short of being able to beat a moderate amateur player, let alone a top professional. The tree-searching techniques that work for chess do not work well for Go, so a successful Go program may need to use more sophisticated techniques.

The reason most often proposed for Go being harder to program than chess is the size of the tree-branching factor: in a chess position, a player typically has about 30 possibly moves, but in Go a player typically has 300 moves to consider. This makes the tree-searching slower by a factor much greater than 10: for an n-move lookahead, the tree is bigger by a factor 10ⁿ. However, shogi (Japanese chess) can have a similar branching factor. A player can have over 300 possible moves in a shogi position, yet there are programs that play shogi fairly well - amateur 4-dan, according to one site.

A more plausible reason for the difficulty of Go programming is that there is no easy method of evaluating a position. In chess, if you look eight moves ahead and find that you have won a knight for a pawn, that is almost certainly a good thing to have done. But in Go you can look eight moves ahead and find that you have made a secure group while your opponent has made some "thickness". Which is worth more, the group or the thickness? Does it depend on the surrounding positions? Do you have a way of playing that will annull the thickness?

There is plenty of motivation to write a good Go program. The best programs are sold commercially to Go players, particularly in Japan, where the total market is worth US $5,000,000. Also, the Ing Chang-Ki Weiqi Educational Foundation ("the Ing Foundation") has endowed a prize fund which will pay 40,000,000 Taiwanese dollars, currently worth about US $1,250,000, to a program that proves itself able to beat trainee professional Go players.

Since the mid-eighties, there has been at least one international computer Go tournament each year. These are tournaments in which computer programs play Go against each other, with time limits, as in a normal human Go tournament.

The annual Ing Cup, sponsored by the Taiwanese Ing Foundation, has been held since 1986; and the annual FOST Cup, sponsored by the Japanese Foundation for the Fusion of Science and Technology, has been held sice 1995. Each year most of the best programs have competed in these events, and the results are listed on pages maintained by the British Go Association, by Michael Reiss and by David Fotland.

From 1991, one of the leading competitors in these events was Handtalk, written by Professor Chen Zhixing, in Guangzhou, China. Handtalk was the winner of six consecutive tournaments: FOST 1995, Ing 1995, FOST 1996, Ing 1996, FOST 1997 and Ing 1997. It was an impressively fast, and small, program, written in assembler. The 1995 version was only 104K in size (including the code to play a rather irritating tune through the PC speaker). In the course of these six top-level tournaments, Handtalk won forty-four games and lost two, an impressive performance.

In 1998 Professor Chen rewrote Handtalk as a new program, which he called Goemate. Goemate used many of the same ideas and data structures as Handtalk, but was rewritten, more cleanly, from scratch. His decision to rewrite his program was perhaps unfortunate, as Goemate did not play as well as Handtalk. This poorer performance of a rewritten program is a common experience among programmers, indeed it seems to be universal among Go programmers who have rewritten their programs from scratch. Professor Chen has gradually been improving the performance of Goemate, and it now plays better than Handtalk did.

In the 1998 FOST tournament, Goemate was placed third. Both of the programs which were placed ahead of it were relative newcomers, having first competed in 1997.

Following this tournament, Professor Chen became suspicious of these two new programs. His suspicions were first raised when in certain positions they played similar, bad, moves to an old version of his own Handtalk.

However, such evidence is only a suggestion, it is far from conclusive. It was significant because it led Professor Chen to make more detailed investigations.

After making detailed investigations of these two programs, Professor Chen reported his findings to the organisers of the 1998 FOST tournament. These findings are reproduced on a site maintained by Professor Chen.

The organisers of the FOST tournament considered Professor Chen's claims, and made an official announcement about it. As far as the allegations against Silver Igo were concerned, this statement left a lot to be desired: all the parties concerned were unhappy about this outcome. However, FOST had no experience in dealing with such allegations, and was in a difficult position.

While Professor Chen was making his investigations, programs were being entered for the 1998 Ing tournament. The programs entered included Goemate and the two programs which Professor Chen was investigating. When he had evidence that these two programs were plagiarised, he sent it to the organiser of the Ing tournament. The organiser examined this evidence, decided that it should be considered seriously, and raised the matter with the people who had entered these two programs for the Ing tournament.

One of them denied plagiarism, but withdrew his program for technical reasons. This program has not entered any computer Go tournament since then.

However it proved very difficult to contact the authors of Silver Igo. They are in North Korea, and the regime of that country makes it almost impossible to contact any North Korean citizen from the rest of the world. The most effective route of communicating with them is probably via the company Silver Star which distributes versions of their program in Japan.

Although they had announced their intention of entering the Ing tournament, the authors of Silver Igo did not send it to England before the deadline which had been set for all entrants, so it did not compete.

Professor Chen's evidence relating to Silver Igo was examined by an expert in games programming and in assembly code. This expert stated:

"Assuming that the silver.exe does contain the code bytes that Chen reports (I have no reason to doubt it), then I could say: Chen has supplied convincing evidence that silver.exe contains code in common with EHT that in my opinion is (a) inserted as "asm" and not compiled from C/C++ source, and (b) not credible as an independent invention."

Perhaps as a response to FOST's inconclusive handling of the allegation of Silver Igo's plagiarism , a new international computer Go tournament, the CGF tournament, was set up. One of its stated objectives was "to solve the problem of plagiarism". This tournament was held in July 1999. In this tournament, Goemate was placed third and Silver Igo, now called KCC Igo, was placed seventh. After it was over, Professor Chen reported to the organisers that he believed that KCC Igo was plagiarised from his Handtalk, and provided evidence. The organisers began an investigation of this evidence, and abandoned it without reaching a conclusion.

In the 1999 FOST tournament, KCC Igo was placed first and Goemate seventh. Dr. Michael Reiss, the author of Go4++, one of the programs taking part, reported to the organisers that he believed that KCC Igo was plagiarised from Handtalk. They rejected this, as he had not provided evidence himself, but had merely referred to the evidence of Professor Chen. Later Professor Chen made a similar report, and provided evidence. The organisers began an investigation of this evidence, which is ongoing.

In the 1999 Ing tournament, Goemate was placed second and KCC Igo third. In previous tournaments, KCC Igo had been operated by an employee of Silver Star Japan, but in Ing 1999, the KCC Igo programmers themselves took part.

Professor Chen reported to the organisers that he believed that KCC Igo was plagiarised from his Handtalk, and provided evidence. The organisers some of those present to set up a committee to investigate and report on the evidence. At the time of writing (December 1999) this committee has not yet met.

• In September 1999, Professor Chen provided further evidence of plagiarism, in the 1999 version of KCC Igo.



• Silver Igo deny all accusations of plagiarism, in a reply given in November 1999.



• In December 1999, another leading Go programmer made a statement that he believes that KCC Igo is definitely plagiarised from Handtalk.



• In December 1999, Professor Chen provided evidence that the most recent commercially available version of KCC Igo, sold in Japan as Ginsei Igo, is not only plagiarised from Handtalk, but now contains various measures whose only purpose is to make it more difficult to prove this, by various anti-tracing devices.

There can be no doubt that the programmers of KCC Igo are competent and very intelligent programmers. Therefore it is puzzling why they should persist in plagiarism, and in attempts to conceal it, when they could write their own program from scratch. Quite apart from considerations of honesty, it is far easier to maintain and modify one's own program than one written by someone else, particularly when one does not understand how that program works.

All I can suggest is that Professor Chen's Handtalk incorporated some brilliant new ideas, which the North Korean programmers have not yet been able to understand.

If Professor Chen's accusations are true, it is possible that the authors and publishers of KCC Igo are in breach of copyright law. Indeed, it is possible that Professor Chen will sue them in a Japanese court. Fortunately, this is not a point which concerns organisers of computer Go tournaments: they are not experts in copyright law, and do not have the funds to employ such an expert.

The reason that Professor Chen has made his reports to the organisers of these events is that he believes that KCC Igo is in contravention of the rules of the events. This should be much simpler to judge than a question of international copyright law. The rules of these tournaments include:

CGF:

"Any unfair practice, such as duplicating a program developed by someone else, disqualifies the participant."

"A participating program may not be a copy, modified or not, of another participant's program. Such entries will be disqualified and prizes will be forfeit."

As things stand, the programmers of KCC Igo have been repeatedly accused of plagiarism. Insofar as these claims have been officially investigated, they have been found to be true. Yet no public statement has been made denouncing them. Nor has any public statement been made denying the validity of these claims.

Many people find this state of affairs unsatisfactory. Various reasons have been suggested to explain this inaction. These reasons are listed below. These are all conjectures, and may well be mistaken.

• Lack of Resources
  
  To make a full investigation of all Professor Chen's claims would require the employment of an expert for several weeks. The cost of this would go well beyond the normal budget of a computer Go tournament.



• Cultural differences
  
  The events in which KCC Igo has been able to compete without penalty have all been in China and Japan. Politeness, and respect for one's rivals, are more important in the cultures of these countries than they are in Europe and North America.



• Threat of legal Action
  
  If anyone makes a public statement critical of KCC Igo, there is a risk that they will be sued for libel by the distributors of its commercial versions, Silver Star Japan. However clear it is that their statement is justified, the legal defense will be expensive, and again would go well beyond the normal budget of a computer Go tournament.

The next international computer Go event will be at the Mind Sports Olympiad, in August 2000. We have already stated our policy regarding plagiarism:

MSO:

"We insist that all participants have their source code available for scrutiny... We will allow people to enter and then judge any claims when they arrive in London. Programs only play if a member of the programming team is present."

"We hope that this policy will be more conclusive than the methods used by other organisers of computer Go tournaments."

- Ray Keene