AndreaCrotti/Razz

Subversion checkout URL

You can clone with
or
.
simplified version of razz poker for simulation
C Python Shell
latest commit 2774547db8
authored
 Failed to load latest commit information. Doxyfile Makefile README.org Apr 18, 2011 check_mem.sh Feb 25, 2010 glue.sh Feb 25, 2010 precision.c Feb 25, 2010 precision.py razz.c Apr 15, 2011 razz.h razz.py Apr 17, 2011 test.py Apr 6, 2011 theory.py Apr 17, 2011

RAZZ SIMULATION

1 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 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

• there is 3% of probability to get a null hand, which is an hand where we don’t get 5 different cards
• there is 7% of getting a 5, which represents the best hand possible in Razz.

And so on.

2 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:

• take in input the cards
• remove them from the deck
• for every possible combination of 4 out of the remaining cards
• generate a razzHand
• rank it

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)\$

3 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.

3.1 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.

3.1.1 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.

3.1.2 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.

3.1.3 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.

3.1.3.1 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 (2**31)-1. The period of this random number generator is very large, approximately 16*((2**31)-1).

3.1.3.2 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 addend `c’ is 0xb (11). The modulo is always fixed at m = 2 ** 48. r(n) is called the seed of the random number generator.

3.1.4 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.

3.2 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
```

4 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   ```

5 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)

5.1 Other possible generators

• multiple with carry very fast and using only arithmetic given a large amount of random seeds It uses a similar formula to linear congruential generators but here the c changes at every execution.
• mersenne twister
Something went wrong with that request. Please try again.