[computer-go] 10k UCT bots

[Hideki Kato]

Álvaro Begué: <7b0793ea0805131100l4d804937k6814b9f4f481a89d at mail.gmail.com>:
>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;

This code introduces few bias unless num_candidates is a power of two, 
though.
#Assuming rand() returns [0 .. power of two).

-Hideki

>   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.
>>
>_______________________________________________
>computer-go mailing list
>computer-go at computer-go.org
>http://www.computer-go.org/mailman/listinfo/computer-go/
--
gg at nue.ci.i.u-tokyo.ac.jp (Kato)