Page 1 of 1
Multiplayer partial round-robin
Posted: 05 December 2021, 03:48
by dgjxqz
For turn based games, Swiss system can take very long to complete. Currently round robin only supports 2 players. The following javascript demonstrates one of the many ways to arrange matches for one round:
Code: Select all
const ttl=60; // total participants
const ppm=4; // participant per match
const mch=Array(ttl).fill().map(q=>[]);
for(let q=0;q<ppm;)Array(ttl).fill().map((j,k)=>[Math.random(),k]).sort().every((j,k)=>mch[k].indexOf(mch[k][q]=j[1])==q)&&q++;
console.table(mch);
It ensures that everyone plays the same number of matches and if turn order is important everyone gets to start first at least once (only if ppm * 2 < ttl, else generate mch for ppm = ttl-ppm). But it doesn't try to avoid repeatedly pitting the same players against each other.
Anybody has any better algorithms?
Re: Multiplayer partial round-robin
Posted: 05 December 2021, 16:51
by Hardin2000
Does that work if the number of total player is not a perfect multiple of number of players per match?
Many times we create a tournament for 60 players but only 58 or 59 show up. Or someone quit just a few minutes before the tournament start.
Re: Multiplayer partial round-robin
Posted: 06 December 2021, 01:02
by dgjxqz
Yes, it always create matches equals to the number of total players (as oppose to swiss system which has total players divide by players per match) and everyone gets to play the number of games equals to the number of players in a single match.
If your tournament is 4 player per match, all matches will have 4 players. You won't end up with situation where some matches have 4 players and a few remaning matches have 3 players.
It only fails if you create a tournament of 6 players per match and 6 or less players signup.
Re: Multiplayer partial round-robin
Posted: 06 December 2021, 23:12
by Hardin2000
But that was my question.
What will happen with your system if only 19 players subscribe for tournament with 4 players games?
Re: Multiplayer partial round-robin
Posted: 07 December 2021, 01:00
by dgjxqz
Swiss system only generate 5 matches for 19 players where each plays once, hence you get 4,4,4,4,3 players for your matches. This system generate 19 matches for 19 players where each plays 4 times, hence you get 4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4 players for your matches. For round-robin, players aren't restricted to play only once per "round".
An example of the output, you can try the code yourself from your browser console. Note that your random seed wiil be different.
Code: Select all
(Index) 0 1 2 3
0 18 6 3 8
1 13 10 1 4
2 14 7 18 11
3 2 11 14 16
4 12 14 0 6
5 5 2 6 13
6 7 12 4 9
7 11 18 8 7
8 9 8 13 1
9 3 16 17 5
10 10 9 2 0
11 15 17 9 14
12 16 1 15 12
13 17 15 16 2
14 0 3 5 10
15 4 0 10 18
16 6 4 11 15
17 1 5 7 17
18 8 13 12 3
Re: Multiplayer partial round-robin
Posted: 14 December 2021, 04:15
by dgjxqz
This is a revised algorithm, it tries to avoid the same plauers, doesn't rely on PRNG, but isn't perfect.
Code: Select all
const ttl=9; // total participants
const ppm=4; // participant per match
let rnd=14; // number of rounds
const nct=Array(ttl).fill().map(q=>Array(ttl).fill(0)); // encounters
nct.forEach((j,k)=>j[k]=1/0); // avoid self
for(;rnd--;){
const mch=Array(ttl).fill().map(q=>[]);
for(let q=0;q<ppm;q++){
const pul=Array(ttl).fill().map((j,k)=>k);
for(;pul.length;){
const cdd=pul.pop();
const tgt=mch.reduce((j,q,k)=>{
q=mch[j].length-q.length;
if(q)return q<0?j:k;
const sum=q=>mch[q].reduce((j,k)=>j+nct[cdd][k]**2,0);
q=sum(j)-sum(k);
if(q)return q<0?j:k;
return j;
},0);
const cnt=q=>mch[tgt].reduceRight((j,k)=>{
nct[j][k]+=q;
nct[k][j]+=q;
return j;
});
if(mch[tgt].length>q){
cnt(-1);
pul.push(mch[tgt].pop());
}
mch[tgt].push(cdd);
cnt(1);
}
};
console.table(mch);
}