[computer-go] A new pairing system idea for CGOS

[Matt Gokey]

Don Dailey wrote:

> Paring in rounds is good for the first goal and is what I plan to do.
I know, I was just being complete in repeating this decision...

> Your basic idea is sound - but it's all in the formula for point 2.  I
> would not base it on the rating, I would base it on the RANKING
Why the ranking over the rating? Ranking eliminates the real strength
differences.  A cluster of 3 players near 1700 and then one at 1300
looks much different than rank 1, 2, 3, 4.

> Also, the formula MUST have a random component in it. 
I think you may have misunderstood the concept.  The choice in step 2 is 
random and the rating is specifically used over the ranking to calculate 
the distances and weights.  Let me explain further.

OK here is the steps again:
>> 1. Pick a random player A from the remaining available players.
>> 2. Select a player B from the remaining available players using a 
>> weighted random selection with the weight based on an inverse
 >> distance formula between player A's rating and each remaining
 >> player's rating.
>> 3. Repeat until all players are paired.

I was probably not clear enough, especially step 2.

In step 1 a random player is chosen because I thought this would help 
reduce the potential issue expressed by others that the top down method 
might create (favoring pairings between strong programs too heavily) and 
because step 2 is going to choose an opponent randomly from _all_ the 
remaining players, not evenly, but favoring players with closer ratings. 
  Players with _ratings_ closer to player A's rating will be weighted 
more heavily.  This is the idea of inverse distance weighting I 
proposed.  In this way any player can be selected but will still prefer 
players with progressively closer ratings. Steps 1 and 2 are repeated 
until all pairings are made.  The weights used for the random opponent 
selection are calculated for each iteration.

A simple linear inverse weighting could be something like this:
1.  Calculate the distance between Player A's rating and each other 
player X's rating (|A-X|).
2.  Normalize each distance by subtracting the min distance.  maximum 
normalized distance = spread.
3.  Calculate the weight for each player X with something like:
minWeight + (spread - normalized dist X)/(spread/(maxWeight-MinWeight))

The selection is made randomly from the weighted list.

The weight formula could be linear or stepped/tiered or non-linear, 
etc.; there are lots of possibilities.  Perhaps to get some of the 
benefit of the top-down method, the step 1 player A selection could be a 
weighted random selection also - just based on the rating (i.e. it would 
tend to choose higher rated programs first but not necessarily).

Here's a simple example using the linear formula from above:

player  rating
1       1100
2       1200
3       600
4       800

Pick random player from list
player 4, rating 800

Distance from player 4 for each other player
1 = 300, normalized = 100
2 = 400, normalized = 200
3 = 200, normalized = 0

Player weights with min weight = 1, max weight = 5
player 1 = 1 + (200 - 100)/(200/4) = 3
player 2 = 1 + (200 - 200)/(200/4) = 1
player 3 = 1 + (200 - 0)/(200/4) = 5

Thus the weighted list to choose player B from would be:
player 1 x 3, player 2 x 1, player 3 x 5 (1 1 1 2 3 3 3 3 3)

Selecting randomly from this weighted list will favor player 3, then 1, 
and finally 2.  But _any_ player can be selected.

Matt