我正在开发 Texas Hold 'em hand-range equity evaluator,它使用 Monte Carlo 模拟评估手牌分布。我遇到了两个烦人的问题,我无法给出任何理由。
问题#1:
简而言之,评估器首先从玩家的手牌分布中挑选手牌。比如说,我们有以下内容:
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...
}
替代方法要快得多,因为不再有那么多碰撞了。然而,结果非常有偏见。为什么?如果评估者通过一次或多次尝试选择一只手,这有什么关系?同样,显然是这样,但我不明白为什么。
编辑:
仅供引用,我使用的是 Boost 的随机数生成器,更准确地说是 boost::lagged_fibonacci607。不过,同样的行为也会发生在梅森扭曲器上。
下面是代码:
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)
++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);
}
最佳答案
对于问题 #1,我不认为偏见是问题固有的,而是您的实现所固有的。
我的意思是,如果你发无限多手牌,首先发牌,然后玩家发牌 (*),并且只考虑一手牌是 AA 的“发牌”另一个是 KK,胜率应该和你发无限多手牌一样,先发玩家手牌,然后发牌,再次只考虑一手是 AA,一手是 KK 的“发牌”。
当您第一次从一组离散的手牌中选择玩家手牌时,您会限制可以放置在棋盘上的牌。
如果您先放置公共(public)牌,则没有限制,如果您在此之后随机选择一对 AA/KK 手牌,直到您没有碰撞,则您有 (*)强>
我会看看是否可以详细说明。
关于c++ - 统计数学问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/1824633/