Don,
I see where this argument comes from, but you are not taking it to its
conclusion. Unless you can, in the end, show that your algorithm can
outperform another one with the same time limit, you have not proved
that it is an advance. That is why tournaments are played with time
limits, not limits on the number of playouts. Time is an important
dimension of the game of Go.
Here is why: if I follow your argument to its conclusion, I can come up
with an algorithm that spends five minutes per move looking through
databases of moves, performing simulations, and god knows what, and show
a 20% improvement over an algorithm that thinks for 5 seconds. That is
an "interesting" intermediate result. But would you then allow me to
write "obviously it will be just as quick as soon we've done a bit of
optimisation" in the epilogue, and accept that? What if there is no way
to optimise it? What if the old algorithm will always scale better with
the same time limit, on faster hardware? I guess you might let the
argument pass under tight conditions: the "other" program is a version
of the same program, and architecturally similar; and no algorithms
beyond linear complexity per move were added, or something of the sort.
You mix "proof" and "evidence" a few times in the same paragraph; the
sorting algorithm is probably not a good comparison. With a sorting
algorithm, you would first prove its big O and omega complexities, maybe
look at average cases too. I don't see a lot of people trying to "prove"
that their algorithms are improvements in Go, because it is generally
too complex; so evidence is all we get.
Christian
Don Dailey wrote:
On Tue, Jul 7, 2009 at 6:31 AM, Christian Nentwich
<christ...@modeltwozero.com <mailto:christ...@modeltwozero.com>> wrote:
>The problem I think is to find a good tradeoff between heavyness
and speed. In my test with Valkyria vs Fuego, Valkyria is superior
when the number of playouts are the same. But >Fuego can play 5
times more playouts per second on the hardware that results in
Fuego being slightly stronger than Valkyria at the moment.
Indeed - this makes me wonder why I keep seeing papers where
different versions of algorithms are compared with the same number
of playouts, rather than under the same time limit.
Because this is the right testing methodology to use. The first
thing you want to know is if the core idea is good. This is because
you will never know if you implemented it in the fastest possible
way. But once you know that the idea gives you better results with
the same number of playouts you have identified something about it
that is superior - then you can go from there.
There are two aspects that you are concerned about with tests like
this. The first and most important thing is the theoretical soundness
of the idea or approach being used. The second is the engineering
issues, which are really quite open ended and tough to nail down
accurately. Not only that, but you can kill 2 birds with one stone -
if the theory is not sound, then there is no need to pursue the
engineering aspect.
There is probably no great crime in doing it your way if your only
goal is to produce a strong program, but if your test fails you don't
really know if it failed because the idea is stupid or if your
implementation is unduly slow.
If you are writing a paper you certainly do not want to claim results
based solely on just your particular implementation of an idea that
might be bad anyway. There is nothing wrong with presenting an
engineering paper about an interesting way to implement something, but
even then it would be a pretty silly paper if you did not present at
least some analysis on why someone would WANT to implement this thing
i.e. it is a commonly used thing (a new sorting algorithm) or has
some practical application that you can identify.
What is the motivation in this? I cannot conceive of any good
reason for running an experiment this way, so I would be
interested in opinions. It seems to me that making algorithms
heavier and then demonstrating that they are stronger with the
same number of playouts misses the point - why would one not run
an experiment under the same time conditions instead?
As I said, when you are writing a paper you have to prove that
something is theoretically sound, at least empirically. If you are
writing an engineering paper you might present an interesting
implementation of some idea, but it should be an idea that has first
been shown to be interesting in some way. For instance a new
faster sorting algorithm is interesting. But you certainly don't
want to present evidence that YOUR IMPLEMENTATION of YOUR IDEA is no
good when you have not even attempted to establish whether the idea
itself is viable.
- Don
Christian
_______________________________________________
computer-go mailing list
computer-go@computer-go.org <mailto: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/
--
Christian Nentwich
Director, Model Two Zero Ltd.
+44-(0)7747-061302
http://www.modeltwozero.com
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
