[computer-go] 10k UCT bots

[Álvaro Begué]

Ooops! I hit sent before I finished writing the pseudo code. Sorry.

int pick(Move *empties, int num_empties) {
 int num_candidates = num_empties;
 int picked;

 while(1) {
   picked = rand()%num_candidates;
   if(!acceptable(empties[picked])) {
     num_candidates--;
     swap(empties[picked],empties[num_candidates]);
   }
   else
     break;
 }
 return picked;
}



On Tue, May 13, 2008 at 1:57 PM, Álvaro Begué <alvaro.begue at gmail.com> wrote:
> On Tue, May 13, 2008 at 1:51 PM, Mark Boon <tesujisoftware at gmail.com> wrote:
>  >
>  > On 13-mei-08, at 14:10, Álvaro Begué wrote:
>  >
>  >
>  > What others do is the right thing to do. Your method will introduce
>  >
>  > some biases.
>  > Could you elaborate what bias it could lead to? I also do the same as Jason.
>  > I did consider the possibility of a bias but couldn't immediately think of
>  > one.
>
>  This has been explained already. After the first eye appears on the
>  board, the first empty point after the eye has a probability of being
>  picked that is twice the probability of any other empty point.
>
>
>  > What good does moving it to the end of the list do? Next time around it's
>  > just as likely to be picked as when left in place. Or do you only process
>  > the 'end' after the 'front' moves are all tried?
>
>  You move it to the end and you reduce the number of candidates by one.
>  The code is roughly this:
>
>  int pick(Move *empties, int num_empties) {
>   int num_candidates = num_empties;
>   int picked;
>
>   do {
>     picked = rand()%num_candidates;
>     num_candidates--;
>   } while(!acceptable(empties[picked]);
>
>   return picked;
>  }
>
>
>  Álvaro.
>