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

[Don Dailey <drd@xxxxxxxxxxxxxxxxxxxxx>]

   From: William Harold Newman <william.newman@xxxxxxxxxxxxxxxxx>

   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.)

I never claimed it was impossible to incorporate non-randomness into a
program,  only  that I  don't  think it  "limits"  a  program.  It was
earlier implied that   determinism  was a limiting    requirement that
prevented sophisticated AI techniques from being used.  

In earlier emails I argued that it  was worth the  time to design your
program to be deterministic.  The whole  thrust of my argument is that
you  don't have  to  weaken your  program in  any   significant way to
accomplish good solid deterministic behavior.

If  it  turns out that  I  am wrong about  this,  it  won't be because
someone could not  use a real time clock.   I'm not forced to use YOUR
exact time management  technique any more than  I  am forced to  use a
true random  number   generator  instead  of a psuedo   random  number
generator just because you say so.

For any useful time management scheme you can  dream up, I can provide
a close deterministic  approximation.   

By the way, even though your email is mostly correct (but not relevant
to my points)  you made a  big error and then  used it to justify your
point which was  not fair.  You talked  about "making a fake record of
the clock running out", but you are not allowed to  wait until AFTER a
move is played and then  make up arbitrary data  and claim it was part
of the  input state.  If your program  is deterministic,  which is our
premise, then the output is defined soley  from the input state, which
cannot be contrived after the output happens.  Your program is allowed
to publish it's input  state as long as  it is published before it has
knowledge   of  the opponents move  (actually   even this  is a little
dangerous if the move is easy to anticipate.)



   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!)

Which is what every one of us has already said.

Essentially, you described  the engineering approach  accurately.

A few people seem to  feel threatened somehow  by  this idea, as  I've
seen some critical,  negative and  dismissive  emails on this.    It's
certainly  not anything worth   taking seriously, it's  just a talking
point.

Don