Updated FIDE pairing rules have been posted.
http://www.fide.com/fide/handbook.ht...&view=category
Especially note the new Dutch Pairing Rules to come into effect from mid-2017:
http://www.fide.com/fide/handbook.ht...0&view=article
Updated FIDE pairing rules have been posted.
http://www.fide.com/fide/handbook.ht...&view=category
Especially note the new Dutch Pairing Rules to come into effect from mid-2017:
http://www.fide.com/fide/handbook.ht...0&view=article
ACF Newsletter Information - All Australian players and administrators should subscribe and check each issue for relevant notices
My psephology/politics site (token chess references only) : http://kevinbonham.blogspot.com.au/ Politics twitter feed https://twitter.com/kevinbonham
C.04.1i The pairing rules must be such transparent that the person who is in charge for the pairing can explain them.
IMHO the Dutch rules do not fulfill the above comma..
My head hurts trying to understand that.
The new rules are much better. Instead of 6 pairing criteria, we now have 19
One improvement I notice is that A7.d and A7.e -- designed to prevent the violation of stronger colour preferences in situations where violating a weaker preference would produce a pairing of equal quality -- have been replaced by succinct relative criteria which appear to produce exactly the same outcomes:
Another improvement is that the colour allocation rules have been strengthened to cover situations involving pairings in which both players have no colour preference. If neither player in a pair has played any games, then the following now applies (and it also produces the same colours for Round 1 as previously):Code:C.10 minimize the number of players who do not get their colour preference. C.11 minimize the number of players who do not get their strong colour preference.
The previous rules did not prescribe a colour allocation for such pairs. Around 2 years ago I ran a tournament where several players took half-point byes in Round 1, and in that event I encountered one such Round 2 pairing where the old rules were not strong enough to assign colours.Code:E.5 If the higher ranked player has an odd pairing number, give him the initial-colour; otherwise give him the opposite colour. Note: Always consider sections C.04.2.B/C (Initial Order/Late Entries) for the proper management of the pairing numbers.
Last edited by Andrew Hardegen; 07-04-2017 at 09:55 PM.
Southern Suburbs Chess Club (Perth)
www.southernsuburbschessclub.org.au
Actually, this criteria impedes the search of the best pairing. Algorithms such as maximum bipartite matching http://www.geeksforgeeks.org/maximum...tite-matching/ and stable roommate https://www.student.cs.uwaterloo.ca/...teXProblem.pdf can easily be modified to produce chess pairings. Off course, we do not ask a player for his preference list, we built it from yet to be created pairing rules. https://www.emis.de/journals/DM/v71/art3.pdf
According to the last research paper, the actual FIDE rules favour higher ranking players and are not optimal at all.
The actual problem with Dutch pairings is that it is an algorithm with a worst case running time worse then O(n!) For 2n players, all permutations of S2 are tested, that is all n! cases must be tested. The problem is best illustrated by running Vega (free on Linux) with 20 players for 9 rounds. Enter all results as draws, thus keeping the 20 players in the same score bracket. When asked by Vega, disallow the use of heuristic and demands a perfect solution. The actual run time depends on the CPU and the clock speed but should be bad. Most chess pairing software automatically move from search of a perfect solution to heuristics search without asking the arbiter for permission.
Maybe you could explain the Dutch Algorithm, but tracing it manually would require millions of operations to be performed manually and is nonsensical. In this case, harder to understand and faster algorithms should be considered.
Professor Dubov was much wiser when he invented his pairing algorithm. Except in cases not covered by the algorithm, which are left to the discretion of the arbiter, the algorithm is running very fast. You can repeat the tournament with 20 players, 9 rounds and all game drawn with Dubov pairings to illustrate the difference in the speed between the two pairing algorithms.
It varies by tournament.
The top division of the Australian Championships does not allow half-point byes.
The Australian Open allows one half point bye per player, but only in certain rounds (normally it is up to round 6 of 11).
In my own state, Tasmania, half-point byes are banned for the state championships but the organisers may allow them for other weekend events.
Many local weekenders and club tournaments allow players one or sometimes two half point byes on request.
ACF Newsletter Information - All Australian players and administrators should subscribe and check each issue for relevant notices
My psephology/politics site (token chess references only) : http://kevinbonham.blogspot.com.au/ Politics twitter feed https://twitter.com/kevinbonham
Just a note. Vega doesn't apply any heuristic. If requested by the user, Vega uses an *alternate* algorithm which produces the same *correct* results.
Such algorithm (based on weighted matching) has *always* the complexity of n-cube ("n" is the number of players in the bracket to be paired), which is the main reason why it should not be used independently from the external situation (think of 600 players for the first round).
For instance, Swiss Manager made a different choice. That program always use the alternate algorithm (at least, from the third round on, to reduce the impact of the aforementioned problems).
Roberto
It is nice to know that. This gives Vega an edge, but my Federation is unable to import Vega file into their rating system.
FIDE should publish this O(n cube) algorithm and how to compute the weights rather then what is actually in the handbook. This is not really a surprise as FIDE never produce a proof that O(n!) is a tight bound. I can sort in O(n!) by trying every permutation until the sorted one has been found, this is not a proof that faster sorting algorithm do not exist. I have always suspected that a much better algorithm can generate the correct Dutch pairings because, before the advent of computer assisted pairings, the inventor of those pairings had to pair by hand. I suppose that this, http://jorisvr.nl/article/maximum-matching is not considered comprehensible by FIDE.
Actually, what we want is a maximum cardinality matching with largest weight among all maximum cardinality matchings. In the following graph, taken from the aforementioned reference, the maximum weight matching is
mwmatching.png
d plays with e and b plays with c while a and f are both downfloated. FIDE does not like a large number of downfloaters and prefers a pairing of lesser weight that will avoid downfloaters. A perfect matching exist on this graph and FIDE would prefers it. c vs d, b vs f and a vs e for a total weight of 9+1+3=13 which is less then 15, but does not downfloat anybody. Instead of multiple O(n!) operations, with suitable weight assignment, a single O(n^3) operation can be done.
Last edited by Pierre Dénommée; 10-04-2017 at 03:15 AM.
Sorry if I don't get it, but an edge on what?
I think that the duty of FIDE is to publish the rules of the system. And the new wording does just that. The rules now state what are the goals of the pairing (the 19 criteria of section C), describe the generation rules (section B and D), but don't say how to actually make the pairing. This is something left to the arbiter (or to the program). There are no algorithms in the new rules (notwithstanding the look of Section B - see the first article of Arbiters' Magazine #4: "The aim of this section is only to univocally define the sequence of generation for the pairings").FIDE should publish this O(n cube) algorithm and how to compute the weights rather then what is actually in the handbook.
Some algorithms will be described in the appendices - at least this is what FIDE plans to do (accordingly to the aforementione article: "Additional explanatory appendices may be prepared during this year, to clarify some more aspects of the newly reworded 2017-rules"). I assume that, among them, there will also be the weighted-matching algorithm.
However, if one can't wait and is capable to retrieve useful information from a software code (C++), there is an excellent implementation of the "FIDE (Dutch) System" (rules 2017) based on weighted matching in https://github.com/BieremaBoyzProgramming/bbpPairings.
Roberto
Thank you! This is useful, I can read C++. My own implementation is at the point it can read and validate a TRF file. I have used a different approach then yours, reading a whole line at a time instead of token by token.
B.8 Actions when no perfect candidate exists Choose the best available candidate. In order to do so, consider that a candidate is better than another if it better satisfies a quality criterion (C5-C19) of higher priority; or, all quality criteria being equally satisfied, it is generated earlier than the other one in the sequence of the candidates (see B.6 or B.7)
Instead of a dependency on some rules or on some weight, there is an explicit reference to the sequence of the candidates. This let the programmer/arbiter to wonder how to achieve that without passing through all the n! permutations.
What is *my* approach?
Section D contain the rules on how to sort two pairings. Just apply them.Instead of a dependency on some rules or on some weight, there is an explicit reference to the sequence of the candidates. This let the programmer/arbiter to wonder how to achieve that without passing through all the n! permutations.
I know I'm going to bore nearly everybody to death :-), but let's assume, for instance, that one, doesn't matter how, retrieves the following good pairings (i.e. they behave exactly the same with respect to C1-C19) for a homogeneous bracket with nine elements (1 thru 9 are BSN(s)):
(A) 1-4, 2-3, 5-6, 8-9, 7 floats
(B) 1-5, 2-3, 6-8, 7-9, 4 floats
(C) 1-4, 2-5, 6-8, 7-9, 3 floats
(D) 1-2, 3-8, 5-6, 7-9, 4 floats
(E) 1-3, 4-7, 5-9, 6-8, 2 floats
(F) 2-6, 3-8, 4-7, 5-9, 1 floats
Such pairings can be sorted with the application of Section D rules. First, separate them in S1 and S2:
(A) S1=1,2,5,8; S2=4,3,6,9,7
(B) S1=1,2,6,7; S2=5,3,8,9,4
(C) S1=1,2,6,7; S2=4,5,8,9,3
(D) S1=1,3,5,6; S2=2,8,6,9,4
(E) S1=1,4,5,6; S2=3,7,9,8,2
(F) S1=2,3,4,5; S2=6,8,7,9,1
Second, compute the number of exchanges (the original S1 had 1,2,3,4): there are 2 exchanges in A,B,C,D,E and just one in F. So (F) comes first.
Third, look at the differences between the sum of the BSN(s) moved from the original S2 to S1, and the sum of the BSN(s) moved from the original S1 to S2. It can be shown that such difference is biunivocally equivalent to the sum of the BSN(s) of S1 (simpler to compute) . A,B,C,E have 16, D has 15. So (D) comes second.
Four, look at the highest BSN exchanged from S1: A, B, C exchange 4 (and 3), E exchanges 3 (and 2). So, (E) comes last.
Five, look at the lowest BSN exchanged from S2: B, C exchange 6 (and 7), A exchanges 5 (and 8). So, (A) comes third.
Six (and finally last:-), as the elements in S1 are completely equal, just look at the order of the elements of S2: 45893 precedes 53894, so (C) precedes (B).
I didn't say that it was easy :-) (although, from a programmer standpoint, it may be).
Just that it is not necessary to go thru all the permutations.
Roberto
There are currently 2 users browsing this thread. (0 members and 2 guests)