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

[Matthew John Saffell <saffell@xxxxxxxxxxx>]

Look - here's the point: all bug-free algorithms are deterministic.  That
is, given the same set of inputs it will produce the same output.  It
doesn't matter if you have a random number generator - it is also
deterministic.  Given the algorithm and the random seed, it will always
produce the same sequence. This is DETERMINISTIC.  Sure it produces a
string of pseudo random numbers, and you can create things that behave
stochastically, but given the same start state (All the state including
random seeds etc) the algorithm will do exactly the same thing it did the
first time.  Think of it as "conditionally" deterministic if you want.   

So: A deterministic go program does not need to respond to a given board
position the same way each time it sees it as long as some other part of
its state is different (eg. random seed).  Hence it's behavior appears to
have random qualities, but it is entirely deterministic.  The point is
that if _all_ the state is the same, it should produce the same output.
It it doesn't then there are bugs, or just sloppy programming going on.

Matt


On Sun, 10 Dec 2000, Steve Korfhage wrote:

> 
> 
> >You make it  sound as if avoiding deterministic  behavior is some kind
> >of virtue and  allowing it   allows  you to write  more  sophisticated
> >higher level AI programs.  This is nonsense and has nothing to do with
> >AI.
> 
> I am not portraying any "virtues", Please don't label me.
> 
> 
> >The only reason a computer  based algorithm might be non-deterministic
> >is if you do not, or are not able to  document all it's inputs.
> 
> An algorithm may be deterministic, but it is not necessary that its results 
> are.  If you don't believe this,  check into stochastic methods.  The most 
> common of these is "simulated annealing", which attempts to model a natural 
> random process.  This class of methods, which definitely has something to 
> do with AI, are most commonly used for solving optimization and constraint 
> based problems, and they *intentionally* introduce non-deterministic 
> behavior.  They have been proven to be beneficial for many types of problems.
> 
> Stochastic methods and learning algorithms are the non-deterministic 
> behaviors which I am concerned about eliminating.  These approaches can be 
> successfully used in solving problems with exponential search space, like Go.
> 
> >These inputs  might include flaky hardware or  even  software bugs where you
> >access   uninitialzed    memory.     Some  parallel   algorithms   are
> >non-deterministic,  but only because it's  not possible to predict the
> >state of the  hardware at every given  instance of execution.  Even in
> >this case, it's no virtue, it's an undesirable side affect.
> >
> >I think we all agree that we don't wish  to require all programs to be
> >properly deterministic in this respect, but having said that, I'll bet
> >most are.  Since programs  are  deterministic by nature, you  actually
> >have to program  them  explicity to  change this  behavior.   Or if  a
> >program   is complex  enough  it  will have  enough   bugs to make  it
> >nondeterministic,  which  might mean   it is accessing  un-initialized
> >memory or some other goof like this.
> >
> >Don
> 
> Obviously, programming/design errors are excluded from the definition of 
> non-deterministic behavior for the purpose of this discussion. Like you 
> said, most programs will probably have errors, but this is not intentional. 
> I prefer to leave the implementation open to any method desired, and 
> instead prevent or detect inputs coming from outside the algorithm.
> 
> 
> 
> -----------------------------------------------------------------
> Steve
> s_korfhage@xxxxxxxxxxxxxxxxx
> korfhage@xxxxxxxxxxxxxxxxx
>