Statistical mathematics issues
I'm developing a Texas Hold 'em hand-range equity evaluator, which evaluates hand-distributions with Monte Carlo -simulation. I've faced two annoying problems which behaviors I cannot give any reason.
Problem #1:
In a nut shell, the evaluator works by first picking up hands from player's hand-distributions. Say, that we have the following:
AA - 6 hands KK - 6 hands
We pick up a board cards and after that, one hand randomly from both players which does not collide with the board cards.
The given example gives the following equities, which are correct:AA = ~81.95% KK = ~18.05%
Now the problem. If the evaluator first chooses the hole cards and the board cards after that, this doesn't work. Then I get something like this:
AA = ~82.65% KK = ~17.35&
Why does it get biased? What does it matter, if one chooses hole cards or board cards first? Obviously it does, but cannot understand why.
Problem #2:
If I have ten hand-distributions with the following ranges:
AA KK+ QQ+ JJ+ TT+ 99+ 88+ 77+ 66+ 55+
my evaluator is very slow. This is due the fact that when choosing hole cards from the distributions, there's a lot of collisions. There's many trials before we get ten hole cards and a board, which does not collide. So, I changed the method how the evaluator chooses a hand from the distribution:
// Original - works.
void HandDistribution::Choose(unsigned __int64 &usedCards, bool &collided)
{
_pickedHand = _hands[(*Random)()];
collided = (_pickedHand & usedCards) != 0;
usedCards |= _pickedHand;
}
// Modified - Doesn't work; biased equities.
void HandDistribution::Choose(unsigned __int64 &usedCards, bool &collided)
{
// Let's try to pick-up a hand from this distribution ten times, before
// we give up.
// NOTE: It doesn't matter, how many attempts there are (except one). 2 or 10,
// same biased results.
for (unsigned int attempts = 0; i < 10; ++i) {
_pickedHand = _hands[(*Random)()];
collided = (_pickedHand & usedCards) != 0;
if (!collided) {
usedCards |= _pickedHand;
return;
}
}
// All the picks collided with other hole cards...
}
The alternative method is much faster, since there are not so many collisions anymore. However, the results are VERY biased. Why? What does it matter, if the evaluator chooses a hand by one attempt or several? Again, obviously it does, but I cannot figure out why.
Edit:
FYI, I am using Boost's random number generator, more precisely boost::lagged_fibonacci607. Though, the same behavior occurs with mersenne twister as well.
Here's a the code as it is:
func Calculate()
{
for (std::vector<HandDistribution *>::iterator it = _handDistributions.begin(); it != _handDistributions.end(); ++it) {
(*it)->_equity = 0.0;
(*it)->_wins = 0;
(*it)->_ties = 0.0;
(*it)->_rank = 0;
}
std::bitset<32> bsBoardCardsHi(static_cast<unsigned long>(_boardCards >> 32)),
bsBoardCardsLo(static_cast<unsigned long>(_boardCards & 0xffffffff));
int cardsToDraw = 5 - (bsBoardCardsHi.count() + bsBoardCardsLo.count()), count = 0;
HandDistribution *hd_first = *_handDistributions.begin(), *hd_current, *hd_winner;
unsigned __int64 deadCards = 0;
boost::shared_array<unsigned __int64> boards = boost::shared_array<unsigned __int64>(new unsigned __int64[2598960]);
memset(boards.get(), 0, sizeof(unsigned __int64) * 2598960);
hd_current = hd_first;
do {
deadCards |= hd_current->_deadCards; // All the unary-hands.
hd_current = hd_current->_next;
} while (hd_current != hd_first);
if (cardsToDraw > 0)
for (int c1 = 1; c1 < 49 + (5 - cardsToDraw); ++c1)
if (cardsToDraw > 1)
for (int c2 = c1 + 1; c2 < 50 + (5 - cardsToDraw); ++c2)
if (cardsToDraw > 2)
for (int c3 = c2 + 1; c3 < 51 + (5 - cardsToDraw); ++c3)
if (cardsToDraw > 3)
for (int c4 = c3 + 1; c4 < 52 + (5 - cardsToDraw); ++c4)
if (cardsToDraw > 4)
for (int c5 = c4 + 1; c5 < 53; ++c5) {
boards[count] = static_cast<unsigned __int64>(1) << c1
| static_cast<unsigned __int64>(1) << c2
| static_cast<unsigned __int64>(1) << c3
| static_cast<unsigned __int64>(1) << c4
| static_cast<unsigned __int64>(1) << c5;
if ((boards[count] & deadCards) == 0)
++count;
}
else {
boards[count] = static_cast<unsigned __int64>(1) << c1
| static_cast<unsigned __int64>(1) << c2
| static_cast<unsigned __int64>(1) << c3
| static_cast<unsigned __int64>(1) << c4;
if ((boards[count] & deadCards) == 0)
开发者_Python百科 ++count;
}
else {
boards[count] = static_cast<unsigned __int64>(1) << c1
| static_cast<unsigned __int64>(1) << c2
| static_cast<unsigned __int64>(1) << c3;
if ((boards[count] & deadCards) == 0)
++count;
}
else {
boards[count] = static_cast<unsigned __int64>(1) << c1
| static_cast<unsigned __int64>(1) << c2;
if ((boards[count] & deadCards) == 0)
++count;
}
else {
boards[count] = static_cast<unsigned __int64>(1) << c1;
if ((boards[count] & deadCards) == 0)
++count;
}
else {
boards[0] = _boardCards;
count = 1;
}
_distribution = boost::uniform_int<>(0, count - 1);
boost::variate_generator<boost::lagged_fibonacci607&, boost::uniform_int<> > Random(_generator, _distribution);
wxInitializer initializer;
Update *upd = new Update(this);
_trial = 0;
_done = false;
if (upd->Create() == wxTHREAD_NO_ERROR)
upd->Run();
hd_current = hd_first;
::QueryPerformanceCounter((LARGE_INTEGER *) &_timer);
do {
hd_current = hd_first;
unsigned __int64 board = boards[Random()] | _boardCards, usedCards = _deadCards | board;
bool collision;
do {
hd_current->Choose(usedCards, collision);
hd_current = hd_current->_next;
} while (hd_current != hd_first && !collision);
if (collision) {
hd_first = hd_current->_next;
continue;
}
unsigned int best = 0, s = 1;
// Evaluate all hands.
do {
hd_current->_pickedHand |= board;
unsigned long i, l = static_cast<unsigned long>(hd_current->_pickedHand >> 32);
int p;
bool f = false;
if (_BitScanForward(&i, l)) {
p = _evaluator[53 + i + 32];
l &= ~(static_cast<unsigned long>(1) << i);
f = true;
}
if (f)
while (_BitScanForward(&i, l)) {
l &= ~(static_cast<unsigned long>(1) << i);
p = _evaluator[p + i + 32];
}
l = static_cast<unsigned long>(hd_current->_pickedHand & 0xffffffff);
if (!f) {
_BitScanForward(&i, l);
p = _evaluator[53 + i];
l &= ~(static_cast<unsigned long>(1) << i);
}
while (_BitScanForward(&i, l)) {
l &= ~(static_cast<unsigned long>(1) << i);
p = _evaluator[p + i];
}
hd_current->_rank = p;
if (p > best) {
hd_winner = hd_current;
s = 1;
best = p;
} else if (p == best)
++s;
hd_current = hd_current->_next;
} while (hd_current != hd_first);
if (s > 1) {
for (std::vector<HandDistribution *>::iterator it = _handDistributions.begin(); it != _handDistributions.end(); ++it) {
if ((*it)->_rank == best) {
(*it)->_ties += 1.0 / s;
(*it)->_equity += 1.0 / s;
}
}
} else {
++hd_winner->_wins;
++hd_winner->_equity;
}
++_trial;
hd_first = hd_current->_next;
} while (_trial < trials);
}
For problem #1 I don't think the bias is intrinsic to the problem but rather to your implementation.
What I mean is that if you deal an infinite number of hands, dealing first the board cards and then the player hands (*), and only consider the "deals" where one hand is AA and the other is KK the equity should be the same as if you deal an infinite number of hands, dealing first the player hands and then the board cards, and again only consider the "deals" where one hand is AA and one is KK.
When you first select the player hands from a discrete set of hands you restrict the cards that can be placed on the board.
If you place the board cards first you have no restriction and if you after this randomly select a pair of AA/KK hands until you don't get a collision, you have the analgoue of (*)
I'll see if I can elaborate a little more.
can it be a random number generator? Could not tell from the code what number generator is used.5
I can't say for certain as I obviously can't see the entire program source, but my first suspicion upon seeing the differing equities is that for your Monte Carlo simulation you simply aren't running enough trials to get a good evaluation of the hand's equity.
It could very well be some other problem but it is simple to figure out if this is the cause of your discrepancy. I would try running a very large number of trials (in excess of 1 million) multiple times and see how widely your equities vary.
I think that you shouldn't use collisions. They are very inefficient, especially when a lot of them occur, and when you try to reduce their number, it is very likely that you introduce a bias: you simulate a distribution by the probability of collisions, so having the complete set of possible collisions is necessary. Any reduction must keep the distribution the same, so this is like reducing a fraction.
Problem 1: How did you determine that the first set of equities is correct? Independent sources? I would assume that first picking the hole cards, then the board cards from the remaining cards would be "obviously" correct (or is this naive?), as long as picking the hole cards can be done independently (see problem 2).
Problem 2: Hand (hole card) distributions are not independent when the hand ranges overlap. If one player has AK+, the other hands unknown, the situation is different from where one player has AK+, and another AA: in the second case, it is more probable that the first player actually has KK than in the first case. In your example of ten hands, the player with 55+ is very unlikely to have something like KK. Again, how did you determine the correct equities?
I'm sorry that I can't give you a conclusive answer to your problems, but I think that you need to do or read about some involved statistical analysis to deterministically produce correct hand distributions and ensure that they are also independent of the order of players.
EDIT: Thank you for posting something that lets us gauge the kind of code you are working with. As harsh as it may sound, I now tend to advise you to start from scratch, but first learn about structured programming.
Just a few hints: You currently seem to represent a set of cards as a 52-element bit-field. While this seems efficient at first, you see that just dealing cards from such a deck is very complicated. So, keep it simple: make a class that describes a card; make a class that describes a deck of cards; implement a Fisher-Yates shuffle for that; give it a deal() method that returns a card, etc.. Oh, and don't use pass-by-reference, use return values instead. You want to see where values get modified, without diving into each subroutine.
EDIT 2: Regarding "I cannot use a class, it is too slow": What gives you the idea that a using classes makes your code slow? Classes are just a compile time concept in C++ (approximately). Even if you don't want to use classes or structs, use proper data structures like arrays; this is not less efficient than bit fiddling.
Your problem is that in order to get a number of random card from a deck, you batter it with sets of random requests until one succeeds completely, instead of just requesting that certain number of the unused cards. The algorithmic complexity of this approaches infinity as the number of available cards decreases.
This is what the famous quote "Premature optimization is the root of all evil" is about: you prematurely "optimized" your data representation, and now you can't efficiently get random cards anymore. Get your algorithm right first, then look for bottlenecks (that means testing and measuring, a.k.a. profiling) and optimize those.
Andreas Brinck replied to your problem #1.
I think that your problem #2 is caused by the same issue.
Instead of detecting collisions, just simulate a stack of cards and pick in the remaining cards. If you do not do this, you have to be careful about the probabilities or you may cause a bias in the conditional probabilities depending of your algorithm.
By the way, this might be of some help for you:
- http://en.wikipedia.org/wiki/Poker_probability_%28Texas_hold_%27em%29
加载中,请稍侯......
精彩评论