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

[William Harold Newman <william.newman@xxxxxxxxxxx>]

On Mon, Dec 11, 2000 at 02:25:58PM -0500, Don Dailey wrote:
> 
> > I'm not claiming that a "deterministic" program can't do simulated
> > annealing and machine learning and so forth. (I vaguely remember that
> > someone else may have claimed that, but I definitely remember that it
> > wasn't me.:-) I did my Ph. D. thesis on Monte Carlo simulations of
> > quantum mechanics, and I learned a thing or two about PRNGs along the
> > way. I even went to some trouble to make my Monte Carlo programs as
> > deterministic as possible, in part for debugging. My argument here is
> > only about the difficulty of making a program's time consumption
> > deterministic.
> 
> I didn't  say YOU claimed  this.  In  fact I  assumed you knew better,
> because you seem to at least understand  the issues.  You seem bent on
> trying to prove to me that programs written in a non-deterministic way
> are non-deterministic,  which  isn't very useful.   All I  am claiming
> that you can write a strong deterministic program that is not severely
> handicapped.  You are not making any points I don't disagree with.
                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Perhaps that's part of the problem.:-|

> >                                                 I hope to convince you
> > that while ignoring the real time clock may work well for your
> > programs, it does not necessary work well for other people's programs.
> 
> Ok,  so now you   have identified the  single  point worthy  of debate
> because this  is where we disagree.   I maintain that you don't ignore
> the concept of TIME, you  just have to adjust your  point of view that
> you   somehow just HAVE to  use  a non-deterministic  measurment of it
> because it makes you unhappy to do otherwise.  You seem to accept that
> it's ok to use deterministic random numbers (psuedo-random), why can't
                                                               ^^^^^^^^^
> you  use  a deterministic  measure   of time?   Because  it  makes you
  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> unhappy?   
  ^^^^^^^^

Because you haven't convinced me that it's practical to do so. Because
I'm not aware of any programs which successfully do so, and I think
that's not a coincidence: trying to do so seems to me to be a severe
limitation on a program.

Don Dailey also wrote in another message that
> I never claimed it was impossible to incorporate non-randomness into a
> program,  only  that I  don't  think it  "limits"  a  program.  It was
                       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> earlier implied that   determinism  was a limiting    requirement that
> prevented sophisticated AI techniques from being used.  

I believe that on a typical modern system (vanilla Windows or Unix)
it's often impractical to avoid using an external real-time clock to
estimate elapsed time. It's relatively practical to avoid using such a
clock if your program has very predictable memory access patterns,
e.g. just doing FFTs and matrix multiplications. It's much less
practical when your program has memory access patterns which depend on
the input data in a complicated way, as in e.g. many search algorithms
for NP-or-harder problems.

A great way to start convincing me that bounding runtime in an
open-loop way isn't in practice an important limit for search programs
would be to show me an example of a search program as powerful as GCC,
SMLNJ, SBCL/CMUCL, or crafty which does bound runtime in an open-loop
way. The best example that I'm aware of is early versions of Handtalk:
IIRC Handtalk was so fast in general that the programmer didn't bother
to check the real-time clock. However, my recollection is that
Handtalk then lost on time against a pathological opponent in a
tournament, and the programmer switched over to checking the clock!

If you can't show a successful example of your design philosophy, I'll
be predisposed to be skeptical. However, you could still start
convincing me by explaining, in somewhat more detail than you have so
far, how you propose to make your application code estimate the
elapsed runtime in the presence of nontrivial, input-data-dependent
memory access patterns.

-- 
William Harold Newman <william.newman@xxxxxxxxxxxxxxxxx>
software consultant
PGP key fingerprint 85 CE 1C BA 79 8D 51 8C  B9 25 FB EE E0 C3 E5 7C