<br><br><div class="gmail_quote">On Thu, Apr 7, 2011 at 2:01 PM, Brian Sheppard <span dir="ltr"><<a href="mailto:sheppardco@aol.com">sheppardco@aol.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
Measuring small differences is a big problem for me. I would like to have better tools here.<br></blockquote><div><br></div><div>As far as I can tell, you MUST test in a similar way to this (which I will describe next) in order to really make significant progress quickly.  Anything else is just fishing around and is subject to a lot of wasted effort.</div>
<div><br></div><div>Here is the general outline, and all the top chess program authors are following similar schemes and I will give you my thoughts on using this same method in computer go and the pitfalls at the end.  </div>
<div><br></div><div>I had to build my own tester for this, for use with chess but it could easily be done with go.   I have a 6 core i7-980X and my tester is non-graphical (GUI is a huge slowdown) and can run any number of games simultaneously.    This is an absolutely necessary tool for making progress for me. </div>
<div><br></div><div>I also find I get more games per minute if I set my tester to run 12 games (cpus = 12 in my config file),  even though the machine only has 6 physical cores.   Ponder is a waste of time (that can be tuned separately)  and so is MP (that should be tested and tuned separately.)   </div>
<div><br></div><div>The other thing is that you have to test much faster than you would really like to.   I want my program to play chess at long time controls well, but due to the limitations of my ability to test,  the majority of tests are done at time controls where each side is given about 15 seconds for the entire game.  We actually use fischer time controls most of the time.   That is actually more like 8 or 9 seconds in reality since I am pushing the test instances to 12 on a 6 core machine.     So at this time control I can get 24 games per minute.    </div>
<div><br></div><div>Believe it or not,  these results usually match longer time control results.    However,  once I have versions that I believe to be good based on fast tests,  I run a longer test which takes a day or two to get the number of samples I want.    I require 10,000 games samples before making decisions although I will stop tests early when it's clear that the version in question is not going to make it.    </div>
<div><br></div><div>A lot of version only win by 1 or 2 ELO.   It's important for statistically valid reasons not to make judgement based on intermediate results - the full 10,000 games must be run before I accept a version as my new best version.   (The error margins have different meanings if you don't set the number of games in advance.   Obviously,  it is wrong to stop the test when you "like" what you see but keep it going when you don't like it,  you would be unconsciously manipulating the results.)</div>
<div><br></div><div>Ok,  what about Go?   </div><div><br></div><div>Let's assume we are talking about 19x19 Go.   You will by necessity have to test much slower with Go than chess.   You have to evaluate for yourself the trade-offs.     In order to get the number of samples you need,  you will have to test much faster than you really want to.     We have found that even in chess, some of our ideas do not scale as well as others.  In extreme cases some ideas test very well on short searches but go the other way on long time control tests.  This is probably going to be more of a factor in Go.     But this is something that will require some time to gain some experience with and over time you will learn which TYPES of changes scale.      </div>
<div><br></div><div>The question you have to constantly ask is whether to go for large samples or high quality.   The answer is that you almost certainly have to do both.   Unless you have large samples the results are not very valid,  but they might not be valid if you don't run at long enough time controls either - so it's something you have to learn for your program.  </div>
<div><br></div><div>Don't be too sure that really short time controls are not valid however.   I was VERY surprised to find (at least in chess) that the correlation is extremely high.   If it plays well at game in 5 seconds it will play well at game in 5 minutes.   </div>
<div><br></div><div>I suspect that in 19x19 you will need to triple what I use in chess but I'll bet that even game in 10 seconds will return more or less valid results.   </div><div><br></div><div>One other thing is that you need to minimize overheads such as startup time as much as reasonably possible.  If your program needs 5 seconds to initialize before starting a game,  you are playing that price over and over again.    </div>
<div><br></div><div>I know many will not like to hear this,  but you HAVE to run a lot of games and it may require more patience than you are willing to give.    However, it may not be so bad if you are in the phase of development where you are making 20-50 ELO improvements at a time.    I use 10,000 games but 5,000 may be a good compromise.    The ISSUE for ME is that I can come up with ideas and implement them far faster than I can test them - so you have to be picky about what to put through this process.    </div>
<div><br></div><div>This IS the big secret to recent advancement in computer chess,  and it will work for Go too.     How many paper on computer go have you read where some idea was tried,  then it was tested against a version without the idea in a 100 game match?    I generally assume the paper authors are idiots when I see that,  unless they point out the flaws themselves or the result is staggering.  </div>
<div><br></div><div>Don</div><div><br></div><div><br></div><div> </div><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<br>
For instance, I am trying to measure whether a particular rule is an improvement, where with the rule it wins 60.5%, and without 60.0%. You need a staggering number of games to establish confidence. Yet this is the small, 5 to 10 Elo gain that Don referred to.<br>

<br>
I hoped to isolate cases where the *move* differs between versions, and then analyze (perhaps using a standard oracle like Fuego) whether those moves are plusses or minuses. But this is MCTS, and the program does not always play the same way even in the same position.<br>

<div><div></div><div class="h5"><br>
-----Original Message-----<br>
From: <a href="mailto:computer-go-bounces@dvandva.org">computer-go-bounces@dvandva.org</a> [mailto:<a href="mailto:computer-go-bounces@dvandva.org">computer-go-bounces@dvandva.org</a>] On Behalf Of "Ingo Althöfer"<br>

Sent: Thursday, April 07, 2011 12:25 PM<br>
To: Aja; <a href="mailto:computer-go@dvandva.org">computer-go@dvandva.org</a><br>
Subject: Re: [Computer-go] 7.0 Komi and weird deep search result<br>
<br>
Hello Aja,<br>
<br>
> ... Also, I will be more careful in measuring the<br>
> improvement, as exampled a lot in your description (my supervisor<br>
> Remi Coulom also repeatedly corrects me at this point).<br>
<br>
Remi was a strong computer chess programmer ("The Crazy Bishop")<br>
before he went to computer go. There is for instance a photo of<br>
him at the WCCC 2004, in the middle of the report<br>
<a href="http://www.chessbase.de/newsroom2.asp?newsid=3350" target="_blank">http://www.chessbase.de/newsroom2.asp?newsid=3350</a><br>
<br>
Ingo.<br>
<br>
<br>
<br>
<br>
> Aja<br>
>   ----- Original Message -----<br>
>   From: Don Dailey<br>
>   To: Aja<br>
>   Cc: <a href="mailto:computer-go@dvandva.org">computer-go@dvandva.org</a><br>
>   Sent: Wednesday, April 06, 2011 9:51 PM<br>
>   Subject: Re: [Computer-go] 7.0 Komi and weird deep search result<br>
><br>
><br>
><br>
><br>
>   On Wed, Apr 6, 2011 at 3:32 AM, Aja <<a href="mailto:ajahuang@gmail.com">ajahuang@gmail.com</a>> wrote:<br>
><br>
>     Hi Don,<br>
>     Thanks for your penetrating ideas. Yes, I would like to reconsider my<br>
> feeling and hope that it doesn’t misguide anyone.<br>
><br>
>     We both know the recent controversy between Fruit and Rybka (or Fabien<br>
> and Vasik), but of course it’s not the issue here right now. Just want<br>
> to mention in passing that Fabien said he might develop a Go program in the<br>
> next few years, so we can expect for another open-source strong program.<br>
><br>
><br>
>   I hope he does,  but of course I did not bring this up to talk about the<br>
> controversy,  just the reality that computer chess software is marching on<br>
> at a remarkable pace and this was an excellent example to illustrate that.<br>
><br>
><br>
>     It’s just my guess that it’s very hard for current MCTS to surpass<br>
> amateur 5d or 6d. One main reason is it’s difficult to solve a lot of<br>
> different semeai and life-and-death instances in pro level, even if the<br>
> program is running on a super big hardware (by this point I was impressed by<br>
> Olivier’s talk in a conference of Taiwan, in which he gave an “easy”<br>
> semeai example that Mogo cannot solve with very larger number of simulations).<br>
><br>
><br>
>   I want to point out that in computer chess that this same exact thing<br>
> was often done not so many years ago.   A relatively simple position would be<br>
> presented that humans easily understood,  but seemed completely out of<br>
> reach for computer chess programs to understand.   It was easy to see that<br>
> computers would need some ridiculous breakthroughs to be able to understand<br>
> such positions and the conclusion was that computers probably would never be<br>
> close to the top humans in chess.<br>
><br>
><br>
>   It's my view that such illustrations tended to cause people to draw the<br>
> wrong conclusions and sent people off in the wrong direction,  looking for<br>
> non-existent breakthroughs and concluding that incremental progress was a<br>
> completely foolish way to proceed.<br>
><br>
><br>
>   I believe we (as humans) lack a bit of imagination when it comes to<br>
> these sort of things.   For example the 4 minute mile was consider<br>
> physiologically unattainable a few years before the first one was run - in other words<br>
> it was hard to imagine it ever happening.    It's often difficult for us to<br>
> imagine things that are too different from what we are currently<br>
> experiencing (especially  once we decide it is "hard.")     Maybe part of the<br>
> problem is that we live in an instant gratification society and no longer think<br>
> in terms of hard work and gradual progress,  we want an instant<br>
> "breakthrough."<br>
><br>
><br>
>   Progress is a funny thing if you put numbers on it.  If you get 1%, it<br>
> doesn't seem like hardly anything. But if you add 1% to that, then 1% again,<br>
>  it's like compound interest in a bank and you look back over just a few<br>
> of these and are surprised by how much progress you make.<br>
><br>
><br>
>   I have been surprised that in chess the point of diminishing returns is<br>
> farther away that it seems and I'm sure in GO it is even more so by a large<br>
> degree.   In other words ELO progress in software has been more or less<br>
> steady,  not slowing to a crawl.   Yes, it is punctuated with small spikes<br>
> but seen over anything more than a couple of years it's remarkably smooth.<br>
> As evidence of that,  the program Houdini recently was released that is at<br>
> least 50 ELO over it's nearest competitor,  but you can be sure that is<br>
> only a temporary situation - it will look like a weak program in 2 or 3<br>
> years.<br>
><br>
>     Another aspect is that it’s extremely hard for MCTS to<br>
> consider/argue for few points in early stages on 19x19 (because it only sees winning<br>
> rate and dynamic komi is far from enough to fix it) and that is exactly what<br>
> pros are very able to.<br>
><br>
><br>
>   The only thing you are telling me is that we picked a hard problem.<br>
> There is nothing here inherently unsolvable,  we are  just impatient and<br>
> cannot imagine (yet) how we are going to solve this.<br>
><br>
><br>
>   I have discovered that in computer chess (which I have been into for<br>
> decades) the "unsolvable" problems didn't really make that much difference in<br>
> the short term.     The solutions come at a natural rate and until programs<br>
> get a lot better in other areas you will find that some of these "glaring"<br>
> weaknesses do not make much different in terms of how strong the program<br>
> is at the moment even when it seems like its a huge deal.    These<br>
> weaknesses gradually start making a huge difference  when the program is really good<br>
> and we tend to judge programs more by their weaknesses than their<br>
> strengths.    So when we see something "ugly" it makes us think the program cannot<br>
> be as strong as it actually has proved to be.    And computer program have<br>
> strengths and weakness in different proportions than we do so this tends to<br>
> distort our own views of how good or bad they play.<br>
><br>
><br>
>   An example in computer chess is basic endgame knowledge.   It's really<br>
> ugly to see a chess program trade down from a won ending to a draw because<br>
> it doesn't understand that certain simple endings cannot be won despite<br>
> being a piece up. Years ago, after seeing glaring example of this horrible<br>
> weakness, I took some time and implemented a large number of scoring<br>
> corrections to deal with this as well as putting in king and pawn versus king perfect<br>
> play database.   I patted myself on the back and expect to see a decent<br>
> ELO gain.    However even on modern programs this probably does not add more<br>
> than 2 or 3 ELO and I'm being generous.     If you show a grandmaster some<br>
> of these glitches he might conclude that your program plays like an amateur<br>
> (in fact when programs first became master strength many strong human<br>
> players would see one of the "ugly" moves and conclude that the program could<br>
> not play a move like that and even be "expert" strength, let alone master<br>
> strength.)<br>
><br>
><br>
>   I'm not saying these are not real problem in computer go,  but the point<br>
> is that there a large number of problems that altogether define exactly<br>
> where we stand right now and we just have to start making dents (which we<br>
> actually have been doing to a remarkable degree if you would only look more<br>
> carefully.)    The bigger problems are just going to take longer to fix than<br>
> the lesser problems.      Also,  I believe we have to get over this notion<br>
> that we have to "fix it" completely.  We probably will not fix it suddenly<br>
> with a one line program change,  but we can and will find ways to minimize<br>
> the problems, and it may be gradual and incremental.<br>
><br>
><br>
>   In your example you rightly note that program do very well when in their<br>
> "sweet spot",  when there are clearly defined goals that affect winning<br>
> percentages.     In computer chess it used to be believed that no amount of<br>
> searching could improve the programs "horrible" positional play and that<br>
> computers only played well if there were immediate tactical considerations,<br>
> otherwise they quickly went wrong.     That turned out not to be true, it<br>
> was just not clearly understood at the time because we were looking at the<br>
> problem through our own biased eyes and seeing the ugly things.     The truth<br>
> of the matter is that the tree search and playouts works well in all<br>
> positions but some more than others and we will find ways to clearly improve the<br>
> situation in the future with incremental progress (not major<br>
> breakthroughs.)    Also, we have some clearly wrong things that we will fix (like eye<br>
> definitions we have are approximations and are sometimes broken.)<br>
><br>
><br>
>   I'll say it again,  I think computer go is still in it's infancy and we<br>
> are still looking for the big fixes and have not yet come to fully<br>
> appreciate the immense practical power of incremental improvements over time.<br>
> When the problem looks big we feel like small improvements are a waste of time<br>
> but nothing is farther from the truth.<br>
><br>
><br>
><br>
><br>
>     The progress in hardware by Mogo, Fuego and pachi is well-known and<br>
> impressive, so that I don’t think the amazing progress in computer Go is<br>
> mainly due to software. Both hardware and software are important in making a<br>
> strong Go program for now, as far as I can see.<br>
><br>
><br>
>   I think the pattern is the same as it happened in computer chess.   But<br>
> I personally believe that software will be a much bigger contributor to<br>
> progress in the future (even if you ignore the "slowdown" of Moores law.)<br>
><br>
><br>
><br>
><br>
>     I hope your prediction is right: “without anything really major (but<br>
> no doubt some new small ideas) we are going to see your KGS 5 and 6 dan<br>
> and much higher in 5 to 10 years.” If not, then we will have a lot of<br>
> “interesting” work to do, no matter testing methodology, engineering or<br>
> academic etc.<br>
><br>
><br>
>   I am convinced I am right on this one.   I have absolutely nothing<br>
> against finding major breakthroughs of course but I think what we will call<br>
> "breakthroughs" will be things that add up to 50 ELO or less.    In chess it<br>
> was things like check extensions,  null move pruning, futility pruning,  LMR<br>
> etc.    We called null move pruning a "major breakthrough" but when it was<br>
> first used it added something like 40 or 50 ELO to the strength of a chess<br>
> program.    Is that a major breakthrough?  You don't notice 50 ELO right<br>
> away by watching it play because it still will lose 43 percent of the games<br>
> and thus still get outplayed in many games,  but  It depends on your<br>
> definition of "major" I guess.     In go that would be something like 1/2 dan.<br>
> I do think there will be a few of these kinds of breakthroughs.    What<br>
> happens is that these good ideas need to get refined and improved too.   I<br>
> think we get much more out of null move pruning than we used to.   LMR when<br>
> first implemented does not give chess program hardly any gain until it's<br>
> done just right.   But when refined it's pretty huge.   My first LMR<br>
> implementation was only about 20, now it's like 100 ELO or more.<br>
><br>
><br>
>   Thanks for listening to me ramble on about this ...<br>
><br>
><br>
>   Don<br>
><br>
><br>
><br>
>     Aja<br>
><br>
<br>
--<br>
GMX DSL Doppel-Flat ab 19,99 Euro/mtl.! Jetzt mit<br>
gratis Handy-Flat! <a href="http://portal.gmx.net/de/go/dsl" target="_blank">http://portal.gmx.net/de/go/dsl</a><br>
_______________________________________________<br>
Computer-go mailing list<br>
<a href="mailto:Computer-go@dvandva.org">Computer-go@dvandva.org</a><br>
<a href="http://dvandva.org/cgi-bin/mailman/listinfo/computer-go" target="_blank">http://dvandva.org/cgi-bin/mailman/listinfo/computer-go</a><br>
<br>
_______________________________________________<br>
Computer-go mailing list<br>
<a href="mailto:Computer-go@dvandva.org">Computer-go@dvandva.org</a><br>
<a href="http://dvandva.org/cgi-bin/mailman/listinfo/computer-go" target="_blank">http://dvandva.org/cgi-bin/mailman/listinfo/computer-go</a></div></div></blockquote></div><br>