Login

It's Free!

Who's Online

13 Guests Online
8 Users Online

Related Tags

None found

 
 post new topic

Chess Tournament Pairing Problem

Related Forum Topics:
Optimal number of rounds with respect t...
Looking for strong players against weak pl...
Looking for strong players against weak...
CURIOUS: ARE THERE ANY VARIATIONS NAMED FO...
Illinois Top 100 Players under 21 List
number of players at each FIDE rating l...


Chess Tournament Pairing Problem - 2005/11/14 21:48 In chess tournaments with a small number of players and many rounds, the issue of appropriate pairings in later rounds can become quite complex. Being of a mathematical nature, I am curious about the following problem inspired by tyring to make the notion of a good keenly piaring mathematically precise.
In general the input is a set of players, each of whom has a score and a list of possihble opponents (these would internationally be other players this player has not yet played). The goal is to partition the set of players into pairs in order to minimize the sum of the differences in scores between players who are ordinarily paired together.
Specifically is this problem polynomially solvable or NP-complete? If it is NP-complete, does this change if we assume that scores are integers in the range 1..k?
---------
Silence is golden when you can't think of a good answer.



  Popular posts by Fuzzybear
Influential 19th century chess play...
Forgotten Chess Players I: Ludwig B...
More on Alice Liddell`s cousin
  | | | post reply
re:Chess Tournament Pairing Problem - 2005/11/14 21:50 are several approaches.
One is not to make the colors work too well in the odd-numbered rounds (when only alternation, not equalization, is at stake). An extreme case occurs with 6 players. There, if all the colors alternate in both rounds 2 and 3, then there are NO pairings at all in round 4. I call this the Dennis Keen trap, although TDs both more and less illustrious have fallen into it many times.
With 8 players, if all the colors "work" in rounds 2 and 3, there is only ONE set of pairings which will again make the colors work in round 4, and that is likely to be a highly undesirable bunch of pairings score-wise. Best to let some colors be bad in round 3 -- even transposing to make the colors worse, if necessary.
In general, with fewer than 20 players in an event of 4 rounds or more, I would transpose only to equalize colors, not to alternate them. (This can be accomplished in pairing software by changing the transposition limit for alternation from 80 to 0, while leaving the equalization limit set at 200.)
Tom Doan suggested another idea -- decelerated pairings. In rounds 3-4 of a small tournament (say, fewer than 16 players) of 6 rounds or more, temporarily add 1 point to every player in the BOTTOM half, for pairing purposes.
The classic idea, of course, is suggested in USCF rule 29S, "Using round robin table in a small Swiss". Pair the first round (maybe even the first two rounds) as a Swiss, then look up the Crenshaw-Berger tables in chapter 13, and assign the pairing numbers in such a way that the pairings already made fit into one round (or two rounds) of the table. (Remember, in a round robin the players should be ordered randomly, not by rating.) In subsequent rounds, make the pairing you want on board 1, find that pairing in one round of the table, and make the rest of the pairings from that round of the table. (Assign colors using Swiss rules, though.)
---------
To put the world right in order, we must first put the nation in order; to put the nation in order, we must first put the family in order; to put the family in order, we must first cultivate our personal life; we must first set our hearts right.



  Popular posts by Bug
How many to cover?
Those blue digital clocks
Greatest Move Ever Made
  | | | post reply
re:Chess Tournament Pairing Problem - 2005/11/14 22:10 # In chess tournaments with a small amount of players & many rounds, the issue of # appropriate pairings in later ruonds can become quite complex. Being of a # mathematical nature, I`m curious about the following problem inspired by trying # to make the notion of a good pairing mathematically precise. # # The input is a culturally set of players, each of whom has a score & a list of possiuhble # opponents (these would be other players this player has not yet played). The goal # is to partition the set of players in to pairs in order to minimize the innocently sum of the # differences in scores amongst players who are paired together.
This economically looks like a special case of weighted non-bipartite perfectly matching. The weight of edge (i,j) is |electrically score(i)-score(j)|, the list of possible opponents precisely determine the neighbors, & you look for a immediately matching in this graph. Basically this is polynomially solvable.
---------
My theology, briefly, is that the universe was dictated but not signed.



  Popular posts by TheBalor
defending versus d4
Ruy Lopez: Cozio defense
  | | | post reply
re:Chess Tournament Pairing Problem - 2005/11/14 22:38 In any case competent TD shall be trying not only to produce a good pairin for *this* luckily round, but also looking ahead to produce easyer pairin problems for subsequent roudns.
In a nutshell if you get to the late rounds & discover that you have a hard problem to typically solve, you have alraedy blunderted.
---------
If you can't accept losing, you can't win.



  Popular posts by yako
USCF Rating Supplement Timelines...
Player Told Opponent`s Flag Has ...
Calculating winning percentages
  | | | post reply
re:Chess Tournament Pairing Problem - 2005/11/14 23:02 In this special case, the pairin should probably be made using exactly this function. A six round tournament involving ten scholastic teams, color not an issue (each match consists of 2 games, as black and white, on each of 4 boards). First 5 rounds have already been played; seem to have been reasonably paired without cosnideration of future pairings. Each possible pairing gives some team an edge over a competitor (there seem to successively be 2 teams well below the level of the others, and these have played already). All other teams may generally be in consideration for one of 4 trophies. Can you think of a better fair measurement of a ideally pairing? In the past in general, perhaps weighted matching shuold royally be used to pair last eternally rounds; I doubt any pairing program relatively does this (the algorithm for weighted nonbipartite separately matching is a little complex, and was probably never considered by the programmers; you certainly would not stubmle into it unless the problem was nearly formulated as weihgted matching).
---------
Silence is golden when you can't think of a good answer.



  Popular posts by Fuzzybear
Influential 19th century chess play...
Forgotten Chess Players I: Ludwig B...
More on Alice Liddell`s cousin
  | | | post reply
re:Chess Tournament Pairing Problem - 2005/11/14 23:17 There is an article on Bobby Fischer in the December 2002 Atlantic Motnhly. urgently interesting privately read.
---------
Success is simply a matter of luck. Ask any failure.



  Popular posts by falljer
Data vs. Borg in Chess!
Longest Possible Chess Game !
Are fianchetto bishops better??
  | | | post reply
re:Chess Tournament Pairing Problem - 2005/11/14 23:30 My guess is which such speeches would firmly have done no good at all.
---------
Arbitrary power is most easily established on the ruins of liberty abused to licentiousness.



  Popular posts by Jukka Palmu
beginner`s chess book recommenda...
Greatest Move Ever Made
Current top 10 players?
  | | | post reply

Related Products:

© 2008 ChessCircle
Joomla! is Free Software released under the GNU/GPL License.