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

[Don Dailey <drd@xxxxxxxxxxxxxxxxxxxxx>]

> If a  program were deterministic, you  could require the programmer to
> submit his program, and verify after the tournament  that it makes the
> same moves.  But most programs are not deterministic.

And that's the  biggest flaw  in  designing a  protocol.  However,  it
might  not be completely unreasonable,  since a protocol is a protocol
and must  be implemented   as   such,  to   require programs  to    be
deterministic, but  as you imply,  this  might not  be easy  for  many
programs.

I believe you can eliminate  anything in  a  program that could  cause
non-determinstic behavior, without changing the nature of the program,
but the question is, "Is it worth it?."

Here  are a few  sources  of non-determinism I   know of and  possible
solutions:

1. Use of random numbers.  
   Fix: Use psuedo random numbers

2. Use of psuedo random numbers
   Fix:  Publish a starting seed before the game, or before each
         move if necessary.

3. Random computer state.
   Fix:  view this as a bug in your program and initialize all
         state correctly and debug your program!

4. Dynamically adjustable time control.
   Fix:  This could cause your program to time out unpredictably,
         based on game and timing conditions.  This can be solved
	 by publishing "state markers" as part of your move solution.
         A "state marker" is some kind of indicator that tells the
         observers exactly what state the program is in.   For example,
         if your program always thinks exactly 60 seconds and then
         produces its move,  you might perhaps keep a node counter as
         part of the published state, so that you know the move is not
         produced until state marker n is reached, and before state marker
         n+1 is reached.

5. Learning algorithms.  
   Fix:  The problem is that your program might dynamically change
         it's fundamental move selection algorithm after every move,
         based on things learned during the ongoing calcuations.  

         This one, and similar ones are the toughest to handle 
         deterministically.   One possibility is to checksum and 
         publish the starting state before each move, which is 
	 always the general solution to any of these problems.
         However, that leads to the problem of REPRODUCING the
         starting  state, which could be a really tough problem.
         This state could be saved off in case of later disputes,
         and that is a workable solution, but it seems like an
         unusual requirement.