There may be some confusion about what the assumptions and goals are for
the CGOS pairing objectives. I am hearing conflicting statements. So I
for one am unsure ;-)
Don Daily wrote (from Re: [computer-go] A new pairing system idea for
CGOS, 10/8/2006):
>> 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.
>
> Because a cluster of 2 or 3 bots near 2100, all of them Mogo versions,
> would mean all or mostly mogo vs mogo. One of the design goals of CGOS
> is variety. I don't want pairing based on rating pockets.
In the current thread Don also wrote:
> [snip]
> 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 [snip]
And I'd have to go back though the messages, but I'm pretty sure I've
heard it stated several times that CGOS should prefer pairing players of
similar "strength" more often than those of dissimilar "strength"
(whatever this means). Sometimes ratings are used and sometimes
rankings are used, even though the two have different meanings and
implications.
If there are clusters of ratings in the pool with shelves (which there
likely will be) then pairing by ranking will likely result in pairing
significantly different strength players more often than you want
(because some closely ranked players will be far apart in relative
rating strength). In the "real" world the ratings will not be
distributed evenly. Also there may not be drastic drop-offs from the
2100 to 500 range, but there will certainly be clusters and thus
drop-offs.
Both methods (by rating or by ranking) will tend to favor pairing
different but similar strength versions of the same program together
(i.e. the Mogo example Don cited), since presumably if all the versions
of Mogo have ratings near 2100 then they will be ranked closely together
as well. But is this really a big concern? Are there multiple versions
of the same program being played at the same time commonly? And if
there are and they are of similar strength then why wouldn't one want to
pair them, like any others? And how would a rank based method improve this?
Don then also wrote:
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.
The only issues I see with this technique, if I understand it correctly,
is that some players can never be paired, and that clusters will be
ignored, therefore in some cases pairing weak programs with stronger
ones too frequently.
IMO we need to be more explicit. Don asked about how he should do
pairing on CGOS so I was just offering a suggestion, but without
describing the problem explicitly and the objectives it makes it
difficult. Here are some key assumptions/requirements I thought of that
apply to CGOS and that would create an effective pairing distribution:
1. The pool of players will not be uniformly distributed by rating,
there will likely be clusters and isolated points.
2. The pool of available players can change between each round.
3. In any round, it should be possible that any available player can be
paired with any other available player. The probability of this
happening for any specific pairing depends on the pairing algorithm, but
between any two players it should not be zero nor 1 (unless of course
there are only two players in the pool).
4. In each round, pairings of players of similar strength are preferred
with the probability of the pairings correlated to the relative strength
(however defined). How specifically this probability/selection is made
depends on the algorithm and its sensitivity to the relative strengths.
I don't know if these are the same assumptions and objectives everyone
had in mind or not nor if they are even valid or complete, but it would
make sense to define/communicate what we want to achieve before we try
to devise a method for it. Don? Anyone else?
The rating-weighted random pairing method I suggested was meant to
handle these assumptions and satisfy these requirements.
To test the pairing methods, I suggest something similar to what Don did
with N evenly distributed players and N current CGOS players, plus also
creating sets of N randomly distributed players; and then run many
simulations of sample pairings on these groups for different values of N
and plot/analyze the results.
When I have some free time and if Don is interested, I may run some
simulations for the method I proposed and post some results. Don,
please let me know whether your mind is made up already.
Matt
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
