Calculate Rounds From Matchups

[cblaze22]

I am currently using the best fit algorithm to calculate my matchups and rounds.

https://www.devenezia.com/downloads/round-robin/rounds.php

I have the need to take these matchups and recalculate the rounds from the matchups in the exact order.  Is it possible to do this and if so how?  Any psuedocode would be great.

[Ian Wakeling]

Do you mean that starting with the n*(n-1)/2 possible pairings of n players you want to arrange them into rounds of play?

There may be alternatives, just start with the standard schedule from the cyclic algorithm and then randomize it.  You are free to apply a random permutation to the team numbers, for example:

(1 2 3 4 5 6 7 8)  ->  (5 8 3 7 4 1 2 6)

and the schedule will still have all the pairs once, but it will look different.

[wbport]

I've had this RR generator on the web for quite a few years: rrpair.htm.  It alternates White/Black or Home/Away until the players/teams meet the one with the highest even number (if even number of competitors), but that's unavoidable.

[cblaze22]

Does this take a list of matches and find the rounds?

[Ian Wakeling]

My solution gives you a way of arranging all possible matchups into rounds, and getting a different schedule each time.  Which is what I thought you were asking for.  

You could just assign the matchups randomly to rounds and then apply an iterative improvement approach, swapping pairs of matchups between rounds in order to improve the round balance.  This will work but it will be less efficient, for larger numbers of teams there may be a noticeable demand on CPU.

[cblaze22]

Do you think saving the a round per matchup is a better approach then calculating it on the fly.  Seems there is no set way to calculate the round on the fly.

[Ian Wakeling]

We are at cross-purposes I think.  Above wbport has implemented one way to calculate the rounds on the fly, the cyclic algorithm is another.   There is even some VBA code in this Excel file that you may be able to adapt.

[cblaze22]

From what I can see all these approaches are just taking a number of teams, then generates the matchups and doing the rounds at the same time.  My situation is I have AvB, CvD, etc already created.  I need to find round one for A,B,C,D and so on for the MATCHUPS already created.

Let's say I generated all my matchups using the balanced algorithm as my base and duplicating games for extra rounds from those games.  Say we have 6 teams but each team needs to play 10 games.

I generate all those games perfectly, and even have the rounds, however I dont save the rounds because later they can modify these games or add/substract ones.  I take all their matchups and want to refind the rounds from their matchups that were originally but find the rounds on the fly my putting the right matchups together.  However all my algorithms end up not fitting the match ups together.

[Ian Wakeling]

Can you give an example of some matchups that you are not able to resolve into rounds?

[cblaze22]

Here is a good example.

I currently have some code that tries to get matchups to fit each round.  I sometimes end up with 9vs10 twice because of this situation.

Round 1

1v2
3v4
4v6
7v8
9v10

Round 2

1v4
2v3
4v7
6v8
9v10 <--- incorrect already used

Now this isnt the correct order in my processing but you get the idea.  I used the best fit algorithm to find the matches and those matches per round are used.  I need to recreate those rounds with those matchups that could be randomly sorted.  

[Ian Wakeling]

I think you need to have a more sophisticated algorithm.  The simplest thing to do would be to consider the matchups in a random order, so do not always place 1 v 2 in the first position in the 1st round, rather the first matchup placed should always be selected at random.  Then if the algorithm gets stuck, as in your example, restart the process with the matchups in a different random order.  Keep going like this until you find a solution.

A more complex modification would be to consider back-tracking.   So when you discover that 9 v 10 is not allowed in Round 2, you remove the last matchup placed in Round 2.  Let's say that was 6 v 8. With that matchup gone, look for an alternative,  say 6 v 9, and then Round 2 can be completed with 8 v 10.  Of course you need to keep track of every step you have made, as you may need to back-track two or more steps in order to find a solution.

Personally I prefer a completely different approach.  I place all the matchups to be played into rounds at random,  then construct a criterion that penalises rounds that contain the same player two or more times.  Next evaluate all possible swaps of two matchups from different rounds and pick one that improves the criterion the most.   You may need to inject a little randomness into the choice of swap to prevent going around in circles.  In general terms this is the approach I am using in the Windows program here.

[cblaze22]

In regards to the random, I want to cut down the number of iterations as much as possible.  Im worried I could have extra iterations in play.

In regards to backtracking I am doing something like that already, however there seems I still run into the issue of games not ending up the same as the first fit algorithm.

The third one I would agree would work but that is where I am stuck.

I also sent you an email by the way.