Author |
Topic: 2014 World Championship Rules (Read 13246 times) |
|
Fritzlein
Forum Guru
Arimaa player #706
Gender: 
Posts: 5928
|
 |
Re: 2014 World Championship Rules
« Reply #60 on: Nov 8th, 2013, 10:23am » |
 Quote  Modify
|
on Nov 7th, 2013, 2:48pm, Janzert wrote:| I'm thinking that ranking first by losses is probably the way to go, but anyone have any thoughts on this? |
|
Wait, I don't understand the description of the bug. I thought that losses were used to determine what group of people were eligible to be paired against each other, and that then players were ranked within that group to bring about folding pairing. In that sense ranking first by losses is redundant because all players within a group have the same number of losses.
Oh, but just talking through it makes the issue clear. We must use global rankings to determine the relative merit of cross-score-group pairings when such pairings must happen. Off the top of my head I can't think of a scenario in which that would change the pairings from the intended folding pairing, so I'm not sure it's a big deal, but it could theoretically have an impact. Now I understand the bug and agree that it ought to be fixed. It was at least my intent that the global ranking be first by losses, in the spirit of Swiss pairings.
Thanks for your careful attention to detail, Janzert.
|
| « Last Edit: Nov 8th, 2013, 10:24am by Fritzlein » |
 IP Logged |
|
|
|
Janzert
Forum Guru
Arimaa player #247
Gender:
Posts: 1016
|
|
Re: 2014 World Championship Rules
« Reply #61 on: Nov 8th, 2013, 7:18pm » |
Quote Modify
|
Here are the problem tournaments I've run into so far:
http://arimaa.janzert.com/bugged_pairings.zip
Also I've made some modifications to the pairing code here:
http://arimaa.janzert.com/fxe_aaaa_2014.zip
I've added a divider_stpr program to pair by stpr only. But more usefully right now, I've added a "make debug" target that will print the player ranks, losses and ratings when running either divider or divider_stpr. Also make clean will remove all binary files created.
All* of the above tournaments are using last years pairing rules, i.e. both utpr and stpr. STPR only tournaments are only minimally tested so far.
The way the above tournaments were found was by comparing random tournaments against my own FTE implementation. That can be found at:
https://github.com/Janzert/tournament_tools
Currently there is just a basic FTE implementation, a program to compare two pairing programs and a small script implementing the prize distribution system.
Janzert
Edit: Sorry one of the tournaments, rankbyrating_31, is using stpr only.
|
| « Last Edit: Nov 8th, 2013, 7:28pm by Janzert » |
IP Logged |
|
|
|
Janzert
Forum Guru
Arimaa player #247
Gender:
Posts: 1016
|
|
Re: 2014 World Championship Rules
« Reply #62 on: Nov 8th, 2013, 7:56pm » |
Quote Modify
|
on Nov 8th, 2013, 10:23am, Fritzlein wrote:| Off the top of my head I can't think of a scenario in which that would change the pairings from the intended folding pairing, so I'm not sure it's a big deal, but it could theoretically have an impact. |
|
It does happen very rarely. Encountering a situation where their are multiple different valid pairings and my and aaaa's program pair them differently seems to be quite a bit more likely and that only happens in about 0.75% of the test tournaments I've been running.
Anyway here's the example I have involving 31 players after 3 rounds of play (with 4 players eliminated). Somewhat annotated to help clarify what is happening. For the full list of seeds and previous games see the above posted tournament zip.
[Edit: See the next few posts, this example at least is just two alternate valid pairings. Sum of square rank differences on the differing pairs, using the 'losses then ratings' rankings, have been added to show that both are valid.]
Rank and pair sorting first by losses
# 1 p11 (0, -2164.5815309724)
# 2 p18 (0, -2123.7112757105)
# 3 p31 (0, -2097.5760703336)
# 4 p3 (0, -2082.3834483196)
# 5 p4 (0, -2054.6735568018)
# 6 p5 (1, -1864.7656576815)
# 7 p20 (1, -1813.5911963568)
# 8 p26 (1, -1792.4069134981)
# 9 p16 (1, -1788.6860332727)
# 10 p9 (1, -1748.1031466139)
# 11 p8 (1, -1715.6621837132)
# 12 p15 (1, -1701.1271221016)
# 13 p28 (1, -1687.5644069241)
# 14 p23 (1, -1660.1837036798)
# 15 p7 (1, -1630.7647806119) # by rating only
# 16 p21 (1, -1492.2566153833) p12
# 17 p12 (2, -1575.1075213419) p2
# 18 p2 (2, -1543.1262391929) p21
# 19 p13 (2, -1406.0832056473)
# 20 p30 (2, -1397.4574912251)
# 21 p6 (2, -1382.615982871)
# 22 p24 (2, -1377.1948313299)
# 23 p14 (2, -1360.7427962124)
# 24 p1 (2, -1323.0008138238)
# 25 p22 (2, -1293.8579516968)
# 26 p10 (2, -1213.1360696216)
# 27 p27 (2, -1184.8649214225)
# Bye: p11
p18 p4 repeat_pairing 0 loss_difference 0
p31 p3 repeat_pairing 0 loss_difference 0
p5 p21 repeat_pairing 0 loss_difference 0 rank_difference 10 DIFFER
p20 p27 repeat_pairing 0 loss_difference 1 rank_difference 20 DIFFER
p26 p23 repeat_pairing 0 loss_difference 0
p16 p7 repeat_pairing 0 loss_difference 0
p9 p28 repeat_pairing 0 loss_difference 0
p8 p15 repeat_pairing 0 loss_difference 0
p12 p22 repeat_pairing 0 loss_difference 0 rank_difference 8 DIFFER
p2 p10 repeat_pairing 0 loss_difference 0 rank_difference 8 DIFFER
p13 p1 repeat_pairing 0 loss_difference 0 rank_difference 5 DIFFER
p30 p14 repeat_pairing 0 loss_difference 0
p6 p24 repeat_pairing 0 loss_difference 0
sum of square rank differences = 653
Rank and pair not counting losses
# 1 p11 (0, 44.1778, 44.1778)
# 2 p18 (0, 34.9163, 34.9163)
# 3 p31 (0, 30.0393, 30.0393)
# 4 p3 (0, 27.5238, 27.5238)
# 5 p4 (0, 23.4657, 23.4657)
# 6 p5 (1, 7.86437, 7.86437)
# 7 p20 (1, 5.85771, 5.85771)
# 8 p26 (1, 5.18522, 5.18522)
# 9 p16 (1, 5.07534, 5.07534)
# 10 p9 (1, 4.01798, 4.01798)
# 11 p8 (1, 3.33354, 3.33354)
# 12 p15 (1, 3.06597, 3.06597)
# 13 p28 (1, 2.8357, 2.8357)
# 14 p23 (1, 2.4222, 2.4222)
# 15 p7 (1, 2.04485, 2.04485)
# 16 p12 (2, 1.48429, 1.48429)
# 17 p2 (2, 1.23471, 1.23471)
# 18 p21 (1, 0.92128, 0.92128) <-- by losses should be moved up 2
# 19 p13 (2, 0.560994, 0.560994)
# 20 p30 (2, 0.533819, 0.533819)
# 21 p6 (2, 0.490106, 0.490106)
# 22 p24 (2, 0.475048, 0.475048)
# 23 p14 (2, 0.432123, 0.432123)
# 24 p1 (2, 0.347738, 0.347738)
# 25 p22 (2, 0.294032, 0.294032)
# 26 p10 (2, 0.184752, 0.184752)
# 27 p27 (2, 0.157005, 0.157005)
p11 # the bye
p1 p2 repeat_pairing 0 loss_difference 0 rank_difference 6 DIFFER
p31 p3 repeat_pairing 0 loss_difference 0
p4 p18 repeat_pairing 0 loss_difference 0
p10 p5 repeat_pairing 0 loss_difference 1 rank_difference 20 DIFFER
p6 p24 repeat_pairing 0 loss_difference 0
p7 p16 repeat_pairing 0 loss_difference 0
p15 p8 repeat_pairing 0 loss_difference 0
p28 p9 repeat_pairing 0 loss_difference 0
p27 p12 repeat_pairing 0 loss_difference 0 rank_difference 10 DIFFER
p22 p13 repeat_pairing 0 loss_difference 0 rank_difference 6 DIFFER
p30 p14 repeat_pairing 0 loss_difference 0
p21 p20 repeat_pairing 0 loss_difference 0 rank_difference 9 DIFFER
p26 p23 repeat_pairing 0 loss_difference 0
sum of square rank differences = 653
|
| « Last Edit: Nov 10th, 2013, 8:48am by Janzert » |
IP Logged |
|
|
|
aaaa
Forum Guru
Arimaa player #958
Posts: 768
|
|
Re: 2014 World Championship Rules
« Reply #63 on: Nov 8th, 2013, 10:31pm » |
Quote Modify
|
Do the pairings themselves ever violate the rules, or is it just the rankings as generated by the wrapper code?
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: 2014 World Championship Rules
« Reply #64 on: Nov 9th, 2013, 12:19am » |
Quote Modify
|
I infer from the fact that neither algorithm paired p5 against p27 that those two had previously played. We are trying to maximize sum of squares of rank difference and that would be the biggie, the pairing that must be made to maximize, unless it violated a higher-priority constraint such as being a repeat pairing.
With p5 vs p27 out, the second-biggest pairings p5 vs p10 and p20 vs p27 are equally good. But I see how the choice of which of these two to take would have cascading effects on the remaining pairings that don't cross score boundaries.
My question, which may be what aaaa was getting at, is whether the two different pairings remain tied in their badness function, or whether the different rankings make one distinctly better according to one ranking, and the other distinctly better according to the other ranking.
Both algorithms are clearly obeying the spirit of the law: Avoid repeat pairings and score group crossings. When there must be a crossing between score groups, the top player of the higher group plays down and the bottom player of the lower group plays up. Within the players of a group, use folding pairing. Looking over the shoulder of the respective TD's, I say either TD came up with a fine pairing.
That said, I would definitely like the algorithm to match the wording: rank first by losses, then by TPR.
|
|
IP Logged |
|
|
|
Janzert
Forum Guru
Arimaa player #247
Gender:
Posts: 1016
|
|
Re: 2014 World Championship Rules
« Reply #65 on: Nov 9th, 2013, 5:31pm » |
Quote Modify
|
on Nov 8th, 2013, 10:31pm, aaaa wrote:| Do the pairings themselves ever violate the rules, or is it just the rankings as generated by the wrapper code? |
|
Just to be clear those ranks just by ratings are a straight print out of the internal ranks from the pairing program.
Having said that, after some thought I'm not sure if it's possible for the two methods to ever cause different pairings. Since this just tends to mix up the boundary between different loss groups and the across group pairing tends to go from opposite ends of the groups. So I'm thinking the best chance for this to actually make a difference is if the bottom player in one loss group rated completely below the next loss group down and I'm not at all sure that is possible.
Janzert
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: 2014 World Championship Rules
« Reply #66 on: Nov 9th, 2013, 6:12pm » |
Quote Modify
|
on Nov 9th, 2013, 5:31pm, Janzert wrote:| Having said that, after some thought I'm not sure if it's possible for the two methods to ever cause different pairings. |
|
Wait, the two methods can certainly cause different pairings, and you gave an example of that, right? I expect that all priorities except the lowest priority (namely folding pairing) will be respected by both algorithms. If so, the remaining question is whether one algorithm gets "closer" to folding pairing than the other algorithm does, based on some mathematical definition of "closer".
|
|
IP Logged |
|
|
|
aaaa
Forum Guru
Arimaa player #958
Posts: 768
|
|
Re: 2014 World Championship Rules
« Reply #67 on: Nov 9th, 2013, 7:37pm » |
Quote Modify
|
on Nov 7th, 2013, 2:48pm, Janzert wrote:| There also seems to be a bug that rarely gets the rank order wrong when utpr is tied and it needs to tie break with stpr. Not sure what is triggering or going wrong with that yet. |
|
From the looks of it, this is caused by a minuscule difference in UTPR. I tried to prevent this from happening by having the iterative method that calculates the performance ratings enforce a uniform calculation for each player each round, but I guess this can go astray whenever any isomorphism is established over multiple rounds.
on Nov 9th, 2013, 5:31pm, Janzert wrote:| Just to be clear those ranks just by ratings are a straight print out of the internal ranks from the pairing program. |
|
Then this is just a misunderstanding. Responsibility for adhering to the pairing rules is mostly concentrated in the actual respective scheduling algorithms (functions bestScheduleFTE and bestScheduleSwiss), which already need the number of losses for the remaining players in their calculation and treat the order of the given list of players as a further tiebreaker for the ranking. The order, as externally given, is by UTPR, then STPR and finally by earlier occurrence in the seed file.
|
|
IP Logged |
|
|
|
Janzert
Forum Guru
Arimaa player #247
Gender:
Posts: 1016
|
|
Re: 2014 World Championship Rules
« Reply #68 on: Nov 10th, 2013, 8:52am » |
Quote Modify
|
on Nov 9th, 2013, 6:12pm, Fritzlein wrote:
Wait, the two methods can certainly cause different pairings, and you gave an example of that, right? |
|
It turns out that the example above is actually an example of two different valid pairings. I've now added the sum of squares of rank differences to the differing pairings to show that. I apparently calculated it wrong when initially finding this example.
Janzert
|
|
IP Logged |
|
|
|
Janzert
Forum Guru
Arimaa player #247
Gender:
Posts: 1016
|
|
Re: 2014 World Championship Rules
« Reply #69 on: Nov 10th, 2013, 8:56am » |
Quote Modify
|
on Nov 9th, 2013, 7:37pm, aaaa wrote:
From the looks of it, this is caused by a minuscule difference in UTPR. |
|
Ahh, I should have known to look for that. I had to deal with the same issue in my own implementation. The joys of floating point.
Janzert
|
|
IP Logged |
|
|
|
aaaa
Forum Guru
Arimaa player #958
Posts: 768
|
|
Re: 2014 World Championship Rules
« Reply #70 on: Nov 10th, 2013, 2:02pm » |
Quote Modify
|
on Nov 9th, 2013, 7:37pm, I wrote:| I guess this can go astray whenever any isomorphism is established over multiple rounds. |
|
After properly thinking about how the algorithm actually calculates the performance ratings, I realized that this statement above doesn't make sense, so I investigated what really makes these rating discrepancies occur. It turns out that these are the result of perfectly even performances occurring through differently structured "beat paths". Let me illustrate this with graphs denoting players beating each other in the two given scenarios. The colored nodes represent the "even" players, with their colors matching if and only if their performance ratings as calculated by the algorithm do.
wrongsort_22:
wrongsort_38:
Given the asymmetry, it doesn't seem that unfair to tolerate these false assessments of unequal performances.
|
|
IP Logged |
|
|
|
clyring
Forum Guru
Arimaa player #6218
Gender: 
Posts: 359
|
|
Re: 2014 World Championship Rules
« Reply #71 on: Nov 10th, 2013, 9:00pm » |
Quote Modify
|
Asymmetry? In my eyes, those are all examples of symmetry with respect to reversal of edge direction.
|
|
IP Logged |
I administer the Endless Endgame Event (EEE). Players welcome!
|
|
|
Janzert
Forum Guru
Arimaa player #247
Gender:
Posts: 1016
|
|
Re: 2014 World Championship Rules
« Reply #72 on: Nov 10th, 2013, 9:07pm » |
Quote Modify
|
on Nov 10th, 2013, 2:02pm, aaaa wrote:
Given the asymmetry, it doesn't seem that unfair to tolerate these false assessments of unequal performances. |
|
In wrongsort_22 p19 & p11 are 1 least significant bit* above 1.0 while the rest of those 'same rating' players are 1 lsb below 1.0. In the wrongsort_38 example, p37 is exactly 1.0, the 'red' group is 1 bit shy of 1.0, and p3 is off by it's 1st and 3rd least significant bits.
Given that, I'm pretty hesitant to say it's an actual rating difference and not an artifact of floating point inaccuracies.
Janzert
* In the significand, the exponent is admittedly quite small still.
|
|
IP Logged |
|
|
|
aaaa
Forum Guru
Arimaa player #958
Posts: 768
|
|
Re: 2014 World Championship Rules
« Reply #73 on: Nov 10th, 2013, 10:49pm » |
Quote Modify
|
Of course all those ratings are really equal. My point concerned the fairness of letting it go unaddressed, as isomorphism isn't violated and players aren't, for example, treated differently based on where they are on the seed list.
|
|
IP Logged |
|
|
|
clyring
Forum Guru
Arimaa player #6218
Gender:
Posts: 359
|
|
Re: 2014 World Championship Rules
« Reply #74 on: Nov 16th, 2013, 9:09pm » |
Quote Modify
|
I doubt it will be an issue this year given the discontinuation of UTPR in pairings.
|
|
IP Logged |
I administer the Endless Endgame Event (EEE). Players welcome!
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print