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

[Don Wagner <don.wagner@xxxxxxxxxx>]

I don't think that steps 1 and 2 are to difficult, the dificult part is in
the third criteria.  If I have a program with good time management, then I
may be checking the time every so often to see if I can keep thinking, or
need to return a move.  If I have some code like

if (TimeLeft > 500)
   EvaluteFurther()
else 
   ReturnMove()

if when plying the original game, the TimeLeft = 501 and due to an extra
interrupt in the verification, the TimLeft = 500, then I could potentially
have the game move differently.  One remedy is when I say what my move is, I
can also give some state information which can say how many time slices I
used. This would also be usefull when debugging my program.
 E.G.

TimeSlices=0
if (TimeLeft > 500){
   ++ TimeSlices	
   EvaluteFurther()
else 
   ReturnMove( TimeSlices)

of course, then I can also use this state information to cheat :^(   e.g.
MyState= 2000 + col*100 + row
which would be incredibly easy to reduplicate the move.


-----Original Message-----
From: Steve Pagliarulo [mailto:s_pagliarulo@xxxxxxxxxxxxxxxxx]
Sent: Tuesday, December 05, 2000 1:10 PM
To: computer-go@xxxxxxxxxxxxxxxxx
Subject: Re: computer-go: Authenticating the identity of a remote
go-playing computer program


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