The proposal discussed by Mr. Regan would use “brute force” calculation. In such an algorithm, you’d evaluate every possible set of pairings, and assign a score to each set. The set with the highest score would then be what the program spit out for that round.
“Every possible set”, of course, would include sets of pairings that involved rematches, multiple score-group drops, and many other pairings that are clearly illegal under USCF rules. However, those pairings, while illegal, certainly exist as possibilities in the decision tree. Ergo, the program, if it’s evaluating the tree straightforwardly, would have to examine those branches…no matter how obviously wrong they may be.
Yes, the idea is to look at all possible pairings. This does include rematches etc. I don’t think one can rule out any pairing though. You may be in a situation where you have to have a rematch. As we know this is when the number of players is only slightly larger than where you could run a round robin in the number of rounds available.
The key would be to assign a large penalty to things like rematches and going a large number of score groups away.
Coming up with the scoring rules would require us to actually place relative values on the various compromises we have to make to balance colors, not pair teammates, and get the same average rating difference.
Mike
For a number of years I worked a tournament with grade-based divisions and rating-based sections within the division. The team trophies were based on the best four scores the team had in the division. One year the five-round K-3 division had a 600-699(?) section with only four players. Reducing that section to a three-round quad would have hurt the teams the players were on, so it remained a five-round event with players having rematches.
Since the objective is merely to find the pairing set with the highest score, any pairing set which scores lower than any other could immediately be eliminated, thus saving a lot of work and making the program run faster.
If two pairing sets are identical, except for color assignment, then the one that follows the deterministic algorithm29E4 … Pairing players due the same colorwill automatically have a higher score, so the other pairing set can be eliminated immediately. So I agree with wilecoyote.
If, on the other hand, the objective were to find ALL mathematically possible pairing sets, and list them in order from highest score to lowest, then that would be another matter.
Mr. Regan broached the subject of creating a brute-force algorithm for the purpose of pairing. He clearly states that his purpose (objective) is precisely to find all possible pairing sets, and list them in score order. That - and only that - is the basis for my comments about the solution space. There is absolutely no statement or implication on my part that such an algorithm is best suited for the job of making pairings - though I did say that it is an interesting idea with some merit.
I like this idea, but I don’t think your formula is correct because it does not take account of colors. If the color assignments matter in evaluating a pairing, there are 2 ways to pair 2 players: 1v2 and 2v1 where the first mentioned plays white. There are twelve ways to pair 4 players: [1v2 3v4], [1v2 4v3], [2v1 3v4], [2v1 4v3], [1v3 2v4], [1v3 4v2], [3v1 2v4],[3v1 4v2],[1v4 2v3],[1v4 3v2],[4v1 2v3],[4v1 3v2]. So while it does not grow factorially, the number of pairings which must be considered grows much faster than in your table. In fact, if colors are important (i.e. 1v2 is not the same as 2v1), the number of pairings of n players is 2^(n/2) more than in your table, which is an exponential factor. Here are the numbers with colors considered
It looks fairly easy to use brute force up to 12 players or perhaps 14 players. Beyond this, the numbers start to look daunting, but there are a number of optimizations possible. The number of possible pairs is small. For example, with 16 players, there are only 120 possible pairs (16x15/2). For each pairing, much of the score depends on who the opponents are (do they belong to the same score group? have they played before?). A particular pairing represents different combinations of the possible specific pairs, but the specific-pair-dependent score only has to be computed 120 times. For each specific pair of players there are only two color parities (one player White the other Black, and the other way round), and so only two color scores have to be computed for each specific pair. And, if a particular color-assigned pairing gives every player in the base pairing his due color, no other color-assigned pairing with the same base pairing needs to be considered.
With optimizations like this, it is possible that the brute force approach would be feasible up to 16 players. Even 18 players is possible if the TD can wait several minutes for the pairings to be computed, though that would probably be looked upon as impractical by scholastic TD’s. At 20 players we have reached the point where brute force would definitely be impractical, and after only a few more increases in the number of players, we would have to hold the next round at the Restaurant at the End of the Universe.
OK, I’m just a lowly Local TD. But back in my misspent youth I did the pairings for the VA Open by hand.
It seems to me that Swiss Sys got it right. The top two players played each other in the final round, and someone else had to drop two score groups. The proposed alternative was to pair 1-3 and 2-4. However, the rulebook is quite clear that this alternative is incorrect: “A pairing which drops a player down two or more score groups should be chosen over a pairing which drops two or more players down for one or more score groups.” (5th edition, p.139)
I believe your reasoning is flawed. You have the same number of drops with both pairings. You must obviously drop the lone player with 3.0 to the 2.5 score group, where there are two players. Once you pair the 3.0 with one of the 2.5 players, the other player with 2.5 must drop to a lower score group. The pairings Alpha-Charlie and Baker-Delta drop each of Alpha and Baker one score group. The pairings Alpha-Baker and Charlie-Foxtrot drop Alpha one score group and Charlie two score groups. According to rule 29D1, the pairings Alpha-Charlie and Baker-Delta are correct.
I wrote some test code to enumerate the “base pairings” for various numbers of players, and on my desktop PC it is possible to enumerate all possible “base pairings” (i.e. ignoring color) of 16 players in 0.08 seconds. That is 2 million pairings. 18 players requires 1.53 seconds for the 34 million possible base pairings. For 20 players, which is 655 million possible base pairings, it takes 38 seconds.
Of course, that is not scoring all the enumerated pairings and selecting the best. Obviously, scoring a pairing is more time-consuming than counting it. Scoring rather than counting could easily be an order of magnitude slower, which would still be close to instantaneous for 16 players, and still practical for 18 players. If the scoring required two orders of magnitude more time, 16 players would still be practical but probably not 18.
OK – the flaw in my reasoning was not seeing Alpha as dropping a score-group!
However, I do not see any relevant text in 29D1, but in 29D: “In such situations, the first priority… is to have players play as close to their score group as possible.”
What about 200 player sections, like some sections at the World Open? Or 600 player sections, like at the U.S. Open? As you suggested, at some point the computation becomes so slow that it’s impractical. I suppose you could use a different algorithm for larger sections.
Well, sure. Obviously, there would need to be another algorithm for events larger than 16-18 players. There are a lot of such events. But “brute force” probably covers a lot of events, and has the advantage that it is easy to understand and program.
There are algorithms for finding the “minimum cost perfect matchings” on graphs, which run in polynomial time. For example, Edmond’s algorithm (en.wikipedia.org/wiki/Stable_roommates_problem), and there are algorithms for finding “stable matchings” if they exist, which are applicable to pairing Swiss System chess tournaments. There are also probabilistic heuristic approaches to the problem. These are not guaranteed to find the minimum cost pairing in every case, but they usually do, and they run faster for large graphs (numbers of players) than the deterministic approaches. They are usually easier to program. For example WinTD reportedly uses a simulated annealing heuristic. The traditional system using pairing cards (which SwissSys probably attempts to model) is another heuristic approach.
As with the brute force approach, in order for these approaches to work, it is necessary to have a system for computing a “cost” or “desirability score” for each possible pair in the pairing. That is, a numeric measure of how desirable a matchup is between two players, which can be summed over a pairing with the result that pairing A is preferable to pairing B if the sum of the pair costs for A is lower than for B.
(Actually, with the brute force approach it is not necessary to have a “cost” for each pair in the pairing. It is only necessary to be able to say whether one pairing is better than another and for this ordering to be transitive (A>B and B>C if and only if A>C). This probably suffices for an approach like WinTD’s, also. However, for some of the other approaches, such as Edmond’s Algorithm, each edge in the graph (i.e. pair in the pairing), must have a definite “cost” associated with it.)
So the real work is developing a way of expressing these costs. The brute force approach is just a nice simple setting for experimenting with this. Unfortunately, it is a lot of work to extract from the USCF pairing rules a set of such costs, with the 80/200 limits making it particularly troublesome.
There is no rating limit for transpositions that are made to satisfy 27A1 or 27A2 (those kick in further down the prioritized list, for 27A4 and 27A5).
Alpha-Baker would violate rule 27A2 in the 2.0 score group, while the transposition to Alpha-Charlie is able to follow rule 27A2. Rule 29D1 (Determination of the odd player) specifies that it is not an exception to 27A1 or 27A2, though it references that by description instead of by rule number.
Even if this were not specified, I do not find justification in the rules for giving 29D1 priority over 27A2.
Brian,
As Ken showed earlier for a given pair of players there is only one color allocation that is allowed. So, we don’t get that extra factor of two for each pair.
As you said, generating the possible boards is they easy part. Getting a fast evaluation process would be the key.
I also agree with the point about the lack of clear rules. For example, are the 80/200 limits hard limits? If I can improve the colors for five boards by doing an 81 point transposition, is that allowed? If so, what the relative importance of the two?
Mike
But, as you said earlier, you were looking to generate all possible pairings. I take that to mean, literally, every possible grouping of two players, each and every round. If that is really the goal, every possible color allocation must be included, right? If so, then your solution space is actually significantly larger than your original calculation, as I mentioned a while back.
Maybe automatically discarding any set of pairings with an individual pairing that has a certain score, or any set of pairings below a certain total score? I hope you decide to investigate this further. It would be very interesting to take a larger tournament with a pairing controversy (such as the 1987 US Open) and run a brute-force algorithm on the pairings for a particular round (the 11th, in this case).
I find the 80/200 limits sometimes overly restrictive, but I understand the reasoning behind them. Having said that, there is often a way to justify a switch or a transposition that is beyond those limits. Sometimes, you can do it with multiple smaller switches or transpositions that get you the pairing you’re looking for. Back in the days of the yellow pairing card (currently on display in the World Chess Hall of Fame along with an adjournment envelope and a manual demo board in the “Ancient Artifacts” exhibit ), I would do exactly that to fix a pairing issue.
Also (and more to the point for most TDs nowadays), if you plug those limits into a pairing program, you should manually check later-round pairings on the top boards.
Boyd,
I said I wanted to find the “best” possible set of pairings by searching the entire solution space. There is no need to include two options for each board, if one of the options will never happen. So, the real solution space doesn’t need to include color options that would never happen.
I’ve only thought about the evaluation method a little bit but this one thing that you can’t just use brute force. The quality of a given set of pairings is a global parameter. You can’t just look at each board in isolation. This is obvious but important. For example, Player A is rated 2200 Player B is rated 2150 and they have the same color history. You can’t say anything about the goodness or badness of pairing the two without knowing how many other players are in the score group and their ratings. If they’re the only two 4-0 players, then this is a perfect pairing. If there are 20 players rated from 2200 to 1000 this is really bad. If there are 20 players rated between 2250 and 2150, then this is a fine pairing but there could be a better option.
Mike
If the purpose of generating all possible pairings is to find the one with the highest score, then you might as well immediately discard any pairing set that will obviously have a lower score than another.
For example, any pairing set that pairs X (due white) vs Y (due black), and assigns the white pieces to Y, will obviously have a lower score than the same pairing set with the colors reversed in that pairing.
OMG, I know I’m getting old when these items are on display in a museum.
You did say the following a little earlier in the thread.
Given this statement, coupled with your observations prior to it, you can hopefully understand where I may have misinterpreted. I apologize, and thank you for the clarification you provided. I would only note that it sounds strange to discard possible color issues (especially since there are sometimes suboptimal-yet-legal pairings where colors could go either way) and not discard other, always illegal pairings that involve things like rematches.
Just to throw in yet another monkey wrench (that’s fun sometimes) I suppose there could be reasons, when pairing two players with no color history (e.g. half-point byes in round 1), to do it one way or the other.
For example, if two players walk in 15 minutes after all the other games have started, and I decide to pair them against each other in round 1, I will assign colors opposite to the way they were assigned in the last pairing I made. For example, if the higher-rated player had white on the last board paired, I will give the higher-rated black in this new pairing. That preserves the reason for alternating colors down the boards in round 1.
What if you have 14 players for a four round Swiss, players 1, 3, 5 and 7 received white in round one while 2, 4 and 6 received black? If the higher of two players arriving late has a rating between 4 and 5 then your method would have him alternate from 4, which results in five of the top eight receiving white in the first round.
On the other hand, if you simply alternate from the last player paired as part of the top half then you are always either equalizing the top half or getting as close as you can without equalizing.
), I would do exactly that to fix a pairing issue.
fun sometimes) I suppose there could be reasons, when pairing two players with no color history (e.g. half-point byes in round 1), to do it one way or the other.