4

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)
                                                                                        ++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);
}
6
  • Are you using Monte Carlo simulation to calculate the equity?
    – marco0009
    Dec 1, 2009 at 8:13
  • What's the difference between: "pick up one hand randomly from both players and after that, we choose a board cards" and "first chooses the hole cards and the board cards after that"? Dec 1, 2009 at 8:23
  • in regards to the second question, is the number of attempts matter?
    – Anycorn
    Dec 1, 2009 at 8:26
  • unknown: No, it doesn't matter how many attempts there are. Even if there's two, the results gets biased.
    – nhaa123
    Dec 1, 2009 at 8:29
  • That if-for-if-for-if-for-if-for-if-for-else-else-else-else-else pyramid is ... interesting. What does it do?
    – Svante
    Dec 3, 2009 at 16:46

5 Answers 5

1

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.

1
  • I was about to post exactly the same thing than you. The correct way to do this, is to simulate the stack of remaining cards and deal them in the same way than your game.
    – BlueTrin
    Dec 3, 2009 at 16:31
0

can it be a random number generator? Could not tell from the code what number generator is used.5

1
  • I'm using Boost's lagged_fibonacci607. It's the same behavior with mersenne twister.
    – nhaa123
    Dec 1, 2009 at 8:20
0

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.

3
  • Already done this. Ran ~100-300 million trials in both way. If it chooses hole cards first, it doesn't work (biased). If it chooses board cards first, it works.
    – nhaa123
    Dec 1, 2009 at 8:53
  • I hesitated to bring it up at first because the first situation you mentioned stated you were getting the correct equity. But I'll go ahead and ask now. Are you sure you're using an unbiased method for shuffling?
    – marco0009
    Dec 1, 2009 at 9:18
  • I believe I am. I'm generating all possible boards to an array (~2.5 million outcomes) and choosing one with lagged fibonacci / mersenne twister.
    – nhaa123
    Dec 1, 2009 at 9:23
0

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.

6
  • Hi. I determined the equities by enumerating all possible outcomes. Also, compared the results to PokerStove (AA-KK: 81.95% - 18.05%). Regarding the second problem, I've compared the results against PokerStove and Holdem Ranger. I'll put a pseudo-code to the original post how to evaluation goes.
    – nhaa123
    Dec 1, 2009 at 10:26
  • I cannot use a class for a card. It's way too slow. I need to have at least ~1-5 million evaluations per second. On top of that, I'm using 2+2 evaluator. In other words, it's about 100Mb array containing all possible 7-card combinations with their ranks. This whole thing works just as it should. However, I've only got those two problems which I cannot understand. I know it has something to do with statistical mathematics.
    – nhaa123
    Dec 2, 2009 at 7:12
  • The thing is that the algorithm works, as I said. It's only when I change the order how cards are selected (board cards -> hole cards, hole cards -> board cards). The project it in it's final steps and the optimization process is ongoing. I've already profiled the code etc. Please re-read my original question.
    – nhaa123
    Dec 3, 2009 at 7:11
  • It "works" perhaps, but you will never get millions of evaluations in general this way. As you wrote, you get a lot of collisions when more cards are already used. This is unavoidable with your data structure. Your data structure is an "optimization" gone wrong.
    – Svante
    Dec 3, 2009 at 8:27
  • Well, currently, this get ~150k - 1.6 million evaluations per second, which is fine (C2D E4500).
    – nhaa123
    Dec 3, 2009 at 12:37
0

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:

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.