Certification of Tournament Pairing Software

Running Chess Tournaments
21

In that case, it would make sense to eliminate Rule 29 entirely, and simply have Rule 27, with some wording that recognizes that drops to lower score groups, interchanges between halves of score groups, and transpositions within halves will be necessary to deal with score groups that have odd numbers of players, players who have previously met or who otherwise may not be paired, and color equalization and alternation, but that drops, interchanges, and transpositions should be kept to a reasonable minimum.

That would be good in many ways, because it would open the door for computer pairing programs to use more advanced algorithms that could not really be done with cards, such as Edmond’s algorithm or the Gale-Shapely algorithm.

Today, Rule 29 is the worst of all possible worlds, in that it blathers on and on in its hand-waving way, but does not present a deterministic algorithm, while at the same time being specific enough as to make it questionable whether potentially superior pairing approaches such as weighted matching or stable roommates are compliant.

22

The rule book was written for human tournament directors.
Expecting that to be easily translated into computer specs is surrealistic.

Just in case no one believed that you really were a computer programmer, this should prove it. Only a programmer working in the vacuum of computer’s binary world would try to change the business when he finds it too difficult to write a program that models the business. :unamused:

23

Tim, not only a programmer. A mathematician could as well, or even an engineer.

There are a couple ways to define problems:
(1) In terms of objective. “This is how we evaluate a given pairing, so in a particular tournament situation, we find the best pairing according to our evaluation function.”

(2) In terms of procedure. Like computer instructions. “List the players in a score group in rating order, drop out a guy if blah blah, change the colors around if blah blah, etc.”

I haven’t looked at the rulebook for pairings in a very long time but it sounds like we have something somewhere in between (1) and (2), with the emphasis on (2). That is indeed known in most technical disciplines as “a mess” and it’s hard to say much about such systems formally. Is it well defined? Is it consistent? Should we have a given rule or a proposed alternative?

My technical preference is to define a system by (1) then work on a solution, converting it to a machine spec (2). Sometimes there are “solvers” (for example, a Linear Program solver) that accept a specification of type (1) and the problem can be transformed appropriately to be input to the solver. Jeff said there was some sort of point system that sounds like (1).

Just sayin’ that it’s not just computer programmers who would have an itch to formalize what we have and what we have learned about pairing.

24

Add logicians to the list as well!

25

Shades of Galaxy Quest!

26

There is always a fussbudget who rarely plays or directs tournaments who wants to “fix” a problem that rarely happens. There are a number of variables that can affect pairings. In the original Harkness method, the design was to determine a winner and to create fair pairings in the later or last round of the tournament. Modern pairings are more color sensitive than the Harkness pairings. The difference between most human pairings and computer pairings is caused by the degree to which the carbon based director is concerned with colors. The rules on colors were adjusted based on one aberrant incident where one player could have had Black three times in a row. (That he probably played better with Black and had increased chances to win was considered irrelevant, but I digress.)

Players and tournament directors sometimes disagee with the pairings of Swiss-Sys and WinTD. Small tournament sections, odd numbers in score groups, prohibitions against playing team members or family members, withdrawals, fulll point byes, half point byes, etc. affect what the computer program and the human TD can do to make a legal pairing. I have seen computer programs go tilt when no legal pairing can be made in a small tournament. Then the TD had to use his best judgement.

Note that under the original swiss system formulations in the 1940’s, the TD had the option if colors were a potential problem, but the pairing was otherwise normal, to allow the players to flip a coin for color. No one complained. The “deterministic” assignment of color has caused many of the problems in tournaments. I preferred the older Harkness method; it was simpler and more flexible. TD’s who learned to do pairings with cards took the task of doing pairings correctly as a great responsibility and agonised over doing fair pairings. The matchups were more important than colors.

27

BTW, the whole discussion in this thread should be in the Tournament Direction forum.

28

Brian,
I agree that USCF pairing rules have room for improvement. After coding a pairing program you would be in a great position to suggest clarifications and changes. If you present clear rules that are consistent with what the TDs know intuitively then I hope that there is support by the Delegates. I think that any change that is too complicated to pair by hand should be presented as an alternative. I like Sevan’s advice on how get your changes to to the delegates meeting with a great chance for acceptance.

29

I reckon that Rule 29 is as it is because those responsible for it have the sense that pairing is an “art not a science”, as artichoke said above. The feeling is that, as Atkins said, directors learn to pair by doing it with cards, and they develop intuitions over time about what works and what doesn’t and what outcomes “look right” and what do not. They apparently feel unable to articulate these intuitions in the form of rules. Nevertheless, we have Rule 29.

Specifying particular algorithms, such as FIDE does, would make it deterministic whether a particular piece of software is “compliant” or a particular pairing is “legal”, but it would accomplish this by disfavoring other equally good algorithms, used by other TD’s. A lot of times the algorithm used by USCF TD’s is SOP (“seat-of-pants”), but it is the result that counts. If the rules specified a particular algorithm, the specified algorithm might not find a reasonable pairing in all situations. Nobody wants to be told that his way of doing things is not compliant, especially when it produces results as good as the blessed algorithm.

The feeling is that a good TD must use his judgement and experience to do a pairing, or to recognize that a pairing produced by software is acceptable. Though some parts of Rule 29 are highlighted as “TD Tips”, in fact, it is almost all “tips”. That is fine as far as it goes, but we are talking about a Rulebook. A rulebook is not the place for a little introductory tutorial for TD’s on how to do Swiss pairing, What people seek and expect in a rulebook is a clear description of what constitutes an acceptable or legal pairing. That is all. Programmers (and their users) want to know if the pairing software “complies”. Players want to know that they are being treated fairly by the TD. TD’s want to be able to say to players: this is a legal pairing, stop complaining and go play the damn game.

People can go somewhere else than the Rulebook for a handbook on Swiss System pairing. In fact, the less said in the nature of pairing tips the better, lest the tips be taken as normative and prescriptive. In a rulebook, if you don’t have something prescriptive to say, and a good reason for prescribing it, better not say anything.

Despite what some people have said in this thread, currently Rule 29 does not tell you whether a pairing is “legal” or what constitutes compliance in pairing software. Vendors advertise that their software follows the “USCF pairing rules”; but frankly I don’t see how anybody could know that, since the pairing rules neither define what constitutes a valid pairing, nor specify an algorithm for arriving at a valid pairing.

One approach which addresses these issues is FIDE’s. It documents a number of alternative Swiss-pairing algorithms. If you follow one of them you are compliant. They all have the same structure. They start by defining what constitutes an acceptable pairing. Several steps are then described. Upon the completion of those steps, if the result is acceptable, you get to stop. Otherwise, you back up some number of steps, take a different action (generally, it is the relaxation of a constraint), and repeat the steps, perhaps changed somewhat. This continues until you get to an acceptable pairing, and stop, or else you run out of steps (having relaxed all the constraints that may be relaxed). If you run out of steps, that final state is deemed acceptable even if it does not satisfy the initial definition of acceptably – notionally because you have followed the algorithm and tried everything allowed by the algorithm to remove problems.

We don’t have to use FIDE’s approach. The FIDE approach has the disadvantage of requiring particular algorithms, disfavoring other algorithms which may be better in some situations, or at least as good. Another approach would be to describe a metric for saying that one pairing is better than or equally good as another pairing. Then one could specify one particular algorithm, but allow any pairing which is equally good as or better than the one produced by the canonical algorithm.

30

Without commenting on the general topic, I’d just like to say that if it is a problem that the Rulebook has more than rules in it, there are two ways to fix that – one isn’t limited to changing the contents to fit the name, one could change the name (Rulebook and Manual perhaps?) to fit the contents.

31

That would be fine also. But the “rule” part should be separate from the “manual” part. Currently almost all of “Rule” 29 would be in the “manual” part. Left in the “rule” part would be almost no rules describing how to determine whether a pairing is valid.

32

Ouch. Things seemed so doable until I got to your last sentence.

To do this, we don’t only need to know what is an acceptable pairing, we need to rank acceptable pairings on a quality scale.

33

“At least as good as” suffices. But how do you evaluate pairings?

It is not so obvious. Suppose there is a score group with 4 players, A, B, C, D, in ratings order. The ideal “top half versus bottom half” pairing is A-C, and B-D. However, B and D have already played. If A is paired with his “canonical” opponent, C, then B and D both become odd players and have to be paired in a lower score group, resulting in 2 odd players in this score group. If A is paired with D, then C can be paired with B, resulting in no odd players in this score group. So far so good, A-D,B-C seems to be the better pairing. Not quite perfect top half versus bottom half pairing, but not too bad, and no odd players.

But not so fast: suppose that B and D dropping down to the next score group prevents two players in that group from becoming odd players and dropping down themselves; if B and D don’t drop down, then there are still two odd players one group down. So which is the better pairing? A-D eventually creates the same number of odd players as the A-C pairing created, but one score group down. My guess is that odd players in a higher group are worse than the same number of odd players in a lower group. That would be especially true for the top group and the last few rounds. But there is nothing in Rule 29 that says this (though there are hints that you don’t have to sweat too much about the very lowest groups.)

To specify an evaluation function over pairings, you have to be able to answer questions like this, and much more complicated besides.

34

As somene who did pairings with pairing cards, not to prove my manhood (that was only an ancillary benefit) but because that’s what we had, I’m painfully aware of that and other conundra.

35

You can’t evaluate pairings in a vacuum.

If there’s a large prize for first and nominal class prizes, then optimizing the top boards is paramount. But if class prizes are substantial…

If the software itself could take the prize eligibility and distribution into account, that would be cool.

36

If there are large class-based prizes, then presumably there are larger place prizes. Moreover, Swiss System tournaments generally only produce significant results for the first place, or at most the first few places, and often not even that. Further down the crosstable is just a lottery. So, you could say that organizers who stage tournaments with large class-based prizes shouldn’t be expecting the pairings program to bail them out of their stupidity in doing such a thing, and that if they want to run lotteries, they ought to move to Nevada.

37

I don’t like large class prizes, either, but they seem to be here to stay.

38

Good luck changing the U.S. Open.

39

The organizers of events that offer large class prizes don’t appear to be the ones clamoring for certification of tournament pairing software. :slight_smile:

40

The US Open is traditionally a ridiculous format. In the USCF tradition trumps ridiculousness every time. What’s another windmill here or there for us jousters?