On 5/1/07, Chris Fant <[EMAIL PROTECTED]> 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.
We also chose (b), but not for the reason Chris posted. In chess you
typically don't do any initial search to guess what the opponent will
do; you use the second move from the PV line in the previous search.
I think (b) is a more natural thing to do, and in chess it's hard to
do because alpha-beta leaves you with not-so-useful information about
moves that haven't been explored with full window. In UCT we don't
have that problem (which probably means we are working too hard on bad
moves, but that's a subject for another thread).
This is how we implemented it. Our main program is (this is actual
working C++ code):
int main(){
GTP_Manager gtp_manager;
while(!gtp_manager.quit){
std::string line;
while(!is_there_input())
gtp_manager.board.ponder_a_bit();
std::getline(std::cin,line);
gtp_manager.process_command(line);
}
}
ponder_a_bit() runs a fixed number of simulations. Right now it's the
number is 1024 because we are only set to play on 9x9; it should be
smaller for larger boards. The only part of our program that is not
strictly ANSI C++ compliant is is_there_input(), which in POSIX
systems (i.e., non-Windows) looks like this:
bool is_there_input(){
fd_set read,write,except;
FD_ZERO(&read);
FD_ZERO(&write);
FD_ZERO(&except);
FD_SET(0,&read); // stdin
struct timeval timeout;
timeout.tv_sec=0;
timeout.tv_usec=0;
return select(1,&read,&write,&except,&timeout);
}
If you are interested on a Windows equivalent, I might be able to provide one.
The alternative to this kind of design is having two threads: one that
reads input (blocking) and one that thinks. If you use boost::thread,
this is actually very portable. I find multi-threaded programs hard to
debug, and that's why I chose the option I just described.
Álvaro.
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
