On Oct 9, 2008, at 10:39 PM, Don Dailey wrote:
On Thu, 2008-10-09 at 15:20 -0400, [EMAIL PROTECTED] wrote:
Computers + random = can of worms.
What if I get a fast benchmark by implementing the fastest, most
awful, random number generator imaginable? What if every one of my
"random" playouts looks the disturbingly similar?
As to the relevance, the time-eaters in my heavy playouts are
different from the time-eaters in my light playouts.
This is true, but it goes back to the well understood fact that you
cannot have a perfect benchmark.
I think this would be very useful and very relevant, just not
perfect.
Random numbers IS an issue. I required transparency so that any issue
like this can be observed, reviewed, criticized, etc.
However, there is a solution. I don't think this solution is
necessary,
but it is possible: George Marsaglia published a set of very high
quality random number generators that can be implemented with just a
couple of lines of code. We could specify that a specific random
number generator be used. After all, this is only a benchmark. But
these are fast generators.
The final step, which I don't personally support because I think it's
too restrictive but is also possible is to require these programs
to be
deterministic. So you could SPECIFY the exact starting seed for a
random number generator as well as the specific method (or equivalent)
to be used to select moves randomly.
I don't really like that idea, but it makes it possible to perfectly
verify the implementations. I don't like it simply because it places
additional constraints on creativity and flexibility. You might come
up with a very clever and fast way to generate uniformly random moves
for instance that doesn't work within the framework. Or you may want
to benchmark some language that doesn't like 32 bit data types
(perhaps
31 bit types for instance.) A lack of flexibility here would unduly
punish you.
So I'm happy to allow some leeway at the expense of perfect
verification
as long as we have transparency, anybody who wants can see the
code and
criticize it or find flaws. (His implementation is FAST, but he
cheated a little on the random numbers.)
It's also pretty easy to not pick moves uniformly random - I think
some
on this group may have made that mistake. This should show up if we
have good benchmarks. Someone will notice something slightly off
in the
statistics reported and it will be examined or seen to be flawed.
hi, i hate usually replies to my post that zoom in into 1 tiny
detail, apologies for doing that.
However i'd like to zoom in on the uniformity of RNG's. Of course we
all do effort to get uniform
RNG's. In fact the net is overloaded with them. Years ago i googled
and i stumbled upon ranrot
from Agner Fog. http://www.agner.org/random/theory/
Like all fibonacci based RNG's it's completely uniform spreaded.
Now THAT has a few problems. When i did do some work a year or 8 ago
for a guy called
Avery Cardoza, he released a game called Casino2000. Obviously it
also has roulette also.
Now if we take the European roulette version that has a single zero
(US casino's have 2 zero's,
a 0 and 00, which makes odds quite bigger for casino), there is on
paper 1 strategy that might
deliver money. Might, because playing with a system is forbidden of
course.
On paper there is 1 system that wins.
You put 1 fiche, then if you lose that bet you double, if you lose
again you double again.
So you bet
1,2,4,8,16,32,64,128,256,512,1000
Hah, why 1000?
Because usually you won't get further than doubling 10 times.
Each table has a max bet.
So let's limit the number of bets to 8.
7 doublings in short.
Not a single RNG that is considered to be 'good' and 'well'. Yes not
even Mersenne twister,
is *approaching* reality there that happens in casino's. Now i do not
mean the 'bad' casino's,
but simply that the profit you make "on paper" is a lot higher than
in reality (other than that they'll
kick you out of the casino).
The freakin nature of all those bitflippers is such that i'm
*assuming* nowadays in some algorithms that they can produce
a field for me in O ( n log n ). So not only they are too uniform,
they also can produce an entire field, covering every element
in O ( n log n), without a single failure.
Now THAT'S interesting :)
- Don
- Dave Hillis
-----Original Message-----
From: Don Dailey <[EMAIL PROTECTED]>
To: computer-go <computer-go@computer-go.org>
Sent: Thu, 9 Oct 2008 2:44 pm
Subject: Re: [computer-go] programming languages
On Thu, 2008-10-09 at 14:17 -0400, [EMAIL PROTECTED] wrote:
The http://shootout.alioth.debian.org/ site, ...
If we, as a community, could come up with a sufficiently detailed
description of light playouts algorithm (see the current "Light
simulation : Characteristic values" thread), there is no reason
that
this algorithm couldn't join them.
Many potential ways to speed up light playouts involve taking some
liberties regarding the uniform distribution of moves. Specifying
and
verifying the rules here, looks messy to me.
Also, light playouts are more of an intermediate step than an end
goal
for engines. Is making them faster all that relevent anymore?
I think you're missing the point. This would be nothing more
than just
a benchmark. You would be free to implemented it any way you
like as
long as it conforms to the general guidelines, so all programs
should be
equivalent. However one program might use a totally different board
representation than another.
Specifying the rules is probably not too hard but verifying them
would
be trickier. The simplest way to verify is:
1. benchmarks that provide strong empirical evidence.
2. Source code is available for all to inspect.
I agree that this is far from the best way to implement a program
but it
would really be useful as a benchmark for board games. I would trust
the results of this shootout way beyond the computer language
shootout.
This is because it's an actual program that should also be able to
play
a real game.
John Tromp did something along the same lines with connect-4. He
had a
java and C implementation that were equivalent in output. I actually
didn't trust his benchmark because he wrote C code generic and
simple,
not like a high performance guru would write C code. I can't
really
be too critical unless I actually were to try to improve on the C
version.
To me the advantage of C is that you can write code that you wouldn't
write in Java. There is very little advantage of C over Java
otherwise. If you start with the best Java program you can and then
port it to C as faithfully as possible, you get a different result
than
if you take the best possible C program you can write and try to
port it
to Java. For each language, you would probably write fast code
differently.
I think the right way to do John's benchmark is to get each language
zealot in competition with each other. Let the C programmer
prove he
can do it much faster. And the Java programmer can respond if he
wants
to.
- Don
- Dave Hillis
____________________________________________________________________
__
McCain or Obama? Stay updated on coverage of the Presidential race
while you browse - Download Now!
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
_____________________________________________________________________
_
McCain or Obama? Stay updated on coverage of the Presidential race
while you browse - Download Now!
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
