On Tue, 2007-05-01 at 07:51 -0400, Chris Fant wrote: > > You can: > > > > a) Guess your opponents next response, and assume they will make this > > move. Fire off a search from the resultant position. If you guess > > correctly, then you save X seconds. But if you only guess correctly p > > % of the time, you expect to gain pX seconds of extra thinking time > > per move. > > > > b) Think as if you were your opponent. Once your opponent makes a > > move, you keep the relevant sub-tree. This means that you will always > > get useful information from each ponder, but (assuming that you don't > > use the transposition information) you have wasted time searching > > moves the opponent didn't choose. I think a crude way of estimating > > the amount of time gained by this form of pondering would be to > > determine the expected value of: > > Don has stated a couple of times that option (A) worked better for > him. I chose option (B) without testing option (A) because I did not > want to have to decide how many seconds to use to guess the opponent > move before starting to think about my next move.
You can also implement option A and just start your clock (while keeping the search going) which is how Lazarus used to do it. So even if Lazarus spent a minute thinking on the opponents time it would still spend whatever it was allocated additionally. However, that's clearly not best if you consider the nature of the ELO rating curve per doubling. In this case you would have recieved most of the benefit from the 1 minute pondering amd the extra time is mostly wasted - would be much better spent amortized over the rest of the game. Since Lazarus spends a fixed percentage of remaining time on a given move, I would rather play instantly (assuming the opponent took a long time to move) and defer the running of my clock down. If you do this, the next move immediatly benefits with a little extra thinking time even if it's not predicted correctly. I hope my explanation isn't confusing. In a nutshell you can squeeze extra strength out of your program my allocating time as evenly as possible. Remember the ELO rating curve experiment? Each additional second of thinking time returns less expected ELO improvement (because each doubling of time returns a fixed amount of ELO improvement - it's not linear.) The way to take advantage of this fact is to allocte your time as evenly as possible. The previous paragraph has caveats - if you KNOW that a move is particularly difficult or easy, you can take advantage by allocating more or less time to that move. It's known that EARLY moves in the game can benefit from additional thinking time so they should be given more time. If you KNOW for sure what the best move is, you should of course play it immediately. As I mentioned before Lazarus plays fast when the game is a forgone conclusion (when it's score as reported by the UCT search is close to certainty.) Lazarus tries to use that time earlier in the game. I really hate it when Lazarus loses a game but there is still 2 minutes left on the clock! Those 2 minutes could have saved the game! However it is not possible to always get this right because there are many unknown factors such as how long the game will last - or at what point it will not really matter. I also think there is something to be gained from determining if a move is obvious and returning a move more quickly. At some point I will experiment with this too. This would be even more beneficial against programs that ponder. In Chess it's not known how long a game can last, so you can play yet another game with time allocation. You want to front load your time even more heavily (especially in sudden death games) because if the game ends suddenly you may have a lot of unused time left on your clock. But of course this is a gamble which you will sometimes lose - but it's still a positive expectancy gamble so it should be made if you are a wise gambler. By the way, I noticed that some programs understand this principle of using more time early in the game. Some programs spent more on the early moves than Lazarus, and I will notice that Lazarus is almost finished with a game and other programs will only be in the middle or even early part of the game. Lazarus may error on the side of "even time allocation." I've seen it lose good or winning positions when early time allocation is too aggressive but on the other hand it may not have achieved good or winning positions without this. I did some basic tests of this (nothing major) and it seems like there are a large range of values that don't make too much of a difference but I should re-investigate. The only thing really clear is that you should do this to a reasonable extent. The intution for this is that many games on CGOS are technically over after just a few moves - and after this it doesn't make much difference how you allocate your time as you have already won or lost. - Don _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
