Game.Tournament

Tournament construction and maintenance including competition based structures and helpers.

This library is intended to be imported qualified as it exports functions that clash with Prelude.

 import Game.Tournament as T

The Tournament structure contain a Map of GameId -> Game for its internal representation and the GameId keys are the location in the Tournament.

Duel tournaments are based on the theory from http://clux.org/entries/view/2407. By using the seeding definitions listed there, there is almost only one way to generate a tournament, and the ambivalence appears only in Double elimination.

We have additionally chosen that brackets should converge by having the losers bracket move upwards. This is not necessary, but improves the visual layout when presented in a standard way.

FFA tournaments use a collection of sensible assumptions on how to optimally split n people into s groups while minimizing the sum of seeds difference between groups for fairness. At the end of each round, groups are recalculated from the scores of the winners, and new groups are created for the next round.

Building Block A: Duel helpers

seeds :: Int -> Int -> (Int, Int)

Power of a tournament. It's defined as 2^num_players rounded up to nearest power of 2. type Power = Int

Computes both the upper and lower player seeds for a duel elimiation match. The first argument is the power of the tournament:

p :: 2^num_players rounding up to nearest power of 2

The second parameter is the game number i (in round one).

The pair (p,i) must obey

p > 0 && 0 < i <= 2^(p-1).

duelExpected :: Integral a => a -> (a, a) -> Bool

Check if the 3 criteria for perfect seeding holds for the current power and seed pair arguments. This can be used to make a measure of how good the seeding was in retrospect

Building Block B: Group helpers

groups :: Int -> Int -> [[Int]]

Splits a numer of players into groups of as close to equal seeding sum as possible. When groupsize is even and s | n, the seed sum is constant. Fixes the number of groups as ceil $ n / s, but will reduce s when all groups not full.

robin :: Integral a => a -> [[(a, a)]]

Round robin schedules a list of n players and returns a list of rounds (where a round is a list of pairs). Uses http:en.wikipedia.orgwikiRound-robin_tournament#Scheduling_algorithm

Tournament Types

data GameId

The location of a game is written as to simulate the classical shorthand WBR2, but includes additionally the game number for complete positional uniqueness.

A Single elimination final will have the unique identifier

 let wbf = GameId WB p 1

where 'p == count t WB'.

Constructors

GameId

Fields

bracket :: Bracket

round :: Int

game :: Int

Instances

Eq GameId

Ord GameId

Show GameId

data Elimination

Duel Tournament option.

Single elimation is a standard power of 2 tournament tree, wheras Double elimination grants each loser a second chance in the lower bracket.

Constructors

Single

Double

Instances

Eq Elimination

Ord Elimination

Show Elimination

data Bracket

The bracket location of a game.

For Duel Single or FFA, most matches exist in the winners bracket (WB) , with the exception of the bronze final and possible crossover matches.

Duel Double or FFA with crossovers will have extra matches in the loser bracket (LB).

Constructors

WB

LB

Instances

Eq Bracket

Ord Bracket

Show Bracket

data Rules

Constructors

FFA GroupSize Advancers

Duel Elimination

type Results = [Result]

Results in descending order of placement.

Only constructed by score once the last game was played.

results :: Tournament -> Maybe Results

data Result

Record of each player's accomplishments in the current tournament.

Instances

Show Result

player :: Result -> Int

Player associated with the record.

placement :: Result -> Int

Placement of the player associated with this record.

wins :: Result -> Int

Number of games the player associated with this record won.

total :: Result -> Int

Sum of scores for the games the associated player played.

type Size = Int

data Tournament

type Score = Int

type GroupSize = Int

type Advancers = Int

Tournament Interface

tournament :: Rules -> Size -> Tournament

Create match shells for an FFA elimination tournament. Result comes pre-filled in with either top advancers or advancers intersect seedList. This means what the player numbers represent is only fixed per round. TODO: Either String Tournament as return for intelligent error handling

score :: GameId -> [Score] -> Tournament -> Tournament

Score a match in a tournament and propagate winners/losers. If match is not scorable, the Tournament will pass through unchanged.

For a Duel tournament, winners (and losers if Double) are propagated immediately, wheras FFA tournaments calculate winners at the end of the round (when all games played).

There is no limitation on re-scoring old games, so care must be taken to not update too far back ones and leaving the tournament in an inconsistent state. When scoring games more than one round behind the corresponding active round, the locations to which these propagate must be updated manually.

To prevent yourself from never scoring older matches, only score games for which safeScorable returns True. Though this has not been implemented yet.

 gid = (GameId WB 2 1)
 tUpdated = if safeScorable gid then score gid [1,0] t else t

TODO: strictify this function TODO: better to do a scoreSafe? call this scoreUnsafe

count :: Tournament -> Bracket -> Int

Count the number of rounds in a given bracket in a Tournament. TODO: rename to length once it has been less awkwardly moved into an internal part

scorable :: GameId -> Tournament -> Bool

Check if a GameId exists and is ready to be scored through score.

keys :: Tournament -> [GameId]

Get the list of all GameIds in a Tournament. This list is also ordered by GameId's Ord, and in fact, if the corresponding games were scored in this order, the tournament would finish, and scorable would only return False for a few special walkover games. TODO: if introducing crossovers, this would not be true for LB crossovers => need to place them in WB in an 'interim round'

testcase :: IO ()