Re: [computer-go] KGS Tournaments: Cheating

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

On Mon, Mar 07, 2005 at 03:46:50PM +0100, Persson, Magnus wrote:
> As an author of a program that do not play reproducible, I must state
> that it is not necessarily easy to make such a program play
> reproducibly.

I also have a program for which playing reproducibly would be somewhat
unnatural. My program does searches where both the branching factor
and the effective cost per node seem to fluctuate quite a lot, and I
haven't figured out any way to bound its search which works nearly as
well as just measuring the real computer resources spent in search so
far (primarily wall clock time, but also number of bytes of the heap
allocated and GCed) and cutting off search when those numbers get too
large. Wall clock time is not reproducible at all, and the number of
bytes GCed is mostly reproducible, but not absolutely reliably so.
 
Probably it would not be too hard to make a version with conservative
cutoffs which played reasonably well. But it would be a conversion
from a sort of "closed loop" feedback from real resources actually
used, to "open loop" guesses about real resources actually used. And
my wild guess it that a quick and dirty conversion would take a couple
of programming days, and furthermore the result of such a quick and
dirty conversion would have to be pretty conservative about the amount
of time it used (to make allowances for poorly understood worst cases)
and so would end up, on average, only using 30-60% of the actual wall
clock time available.

(And beyond that, extending this system to thinking on one's
opponent's time would probably be a further PITA.)

> In order to have random move generator (which is a necessity in my
> program) providing the same result every time, I would need to set a
> fixed limit of calls to the random generator at each move. But then I
> lose control over time it takes to compute the move and would end up
> having to play moves faster than the time limits allow. Now it also
> happens to be the case that the playing strength of my program depends
> strongly on the thinking time.

Incidentally, it sounds to me as though that "same result each time"
problem might be somewhat tractable. Most programs calculate the hash
of board positions (Zobrist or whatever). If your program knows such a
hash value, you can use that hash to generate a fresh seed for your
RNG, independent of how the RNG has been called before. Then, no
matter how you arrived at the position, your program can analyze it
the same way. (I've done something similar to this, in fact, with no
problems so far.)
 
> Thus, forcing a program to play in a reproducible way will be unfair to
> it, because it would not be able to use the time controls in a flexible
> and efficient way. It is impossible to know in advance how long time it
> takes to compute the best move.

Yes, as I said, fundamentally it seems like a conversion from closed
loop to open loop, and in practice for at least some programs that's
going to be a significant problem.

-- 
William Harold Newman <william.newman@xxxxxxxxxxxxxxxxx>
People don't learn from History.  Most of them don't even learn from
Current Events. -- Pyotr Filipivich
_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/