[computer-go] Improvement of UCT search algorithm

[Don Dailey]

On Thu, 2006-10-05 at 14:04 +0200, Łukasz Lew wrote:
> BTW2
> CGOS pairing algorithm rarely pair strong programs against themselves,
> especially when there is a bunch of very weak players urging to play
> with them. Maybe we could shut down some of them (with rating < 800
> and #games > 10000)?


ABOUT CGOS.  Your observations are correct, one of the goals of CGOS
is to provide a lot of opponent variety.  I have a parameter that
controls the amount of variety, but it's not clear how desirable it
would be to decrease the opponent variety.  Part of the motivation of
CGOS, and what makes it different than other servers, is that the
pairings guarantee variety and discourage elitism (where players
refuse to play players outside their club.)  If the players don't mix,
this has a bad effect on the rating pool.  If they mix too much, the
players tend to get severe mismatches.

To make things worse, there are extremely weak programs on CGOS that
won't go away!  There is a program rated close to -300 that is a
constant feature on CGOS.

But something that will help significantly is when I switch over to
pairing in discreet rounds.  I will pair top - down.  The best player
will get an opponent chosen for him probabilistically by the following
method:

   1.  Choose best remaining player as player 1.
   2.  Select N candidate opponents randomly from available players.
   3.  Choose the BEST of those N candidates as opponent for player 1.
   4.  Repeat until all players are paired.

A stand-in players will always be available to round out the pairings
if there are an odd number of players.  So each player is guaranteed a
game for each round.    Or I may perhaps just always shut out the
weakest rated player.

This is simple to understand and explain.  


What I expect to happen is a flood of suggestions on more
"sophisticated" ways to do the pairings based on people intuition and
preferences about how it should be done, but I am not likely to use
CGOS to experiment with these intuitions although I'm always willing
to listen to ideas.

The reason I am taking this stand is that this is a much harder
problem than I imagined it to be, and it's far easier to sit back and
dream up experiments for someone else to do than to actually provide a
sound idea that has been thoroughly checked out in advance.  So if you
think you have a great idea, write a paper on it or build a simulator,
test it, and prove it to me.  Then I might implement it.

Also, please don't bother to suggest anything that is not dirt simple
to implement.  For instance I'm not going to implement anything based
on an analysis of how many times each player has played particular
opponents.   


- Don