3 ms·
I'm not sure exactly what the algorithm is for choosing pairs, but naively it seems like it should be possible to bucket the players in some way, at which point
by saghm 5y ago
I'm not sure exactly what the algorithm is for choosing pairs, but naively it seems like it should be possible to bucket the players in some way, at which point the pairings within each bucket can be generated in parallel, with buckets getting merged if they get too small. The tricky part is coming up with a way to bucket them that's both efficient and will lead to enough pairings, and I'm not sure what the criteria is. If it's completely random, then ideally any bucketing should work fine. If it's based on ratings or existing records, it seems like starting by grouping players within certain ranges of that stat should work (assuming the boundaries can be picked based on the distribution of the players). I don't know enough to know for sure that bucket grouping would work here, but it doesn't seem like knowing the entire set of results beforehand should be necessary (unless there's some standard algorithm for choosing pairings that's very prescriptive).
- dmurray 5y agoThe pairing is based on ratings and existing records, and happily isn't dependent on a standard prescriptive algorithm, unlike traditional Swiss tournaments. It would be fine to accept some reordering of game-finishing events. I'm certain the process can be parallelized - it just hadn't been considered necessary before.
- lmm 5y agoIf they're doing tournament pairing the traditional way then you can't do that kind of bucketing because it's always possible that someone will "spill" down if they can't be matched in their bucket, and that would completely change the pairing in each lower bucket (if you add one more person at the top of a bucket you would zig-zag down all the pairings below them, except the new pairings have nothing in common with the previous pairings and so you have to redo things like whether they've played each other before).