The game of Bridge is played with 52 different playing cards that are randomly distributed among four players, each player ending up with thirteen cards: a so called "deal". Roughly a little less than 2^96 Bridge deals are possible. In this document the requirements for a program that generates random deals are described as follows:
- The software should be able to generate every possible bridge deal, since that is also possible with manual dealing.
- The software should generate every deal with the same probability, without being influenced by the board number, previous hands or any other circumstance.
- It should be impossible to predict deals, even after having seen all other deals in the session.
This document goes on to state that pseudo random generators cannot be used to generate deals as seeing the first elements of a pseudo random sequence will make it possible to compute the seed used and thus enable a hacker to predict the deals that will follow.
Moreover, as most pseudo random generators take a seed of 32 bits it should follow that these generators will be capable of producing at best 2^32 different Bridge deals as opposed to the required 2^96 and that, following the so called Birthday paradox, it is likely that the same deal will be produced after the square root of 2^32 deals.
The author of the document that describes the requirements of a Bridge deal producing application has written a program, used world wide to produce random deals, that generates a 96 bit seed using a human typing randomly on the keyboard. In fourteen years no flaws have been demonstrated in this approach.
I would like to write a routine that forgoes the need to use human input to generate the seed required.
In comes the RNGCryptoServiceProvider
. I used this using the code below to generate random numbers, first in the range 1 to 52, then in the range 1 to 51, and so forth until one card remains.
Testing the resulting deals I am pretty confident that this code is capable of producing any deal it is capable of with the same probability and that the chance of any card ending up with one of the four players equals 0.25.
But as the strength of the seed used in the RNGCryptoServiceProvider is not known to me I am wondering if:
- This code will be able to, or can be adapted to, producing 2^96 different deals.
- This code's next deal is not going to be predictable.
EDIT The method to obtain random numbers previously mentioned in this question was flawed. This distracted from the main question, being if this code is able to produce 2^96 distinct Bridge deals. I replaced the random number generator with the one published by Stephen Taub and Shawn Farkas in the MSDN magazine
Code used to produce a cryptographically secure random number in the ranges 1-52, 1-51, and so on up to 1-2, taken from this website
/// <summary>
/// Returns a random number within a specified range.
/// </summary>
/// <returns>
/// A 32-bit signed integer greater than or equal to <paramref name="minValue"/> and less than <paramref name="maxValue"/>; that is, the range of return values includes <paramref name="minValue"/> but not <paramref name="maxValue"/>. If <paramref name="minValue"/> equals <paramref name="maxValue"/>, <paramref name="minValue"/> is returned.
/// </returns>
/// <param name="minValue">The inclusive lower bound of the random number returned.</param>
/// <param name="maxValue">The exclusive upper bound of the random number returned. <paramref name="maxValue"/> must be greater than or equal to <paramref name="minValue"/>.</param>
/// <exception cref="T:System.ArgumentOutOfRangeException"><paramref name="minValue"/> is greater than <paramref name="maxValue"/>.</exception>
public override Int32 Next(Int32 minValue, Int32 maxValue)
{
if (minValue > maxValue) throw new ArgumentOutOfRangeException("minValue");
if (minValue == maxValue) return minValue;
Int64 diff = maxValue - minValue;
while (true)
{
//The cryptoProvider is of type RNGCryptoServiceProvider.
cryptoProvider.GetBytes(uint32Buffer); //The uint32Buffer has a size of 4 bytes.
UInt32 rand = BitConverter.ToUInt32(uint32Buffer, 0);
Int64 max = (1 + (Int64)UInt32.MaxValue);
Int64 remainder = max % diff;
if (rand < max - remainder)
{
return (Int32)(minValue + (rand % diff));
}
}
}