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

[Don Dailey <drd@xxxxxxxxxxxxxxxxxxxxx>]

> 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.

I know all about these technologies, I've used simulated annealing and
GA's to experiment with my evaluation functions.  But if it comes from
a computer it's  still deterministic.  The  key point is  that you are
"simulating" random systems, not  actually creating them.  Even though
it's possible to  actually create  truly  random state, (using  either
special hardware,   or on  the  cheap  using random state   inside the
computer like     disk latencies, mouse  movement   etc)  there  is no
advantage or gain from doing so (in  other words, it's not "limiting")
Every one of  the things you mention  makes heavy use of psuedo random
number generators.

When it comes to the analysis of  algorithms, it's ALWAYS true that if
you know everything about the input  state, you can predict the output
state.  That includes random number generators in software.


> 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.

Well, that remains to be seen, but I would like to believe it's true.  Again,
this does not require true non-deterministic behavior, just simulated
non-deterministic behavior.

Don