Hi! This is the homepage of drawnneal, a piece of free software that can help you create optimized draws for your tournament.

If you are instead looking to generate schedules for appointments, have a look at the related software appoinneal.

If you only need a simple, one-venue round-robin draw - just try the online draw maker, which is also free software (available with documentation here).

Otherwise please read the following notes and contact me in case of question.

GETTING DRAWNNEAL

The most recent version of drawnneal, 0.6, is available from the Sourceforge project page here.

WHAT DRAWNNEAL DOES

Imagine you were to create a draw for, say, a student debating tournament. The tournament will be made up of a number of rounds which will be spread over the year. For each round you'll possibly have a number of venues. You want your teams not to have to travel too far, while you do need to prevent pairs to be repeated. It'd be unfair if some teams were facing strong teams in each and every round while others had a much less difficult time. Teams new to the tournament might urge you to give them debates against other newbies for the first rounds. And if somehow possible you would also like to equally distribute sides (proposition/opposition in debates, black/white in chess, whatever else).
The problem you will be facing is indeed a complex one. No self-respecting human could ever try all possible options in order to optimize the draw. But that's, after all, what we have computers for ;)
Drawnneal will create and optimize such draws using a simulated annealing algorithm. Draws are rated according to their compliance with the criteria named above and slight changes are applied to them, in the beginning possibly even making them worse, then slowly but surely improving them to something close to a global optimum. Your draw will be made in no time (well, almost) and better than any human could ever make it.

BUILDING DRAWNNEAL

You just have to compile drawnneal.cpp using a c++ compiler. For typical GNU/Linux systems you'll probably be using gcc/g++ and a simple

make

will suffice. If you happen to have a different compiler installed please see the appropriate documentation for how compile 'drawnneal.cpp' into an executable 'drawnneal'.

RUNNING DRAWNNEAL

Drawnneal, I'm afraid, has no graphical user interface. For this reason all of the following presupposes that you are running a terminal, the working directory being the drawnneal source directory.

A simple

./drawnneal

will start drawnneal in interactive mode. You will be asked a couple of things about all the days your tournament will have (days consist of a number of rounds with fixed venues, not necessarily limited to one day), the rounds and venues and all the teams. Rough estimations of the travel distances should suffice. For teams that need to be at a specific venue for a specific day just enter very high travel distances for all the other venues on that day in order to penalize them being sent to another venue.

RUNNING DRAWNNEAL SMARTLY

As you might have noticed running drawnneal in interactive mode does not exactly meet today's standard of user interfaces. So that's the reason I recommend the following, even more low level method of entering your data. It doesn't really meet today's standards either, but for me it does the trick.

Create a file named 'input.txt' and fill it with the following lines (only numbers or strings for team / venue names!)

I) Teams and Days

01: number of teams
02: number of days (= groups of rounds with constant venues)
03: number of experience levels for fairness optimization, 1 for don't use (then skip lines concerning experience levels); the higher the level, the more experiences a team
04: level up to which teams are considered as beginners and therefore get easier matches in first rounds (0 for don't use)

This is the general structure of your draw. For instance, if you want 14 teams, your tournament has 3 distinct parts, you want to use two experience levels the lower of which is for beginners you may write:

14
3
2
1

The next section deals with

II) Venues and Rounds

This section contains loops for each day, venue and round:

D01: number of venues for day i
D02: number of rounds on day i
V01: name of venue j on day i
R01: type of round k at venue j on day i; rounds can have two different types (e.g. in debating: prepared/impromptu) marked by '1' or '2'; in case you don't care, just pick '1'
V02: number of teams at venue (except for last venue of the day)

So if for the three days you want to have the first will have two venues called 'Atown' (6 teams) and 'Btown' (the rest), the second will be entirely placed in 'Capital City' and the third one shared by 'DTown' (4 teams), 'ETown' (6 teams) and 'FTown' you will need the following lines. Note how for each round there is a '1' or '2' saying whether the round will be prepared or impromptu and that for the last venue of each day the number of teams need not be specified.

2
2
Atown
1
2
6
Btown
1
2
1
5
Capital City
1
1
2
2
1
3
1
Dtown
2
4
Etown
2
6
Ftown
2

III) Teams

The third section will contain data about each team:
T01: name of the team
T02: experience level, only if limit>1 specified above integer number between 1 and the limit specified above
T03: distance to each venue in km, in the same order as venues were entered above
T04: number of teams this team shouldn't be paired against
T05: numbers of these teams this team shouldn't be paired against, as you entered them, between 1 and the total number of teams

So as we have 14 teams in our example and six venues, this is how the section might look:

Atown Aces
2
1
5000
200
100
150
300
0
Btown B-ginners
1
5000
1
100
130
20
200
0
Capital Captains
2
100
170
1
300
220
150
1
4
St. Elsewhere Eagles
2
120
40
100
300
450
220
0
[... and so on for the rest of the 14 teams ...]

Please note how the experience level is picked from either '1' or '2' because that was the limit we specified. Also note that we gave extremely high distances for the teams from Atown or Btown to the other venues in the first round when they had a venue in their own town (where they should by all means stay) but still haven't used a 0 distance (you should never do that).
We have excluded the pairing of the Capital Captains against the St. Elsewhere Eagles (therefore the 1 and 4 in the closing lines of the Captains). Something like this might be reasonable in a couple of situations, e.g. if you're completing on a draw that's already been going for a few rounds or have some teams that shouldn't meet for other reasons. Usually, you would just give a 0 on the line after all distances and it'll all be fine.

IV) Random Seed

The output of drawnneal will only be fake-random, meaning that starting with a certain integer and unchanged parameters the programm will always create the same draw. The last line of your 'input.txt' will contain that integer. You may as well simply pick '1', your birth year or the outcome of a good old roll of the dice. For our example we took a very meaningful number to do that job for us:

42

V) Finally running drawnneal

That's it. If you call drawnneal with the command line

./drawnneal < input.txt

your parameters will be read and the draw should be optimized. If you want to save your output directly to a file you may as well call

./drawnneal < input.txt > output.txt

In case you want to create several different draws, make sure to for each of the draws change the random seed in your 'input.txt' first.

HACKING DRAWNNEAL

You may change some of the internal parameters of drawnneal by editing the source file and recompiling (with a simple 'make'). This is less difficult than it may sound and it might help you create even better draws.

i) annealing parameters

You can change the parameters thot (initial temperature, default: 10.0), tfactor (factor by which temperature is multiplied with each step, should be lower than 1.0, default: 0.999998) or freeze_timeout (number of unsuccessful steps before draw is considered optimized, default: 10000) to change the annealing process.

ii) rating parameters

How the different criteria mentioned are judged in comparison depends essentially on the penalties for deviation from the ideal configuration a draw gets. You can change either of the 'malus' factors (repeatpairmalus, unequal_p_malus for unequal side distributions, unequal_ip_malus for unequal side distributions for the two different kinds of rounds, newteamunfairnessmalus for hard draws for new teams in the first rounds, generalunfairnessmalus for unequal distribution of hard draws) and see what happens.

iii) rating procedure

Deeper changes to the rating procedure can be made by editing the function 'double rateDraw'. Take care :)

COPYING AND DISTRIBUTING DRAWNNEAL, LEGAL STUFF

This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

CONTACTING THE AUTHOR

Drawnneal has been written an is maintained by Daniel Gruen. Don't hesitate to contact me to send comments, bug reports, wishlists or even money ;)