1
$\begingroup$

I am currently trying to find algorithm to minimize the total time of a tournament.

The game and tournament requirements are as below:

  • The game requires $2$ teams of $2$ players in each team (total $4$ players)
  • Each game takes about $8$ to $10$ minutes to finish

I found out that the perfect number of tournament players (to have $4$ player in the final game), must be $2^n$

However, it is very hard to always have registered players matching this perfect number. So, I can substitute computer players to complete the perfect number.

For example, if the number of registered players is $55$, the nearest perfect number is $64$, so I will substitute $9$ computer players.

What I reached so far is, the total runs (the number of games completed to reach to the final game in the tournament) can be calculated by:

$[$$log_2$ $n$ $]$ $-$ $1$ , where $n$ is the number of players to the nearest perfect number.

and the tournament finish time (minimum) can be calculated by:
$8$ $*$ $($ $[$$log_2$ $n$ $]$ $-$ $1$ $)$

The above does not seem to be the best solution, having $513$ players will take the same time ($72$ minutes) as of $1024$ players. Note: I cannot exclude any registered player from the tournament.

Is there a better approach to minimize the total time of a tournament?

Thank you.

Edit:
Each game can be calculated by the below formula:

$[[B + (T * P * U)] * R] + E$ , where:

$T$ is the time allowed for each player to respond and play, otherwise computer player will play
$P$ is the number of players, which is set to $4$ by default
$U$ is the number of turns (how many times each player will play in one round), which is set to $8$ by default
$R$ is the maximum number of rounds that the game will have (here is the key that will determine the total time of the game will take), this number cannot be less than $4$, it is impossible to finish a game in 4 rounds.
$B$ is the time to catch a bluff in the game, which is set to $10$
$E$ is extra time which happens only once, and it is set to $5$ by default

What I suggested for worst case is:
$[[10+(3*4*8)]*9]+5$ $=959$ seconds $=16$ minutes

$\endgroup$
  • $\begingroup$ You say each game takes "about $8$ to $10$ minutes to finish". Is this random for every game? $\endgroup$ – Riley Dec 12 '17 at 20:44
  • $\begingroup$ This is the average case based on another calculation. The game could finish in time between $5$ to $15$ minutes. $\endgroup$ – user3188039 Dec 12 '17 at 20:48
  • $\begingroup$ So are all times between 5 and 15 minutes equally likely to occur? Can a game only last for a whole number of minutes or any real number between 5 and 15? And are we trying to find an algorithm to minimize the average time of the tournament or the best case? $\endgroup$ – Riley Dec 12 '17 at 20:52
  • $\begingroup$ No, some games could finish in $5$ minutes and others in $15$ minutes. It depends on how fast the players will play and how smart the teams are (one smart team can beat non smart team in less time). The time could be any real number (for example $7$ minutes and $22$ seconds). We are trying to find the algorithm of max number of players with least time to finish the tournament (I hope to find algorithm for $1000$ players to finish tournaments in $60$ minutes) $\endgroup$ – user3188039 Dec 12 '17 at 21:02
  • $\begingroup$ It still seems that the problem is not well-defined. Do we know how fast/smart each player is? Is there some formula for how long a game will last given the players' stats? Or are we just to assume that we have no knowledge of how long any given game will last? How can an algorithm possibly guarantee that a tournament of 1000 players will only last 60 minutes if every game can last an arbitrary amount of time? What if every game lasts 70 minutes? $\endgroup$ – Riley Dec 12 '17 at 21:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.