Author |
Topic: Floating multiple elimination analysis (Read 3554 times) |
|
Marty
Forum Junior Member
Arimaa player #7639
Gender: 
Posts: 10
|
 |
Floating multiple elimination analysis
« on: Oct 15th, 2013, 11:21am » |
 Quote  Modify
|
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 ). 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.
|
|
 IP Logged |
(\__/)
( O.o)
(> < )
This is Bunny, The Great Emperor. Copy Bunny into your signature to help him on his way to world domination.
|
|
|
Marty
Forum Junior Member
Arimaa player #7639
Gender:
Posts: 10
|
|
Re: Floating multiple elimination analysis
« Reply #1 on: Oct 30th, 2013, 6:17am » |
Quote Modify
|
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
|
|
IP Logged |
(\__/)
( O.o)
(> < )
This is Bunny, The Great Emperor. Copy Bunny into your signature to help him on his way to world domination.
|
|
|
clyring
Forum Guru
Arimaa player #6218
Gender: 
Posts: 359
|
|
Re: Floating multiple elimination analysis
« Reply #2 on: Oct 30th, 2013, 6:54pm » |
Quote Modify
|
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 log2(n)+(k-1)*log2(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.
|
| « Last Edit: Oct 30th, 2013, 6:55pm by clyring » |
IP Logged |
I administer the Endless Endgame Event (EEE). Players welcome!
|
|
|
aaaa
Forum Guru
Arimaa player #958
Posts: 768
|
|
Re: Floating multiple elimination analysis
« Reply #3 on: Nov 3rd, 2013, 8:19pm » |
Quote Modify
|
on Oct 30th, 2013, 6:17am, 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.
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print