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

[William Harold Newman <william.newman@xxxxxxxxxxx>]

Part I: Wherein I begin my exposition by responding to MJS' post (and
controlling my almost uncontrollable impulse to CAPITALIZE words like
TIME and CHEATING and FAKE below:-)

On Sun, Dec 10, 2000 at 10:31:03AM -0800, Matthew John Saffell wrote:
> Look - here's the point: all bug-free algorithms are deterministic.  That
> is, given the same set of inputs it will produce the same output.  It
> doesn't matter if you have a random number generator - it is also
> deterministic.  Given the algorithm and the random seed, it will always
> produce the same sequence. This is DETERMINISTIC.  Sure it produces a
> string of pseudo random numbers, and you can create things that behave
> stochastically, but given the same start state (All the state including
> random seeds etc) the algorithm will do exactly the same thing it did the
> first time.  Think of it as "conditionally" deterministic if you want.   

A modern microprocessor has such a complicated state (especially
including the state of its cache) that unless you go to considerable
trouble to initialize it to a known state, the time spent in a
calculation is not deterministic. And using any typical OS (including
MS Windows, almost any Unix, or the Mac OS) makes the calculation time
even less deterministic, because of the way that the OS implements
multitasking, virtual memory, and other things.

If a program checks the wall clock to determine how much calculation
to do, it will still be deterministic in the sense you refer to above.
That kind of determinism is useful for some purposes (like debugging).
However, it's not enough to prevent cheating. For example, I can write
a program which cycles through the most plausible moves, changing its
mind every millisecond or so. When a move comes up which I like, I
make a fake record of the clock running out. Voila.

If you have a proposal for preventing this without making it
impossible for programs to use real-time clocks for time management,
bring it on. Or you can try to forbid the use of real-time clocks for
time management, but I'm afraid that many programmers would be very
unhappy with this. (I would certainly be unhappy with it.)

> So: A deterministic go program does not need to respond to a given board
> position the same way each time it sees it as long as some other part of
> its state is different (eg. random seed).  Hence it's behavior appears to
> have random qualities, but it is entirely deterministic.  The point is
> that if _all_ the state is the same, it should produce the same output.
> It it doesn't then there are bugs, or just sloppy programming going on.

Or there are real-world inputs, like the real-time clock.


Part II: Wherein I reply to the accumulated discussion on this thread

I see at least three ways to go after the problem of human Go players
providing special input to programs in order to make the programs
appear to play better:

First, what lots of people have suggested:
  For important tournaments, require the computers to be physically
  present and take Amazing-Randi-like precautions to prevent cheating.

Second, a proposal similar to someone's idea of running too many
games for humans to help with them:
  For informal internet competitions like the Computer Go ladder
  <http://www.cgl.ucsf.edu/go/ladder.html>, start by not worrying about
  it until it becomes a problem. Then, when and if human cheating
  becomes a problem, deal with it by playing games with such short time
  controls that the human can't compete. (This is only marginally
  practical today, but it should become progressively easier with time
  as computer and network performance improve.)

Third, the "there's an engineering solution to every problem" approach:
  If you want to do something which might be in some sense
  straightforward but which is probably nontrivial enough to be
  well worth publishing, then
  (a) Write a Go program which plays a good enough game of Go to 
      do respectably well in a serious tournament, despite (i)
      being strongly deterministic (i.e. no real-time input) and
      (ii) being specified in a language with sufficiently nice formal
      properties that you can do the zero-knowledge proof below.
  (b) Before each tournament game, submit a cryptographically strong
      hash of the program and its starting state.
  (c) After the tournament, participate in a zero-knowledge proof
      that your program has the given hash and produces the given
      output.
  But until you've demonstrated the practicality of doing this, no
  stampede of others doing it is likely to start. (And even once
  you've demonstrated that this can be done, don't hold your breath
  waiting for the stampede to start!)

-- 
William Harold Newman <william.newman@xxxxxxxxxxxxxxxxx>
software consultant
PGP key fingerprint 85 CE 1C BA 79 8D 51 8C  B9 25 FB EE E0 C3 E5 7C