Re: computer-go: Authenticating the identity of a remote go-playing computer program

["Bob Myers" <rtm@xxxxxxx>]

I have found this discussion useful and invigorating.  I would like to
summarize the discussion up this point, at the risk of misstating or
overlooking someone's thoughts:

1. We can and should continue to have computer go tournaments where people
congregate in a particular physical location, to meet, talk, and exchange
ideas.  Of course.

However, the availability of a way to authenticate remote computer programs
would still be useful, for tournaments that we did decide to hold on the
net, or, for instance, for net-based preliminaries.

2. Authentication involves two aspects.  a) Is a given computer program who
it claims to be?  b) Is a move that program claims to play actually thought
up by that program?

3. Concerning a), I hope everyone can agree that there are viable ways to
uniquely identify a computer program, omitting issues about the number of
angels that can dance on the head of a pin.  (It is true, of course, as
someone pointed out, that even this requires people to obey protocols, such
as e.g. not revealing a private key -- which applies to any encryption
endeavor.)

4. The problem really is b).  As many posters have pointed out, there would
seem to be absolutely no way to verify that a particular move was in fact
produced by the program in question, as opposed to being input by the famous
7-dan human sitting next to the computer.

One proposal is that the program be required, under appropriate initial
conditions, to prove that it played the original move by reproducing it on
demand, for instance, when being operated by a person trying to arbitrate a
claim of cheating.

There has been useful discussion on how this could be done, and I don't
think anyone is willing to say that it is theoretically impossible to do
this, but as even the people proposing this themselves have noted, it is not
really a practical approach.

So perhaps we can take another tack; I can suggest the direction but don't
know the answer.  Ask the question, "What distinguishes a move played the
human 7-dan from a move played by the computer?".  The answer is that the
computer has gone through a particular algorithmic process to reach its
answer.  That process, in turn, can be characterized by some kind of
signature, or profile, or trace.  For convenience, we will call it a
"trace".  Note that if necessary the trace could be composed of bits of
information harvested at different times during the computation process, or
even harvested on demand by some "tournament director"-type computer.

Mathematically speaking, although I am not a mathematician, I believe that
the trace must have (at least) the following characteristics:

1. It is not possible to produce a post-facto trace claiming to be that for
a particular move when in actuality that move was one input by the human
7-dan.  Otherwise, the program could send in the 7-dan move and a fabricated
trace.

2. It must be possible to verify that a particular trace does in fact
correspond to the move played.  Otherwise, the program could send in the
7-dan move and at a trace for some other move which it actually thought
about.

3. The nature of the trace must be such that it is meaningful and possible
to create it for any arbitrarily architected program, including one running
e.g. on a biocomputer.

4. Possibly it is a requirement that the trace would not reveal secret
information about how the program works.

Although I am not entirely comfortable with the proposal which is about to
follow, and may be revealing my utter ignorance about go programming, I
would suggest that one possible trace is the set, over t1 through tn, of the
top 10 pairs (m,v), where m is a proposed move, and v is its estimated
value.

In other words, and to simplify greatly, at 100ms intervals, the program is
required to produce a list of the top ten moves it is currently considering
and its internal valuation of each.

This approach has the secondary benefit of allowing us to identify program
which are possibly infringing.  If traces for two program are too close to
each other, there may be issues needing to be looked at.

Any further thoughts on this?

Bob Myers
Intelligent Go Foundation
www.intelligentgo.org