Algorithm problem: Order matches by difference between players

Dirk80 has asked for the wisdom of the Perl Monks concerning the following question:

Hello wise monks,

I have more an algorithm problem as a perl problem. I'm not really sure how to do it. Here the description of the problem:

I have a group of players. Every player in this group has to play against all other players in this group.

Let's say we have a group of 4 players. The best player in this group is titled with 1, the second best with 2, the third best with 3 and the worst player with 4. The goal is it that the good players play in the early round against the bad players. And the best players shall play against each other as late as possible. The same for the bad players. They shall play against each other as late as possible.

Here a possible result for this group

1-4 1-3 1-2
2-3 2-4 3-4
[download]

This means in the first round the best player (1) is playing against the worst player (4) and number 2 is playing versus number 3. In the second round player 1 is playing against player 3 and player 2 versus player 4. And in the last round the best 2 players play against each other and the bad players 3 and 4 play against each other.

But what am I doing if the group has 6 players, or 8 players or even 12 players?

The goal is it to find an algorithm so that all players in a group play against each other. And which assures that in the early rounds, the difference (e.g. first round best player should play versus worst player) between the players should be as big as possible and then in the late rounds the players with only small difference should play against each other.

The following code is working with 1, 2, 3, 4, 7 and 8 players. But I have massive problems to find a correct algorithm with for example a group of 6 players. My algorithm is then getting into an endless loop. I understand why, but I don't know how to prevent it. The problem is that at the end only combinations are available which cannot match. So the mistake was done in the early rounds.

use strict;
use warnings;

use Data::Dumper;

my @matches;
my $nb_players = 6;
my @rounds;
exit(-1) unless get_matches( $nb_players, \@matches );
exit(-1) unless get_rounds( $nb_players, \@matches, " - ", \@rounds );

print Dumper(\@rounds);

sub get_matches
{
    my ( $nb_players, $ref_matches ) = @_;

    my $odd_nb_players = 0;
    $odd_nb_players = 1 if( $nb_players % 2 );

    $nb_players += 1 if( $odd_nb_players );

    for (my $left_player = 1; $left_player < $nb_players; $left_player
+ += 1 )
    {
        for (my $right_player = ($left_player+1); $right_player <= $nb
+_players; $right_player += 1 )
        {
            push(@$ref_matches, {'left_player' => $left_player,
                                 'right_player' => $right_player,
                                 'diff' => $right_player - $left_playe
+r} );
        }
    }

    # replace not existing player with "bye" if group has an odd numbe
+r of players
    map { $_->{'right_player'} = 'bye' if( $_->{'right_player'} == $nb
+_players ) } @$ref_matches if( $odd_nb_players );

    return 1;
}

sub get_rounds
{
    my ( $nb_players, $ref_matches, $sep, $ref_rounds ) = @_;

    # handle 'bye' as a real player
    $nb_players += 1 if( $nb_players % 2 );

    my $nb_matches_per_round = $nb_players / 2;
    my $nb_rounds = $nb_players - 1;

    my @matches_sorted_by_diff = sort { $b->{'diff'} <=> $a->{'diff'} 
+} @$ref_matches;

    for( my $round_idx = 0; $round_idx < $nb_rounds; $round_idx += 1 )
    {
        my @players;
        my @forbidden_matches;
        my $found_idx;
        my $found_match;
        my $found_match_str;

        for( my $match_idx = 0; $match_idx < $nb_matches_per_round; $m
+atch_idx += 1 )
        {
            my $found;
            my $i = -1;
            for my $ref_match ( @matches_sorted_by_diff )
            {
                $i += 1;

                next if( ("$ref_match->{'left_player'}" ~~ @players) |
+|
                         ("$ref_match->{'right_player'}" ~~ @players) 
+);

                my $match_str = $ref_match->{'left_player'} . $sep . $
+ref_match->{'right_player'};
                next if( $match_str ~~ @forbidden_matches );

                $found = 1;
                $found_idx = $i;
                $found_match = $ref_match;
                $found_match_str = $match_str;
                push(@players, "$ref_match->{'left_player'}", "$ref_ma
+tch->{'right_player'}");
                splice(@matches_sorted_by_diff, $i, 1);
                push(@{ $ref_rounds->[$round_idx] },
                     $found_match_str);
                last;
            }

            unless( $found )
            {
                push(@forbidden_matches, $found_match_str);

                pop(@players);
                pop(@players);
                splice(@matches_sorted_by_diff, $found_idx, 0, $found_
+match);
                pop(@{ $ref_rounds->[$round_idx] });
                $match_idx -= 1;
                redo;
            }
        }
    }

    return 1;
}
[download]

Thank you very much for your help.

Greetings,

Dirk

Comment on Algorithm problem: Order matches by difference between players Select or Download Code

Replies are listed 'Best First'.
Re: Algorithm problem: Order matches by difference between players by wind (Priest) on Apr 18, 2011 at 17:59 UTC
To solve this problem assign the first seed to play last seeded player in the first round and against a higher seed each subsequent round. Then simply rely on the round-robin algorithm of rotating an array's values while keeping one static to ensure that everyone plays against each other: `use strict; use warnings; my $num_players = 6; my @players = (1..$num_players); push @players, 'bye' if @players % 2; # Even number my $num_rounds = @players - 1; for my $round (1..$num_rounds) { # Fold array to assign matches my @matches = map {join('-', sort @players[$_, $#players - $_])} ( +0..@players/2-1); # Print Results print "$round) " . join(', ', @matches), "\n"; # Rotate last position to second splice @players, 1, 0, pop(@players); }` [download] Results: `1) 1-6, 2-5, 3-4 2) 1-5, 4-6, 2-3 3) 1-4, 3-5, 2-6 4) 1-3, 2-4, 5-6 5) 1-2, 3-6, 4-5` [download] This works with any number of players and rounds.	[reply] [d/l] [select]
Re^2: Algorithm problem: Order matches by difference between players by Dirk80 (Pilgrim) on Apr 18, 2011 at 20:32 UTC
Usually I just vote positive. But this time I had to write a little post to say thank you for so many good answers in a very short time. I'm really impressed. I'm writing a lot of code which is not working for all cases. And you just write some lines of code and it is really working for every case.	[reply]
Re^3: Algorithm problem: Order matches by difference between players by wind (Priest) on Apr 18, 2011 at 20:53 UTC
One of my first jobs during the dotcom boom was a gaming website that ran tournaments and analyzed statistics. Coming up with algorithms for round robin, single, and double elimination tournaments was one of the first things I did. A more fun problem is to come up with an algorithm to page a double or single elimination tournament with a large number of seeds. You can of course just do it by hand, but it's more fun if you can configure how many rounds and pairings to show on each page. Glad we could help. - Miller	[reply]
Which is the oldest post in the monastery? by LanX (Saint) on Apr 18, 2011 at 23:00 UTC
~~Wow, Dirk80 you just wrote the 800000th post of the monastery!~~ Hmm I really thought id 100001 was the beginning since id 100000 is (kind of) a user profile. UPDATE: search form for some really old posts ?node_id=3989;nf=0;Wi;D;M, just hit search button! Cheers Rolf	[reply]
Re^3: Algorithm problem: Order matches by difference between players by Ghalko (Novice) on Apr 18, 2011 at 21:29 UTC
The reason I can think of why you were having specific problems with 6 is because it isn't a power of two. Having set up fencing brackets for tournaments this is definitely true for single elimination, but it might also be true for a round robin if you are essentially running it as a no elimination bracket. I bet you would have problems with 10, 12, 14, evens that aren't a power of two, and all n-1 of those numbers with your code. Just an idea really, sort of fun to think about, maybe extremely useful for any tournament above 8 or so.	[reply]
Re: Algorithm problem: Order matches by difference between players by moritz (Cardinal) on Apr 18, 2011 at 15:50 UTC
This matches pretty well what I would do manually: start with player 1, and assign her to the worst player. Then proceed with the second best, and assign it to the second worst etc. In the next iteration the best is assigned to the second-worst, thereby decreasing the "distance" by one. At each step I take a look if the "best choice" player is free, and if not, skip to next free player use strict; use warnings; # perl 5.10 only used for say() and infix // use 5.010; my $size = shift(@ARGV) // 6; for my $turn (0.. ($size - 2)) { my @players; @players[0..($size-1)] = ((1) x $size); for (0 .. ($size / 2 - 1)) { my $current = $_; $current = ($current + 1) % $size until $players[$current]; $players[$current] = 0; my $other = ($size - $turn - $current - 1) % $size; $other = ($other - 1) % $size until $players[$other]; $players[$other] = 0; say $current + 1, '-', ($other + 1); } say '=' x 10; } [download] It seems to work for size 6, haven't tested it for odd sizes. Update: I've just re-check the output and found that it repeats some pairings. While that might be fixable with a hash of already-seen pairs, I won't bother because there's a more elegant, working solution given in another reply. Perl 6 - second systems done right	[reply] [d/l]
Re^2: Algorithm problem: Order matches by difference between players by dwm042 (Priest) on Apr 18, 2011 at 16:32 UTC
On odd sizes, if you allow for the person whose "#", so to speak, has turned up to have a 'bye', then I suspect it works pretty well. In other words, if player 2 in a 7 player tournament has a bye in round 5, player 3 a bye in round 3 and player 4 a bye in round 1, and writing code to allow byes in odd sized tourneys, the same kind of logic as in the even case should fit. This chart might explain it better: 1: 7-6-5-4-3-2 2: 6-5-4-3-B-1 3: 5-4-B-2-1-7 4: B-3-2-1-7-6 5: 3-2-1-7-6-B 6: 2-1-7-B-5-4 7: 1-B-6-5-4-3 David.	[reply]
Re: Algorithm problem: Order matches by difference between players by dwm042 (Priest) on Apr 18, 2011 at 17:20 UTC
Just realized, the problem is trivial in all cases if you allow N rounds for N players. Just skip the round where "your number" comes up. For 6 Players in 6 rounds.. 1: 6-5-4-3-2-B 2: 5-4-3-B-1-6 3: 4-B-2-1-6-5 4: 3-2-1-6-5-B 5: 2-1-6-B-4-3 6: 1-B-5-4-3-2 For 5 rounds, 5 players.. 1: 5-4-3-2-B 2: 4-3-B-1-5 3: B-2-1-5-4 4: 2-1-5-B-3 5: 1-B-4-3-2 Don't know if this is exactly what the OP is looking for, but it reduces the tournament calculation to a count and lookup problem. David.	[reply]
Re^2: Algorithm problem: Order matches by difference between players by davies (Monsignor) on Apr 19, 2011 at 09:35 UTC
I think your algorithm is ideal for odd N, but I see an issue for even N. If you look at your 6 contestant matrix, in even numbered rounds, two contestants have byes. To take the 6 nations Rugby Union tournament as an example, it is played over five rounds, not 6, and all teams play on the same week-ends. Every Monday, all teams have played the same number of matches. This isn't to say that your algorithm doesn't work - it does - but this behaviour is an oddity that may not be acceptable. Regards, John Davies	[reply]
Re: Algorithm problem: Order matches by difference between players by davies (Monsignor) on Apr 18, 2011 at 16:45 UTC
It sounds to me as though you are trying to run a Swiss-system tournament. Various methods are described in the wikipedia link. My quick googling didn't find any Perl modules already written, but that doesn't mean they don't exist. Regards, John Davies	[reply]
Re^2: Algorithm problem: Order matches by difference between players by dwm042 (Priest) on Apr 18, 2011 at 17:58 UTC
Oh yes -- Algorithms::Pair::Swiss and Games::Tournament::Swiss are in CPAN. One thing about Swiss system is that it ranks players by their play in the tournament as well as their rating. That 2500 rated IM may end up playing with the experts if he starts losing in a big American Swiss.	[reply]
Re^2: Algorithm problem: Order matches by difference between players by dwm042 (Priest) on Apr 18, 2011 at 17:10 UTC
Not a Swiss. I thought that too, initially, but Swiss pairs /same scores/ by splitting them in half. It's not a best to worst matching. David.	[reply]
Re^3: Algorithm problem: Order matches by difference between players by davies (Monsignor) on Apr 18, 2011 at 17:58 UTC
Yes, you're right. I didn't read the OP carefully enough. But, if one exists and depending on how it's written, it might still be possible to use a Swiss module to solve this problem. At least some Swiss chess tournaments match scores but then match players by ranking, best v worst. It might be possible to use such an algorithm and insert dummy "scores" and use the ranking to do the rest. But that's putting even more constraints on my originally constrained idea. :-( Regards, John Davies	[reply]
Re^4: Algorithm problem: Order matches by difference between players by JavaFan (Canon) on Apr 18, 2011 at 20:40 UTC
Re^5: Algorithm problem: Order matches by difference between players by davies (Monsignor) on Apr 18, 2011 at 22:39 UTC
Some notes below your chosen depth have not been shown here
Re: Algorithm problem: Order matches by difference between players by dwm042 (Priest) on Apr 18, 2011 at 16:55 UTC
Ok, more thoughts... the odd case is trivial in the algorithmic sense. The pattern I've printed previously for N=7 should work for any odd N. The first half of the field of the even case is also trivial in the algorithmic sense. Player 1 will always have N-1 .. 2, Player 2 will be N-2 to 3, N-1, 1, Player 3 will be N-3 .. (N-1) .. 1, N-2, N-3 .. and all other players from 4 down to N/2 will be the same. The second half of the even case gets complicated, because in manual tests of the case of 8 I saw situations where patterns had to be adjusted because of prior use of a pairing. David.	[reply]
Re: Algorithm problem: Order matches by difference between players by JavaFan (Canon) on Apr 19, 2011 at 09:47 UTC
Question. Suppose you have 16 players, ranked 1-16. From your description, I deduce that you'd like player 1 play players 16, 15, ..., 2, and player 16 to play 1, 2, ..., 15. But what's the preference for the other players? If all players should start with playing against those who are furthest away from them in strength, half of the players should play against player 1 in the first round, and the other half against player 16. So, what's the preferred sequence of play for player 8? And for player 12?	[reply]
Re^2: Algorithm problem: Order matches by difference between players by Dirk80 (Pilgrim) on Apr 19, 2011 at 14:06 UTC
You are right. The preferred way would be that everyone plays against a player who is furthest away from strength. This was exactly what I tried to do. My algorithm was first getting all possible matches and also stored the difference between the two players. Then I sorted all matches after this difference and then tried to build the rounds by biggest possible strength difference. But I had a lot of problems and the algorithm failed for a lot of cases (e.g. 6 players). I looked at the results of the round robin algorithm and I have to say that the results are really good. Perhaps the sequence for player 8 or 12 is not as perfect as for player 1. But it is good enough for my purposes. And I'm not sure if it is possible to make it better. Because it is important that a player has never to wait (except when he is playing against a bye). For me it was the most important that the best players play at the end against each other so that it is like a final altough everyone played against everyone. I even found the round robin algorithm in wikipedia: http://en.wikipedia.org/wiki/Round-robin_tournament. So I think it is a common way to make a tournament according to this algorithm.	[reply]
Re: Algorithm problem: Order matches by difference between players by anonymized user 468275 (Curate) on Apr 19, 2011 at 14:41 UTC
It's not a swiss tournament, that's a truncation of a round robin tournament when there are too many players to play round robin (all play all). The OP scenario looks like a round robin being applied to each group. So the module for that would still be Games::Tournament::RoundRobin One world, one people	[reply]
Re^2: Algorithm problem: Order matches by difference between players by Dirk80 (Pilgrim) on Apr 19, 2011 at 18:42 UTC
You are right. I tried the module Games::Tournament::RoundRobin. It delivers the same result apart from the order of the rounds. The last round is the same as my first round, ... `use strict; use warnings; use Data::Dumper; use Games::Tournament::RoundRobin; my $schedule = Games::Tournament::RoundRobin->new(v => 6, league => [1 +..6]); print Dumper($schedule->wholeSchedule());` [download]	[reply] [d/l]


Problems? Is your data what you think it is?
	PerlMonks