On Tue, Jul 7, 2009 at 12:09 PM, Christian Nentwich < christ...@modeltwozero.com> wrote:
> 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. You are the one that started this conversation with a question about why authors of papers seem to be concerned more with the theoretical properties of algorithms than the practical implementation details. I'm just trying to give you the answer. If you don't like the answer, why did you ask the question? You may not like it, but I'm telling you that in general these kind of papers are about ideas, not implementations. A good paper will have a primary focus on one or the other. > > 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? I never said that. You constructed a ridiculous example here that does NOT produce an interesting result. Your basic idea has to be interesting in the first place if you are going to write a paper that someone might actually want to read. If you can produce a result that gives a 20% improvement and the idea is not ridiculous, then you may have an interesting paper even if it's difficult to get the performance you need to put in a practical program. It would certainly be a badly written paper if your primary conclusion was that "we couldn't get it to run fast enough." The first question any reader would ask is how much improvement is it with the same number of playouts? What would your answer be? "We didn't try that because the only thing that matters to me is that it plays well on my computer with the given time contstraints." (That may be true, and there is nothing wrong with that attitude, but it's not one you would focus a paper on.) There are a ton of algorithms out there that do not run well on a given architecture, but may run well on some other. Or it may be highly feasible with dedicated hardware, or perhaps be particularly easy to parallelize. If the basic idea is sound, that is a much more important result than how much time YOUR implementation took. If you draw conclusions based on that you just have a paper that has your opinion in it. You become a philosopher instead of a scientist. There is nothing wrong with presenting the idea and performance figures but if you want others to have some respect for your paper you need to make sure you are not drawing conclusions based on YOUR implementation and hardware platform. > > You mix "proof" and "evidence" a few times in the same paragraph; So what? I'm not confusing the terms. You just mentioned it in the same sentence but that was not wrong either. It's common when you are dealing with inexact sciences like games programming to accept as "proof" strong empirical evidence. It's called "empirical proof." > 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. Yes, we are not dealing with an exact science here. That is why you need to at least show that in a given test program the algorithm has merit by isolating the theory from the implementation details as much as possible. It's certainly more interesting to me to know that the basic idea works in other programs and I can speculate whether it is likely to work in mine. I don't want also to have to speculate on whether you implemented it efficiently or not, whether there is some advantage to some platforms over others, etc. Now I'm not saying it's bad to include performance numbers - that might be interesting to look at but it's second order information - it's not the key thing. Whether the paper author could make it work from a performance standpoint is not as important as whether the basic idea has some feasibility. - Don > 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/ >
_______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
