Ranking the pairs in a bridge match - what precision?

In summary, The conversation revolves around a bug that was discovered in a program that calculates rankings from the results of a bridge tournament. The bug can be fixed by increasing the precision, but the exact precision needed is not clear. The existing code rounds to one decimal place, but this can cause rounding errors. Various solutions and approaches are discussed, such as using floating point numbers, arbitrary precision arithmetic, or increasing the precision to a specific number of bits. The goal is to find a straightforward solution that can be implemented by the programmer without causing major changes to the code.
  • #1
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
41,229
9,785
I've come across a bug in a program that calculates rankings from the results of a bridge tournament. It should be fixable by increasing the precision, but it's not obvious what the precision needs to be. (I don't have access to the source and anticipate push back from the coder, so I need it to be an evidently straightforward change.)
Here's how standard scoring works:
Each hand is played on up to some number of tables (at most 30, say). Suppose at some table pair X plays the NS cards against pair Y as EW. A score is calculated based on the result at that table. This score is compared with the other scores for the same hand when played by other pairs. If the hand is played N times in all, the NS pair that got the worst result scores 0 points, and the best gets 2(N-1), with other rankings linearly interpolated (i.e. 0, 2, 4... 2(N-1)). NS pairs that got the same result share their points, so e.g. two equal tops get 2N-3 each. Similarly the EW pairs.
An awkward complication is that some hands might be played more often than others. So after the points scoring described above, the scores are rescaled. If a hand was only played M times instead of N times, the points are scaled up by (N-1)/(M-1). This can produce rounding errors. The existing code rounds to one decimal place(!), so 8.25 becomes 8.3 etc., giving some pairs a 0.05 points bonus. Pairs that benefit from this more than others may end up with a correspondingly higher overall points score, when perhaps they should be equal.
So here's the challenge: how precise do the calculations need to be such that the true overall placings can be deduced from the total points? (The total may be made up of up to 30 scores for individual hands.) Bear in mind that a theoretical exact score may involve a sum of fractions like n/28, n/27, ...
One obvious solution would be to work entirely in integers by scoring each hand out of 2*LCM(29, 28...) instead, but that's 4.6E12. Does this imply the precision would need to be 2E-13?
 
Mathematics news on Phys.org
  • #2
Can't you just do the calculation with floating point numbers and only round at the end. There may still be rounding errors but they will ve of the order of the machine precision.
 
  • #3
CompuChip said:
Can't you just do the calculation with floating point numbers and only round at the end. There may still be rounding errors but they will ve of the order of the machine precision.
As I say, I don't have access to the source, and I don't even know what language it is in. Even if floating point is an option, it does not have unlimited precision. So I'd like some basis for saying what precision will always be good enough.
 
  • #4
If your analysis that gives 4.6e12 is correct, floating point 64-bit (or "double") precision should be OK since that is good for 16 significant figures.

Or, you could use a language or a library that supports exact rational integer arithmetic with arbitrary precision integers. http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic lists a few.
 
  • #5
Another approach: for how many games does this need to work? Because if the problem is that the bonus of 0.05 adds up to e.g. 1.0 over 20 games, you can fix it by increasing the precision to 0.0005 so that it doesn't influence the end result when rounded to 1 decimal.
 
  • #6
AlephZero said:
If your analysis that gives 4.6e12 is correct, floating point 64-bit (or "double") precision should be OK since that is good for 16 significant figures.
Yes, I realize that might work, depending on the language it's written in. But since it's going to be a battle anyway, I need to be sure of my fix. So, partly, I'm looking for confirmation of my analysis.
Or, you could use a language or a library that supports exact rational integer arithmetic with arbitrary precision integers. http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic lists a few.
And I quite possibly would have done that had I written the software, but I see no prospect of getting this guy to make such a radical change.
 
  • #7
CompuChip said:
Another approach: for how many games does this need to work? Because if the problem is that the bonus of 0.05 adds up to e.g. 1.0 over 20 games, you can fix it by increasing the precision to 0.0005 so that it doesn't influence the end result when rounded to 1 decimal.
The .05 was the relatively simple case that made me aware of the bug. But as I explained in the OP, the exact scores can be a sum of fractions with denominators up to 29. This means that a difference like 1/28-1/29 could be a genuine difference between two totals, not just rounding error. Or even 1/26-1/27-1/28+1/29, etc.
 
  • #8
Hmm, how bad can it be...?
The guy may be interested in what the effect is if he replaces all his numbers by doubles.
Just adding another digit of precision or introducing a fraction-library kind of raises my hackles - the first doesn't really solve the problem and the second is overkill. :wink:
 
  • #9
The way I understand it he doesn't have access to the source code, but somehow there is an external parameter that determines to how many decimal places results are rounded.
 
  • #10
CompuChip said:
The way I understand it he doesn't have access to the source code, but somehow there is an external parameter that determines to how many decimal places results are rounded.
No, there's no external parameter, but I am assuming that increasing precision to some specified number of bits should be straightforward, if that number of bits is not too great. I'd like to be able to announce to the programmer, and other customers, "just increase it to N bits and the whole problem will be solved". When I sat down to analyse it, I was surprised how tricky it is mathematically.
 
  • #11
haruspex said:
No, there's no external parameter, but I am assuming that increasing precision to some specified number of bits should be straightforward, if that number of bits is not too great. I'd like to be able to announce to the programmer, and other customers, "just increase it to N bits and the whole problem will be solved". When I sat down to analyse it, I was surprised how tricky it is mathematically.

Imagine the great impression you can make when introducing floating point numbers.
From your story I get the impression they have never heard of them!
Once they see them at work, they may gain so much respect for you! :tongue:
Or are you bent on an integer-type fixed-point solution?

Once upon a time (20 years ago by now) I worked for a company that had to process a lot of measurements.
I implemented an algorithm using fixed-point arithmetic, in my naivety thinking that the gain in performance was significant enough to warrant it.
(I had only just completed my studies and was still a bit estranged from reality I'm afraid.)
However, my employer complained that the results did not fit well enough on what was expected.
I tried to explain how important it was to use an integer-type algorithm... but he didn't buy it.
Just to make a point, I converted the algorithm to floating point to show it would fit perfectly then.
... afterward every calculation was always done with full length double arithmetic. o:)
 
  • #12
haruspex said:
No, there's no external parameter, but I am assuming that increasing precision to some specified number of bits should be straightforward, if that number of bits is not too great.
Unless the code is very hacky ("store 1/10 scores as integer"), I would expect that the internal numbers are floats or doubles anyway. The coder would just have to move the rounding from individual hands to the display of the results.
Float should make rounding errors (changing positions) very unlikely, and a double should remove them completely, I agree with AlephZero.
 
  • #13
Thanks everyone for your comments.
Yes, I understand that IEEE double gives 53 bits. (The benefit of switching to floating point, of course, is nothing to with the the difference between fixed and floating per se; it's just that double uses a 64 bit word as standard. 64 bit fixed would be even better.)
If my analysis is right then that seems adequate, but is it? Part of the software fix would be applying a threshold to the total scores for considering two values to be equal. Assuming some error accumulation, we may only have, say, 50 bit accuracy by the end. The total scores could be up to 900, leaving 40 bits for the fractional part. My analysis says real differences could be as small as 2E-12, or about 2-12. OK, so it doesn't absolutely guarantee no mistakes, but the odds of such a pathological case are so small it won't happen in the life of the universe.
That leaves me with two concerns:
- is my analysis right? (This is really why I posted on this forum - I thought the problem was mathematically interesting - but nobody has commented on that.)
- what if the code is so archaic that 64 bit formats are not available?
I guess I'll just have to ask.
 
  • #14
haruspex said:
I thought the problem was mathematically interesting - but nobody has commented on that.

You have too many variables for a proper mathematical analysis.
It really is a real-world problem.
 
  • #15
haruspex said:
That leaves me with two concerns:
- is my analysis right? (This is really why I posted on this forum - I thought the problem was mathematically interesting - but nobody has commented on that.)

I agree it's interesting - but not being familiar with bridge tournment scoring, I found your description of the system hard to follow. (i.e. too much effort required to understand it and then try to analyse it).

But I would guess the system is sopposed to be useable without needing computer software, so it doesn't seem right that it needs extremely accurate calculations. Maybe the theoretical "worst cases" rarely happen in practice?
 
  • #16
AlephZero said:
I agree it's interesting - but not being familiar with bridge tournment scoring, I found your description of the system hard to follow. (i.e. too much effort required to understand it and then try to analyse it).
Yes, it's a bit of an investment. I'd no idea it was this intricate until I investigated the problem. Let me try to simplify it a bit without, I hope, misrepresenting it:
- each pair gets a set of N scores
- each score is a fraction, p/q, 0 <= p <= q <= N.
What is the closest two total scores can be without being equal?
But I would guess the system is supposed to be useable without needing computer software, so it doesn't seem right that it needs extremely accurate calculations. Maybe the theoretical "worst cases" rarely happen in practice?
I don't think anybody previously appreciated the existence of the problem. Certainly the theoretical worst cases can be assumed never to happen. Calculating how bad it can be with what frequency would be some orders of magnitude harder, though, so I hoped to have a guaranteed solution.
 
  • #17
haruspex said:
- each pair gets a set of N scores
- each score is a fraction, p/q, 0 <= p <= q <= N.
What is the closest two total scores can be without being equal?
With exact calculations, 1/lcm(1,2,...N).

This is a trivial lower bound on the deviation between scores, as all scores are a multiple of this value.
At the same time, it can be reached, and I think this can be proven with induction. It might require a lot of games, however.
 
  • #18
In practice, I would guess most hands would be played approximately the same number of times, so the realistic range is 1/lcm(M,N) where M is fairly close to N.

For eaxmplle lcm(1,2, ... 30) = 2^4.3^3.5^2.7.11.13.17.19.23.29 = 2.33 x 10^12.
But lcm(27,28,29,30) is only 2^2.3^3.5.7.29 = 109620.

Also, there will be some complcated constraints on the number of times different hands are played, because (presumably) each player or pair of players can only play their games sequentially, and may have to wait for their next opponents to finish. As an extreme (and completely unrealistic) example, it is probably impossible to have 29 hands each played 30 times and one hand only played once.
 
  • #19
AlephZero said:
In practice, I would guess most hands would be played approximately the same number of times, so the realistic range is 1/lcm(M,N) where M is fairly close to N.

For eaxmplle lcm(1,2, ... 30) = 2^4.3^3.5^2.7.11.13.17.19.23.29 = 2.33 x 10^12.
But lcm(27,28,29,30) is only 2^2.3^3.5.7.29 = 109620.

Also, there will be some complcated constraints on the number of times different hands are played, because (presumably) each player or pair of players can only play their games sequentially, and may have to wait for their next opponents to finish. As an extreme (and completely unrealistic) example, it is probably impossible to have 29 hands each played 30 times and one hand only played once.
Yes, that's not bad. This suggests a prepass which computes the LCM to use based on the actual numbers of times each hand was played.
Thanks.
 

1. How do you determine the ranking of pairs in a bridge match?

The ranking of pairs in a bridge match is determined by the number of points they have accumulated during the match. Points are awarded based on the number of tricks won by each pair and the contract they bid and fulfilled. The pair with the highest number of points is ranked first, followed by the pair with the second-highest points, and so on.

2. Is there a specific method for ranking pairs in a bridge match?

Yes, there are several methods for ranking pairs in a bridge match, including the Butler scoring method, the IMP scoring method, and the Victory Points scoring method. These methods take into account not only the number of points but also the level of competition and the margin of victory.

3. Can ranking the pairs in a bridge match be done with 100% precision?

No, it is not possible to rank pairs in a bridge match with 100% precision. This is because bridge is a game that involves both skill and luck. While scoring methods can provide a fair and accurate ranking, there is always a chance for unexpected outcomes and variations in performance.

4. How important is it to have a precise ranking in a bridge match?

The importance of having a precise ranking in a bridge match depends on the context. In a casual game, the ranking may not matter as much. However, in a competitive setting, a precise ranking can determine the winners and losers and have significant implications for future matches and tournaments.

5. Are there any strategies that pairs can use to improve their ranking in a bridge match?

Yes, there are certain strategies that pairs can use to improve their ranking in a bridge match. These include practicing and honing their skills, studying and analyzing their opponents' playing styles, and making strategic bids and plays based on the current score and situation in the match.

Similar threads

Replies
4
Views
563
  • Electrical Engineering
Replies
9
Views
428
Replies
3
Views
337
  • General Math
Replies
4
Views
7K
  • General Math
Replies
4
Views
3K
Replies
1
Views
3K
Replies
1
Views
2K
Replies
1
Views
2K
Replies
3
Views
1K
Back
Top