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

[Don Dailey <drd@xxxxxxxxxxxxxxxxxxxxx>]

   From: David Fotland <fotland@xxxxxxxxxxxxxxxxx>

   Any program that tries to use all of the available time will not play
   reproducably.  You can't ensure that the timing and speed of the computer
   during replay are exactly the same as during the original game.

   Some programs use data files from the disk, so they would have to be
   included in 
   the checksum.

   A program that learns from play will have to have learning disabled.

   Go programs are complex, and may suffer from bugs that makes their play
   non-reproducable.

   Many programs have configuration settings that are input by the operator
   before
   the game starts.  These will not be included in the checksum.  If the replay 
   operator makes a mistake in configuring the program, it will not reproduce
   results and be disqualified incorrectly.

   The go programmer has to trust the new tournament organizer and send them
   their best unpublished program.

   None of these are insurmountable.

   David


Every one of these is solvable as you mention, but getting all of this
right would be a great big pain.

In my opinion, a lot of these things are well worth addressing anyway,
whether we care about such a verification  system or not.  I have been
writing game software  for many years  and I have discovered that it's
well worth  the effort to stamp out  any source of  non-determinism in
your  program which means some of  the things  you  mention have to be
covered.  Certainly, your program should not vary because of bugs.  If
I make  a simple change in my  program that only affect the efficiency
of some routine, I  have tests that prove   it plays exactly the  same
under a variety  of positions.   I  can't say enough  about how useful
this property is.  There are parameters that change this, such as hash
table size, learning  algorithms and such, but  I go out  of my way to
identify these things and control them.   I can reproduce a game under
any  situation, except when running  the parallel version of the chess
program.  That's a source of chaos that I don't know how to handle but
if I could, I would!

There  is  no  virtue    whatsover in  not understanding    sources of
non-deterministic play, since  computers are highly deterministic.  If
you find them, you have a bug and your program is going to play weaker
with a very high probability.

Don



   At 09:09 PM 12/5/00, you wrote:
   >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
   >
   >