[computer-go] A new pairing system idea for CGOS
Christoph Birk
birk at ociw.edu
Thu Oct 5 16:30:08 PDT 2006
On Thu, 5 Oct 2006, Don Dailey wrote:
> Yes, simulations are good. N may need to change with the number of
> active players at scheduling time.
Here are the results. The alorithm works like this:
1) take highest ranking (remaining) player
2) choose N candidates at random (N depends on #players remaining)
3) select highest ranking of the canditates
4) if un-paired players remain then goto 1)
I tried 4 formulas for N: (NP=14, #players currently active).
The tables show the probability of player at rank XX to be paired
against player at rank YY, divided by the 'unbiased' probability 1/(N-1)
N = 1+(NP-npaired-1)/2 (ie. half the players available)
2 3 4 5 6 7 8 9 10 11 12 13 14
01: 7.0 3.5 1.6 0.6 0.2 0.1 0.0 0.0 0.0 0.0 0.0 0.0 0.0
02: 1.4 2.2 1.4 0.7 0.3 0.1 0.0 0.0 0.0 0.0 0.0 0.0
03: 3.9 2.1 1.2 0.6 0.2 0.1 0.0 0.0 0.0 0.0 0.0
04: 1.2 2.0 1.3 0.6 0.2 0.0 0.0 0.0 0.0 0.0
05: 3.8 2.0 1.2 0.5 0.2 0.0 0.0 0.0 0.0
06: 1.1 2.0 1.3 0.6 0.2 0.0 0.0 0.0
07: 3.9 2.1 1.1 0.5 0.1 0.0 0.0
08: 0.9 2.1 1.4 0.5 0.0 0.0
09: 4.3 2.2 1.1 0.2 0.0
10: 0.7 2.4 1.6 0.0
11: 5.0 2.5 0.4
12: 0.0 3.9
13: 8.7
N=1+(NP-npaired-1)/5 i (ie. 20% of the players available)
2 3 4 5 6 7 8 9 10 11 12 13 14
01: 3.0 2.5 2.0 1.6 1.3 1.0 0.7 0.5 0.3 0.1 0.0 0.0 0.0
02: 2.0 1.9 1.7 1.4 1.1 0.8 0.6 0.4 0.2 0.1 0.0 0.0
03: 1.4 1.3 1.2 1.1 1.0 0.8 0.7 0.5 0.3 0.2 0.0
04: 1.1 1.1 1.1 1.1 1.0 0.9 0.7 0.5 0.3 0.0
05: 1.2 1.2 1.1 1.1 1.0 0.8 0.6 0.3 0.0
06: 1.2 1.2 1.2 1.1 1.0 0.7 0.4 0.0
07: 1.2 1.2 1.2 1.1 0.9 0.6 0.2
08: 1.2 1.2 1.1 1.0 0.8 0.6
09: 1.1 1.0 1.0 1.1 1.3
10: 0.8 1.1 1.5 1.9
11: 1.4 1.9 2.4
12: 2.4 3.0
13: 3.6
N=1+sqrt(NP-npaired-2)
2 3 4 5 6 7 8 9 10 11 12 13 14
01: 4.0 3.0 2.2 1.5 1.0 0.6 0.4 0.2 0.1 0.0 0.0 0.0 0.0
02: 2.2 2.0 1.7 1.3 0.9 0.5 0.3 0.1 0.0 0.0 0.0 0.0
03: 1.9 1.6 1.4 1.1 0.8 0.5 0.3 0.1 0.0 0.0 0.0
04: 1.3 1.4 1.3 1.1 0.9 0.5 0.3 0.1 0.0 0.0
05: 1.6 1.5 1.3 1.1 0.8 0.4 0.1 0.0 0.0
06: 1.5 1.6 1.4 1.1 0.6 0.2 0.0 0.0
07: 1.8 1.6 1.4 1.0 0.4 0.0 0.0
08: 1.5 1.9 1.3 0.7 0.1 0.0
09: 2.5 1.5 1.1 0.6 0.0
10: 0.7 2.2 1.4 0.1
11: 4.4 2.2 0.5
12: 0.0 3.7
13: 8.7
N=1 (fixed, just for verification :-)
2 3 4 5 6 7 8 9 10 11 12 13 14
01: 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
02: 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
03: 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
04: 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
05: 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
06: 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
07: 1.0 1.0 1.0 1.0 1.0 1.0 1.0
08: 1.0 1.0 1.0 1.0 1.0 1.0
09: 1.0 1.0 1.0 1.0 1.0
10: 1.0 1.0 1.0 1.0
11: 1.0 1.0 1.0
12: 1.0 1.0
13: 1.0
Don: I appended the (C-) program for your own experiments.
Christoph
-------------- next part --------------
/* topdown.c */
/* Christoph C. Birk (birk at ociw.edu) */
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <time.h>
#define NP 14
int main(int argc,char** argv)
{
int i,j,k,npaired,p,q;
int n,m=100;
int cand[NP],paired[NP];
int cnt[NP][NP];
float f;
if (argc > 1) m = atoi(argv[1]);
for (i=0; i<NP; i++) {
for (j=0; j<NP; j++) {
cnt[i][j] = 0;
}
}
srand48(time(NULL));
for (i=0; i<m ; i++) { /* outer loop */
for (j=0; j<NP; j++) { /* reset pairings */
paired[j] = 0;
}
npaired = 0;
do { /* new pairing */
//n = 1+(NP-npaired-1)/2;
n = 1+(NP-npaired-1)/5; /* # candidates */
//n = 1+(int)sqrt(NP-npaired-2);
//n = 1;
for (p=0; p<NP; p++) { /* pair strongest player first */
if (!paired[p]) break;
}
for (j=0; j<n; j++) { /* opponents candidates */
do {
q = (lrand48() >> 8) % NP;
for (k=0; k<j; k++) {
if (cand[k] == q) { q = p; break; }
}
} while ((p == q) || paired[q]);
cand[j] = q;
}
for (j=0,q=NP; j<n; j++) { /* finst stronges opponent */
if (cand[j] < q) q = cand[j];
}
paired[p] = q+1; paired[q] = p+1;
npaired += 2;
} while (npaired < NP);
for (p=0; p<NP; p++) {
q = paired[p]-1;
cnt[p][q] += 1;
//cnt[q][p] += 1;
}
}
printf(" ");
for (j=1; j<NP; j++) printf(" %4d",j+1);
printf("\n");
for (i=0; i<NP-1; i++) {
printf("%02d:",i+1);
for (j=1; j<NP; j++) {
f = (((float)cnt[i][j] / (float)m) / (1.0f/(NP-1.0f)));
//if (j > i) printf(" %4d",cnt[i][j]);
if (j > i) printf(" %4.1f",f);
else printf(" ");
}
printf("\n");
}
return(0);
}
More information about the computer-go
mailing list