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

[Don Dailey <drd@xxxxxxxxxxxxxxxxxxxxx>]

The  most important obstactle  is item 1,  getting all the programs to
play deterministically.  Some  programs change their moves after time,
and time can vary.  There are solutions but the programmers must agree
to implement them, and they have to be  implemented correctly.  In the
simplest  case, each program must have  a deterministic mode that they
"guarantee" will play   the  exact same  move,  given  the same  exact
initial  (before the game starts)  settings (and allowing for a random
seed.)  However, this might  defeat programs that use  their opponents
time to do calculatations.  There are solutions to  this too, but they
involve more protocol (yuck!!)

There  is also  the  case for hardware.     My program doesn't run  on
windows, although I know  most do.  But even if  it did, some programs
take advantage   of extra memory,  or  due to hardware   and operating
software bugs   might   even play  slightly  different  on   different
machines.

It  was already  mentioned that  programmers don't  like to send their
execuatables.  They can instead send an  md5 checksum but this doesn't
fully solve  the problem.  In the  case of disputes, the program STILL
has to sent to the organizers.

The only way I see  this working, and  maybe I'm being pessimistic, is
if the programs are required to be 100% deterministic given the intial
program settings and a random seed.  Additionally, the programs should
be  sent ahead of time  to  the organizers  for  verification and  ALL
winning programs should  be  verified whether  a dispute  is raised or
not.

If a program fails verification, is should not be viewed as a cheater,
because there are other reasons why this can happen.  In this case the
loser  could be  required  to pass the   verfication ritual, and if he
succeeds,  he is declared the  winner,  otherwise the original results
stands   (the  better cheater  wins!)   In  any case, the verification
procedure is simply a requirement to claim a win and no one is held at
fault nor is blame assigned.

Why do I think it's important to require all programs (even when there
is  no dispute) to  pass the  verification  process?  Because  it will
avoid all  the hassle  of  accusations and  proofs and disclaimers and
such.  We want to avoid the situation  where a program is suspected of
cheating, and has to "pass a test."   Instead, it is cleaner to simply
view passing the verification procedure  as a  requirement to claim  a
win.

To be honest, I don't think this is  very workable.  Assuming that you
can get everyone to send you their binaries and that they all agree to
create soundly deterministic provable programs, you still would have a
lot  of work involved in running   the verification procedures.  Is it
worth it?

But, I'll keep thinking about the  problem.  We have this same problem
in the  internet chess club but it's  reversed!  You never really know
when you are playing a human, or a computer and  humans very often use
computers for assistance.  I doubt there is a good clean solution.


Don





   I think John Aspinall and I are on the same page here. What we are trying to 
   achieve -- is to use the net to its maximal advantage to minimize the travel 
   of the contestants. All we need to truly verify is "the winners" since even 
   if the losers were spoofing the system it does not matter (it would be great 
   if the program beat a 7-dan human).

   So how do we go about verifying a program was not helped with human 
   intervention?

   1. For tournament purposes don't allow random play. Allow pseudo random play 
   based on an initial seed (to avoid predictability). For verification, the 
   seed is disclosed and the program will play identically.

   2. In order to avoid programming the game "after the fact", a copy must be 
   sent to a trusted party (prior to the tournament) which holds the 
   responsibility for verifying a programs authenticity. This can be as simple 
   as a binary comparison.

   3. The program must then duplicate its play in a controlled environment (for 
   verification) to the satisfaction of the Judges.

   OK, Shoot holes in it....

   Steve


   >From: John Tromp <John.Tromp@xxxxxxxxxxxxxxxxx>
   >Reply-To: computer-go@xxxxxxxxxxxxxxxxx
   >To: computer-go@xxxxxxxxxxxxxxxxx
   >Subject: Re: computer-go: Authenticating the identity of a remote 
   >go-playing computer program
   >Date: Tue, 5 Dec 2000 13:10:47 +0100
   >
   >On Mon, Dec 04, 2000 at 11:10:22PM +0000, Steve Pagliarulo wrote:
   > > We might be able to do this if we have the winners later "prove" it was
   > > their program that made the moves.
   >
   >That's easy: My program is
   >
   >for (;;)
   >   play(random legal move);
   >
   >and the random_number_generator includes such info as cachemisses,
   >disk seek latencies, ... (to make it REALLY random:)
   >
   >More subtle is:
   >
   >for (;;) {
   >   await opponent move;
   >   i = current_time_in_microseconds modulo number_of_legal_moves;
   >   play(i'th legal move);
   >}
   >
   >So, just what kind of proof do you desire?
   >

   _____________________________________________________________________________________
   Get more from the Web.  FREE MSN Explorer download : http://explorer.msn.com