Arimaa Forum - Print Page


    
      
        Arimaa Forum
        (http://arimaa.com/arimaa/forum/cgi/YaBB.cgi)
      

        Arimaa >> Events >> Floating multiple elimination analysis
        
(Message started by: Marty on Oct 15^th, 2013, 11:21am)

Title: Floating multiple elimination analysis
Post by Marty on Oct 15^th, 2013, 11:21am

is there any detailed yet compact description of the floating multiple elimination, its strengths and pitfalls? i am not aware of its use elsewhere, so i suppose it came from arimaa, but couldn't find any good resource on it.

there is the definition in the championships' rules, but that only describe the mechanisms. then there are discussions in the championships' rules threads, but they are lengthy and deal with many other topics regarding the tournaments.

i am especially interested in the minimal and maximal lengths of the FME tournament. for 8 players triple (8,3) elimination i found 8-10 rounds, then randomly got at an 11 round run. one try with 16,3 was 12 rounds long. my experiments weren't automated so i stopped at that.

i think i could develop a moderately reliable formula for the bounds or at least a script to find them, but if anyone already has the desired insight, no point in discovering it again.

guessing the document i am looking for doesn't exist, i've written a concept of my own ( mega.co.nz (https://mega.co.nz/#!dcoTzIQZ!TEmNCjKH7bmWqfEYM9dv20FS72wr0s8l2lMKzXDLIqw) ). it lacks in English and structure (see my excessive use of parentheses) and it is written from the point of real life board games tournaments, concerned with number of rounds and fate of the eliminated players, etc. but that's alright, i am not going to publish it anywhere (as of now) and it is to serve mostly as an additional material for discussion.

Title: Re: Floating multiple elimination analysis
Post by Marty on Oct 30^th, 2013, 6:17am

when one ignores pairing constraints, each round results change into distributing n_i / 2 losses among the n_i remaining players. number of losses needed to decide a winner is always between k (n - 1) and k (n - 1) + k - 1. (k = number of losses for elimination, n = number of players)

this creates a heuristic - long tournaments will eliminate players as soon as possible to play the least games in given number of rounds. short tournaments will follow the opposite.

it seems to me that then the longest tournaments occur when we always give the losses to the players with the most losses so far. this eliminates the lower half in k rounds, half of the remainder in the next k rounds, etc. When only two players, with 0 and k-1 losses remain, give the first one k-1 losses before the grand final.

this makes a formula for the upper bound of the required rounds: k log2(n) + k - 1

for the shortest tournament doing the opposite - awarding losses to the top players - creates a reasonable method. it takes 2 (k - 1) rounds to tie everyone at k - 1 losses, and then the rest turns into a simple knockout.

the formula for the lower bound of the required rounds: log2(n) + 2 (k - 1)

i haven't proved that the described methods indeed lead to the longest and shortest tournaments possible and the second one wastes k - 1 losses on the top player who can as well finish with 0. therefore it is unclear whether the formulae are the correct bounds. at the same time these methods are against the pairing constraints, which means the bounds are not tight. also i supposed n to be the power of 2

Title: Re: Floating multiple elimination analysis
Post by clyring on Oct 30^th, 2013, 6:54pm

I would intuitively/heuristically expect the number of rounds required given a fixed number of lives k and a pairing scheme that avoids pairing between brackets if possible to be asymptotically approximable with log₂(n)+(k-1)*log₂(log(n)) due to the relations between this pairing system and Pascal's triangle, but in practice I would expect this to not be very accurate at all except when n is extremely large.

Title: Re: Floating multiple elimination analysis
Post by aaaa on Nov 3^rd, 2013, 8:19pm

on 10/30/13 at 06:17:59, Marty wrote:

for the shortest tournament doing the opposite - awarding losses to the top players - creates a reasonable method. it takes 2 (k - 1) rounds to tie everyone at k - 1 losses, and then the rest turns into a simple knockout.

the formula for the lower bound of the required rounds: log2(n) + 2 (k - 1)

i haven't proved that the described methods indeed lead to the longest and shortest tournaments possible and the second one wastes k - 1 losses on the top player who can as well finish with 0. therefore it is unclear whether the formulae are the correct bounds.

This formula for the lower bound is wrong because of what you yourself are already pointing out here. A simulation strategy of keeping one player unbeaten while otherwise keeping as many players alive as long as possible, can give lower figures, even when the number of players is a power of 2. For a trivial counterexample, consider a sweep of a two-player match.

If there is a demand for simulation results for certain values, I can throw them on the wiki.