Life In 19x19
http://www.lifein19x19.com/

tournaments as sorting networks
http://www.lifein19x19.com/viewtopic.php?f=8&t=4585		 Page 1 of 1
Author:  emeraldemon [ Fri Sep 02, 2011 2:53 pm ]
Post subject:  tournaments as sorting networks
I was thinking about the somewhat unusual format used for the Super Meijin tournament. In words it's like this:
A and B play. The loser of that match plays C. The winner of match 2 plays the winner of match one for the final. It occured to me that this could be represented as a sorting network:

Code:
--:-----:--
  |     |
--:--:--:--
     |   
-----:----- 


It's a bit hard to draw in ascii, hopefully it makes sense. At each switch, the winner goes up, loser goes down. I know there's quite a bit of theory about sorting networks, but I'm wondering if anything like that has been applied to tournaments, to find some theoretically nice tournaments. What do you all think?
Author:  Harleqin [ Sat Sep 03, 2011 2:53 pm ]
Post subject:  Re: tournaments as sorting networks
The championship preliminary in Hesse (a federal state of Germany) consists of 8 players who play three rounds to determine a complete ordering.

The final round of the national german championship is an 8 player round robin tournament with 7 rounds where each player plays each other player exactly once.

A man with a clock knows which time it is. A man with two clocks is never sure.
Author:  emeraldemon [ Sat Sep 03, 2011 4:29 pm ]
Post subject:  Re: tournaments as sorting networks
I guess I'm thinking something like this: assume you have 8 players, and enough time or money for 7 rounds. These are your constraints. What tournament structure is most likely to pick the best player? Round robin is one method. But you could also have 2 single elimination rounds followed by a best-of-5 final. Or break into 2 groups of 4, play 3 rounds of round-robin, and have the final 4 play 4 rounds.

If you made some assumptions about player strength distribution, it'd be pretty straightforward to simulate different tournaments and see how often the best player comes out on top.
Author:  Joaz Banbeck [ Sat Sep 03, 2011 5:15 pm ]
Post subject:  Re: tournaments as sorting networks
emeraldemon wrote:
...
Code:
--:-----:--
  |     |
--:--:--:--
     |   
-----:----- 

...


Just to clarify:

1) Each player is represented by a horizontal line starting at the left.
2) Each vertical line is a game.
3) Time goes from left to right.
4) The player coming out of the top right is the winner...

Is that correct?


EDIT: I was at the Royal Observatory Museum in Greenwich a few weeks ago, looking at all the centuries old scientific instrumentation...including the watches that cost a year's wages for the average person, and were accurate to within 1/2 hour per day.
Author:  emeraldemon [ Sun Sep 04, 2011 7:10 pm ]
Post subject:  Re: tournaments as sorting networks
@Joaz:
Yes, that's right. I'm basing it off of this:

http://en.wikipedia.org/wiki/Sorting_network
Author:  phillip1882 [ Thu Sep 15, 2011 10:11 am ]
Post subject:  Re: tournaments as sorting networks
hmm, interesting. i think any sort function will work, assuming your willing to have n*log2 n games.
if you really want a rigorous method, i'd reccomend the bitonic merge sort.
(this is closer to n*(log2 n)^2
http://en.wikipedia.org/wiki/Bitonic_sorter
Author:  emeraldemon [ Thu Sep 15, 2011 12:06 pm ]
Post subject:  Re: tournaments as sorting networks
Well, there are some important differences between sorting and a tournament. First, a game's outcome is nondeterministic: imagine sorting in a situation where sometimes comparing to elements gave the "wrong" outcome. Second, a tournament is not (usually) concerned with a complete ranking of the players: most of the interest is in finding the best player. Some tournaments will have a third place match, for example, but rarely is an effort made to distinguish 5th from 6th. One exception is a league-type tournament (such as for the Big 3 Japanese tournaments) where you not only want to know the best, but also the worst so that they can be demoted from the league.

I think maybe to start it's best to come up with a simple framework, something like:

1) All players have a hidden (true) ELO rating.
2) The best tournament structure is the one with the highest likelihood of choosing the best player as the winner of the tournament, staying within the constraints (number of matches/rounds).
Author:  phillip1882 [ Fri Sep 16, 2011 11:19 am ]
Post subject:  Re: tournaments as sorting networks
for an 8 player, 7 round tournament, i don't think you can do much better than the following:
Code:
--:---------------------:---:------:------------:------:------------:---
  |                     |   |      |            |      |            |
--|--:---------------:--|---|--:---|--:---------|--:---|-----:------:---
  |  |               |  |   |  |   |  |         |  |   |     |
--|--|--:---------:--|--|---|--:---|--|--:------:--|---|--:--|------:---
  |  |  |         |  |  |   |      |  |  |         |   |  |  |      |
--|--|--|--:---:--|--|--|---:------|--|--|--:------:---|--|--|--:---:---
  |  |  |  |   |  |  |  |          |  |  |  |          |  |  |  |
--|--|--|--:---|--|--|--:---:------|--|--:--|---:------|--|--:--|---:---
  |  |  |      |  |  |      |      |  |     |   |      |  |     |   |
--|--|--:------|--|--:------|--:---|--|-----:---|--:---:--|-----|---:---
  |  |         |  |         |  |   |  |         |  |      |     |   
--|--:---------|--:---------|--:---:--|---------:--|------|-----:---:---
  |            |            |         |            |      |         |
--:------------:------------:---------:------------:------:---------:---

after the first round, it alternates between the top 4 playing the bottom 4, and the top 4, bottom 4 playing against eachother. this gives players a chance to come from behind if they win 2 in a row, but also severely punishes players for losing against a bad player.
Author:  Laman [ Fri Sep 16, 2011 12:48 pm ]
Post subject:  Re: tournaments as sorting networks
phillip1882 wrote:
for an 8 player, 7 round tournament, i don't think you can do much better than the following: ...

but with 8 players and 7 rounds you should get round robin anyway, don't you? (sorry, i don't know much about sorting networks, that's just my assumption)
Author:  emeraldemon [ Fri Sep 16, 2011 1:31 pm ]
Post subject:  Re: tournaments as sorting networks
Certainly a round-robin would also be 7 rounds. The question is, which tournament is more likely to end with the best player in first place?
Author:  perceval [ Sat Sep 17, 2011 12:48 pm ]
Post subject:  Re: tournaments as sorting networks
slightly off topic: instead of sorting network you can consider more generally trying to apply a sorting algo to a set of players.
But something implicit in tournaments but not in sorting algorithms is that you try to have everybody have the same number of game with the exception of a few bye (meaning that you want an heavily parrallelizable algo: so sorting networks are indeed good candidates, but a decent tournament model should maximise parrallelism before all else);

Imagine applying a standard selecting algo to a tournament of 100 player when you want to know the top 3 to qualifwy them to an event.
apply quickselect:
you select a random player, then make him play against everybody else;
Then if more than 3 players have beaten him, select a random player amongst those that beat the first one and make him play against all of those that beat the first one; Those that have been beaten the first time are out (if more than 3 ar beaten the first pivot)
rince and repeat until exactly 3 players have beaten your pivot.
That would be a pretty dumb tournament model :mrgreen:

back on the topic;, i dont think there are been studies of the effects of errors on the comparison and the resilience of sorting algo to that ?
Page 1 of 1 All times are UTC - 8 hours [ DST ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/