Razz is a project mainly written in C and PYTHON, it's free.
simplified version of razz poker for simulation
RAZZ SIMULATION
Problem Given an initial configuration (3 initial cards for player 1 and 1 for each other player) simulate a very large number of games. For every game get the rank obtained by player 1, where poker and flushes are discarded and the rank is computed with the [[http://en.wikipedia.org/wiki/Razz_%2528poker%2529][rules of razz poker]].
For example running
./razz 3 A 2 3
Will run 10^3 simulations with only one player which has as initial cards Ace, 2 and 3. The simulator must extract a total of 7 cards and take the 5 that give the best hand for razz.
./razz.py 3 A 2 3
-1 0.031
5 0.076
6 0.105
7 0.144
8 0.166
9 0.138
10 0.118
11 0.109
12 0.077
13 0.036
And it's interpreted as
A probabilistic solver Given the assumption that cards dealt to the other players don't interfere we can easily generate all the possible games and get the real probabilities. This could be useful to check whether the randomized algorithm also works correctly.
It's enough to follow those steps:
For this we use itertools in python which is very fast. All the possible combinations that we need to rank are $Binomial(TOT_CARDS - INITIAL_CARDS, 4)$
Randomized solver Instead of computing the probabilities it's faster to extract cards randomly for a big number of times and compute the result /a posteriori/.
* C All the C code is written with c99 standard, and K&R style. razz.c contains the implementation, and razz.h* contains the documentation and definition of the interface.
*** Data structures Only the number of the card is important, so a deck can be represented by a simple array of shorts. More space-aggressive approaches could be used since the cards only go from 1 to 13, but using bit-wise data-structures resulted to be slower due to misaligned data.
typedef short Card;
typedef struct Deck { Card cards[RAZZ_CARDS * RAZZ_REP]; int len; int orig_len; } Deck;
A hand is instead a dictionary, implemented on an array:typedef struct Hand { Card cards[RAZZ_CARDS]; /*< dictionary idx -> occurrences / int len; int diffs; } Hand;
Since I know what is the maximum possible value, it's very easy to assign to every position a card number, and use the array as a counter.
Keep this data structure is very good also to analyze the result.*** Algorithm The main goal is to make it as fast as possible, so everything too expensive should be avoided. In theory to pick randomly a card we should shuffle the whole deck every time and then pick a card.
But shuffling the whole deck is very expensive, so a better solution has to be found.
The solution that I implemented consists of
- generate a random index in the range (0, num_cards)
- swap the card at index with the last card
- decrement by 1 the number of cards
For example given the following deck:
$[1, 2, 4, 3]$
We pick index 1, so 2 is selected an swapped with the last element:
$[1, 3, 4 | 2]$
And now the deck the next random index can only select cards in the deck
$[1, 3, 4]$
This approach is many order of magnitudes faster then shuffling the whole deck and, for the property of the random function, it also gives the right probabilities.** Random generator choice Using random and lrand48 give the same result, while rand differs. Since lrand48 was also slower, I chose random*, and the choice does make a big difference, since profiling the program I noticed that the bottleneck is exactly the random call.
Another important tip is to avoid using the modulo function, and instead this pattern should be used:int pos = (int) (deck->len * (random() / (RAND_MAX + 1.0)));The % operator is slower and doesn't use all the bits from the generated random value.** Random() The random() function uses a non-linear, additive feedback, random number generator, employing a default table of size 31 long integers. It returns successive pseudo-random numbers in the range from 0 to (231)-1. The period of this random number generator is very large, approximately 16*((2**31)-1).
* Rand48()
The rand48() family of functions generates pseudo-random numbers, using a linear congruential algorithm
working on integers 48 bits in size. The particular formula employed is r(n+1) = (a r(n) + c) mod m.
The default value for the multiplicand a' is 0xfdeece66d (25214903917). The default value for the the addendc' is 0xb (11). The modulo is always fixed at m = 2 48. r(n) is called the seed of the
random number generator.
*** Perfomances With 10 millions simulations the C code is still very fast, less than 1 second:
$ time ./razz_fast 7 A 2 3 -1: 0.028419 5: 0.071538 6: 0.117815 7: 0.143025 8: 0.150514 9: 0.143172 10: 0.125754 11: 0.100989 12: 0.073119 13: 0.045655
real 0m0.942s user 0m0.930s sys 0m0.010s
Increasing even more the number of /games/ played make it slower but not significantly more precise.** Python The python version of the program is equivalent to the C program, but in python I didn't try to optimize too much, but only to make it readable and correct. The deck is implemented a list of integers, and to pick a random card it first chooses it randomly from the list and the remove it from the list.
def get_random_card(self): "" "Returns a card randomly from the deck, assuming it's already in random order """ c = choice(self.cards) self.cards.remove(c) return c
Putting them together So now there is a solver that uses exact probabilistic results, one randomized simulation in C and in python. Running the script glue.sh shows the results on a given initial situation for all the 3 modalities.
And as we can see already with 10^7 simulation run the C version is very precise. The python version runs much slower, and 10^5 simulations are not sufficient to get the same level of precision (as expected).
$ ./glue.sh A 2 3 theoretical result: -1 0.0283939662822 5 0.0715324057468 6 0.117993543393 7 0.143008174593 8 0.150201060998 9 0.143196964262 10 0.125620646038 11 0.101096867979 12 0.0732503917386 13 0.0457059789688
c program with 10^7 simulations: -1: 0.028382 5: 0.071485 6: 0.118071 7: 0.142907 8: 0.150132 9: 0.143166 10: 0.125617 11: 0.101164 12: 0.073303 13: 0.045772
python program with 10^5 simulations:
-1 0.01282
5 0.07924
6 0.13027
7 0.15419
8 0.16001
9 0.14831
10 0.1252
11 0.09468
12 0.06245
13 0.03283
Other random generators
This little simulation is based on the fact that randomness works. Pseudo random generators don't create real random numbers, but use a procedure that hides the footprints so that the numbers create the illusion of randomness.
This generators normally need a seed, which is the starting point of the sequence which will be created. /random numbers should not be generated with a method chosen at random/ (Knuth)
** Other possible generators