Ian Wakeling

Eric, Generally these sorts of problems are too large to attempt to evaluate all possible schedules and pick the best, so an optimisation approach is required. You could perhaps try an iterative improvement approach as follows: First plan out the number of games, so for 10 players there would be 3 games per week giving 99 (11 x 3 x 3) slots in which to schedule players. Next decide who is going to play how often, for example player 1 could play 9 times, while players 2 to 10 could play 10 times each. Fill a schedule at random so the players play this many times each. Now look to make swaps of two players from different games to improve the schedule a little, and keep making such swaps until the schedule can no longer be improved. The hard part is to define a criterion to measure how good a schedule is, and so decide which swaps are good to make, by evaluating it before and after. The criterion needs to measure the balance of the schedule in terms of the number of times each player plays with each other and it also needs to penalise having the same player twice in one week, as clearly that is impossible. For the player balance you could use the frequency matrix that counts the number of times each player occurs together in the same game as each other player; the lower the sum of squares of the elements in this matrix, the better the balance should be. There are complications, you may want to restart many times with new random schedules as each run is only likely to find a local optimum, alternatively you need a strategy to avoid getting stuck at a local optimum by making the algorithm move away and also stopping it from going back. There are other approaches possible, for example there are constraint programming languages which you might be able to use to solve the problem. Ian.
