Databases
StackOverflow2013
Postsdbo
POStatistical mathematics issues
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POStatistical mathematics issues
    text
    copied!<p>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.</p> <p><b>Problem #1:</b></p> <p>In a nut shell, the evaluator works by first picking up hands from player's hand-distributions. Say, that we have the following:</p> <pre>AA - 6 hands KK - 6 hands</pre> <p>We pick up a board cards and after that, one hand randomly from both players which does not collide with the board cards.<br /> The given example gives the following equities, which are correct:</p> <pre>AA = ~81.95% KK = ~18.05%</pre> <p>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:</p> <pre>AA = ~82.65% KK = ~17.35&</pre> <p>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.</p> <p><b>Problem #2:</b></p> <p>If I have ten hand-distributions with the following ranges:</p> <pre>AA KK+ QQ+ JJ+ TT+ 99+ 88+ 77+ 66+ 55+</pre> <p>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:</p> <pre><code> // 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 &lt; 10; ++i) { _pickedHand = _hands[(*Random)()]; collided = (_pickedHand & usedCards) != 0; if (!collided) { usedCards |= _pickedHand; return; } } // All the picks collided with other hole cards... } </code></pre> <p>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.</p> <p><b>Edit:</b></p> <p>FYI, I am using Boost's random number generator, more precisely <i>boost::lagged_fibonacci607</i>. Though, the same behavior occurs with mersenne twister as well.</p> <p>Here's a the code as it is:</p> <pre><code> func Calculate() { for (std::vector&lt;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&lt;32> bsBoardCardsHi(static_cast&lt;unsigned long>(_boardCards >> 32)), bsBoardCardsLo(static_cast&lt;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&lt;unsigned __int64> boards = boost::shared_array&lt;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 &lt; 49 + (5 - cardsToDraw); ++c1) if (cardsToDraw > 1) for (int c2 = c1 + 1; c2 &lt; 50 + (5 - cardsToDraw); ++c2) if (cardsToDraw > 2) for (int c3 = c2 + 1; c3 &lt; 51 + (5 - cardsToDraw); ++c3) if (cardsToDraw > 3) for (int c4 = c3 + 1; c4 &lt; 52 + (5 - cardsToDraw); ++c4) if (cardsToDraw > 4) for (int c5 = c4 + 1; c5 &lt; 53; ++c5) { boards[count] = static_cast&lt;unsigned __int64>(1) &lt;&lt; c1 | static_cast&lt;unsigned __int64>(1) &lt;&lt; c2 | static_cast&lt;unsigned __int64>(1) &lt;&lt; c3 | static_cast&lt;unsigned __int64>(1) &lt;&lt; c4 | static_cast&lt;unsigned __int64>(1) &lt;&lt; c5; if ((boards[count] & deadCards) == 0) ++count; } else { boards[count] = static_cast&lt;unsigned __int64>(1) &lt;&lt; c1 | static_cast&lt;unsigned __int64>(1) &lt;&lt; c2 | static_cast&lt;unsigned __int64>(1) &lt;&lt; c3 | static_cast&lt;unsigned __int64>(1) &lt;&lt; c4; if ((boards[count] & deadCards) == 0) ++count; } else { boards[count] = static_cast&lt;unsigned __int64>(1) &lt;&lt; c1 | static_cast&lt;unsigned __int64>(1) &lt;&lt; c2 | static_cast&lt;unsigned __int64>(1) &lt;&lt; c3; if ((boards[count] & deadCards) == 0) ++count; } else { boards[count] = static_cast&lt;unsigned __int64>(1) &lt;&lt; c1 | static_cast&lt;unsigned __int64>(1) &lt;&lt; c2; if ((boards[count] & deadCards) == 0) ++count; } else { boards[count] = static_cast&lt;unsigned __int64>(1) &lt;&lt; c1; if ((boards[count] & deadCards) == 0) ++count; } else { boards[0] = _boardCards; count = 1; } _distribution = boost::uniform_int&lt;>(0, count - 1); boost::variate_generator&lt;boost::lagged_fibonacci607&, boost::uniform_int&lt;> > 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&lt;unsigned long>(hd_current->_pickedHand >> 32); int p; bool f = false; if (_BitScanForward(&i, l)) { p = _evaluator[53 + i + 32]; l &= ~(static_cast&lt;unsigned long>(1) &lt;&lt; i); f = true; } if (f) while (_BitScanForward(&i, l)) { l &= ~(static_cast&lt;unsigned long>(1) &lt;&lt; i); p = _evaluator[p + i + 32]; } l = static_cast&lt;unsigned long>(hd_current->_pickedHand & 0xffffffff); if (!f) { _BitScanForward(&i, l); p = _evaluator[53 + i]; l &= ~(static_cast&lt;unsigned long>(1) &lt;&lt; i); } while (_BitScanForward(&i, l)) { l &= ~(static_cast&lt;unsigned long>(1) &lt;&lt; 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&lt;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 &lt; trials); } </code></pre>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload