Subject: 2-stage Side Events with Group Qualifications and KO Finals Date: Wed, 03 May 2000 22:24:32 +0200 From: Robert Jasiek Newsgroups: rec.games.go, fj.rec.games.go, japan.games.go A popular system for side events has been to have group qualifications and knockout finals. So far organizers had trouble to handle group sizes, rest players, round numbers, or seedings. After an example I give a complete basic theory that can be applied by event organizers. ******* EXAMPLE ******* Suppose you want to held a lightning tournament, e.g., on two evenings. On the first evening you have 5 hours for the qualifications and on the second evening you have 4 hours for the knockout finals. 10 minutes thinking time. You estimate the break between two games as 3 minutes. This makes roughly 23 minutes per game. So you can play at most 13 games on the first evening and 10 games on the second evening. You get 431 registered players. For the groups you set placement criteria within each group as points-direct_comparison-SODOS, e.g. In the qualifications you want to let everybody play every round. Thus you choose the groups to have an even number of players and the number of rounds one less. This gives 13 rounds and groups of size 14. You need 31 groups. 30 groups have 14 players, the 31st group has 11 players. You fill it up to 13 players by taking 1 player each from groups 29 and 30. Groups 29 to 31 then all have 13 players and 1 Bye. (Filling groups with players by mixed strengths, e.g., is well known.) In each group fix player 1 or the Bye and let rotate all other players after each game. Thereby you need exactly 13 rounds, not more. The groups provide places for all players and you will seed the top places first and so on until the finals' players are determined. (The latest seeded players with a low place are chosen randomly among all players with that place in some group.) At most 10 games for the finals would allow you to seed 2^10 = 1024 players. Oops, you don't have so many. So you play fewer rounds. How many? Well, qualifications are meant to eliminate some players, let's say slightly more than half the players. 431/2 = 215.5. This is a first hint but not good enough. We need a power of 2. Thus you seed 128 players and have a knockout with 7 rounds. That's it. ****** THEORY ****** Initial Parameters ------------------ n = # registered players R = max # rounds in group qualification stage S = max # rounds in KO finals For the numbers of rounds you consider your available time and the desired thinking time. Even Groups ----------- g = even group size r = played group rounds R odd => g := R+1, r := R R even => g := R, r := R-1 This always gives even groups and one round less to play than the group size. Number of Groups Z and Handling of Rest Players Y ------------------------------------------------- Z := round_up(n/g) If Z <> n/g, then a group of Y := n mod g rest players must be handled. ("mod" gives the integer rest of a division.) This rest group is filled up to g - 1 players. For this take 1 player each out of g - 1 - (n mod g) randomly chosen other groups. Then g - (n mod g) groups have one Bye each. Player-Group-Distribution ------------------------- Use either the mix strategy or the homogenous strategy. Mix: Let sink the highest ranked player into one group at a time. Homogenous: Fill a single group with the highest ranked players left. Round by round within each even group fix player 1 and let all others move one place clockwise. In an even group with a Bye fix it instead. KO Rounds s ----------- s := min { S, round_down(ld(n/2)) } Normally, you take s := S. However, sometimes you could play more rounds than are needed for a KO. Then the second parameter is an emergency measure ensuring that the maximal power of 2 less than half of n is taken. ("ld" is the logarithm in base 2.) KO Participants k ----------------- k := 2^s They will have to win their way through a binary knockout tree. Seeding ------- Pi; i=1..n is the place due to the placement conditions (like points-direct_comparison-SODOS) after round r of player i in his group. The same place within a group may be reached by more than one player. Places are numbered due to the order 1,2,..,g. Q := { Pi | i=1..n } is the qualification pool of all players' places. Example: All Pi (the places of the players): In group 1 with 6 players: 1 2 2 2 5 6 (here 3 players tie for place 2 even by SODOS). In group 2 with 5 players and 1 Bye: 1 2 3 4 5. Then you combine all groups and get the places (and their corresponding players): 1 1 2 2 2 2 3 4 5 5 6. If you want to seed 4 players, then the two first place players are seeded and two of the four second place players are randomly drawn. End Example. // seeding procedure // all players of the remaining top places are seeded // ,however, for the last free of all k finals' places // random selection is done among equal qualification // place getters c := 0; for (j:=1; j<=g; j++) { M := { q in Q | q = j }; c += |M|; IF (c<=k) {seed M; IF (c=k) break;} ELSE {randomly_select_and_seed k-c+|M| of M; break;} } -- robert jasiek http://www.snafu.de/jasiek/rules.html