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

[Don Dailey <drd@xxxxxxxxxxxxxxxxxxxxx>]

Yes,  I see this as a  problem with a theoretical  solution, but not a
very practical one.

But I   think what  is wanted is   a way  to implement  a verification
protocol  that allows you  to play a  game over  the internet and KNOW
that each  move came  from the claimed  source, without   requiring an
exchange of software, similar to the way  ssh, pgp or other encryption
protocols work.  This doesn't appear to be possible.

Don


   From: "Steve Pagliarulo" <s_pagliarulo@xxxxxxxxxxxxxxxxx>

   The 2 problems you mention, pondering and time-limited play, could probably 
   be simulated if the previously played games are recorded with the moves 
   time-stamped. This would allow an opponent simulator to be written which 
   could replay the moves almost exactly and even verify the response of the 
   program we are testing. Of course the original platform needs to be 
   replicated also...

   Mind you, this is all theory. I agree that this somehow does not seem 
   practical. In fact, this is quite silly. If all you want to achieve is to 
   minimize the travel of contestants, it would be easier to send all the 
   programs to a trusted party (the tournament operators themselves probably) 
   and have them go at it… Let the programmers stay home.

   Steve


   >From: Don Dailey <drd@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 17:33:05 -0500 (EST)
   >
   >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
   >