Use of seeding programs
This document describes the seeding software written by Hans van Staveren. Let me start by immediately saying that these programs are tools, meant to be integrated into wider range software, or used by people not afraid of CSV files and DOS windows. There is no user interface whatsoever. That should get the disclaimer out of the way…
The target of this document is a tournament director with a reasonable amount of skill in the use of computers. If you get nervous by a prompt in a DOS window, please ask outside help.
The process of seeding for a tournament actually is divided into two steps.
1. Making groups of contestants, of similar average strength, and balanced in other criteria, such as country for example
2. Numbering the contestants in these groups to avoid late meetings of same criteria contestants, such as country
These two steps are implemented by the two main programs, called seeding and numberlines.
Both programs read from standard input a file containing some numbers at the start followed by a list of contestants and write on standard output a list of contestants in a different order. If you don’t know what I mean by standard input or output a short example. Suppose the input of the program seeding is contained in a file called input.txt, and you want the output written to a file called output.txt, then in a DOS window(or of course Unix, Linux or whatever) you type : “seeding <input.txt >output.txt” and the program will do it.
The information about contestants is always in the same format: a comma separated list of four values:
So as a simple two line example:
2345,Bocchi – Duboin,1,Italy
7654,van Staveren – Beks,999,Netherlands
The output of the programs is in lines of the same format.
The purpose of the program is to take all contestants for a tournament, and divide them into groups on the basis of two criteria: strength, and other. The groups need not be the same size. The program will take care to make all groups of roughly the same average strength, and will within this limitation try to balance the other criteria over the groups. So if you use country as the other criterion, and the file contains about 30% Polish pairs, the program will try to make each group contain roughly 30% Polish pairs. To make this possible the program needs some leeway in the strength. There should be a number of contestants of the same strength. If not, for example you have 100 contestants with strengths from 1 to 100, the program cannot balance. It is suggested to have no more than about 5 different strengths. If you use seeding to seed a semi-final of say 60 pairs into four groups of 15, based on qualifying stages, you could give the first 4 pairs strength 1, the next 8 pairs 2, the next 16 pairs 3, the next 32 strength 4. This will give a good seeding, and gives the program room to balance the countries.
Actually, the way the program seeding was written, it can balance not only on one, but on three other criteria. Why I did that I cannot remember anymore. It seemed a good idea at the time. So seeding actually accepts lines for the contestants with 6 fields instead of 4. As far as I know nobody uses this, and furthermore numberlines cannot cope with that. Should you find a use for it I would like to be informed.
Now for the input format of seeding. The program needs a list of numbers:
So for the example of the semi-final above the input file will start with 5 numbers:
And this will be followed by a list of 60 contestants.
As I have said, the groups need not be the same size. Suppose you have 56 contestants, and wish to seed for 5 groups of 11, and a pivot for the Howell. Then the input would be 6 1 11 11 11 11 11, but each number on a separate line. The effect of a group of 1 by the way is that it will get an average strength contestant.
After seeding is run the output will be the list of contestants in such an order that if you pick your groups from it from the top you get the desired groups. So in the second example above the first contestant will be the pivot, and after that there are 5 groups of 11 contestants.
The order within the groups is basically not guaranteed, although in the current implementation the contestants are ordered by strength. This cannot be relied upon.
The second phase of seeding is numbering the contestants within the group. You can do that by randomizing for a simple tournament, but you can also let numberlines do it for you. The function of numberlines is to take a description of a movement, and a bunch of contestants, and number the contestants in such a way that contestants having the same criterion will meet each other at the earliest opportunity. If you run a one session tournament it is easy, if it is multi session you have to make a decision. If you want the pair numbers in the group the same for all sessions, you must run numberlines for the final session and backtrack from there. You can also run numberlines for each session, to get early meetings in all sessions, but that gives pairs different numbers per session, and contestants(and sometimes even organizers) tend not to be able to cope with that. The decision is yours.
It must be stated here that numberlines knows nothing about movements. The good news is it can deal with any movement, the bad news is that you have to specify in awful detail what the movement looks like. Simple movements, like a Mitchell give numberlines an easy task. It will be finished in a split second and give absolutely perfect results. But endless barometers for example are more difficult. The program will take more time(it is currently set to take a maximum of 15 minutes!) and the results, although reasonably good, will still have countrymen meeting later than you like. This is unavoidable, these movements are intrinsically difficult in this respect.
Ok, what does the input to numberlines look like? Again, it is a series of numbers followed by the lines of the contestants. The numbers:
Let me give a simple example, say a Howell 8:
1 8 2 7 3 6 4 5
2 8 3 1 4 7 5 6
3 8 4 2 5 1 6 7
4 8 5 3 6 2 7 1
5 8 6 4 7 3 1 2
6 8 7 5 1 4 2 3
7 8 1 6 2 5 3 4
The number of rounds is 7, there are 4 meetings per round, there is one group of size 8. In the first round there is a meeting between pairs 1 and 8, 2 and 7, 3 and 6 and finally 4 and 5. Each line codes the meetings for one round.
Take this bunch of numbers and follow it by 8 lines for the contestants, and numberlines will put them in the best order.
Suppose one of the players is in a wheelchair, and you want them to be the pivot, then the first 4 numbers would become “7 4 2 7 1” so now there are two groups, of size 7 and 1, and the program will renumber within the group from 1 to 7, but pair 8 will stay pair 8.
In a Mitchell movement you would have two groups of equal size. Remember that in a Mitchell with 22 pairs the NS pairs will be numbered 1-11, and the EW pairs 12-22. The program is very general, and will do what you tell it. So please tell it what you want…
The program has been used with individual movements too. In an individual you either have 4 or 6 meetings per table per round, depending if you count your partner. Especially with a big movement the number of numbers becomes staggering.
The program numberlines can take a while to run. It gives progress messages while it does so. The below example is from a run for a 72 pair endless Howell. Eventually it finds a best result with the last same-country meeting at round 44 of 71. The notation 46/7685 means the last round with same-country meeting is 46, and some sort of sum-of-square is 7685. If the latter number becomes lower it means other same-country meetings before round 46 were closer to the beginning. Eventually the program did close to three million iterations to find this. Faster computers will do more iterations, the limit is on clock time. Currently 15 minutes.
At try 1(51840) round
59/13006 beats 1000000/1000000
At try 2(51840) round 56/7540 beats 59/13006
At try 968(51840) round 46/6689 beats 46/7865
At try 5352(51840) round 45/8807 beats 46/6689
Extending search to 53520 tries
At try 408897(2045210) round 45/5739 beats 45/5795
Extending search to 2862279 tries
At try 476020(2862279) round 44/7786 beats 45/5739
Found best possibility at try 476020(2862279), score 44/7786
There are a couple of auxiliary programs to generate movements. These were mainly used in testing this software, but they could prove useful.
As it is currently written numberlines tries to get all meetings by contestants in the groups as early as possible, without regard to the group. Sometimes there are suggestions that contestants of a certain group must meet earlier than other groups. This could be accommodated with a slight alteration to numberlines but that alteration will only be done on request.
This set of programs can solve problems for tournament organizers. This is not easy stuff, but can be very useful if you know what you are doing. I had fun writing this, and will not charge for any use. I would consider it polite if anybody using this software would let me know what for, and into what software they are integrating it.
Suggestions, problems, or other reactions can go to
Hans van Staveren <firstname.lastname@example.org>