Статистические вопросы математики - PullRequest
Новая
       6

Статистические вопросы математики

4 голосов
/ 01 декабря 2009

Я занимаюсь разработкой Техасского Холдема для оценки эквити диапазона рук, который оценивает распределения рук с помощью симуляции Монте-Карло. Я столкнулся с двумя досадными проблемами, поведение которых я не могу объяснить.

Задача № 1:

В ореховой скорлупе оценщик работает, сначала подбирая руки из распределения рук игрока. Скажем, что у нас есть следующее: 

AA - 6 hands
KK - 6 hands

Мы подбираем настольные карты, а затем одну руку случайным образом от обоих игроков, которая не сталкивается с настольными картами.
Данный пример дает следующие правильные акции: 

AA = ~81.95%
KK = ~18.05%

Теперь проблема. Если оценщик сначала выбирает закрытые карты и карты настольных карт после этого, это не работает. Тогда я получаю что-то вроде этого: 

AA = ~82.65%
KK = ~17.35&

Почему это предвзято? Какое это имеет значение, если сначала выбирают закрытые или настольные карты? Очевидно, что это так, но не могу понять, почему.

Задача № 2:

Если у меня есть десять раздач со следующими диапазонами: 

AA
KK+
QQ+
JJ+
TT+
99+
88+
77+
66+
55+

мой оценщик очень медленный. Это связано с тем, что при выборе закрытых карт из дистрибутивов возникает много коллизий. Есть много испытаний, прежде чем мы получим десять закрытых карт и доску, которая не сталкивается. Итак, я изменил метод, которым оценщик выбирает руку из распределения: 


// 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...
}

Альтернативный метод намного быстрее, так как столкновений уже не так много. Тем не менее, результаты ОЧЕНЬ предвзяты. Зачем? Какое это имеет значение, если оценщик выбирает руку одной или несколькими попытками? Опять же, очевидно, что это так, но я не могу понять, почему.

Edit:

К вашему сведению, я использую генератор случайных чисел 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);
}

Ответы [ 5 ]

1 голос
/ 01 декабря 2009

Для проблемы # 1 Я не думаю, что смещение присуще проблеме, а скорее вашей реализации.

Я имею в виду, что если вы разыгрываете бесконечное количество рук, раздаете сначала карты карт, а затем руки игрока (*) , и рассматриваете только «сделки», когда одной рукой является АА и другой - KK, эквити должен быть таким же, как если бы вы разыгрывали бесконечное количество рук, разыгрывая сначала руки игрока, а затем карты карт, и снова рассматривайте только «сделки», когда одна рука - AA, а другая - KK.

Когда вы впервые выбираете руки игрока из отдельного набора рук, вы ограничиваете карты, которые можно разместить на доске.

Если вы сначала кладете карты на доске, у вас нет никаких ограничений, и если после этого вы случайным образом выбираете пару рук AA / KK до тех пор, пока не столкнетесь, у вас будет аналгое (*)

Я посмотрю, смогу ли я уточнить немного подробнее.

0 голосов
/ 03 декабря 2009

Андреас Бринк ответил на вашу проблему # 1.

Я думаю, что ваша проблема №2 вызвана той же самой проблемой.

Вместо того, чтобы обнаруживать столкновения, просто смоделируйте стопку карт и подберите оставшиеся карты. Если вы этого не сделаете, вы должны быть осторожны с вероятностями, или вы можете вызвать смещение условных вероятностей в зависимости от вашего алгоритма.

Кстати, это может вам помочь:

0 голосов
/ 01 декабря 2009

Я думаю, что вы не должны использовать столкновения. Они очень неэффективны, особенно когда их много, и когда вы пытаетесь уменьшить их количество, очень вероятно, что вы вводите смещение: вы моделируете распределение по вероятности коллизий, поэтому, имея полный набор возможных коллизий является необходимым. Любое сокращение должно сохранять распределение таким же, как сокращение дроби.

Проблема 1: Как вы определили, что первый набор акций правильный? Независимые источники? Я бы предположил, что сначала выбирая закрытые карты, а затем карты с оставшимися картами были бы «очевидно» правильными (или это наивно?), Поскольку сбор закрытых карт можно выполнять независимо (см. Задачу 2).

Проблема 2: Распределение рук (закрытых карт) не является независимым, когда диапазоны рук перекрываются. Если у одного игрока есть AK +, у других рук неизвестные, ситуация отличается от ситуации, когда у одного игрока есть AK +, а у другого AA: во втором случае более вероятно, что у первого игрока действительно есть KK, чем в первом случае. В вашем примере из десяти рук игрок с 55+ вряд ли будет иметь что-то вроде KK. Опять же, как вы определили правильные акции?

Мне жаль, что я не могу дать вам окончательный ответ на ваши проблемы, но я думаю, что вам нужно сделать или прочитать о некотором статистическом анализе, чтобы детерминистически получить правильные распределения рук и убедиться, что они также не зависят от порядок игроков.

РЕДАКТИРОВАТЬ: Спасибо за публикацию чего-то, что позволяет нам оценить тип кода, с которым вы работаете. Как бы жестко это ни звучало, сейчас я склоняюсь к тому, чтобы посоветовать вам начать с нуля, но сначала узнайте о структурном программировании.

Всего несколько советов: в настоящее время кажется, что вы представляете набор карт как 52-элементное битовое поле. Хотя на первый взгляд это кажется эффективным, вы видите, что просто разыграть карты из такой колоды очень сложно. Итак, сделайте это просто: создайте класс, который описывает карту; сделать класс, который описывает колоду карт; осуществить для этого тасовку Фишера-Йейтса; назначьте ему метод deal(), который возвращает карточку и т. д. О, и не используйте передачу по ссылке, вместо этого используйте возвращаемые значения. Вы хотите увидеть, где значения изменяются, не вдаваясь в каждую подпрограмму.

РЕДАКТИРОВАТЬ 2: Относительно "Я не могу использовать класс, это слишком медленно": Что дает вам идею, что использование классов делает ваш код медленным? Классы - это просто концепция времени компиляции в C ++ (примерно). Даже если вы не хотите использовать классы или структуры, используйте правильные структуры данных, такие как массивы; это не менее эффективно, чем битовая игра.

Ваша проблема в том, что для того, чтобы получить несколько случайных карт из колоды, вы избиваете ее наборами случайных запросов, пока один из них не завершится полностью, вместо того, чтобы просто запросить определенное количество неиспользованных карт. Алгоритмическая сложность этого приближается к бесконечности с уменьшением количества доступных карт.

Вот о чем известная цитата «Преждевременная оптимизация - корень всего зла»: вы преждевременно «оптимизировали» представление ваших данных, и теперь вы больше не можете эффективно получать случайные карты. Сначала сделайте правильный алгоритм, затем найдите узкие места (это означает тестирование и измерение , a.k.a. профилирование ) и оптимизируйте их.

0 голосов
/ 01 декабря 2009

Я не могу сказать наверняка, поскольку я, очевидно, не могу видеть весь исходный код программы, но мое первое подозрение при просмотре различных акций состоит в том, что для симуляции Монте-Карло вы просто не проводите достаточно испытаний, чтобы получить оценка эквити руки.

Вполне может быть, другая проблема, но просто выяснить, является ли это причиной вашего расхождения. Я бы попытался провести очень большое количество испытаний (более 1 миллиона) несколько раз и посмотреть, насколько широко изменяются ваши акции.

0 голосов
/ 01 декабря 2009

это может быть генератор случайных чисел? Не могу сказать из кода, какой генератор чисел используется. 5

...