Re: [computer-go] Hello / Pondering
On Tue, 2007-05-01 at 07:45 -0700, Peter Drake wrote: Orego also uses option B. Because UCT eventually focuses search on the most promising moves, it probably will spend most of its time on a single move, effectively doing A without the need for extra parameter settings. Is this your intuition or did you actually try it? I think you will be surprised to find that UCT does a fair amount of sibling node exploration. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Hello / Pondering
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. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Hello / Pondering
On 5/1/07, Joel Veness [EMAIL PROTECTED] wrote: My intuition suggests that b) is the better approach, but I know that a) works much better in computer chess. Does anyone know why a works much better in computer chess? Does the benefits of a correct guess (and thinking more deeply than the opponent) outweigh the benefits of having a little bit of extra thought about the move they chose? I think I've heard that chess has a branching factor of 8. In special scenarios where the (1-ply) branching factor is lower, does the best choice change? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Hello / Pondering
Orego also uses option B. Because UCT eventually focuses search on the most promising moves, it probably will spend most of its time on a single move, effectively doing A without the need for extra parameter settings. Peter Drake http://www.lclark.edu/~drake/ On May 1, 2007, at 4:51 AM, 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. ___ 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/
Re: [computer-go] Hello / Pondering
Hi Joel, I did a lot of testing and for me option A seems a little better. The problem with just pondering the latest known position is that there is very little tree under moves the program doesn't think the opponent will play. It appears to be good to get the full blown benefit of a correct prediction. But I would by all means experiment if you are in the mood. Here is a brief overview of how I do it, doesn't mean it's the best way: 1. Assume the opponent will play the move you think is best. 2. Set your thinking goal time as if you were not pondering. 3. Apply the expected opponent move to the board, start thinking. 4. If the opponent takes a long time to move, continue thinking, but as soon as the opponent makes his move then stick with the goaltime you set. This means if the opponent takes a long think, you might have an instant response.In either case you will save some time. This extra time benefits future moves. Once you have implemented this, you will want to change how you set your thinking goal time.Lazarus sets the goaltime of each search based on a percentage of remaining time left. Currently my only modification to this is that Lazarus will play much more quickly if the game is nearly won. This is useful because it enables you to allocate your time more aggressively. It's fairly important to allocate your time aggressively near the beginning of the game and get progressively faster. This is even MORE true if you are pondering. You have to assume that you will get future benefit from the ponder moves and plan accordingly. Pondering will be little benefit if you are playing an opponent who plays instantly but those players usually are weak. When your opponent also ponders, it gets to be interesting, because if you can play instantly, you are depriving him of thinking time - neutralizing his pondering ability. You can get into situations where one player is taking a long time to think while the other player is playing instantly, and you are playing without charge to your clock. To combat this, chess programs sometimes implement a feature to play obvious moves more quickly.But this is a double edged sword - it has to be done right or you may blunder. Of course obvious moves are generally predicted by the opponent which means he gets to think for free - thus the desire to deal with this. (Lazarus doesn't worry about this now.) One might argue that your time is better spent on algorithmic improvements to make your program play better moves. This argument is based on the fact that this kind of improvement is the type of thing you might imagine being applied to a polished program that is being made ready for competition and that it is easier to get improvements doing other things. However, this is worth about 50 ELO rating points and qualifies as a substantial improvement in it's own right. You might as well have it in your programs since it represents a substantial improvement for very little effort. I call this low hanging fruit and you should pick low hanging fruit before climbing a ladder to get the pieces of fruit at the top of the tree. Still, there are good reasons to delay doing this until your program is more advanced - in most of my testing I turn pondering off. I would suggest that you have a relatively solid UCT program in place that is relatively bug-free before getting into this. If you are not a fairly experienced programmer you might find implementing this messy.You will have to get into threading or co-routines programming to make this work. It's actually very easy with UCT since there the search is incremental and you don't have to worry about saving state in order to abort the search gracefully when a move is predicted wrongly. Lazarus also saves subtrees from the previous search. I tried pondering based on just continuously thinking on the latest branch avialable from the game and existing tree, but got much less than I expected. By the way, Lazarus predicts approximately 21% of the opponent moves. However I believe in reality is more effective that this would indicate. When playing strong opponents it predicts more moves. Near the end of a game the prediction rate becomes meaningless because it's just filling the board (more or less) randomly. My 21% is based on all opponents, all moves of the game. Maybe I do a test later and test the prediction rate when playing strong opponents and while the expected result of the game is relatively uncertain. I suspect that on bigger boards, pondering will be less beneficial, at least until programs get substantially stronger and thus prediction rates get higher. - Don On Tue, 2007-05-01 at 17:24 +1000, Joel Veness wrote: Hello, I have lurked for a while now on this list, and now that I finally have a weak monte-carlo/UCT program (goanna) up on CGOS, I decided that I should say hello. I am going to
Re: [computer-go] Hello / Pondering
smaller for larger boards. The only part of our program that is not
strictly ANSI C++ compliant is is_there_input(), ...
...
return select(1,read,write,except,timeout);
...
If you are interested on a Windows equivalent, I might be able to
provide one.
Hi Alvaro,
I'm interested in a windows equivalent, though for a program nothing to
do with computer go. Basically select() on windows does not work for
stdin (it only works for sockets created with winsock).
The code I found to use is:
DWORD stdin_timeout=100;//In milliseconds, so sleep for 0.1s.
HANDLE stdin_handle=GetStdHandle(STD_INPUT_HANDLE);
DWORD stdin_wait_result=WaitForSingleObject(stdin_handle,stdin_timeout);
if(stdin_wait_result==WAIT_OBJECT_0){
//There is input on stdin
}
else{
//Stdin is quiet
}
(For a pondering go program you want stdin_timeout set to 0.)
However, I suspect this code is actually blocking (sometimes?). In
addition behaviour seems to be different in each of:
* Using it from the console
* Using it where stdin is connected to a pipe (also see [1])
* Using it under cygwin, over ssh.
Most of what google has turned up for me so far is that if you want to
reliably read from stdin in a non-blocking way you should use threads.
Like you, this is a path I don't want to go down, especially as
select(stdin) works fine on linux, but it is looking like I have no choice.
Darren
[1]:
http://communicator.sourceforge.net/sites/MITRE/distributions/GalaxyCommunicator/contrib/MITRE/utilities/src/stdin_utility.c
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Hello / Pondering
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. There is no need to spend any extra time if you choose option A. You can just take the guess as the 2nd move from the principal variation when you generate your original move. Yes, I understand that deciding on zero seconds is an option. But consider the following situation: Your engine makes a move very quickly (perhaps it is a statically-recognized, large-group-saving move or maybe your time management code demanded a fast move). Now suppose your opponent thinks about it's move for a much longer time. If your engine uses option A (with zero additional seconds), then you are now pondering for a long time on a subtree that is probably meaningless because your hastily guessed opponent response was not based on sufficient exploration of that subtree. If you had chosen option B, then you are using that large chunk of time to fairly ponder on the entire tree. It just seems right. But on the other hand, it's tough to argue against Don's empirical results. Like he said, it doesn't hurt to try both in your engine -- it just takes time, like everything else. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Hello / Pondering
Hi Peter, On 5/2/07, Peter Drake [EMAIL PROTECTED] wrote: Orego also uses option B. Because UCT eventually focuses search on the most promising moves, it probably will spend most of its time on a single move, effectively doing A without the need for extra parameter settings. Yes, this is one of the reasons why I thought B might be better. One of the main benefits in using option A is that you easily save a lot of time for your remaining moves when you get a ponder hit. Using method B, do you adjust the amount of time to think by the size of the subtree generated by the ponder search? ie, if you want to search for 10 seconds, and your program performs 10K samples a second, then you expect about ~100K samples for the move. If you already start with 95K (because of the pondering), do you adjust your thinking time to roughly perform an extra 5K samples? Joel ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
