[computer-go] CGOS pairings using Christoph Birk formula

[Don Dailey]

I did a simulation myself based on the elimination tournament idea.   I
plotted the results with GnuPlot to get a sense of what was going on.

As much as I like the concept,  it has some bad characteristics.   If I
do the pairings in the logically correct way (where each recursive
sub-tournament is arranged so that the best player in one half will meet
the best player in the other half if there are no upsets) then I get
very lumpy percentage curves.  The best player does not get to play the
second best player as often as he might get to play much weaker players
and it depends on where he is in the pairing chart.    I predicted this
behavior so I am not surprised.

If you do the pairings with a randomized pairing chart (where the first
round is completely random) then you get a very smooth curve.  I did
this with pseudo opponents who were spaced evenly (142 players 20 rating
points apart) and 142 players with the same ratings as the 142 players
currently listed on the CGOS standings page.

When I do it with the actual CGOS ratings,  it's a lumpier line where
when ratings clump together they play together a little bit more - which
is fine.  

However, the curve is not steep enough to suit me.  The very weak
players still get to play the very strong players quite a bit.   I would
prefer that it's a fairly rare event for a 2100 player to play a 500
player unless no other players are available, but it's just not that
rare.   The best players play each other about 2.5 times more than they
would randomly be expected to and the very weakest still play about 40%
of the number of times they would if always randomly paired. 

To reiterate, for the simulation with 142 players I use this:

   1. I take all available players and determine what is the largest 
      available tournament size I can handle.  It must of course be a
      power of 2 and on the first pass it works out to 128 players.

   2. I pick those players at random - the rest have to wait for another
      tournament (although I could start a smaller tournament, I didn't
      in the simulation but I probably would if I implemented it on 
      CGOS.

   3. I play 1 round in all currently active tournaments.

   4. I repeat the process going back to step 1 starting another 
      tournament for available players.


So I'm starting to believe I will use one of Christoph Birk's formulas
with best of N selection:  N=1+sqrt(NP-npaired-2)

With this formula (as well as the others) and pairing from the top-down,
I think gives CGOS a nice distribution.  

- Don