Entry

3

bumps

Tournament Coding [Seeding Placement Problem]

Posted on Jul 8th 2010, 20:28 by clux :: 3 Comments

As a small effort in self-gratification after finishing uni, I have been looking into getting tournament scheduling possibilities coded into clux.org. Initially, I planned on doing this last year before it went live by hooking it into the already unreasonably complex (for this site anyway) event system - which you can only see by registering - but it turned out to take a little more mental effort than I expected. In particular, the problem of how to order seeds into the tournament bracket seemed a bit random. I think it's worked out now however, so I thought I'd share. Venture on if that interests you.

Oh, and my custom $\LaTeX$ renderer is installed for the maths geeks (so for this site: myself), so all maths is now properly rendered in cool transparent white font gifs. As a maths graduate (which feels awesome), this is pretty much a necessity!

System from BlizzCon (n=3)

The seeding is the correspondence $\{p \mid player\} \leftrightarrow \{1,2,\ldots,2^n\}$ where the number $k(p)\in\{1,2,\ldots,2^n\}$ is the estimated ranking for player $p$ , i.e. player $p$ is expected to beat player $q$ if and only if $k(p) > k(q)$ . The main problem is how to sort the players in the first round so that the the best players meet as late as possible (depending on their skill) in the tournament. The image below illustrates this for $2^3$ players. Formally we say:

Defn. If there are $2^n$ players in the tournament then the ordering is proper if the following hold.
1. If the seeding is perfect (perfectly predicts the match outcomes) then only the $2^{n+1-k}$ top seeded players are left in round $k$ .
2. In each round the sum of the seeds in each match is constant.
3. The even seed in each match is placed at the bottom.

canonical n=3 bracket

It's a bit much to assume that seedings are perfect, but the seeding above needs these three conditions to generate the analogous binary tree in $n$ dimensions, so we will use them. Besides, condition 2 does sort of provide some loose similar quality guarantee: the lower the sum, the most likely the better the games. The image above fills out what will happen in an eight player tournament if the seeding is perfect.

Knowing that it was these three properties that we wanted, we could at this point just generated the next level in the canonical tree successively until we got to the desired level to (i.e. make an arbitrarily large tournament system), but this would have been inefficient and a bit tedious (compared to finding patterns in numbers at paper, but that might be subjective). I tried first to find a system in the sequence $\{(1),(1,2),(1,4,3,2),(1,8,5,4,3,6,7,2),\ldots\}$ , but this turned out to be very fruitless. Having ivc over, I explained the problem to him and we stared at it for a couple of hours (because that's just the kind of inviting friend I am).

Turns out the key was to look at the match numbers $1,\ldots,2^{n-1}$ by ordering from the top in the brackets. I.e. match 1 is 1 vs. 8, match 2 is 5 vs. 4 etc. The major clue here is that in a match number that is a power of two, the even numbered seed in that match is also a power of two. In fact match $2^k \mapsto 2^{n-k}$ , so the hard part is interpolating this function for general match numbers.

The system becomes clear first when we look at a full 32 player tournament i.e. $n=5$ . In the interests of fully testing out the LaTeX, I would ideally write this out, but tables are a bit of a pain in TeX, and I have this paper anyway.

canonical n=5 bracket

This is expanded uniquely using the three defined properties and the smaller bracket above. The match numbers in the first round are written on the left. Notice that the top players all follow diagonal paths when they reach vastly inferior players.

system for n=5

The system comes from decomposing the match number $i$ as $i=2^k + l$ where $k = floor(\log_2{i})$ . If we write the even seed as powers of two then they display a binary counting system going up between match numbers that are powers of two. In fact, it's the binary representation of $i-2l$ that is required, so let $c_j = bit_j (i-2l)$ . We can then verify the final function (sending match number to the even seed in that match).

$\displaystyle 2^k + l \mapsto \begin{cases} 2^{n-k}, \mbox{if }l=0 \\ 2^{n-k-1}+2^n \sum_{j=1} 2^{-j}c_j, \mbox{if }0<l<2^k.\end{cases}$

Pretty cool for something as seemingly as simple as a tournament system huh. Here is a PHP function that calculates this function given the match number and the number $n$ . If the maths is unclear, that should help.
```
function seeds_from_match_nr($match,$n) {
  $k = floor(log($match,2));  //highest power of two one can subtract
  $l = $match - pow(2,$k);     //now $match = 2^k + l, where 2^k + l < 2^{k+1} i.e. l <  2^k
  
  if ($l==0) $seedA = pow(2,$n-$k);
  else {
   $C = array_reverse(str_split(decbin($match - 2*$l))); //binary representation of i-2*l
   $seedA = pow(2,$n-$k-1); //first term
   for ($j=0; $j < count($C); $j++) $seedA += pow(2,$n-$j-1)*$C[$j]; //array starts at zero not 1
  }
  $seedB = pow(2,$n) + 1 - $seedA; //sum of seeds is constant in each round
  return ($seedA%2==0) ? array('playerU'=>$seedB,'playerD'=>$seedA): array('playerU'=>$seedA,'playerD'=>$seedB);
}
```
Note the last line positions the even seed at the bottom to make sure we are following the defined convention.

Fun project this. Will hopefully get the tournament system up and running properly by next week. If I know you in some game, register and you might be destroyed later. : )

Oh, and since this is one of my few serious posts I'd appreciate if you keep comments on topic for this one.

Addendum:
Python code:
```
def even_seed_from_match_nr(i, n): #match_nr, log2(participants)
    #decompose i = 2^k + r where 0 <= r < 2^k
    k = int(math.floor(math.log(i,2)))
    r = i - (1<<k)
 
    if (r==0): return 1<<n-k

    nr = bin(i-2*r)[2:][::-1]
    return int(nr,2) << n-len(nr) | 1 << n-k-1
```
One of the crazier things I've written in python. And as such, it needs a few notes, especially on the non-zero r (denoted as l earlier in doc) case:
nr = binary of i-2*r, remove 0b part of string, reverse binary rep, then we create int from binary, shift n-k and add in leading term.
However, nr should be k bits, so we need to shift more if not (when reversing leading become trailing) so must shift extra len(nr)-k bits.
Without the compensation for extra zeroes the return wouldve looked like this:
```
return int(bin(i-2*r)[2:][::-1],2) << n-k | 1 << n-k-1
```
Insane.

Untagged

Comments

No comments.
0

ivc
2 years ago

Reply
Excellent! Like the thoroughness and interstitial Latex rending. Was fun working on the issue.
0

clux
2 years ago

Reply
It was! Thanks for helping figure it out! And yeah, the latex looks awesome now, I'm really happy with it.

Post a comment

Entry

3

bumps

Tournament Coding [Seeding Placement Problem]

Untagged