Алгоритм расчета покер эквити


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

Ниже приведена упрощенная структура покерный калькулятор эквити. Для примера, я создал ее для игры, когда у обоих игроков руки содержать одну из 52 карт, 4 карты на борту(поворот), одна(Ривер) доски карточки слева. Пусть говорят, что игрок, который сумма доску и силы карта выше, тот и выиграл.

#include "stdafx.h"
#include <vector>
#include <iostream>
#include <ctime>
#include <string>

using namespace std;

static const int card_count = 52;

// Checks that board contains the card. A lot of time spent here. Need to be optimized.
bool Contains(const std::vector<int>& board, int card)
{
    for (int boardCard : board) 
    {
        if (boardCard == card)
        {
            return true;
        }
    }

    return false;
}

// Fake function that evaluates hand strength. This is just for example real evaluator is different. So no need to optimize this.
size_t GetHandStrength(const std::vector<int>& board, int card, int b)
{
    size_t stren = 0;

    for (int boardCard : board)
    {
        stren += boardCard;
    }

    return stren + card + b;
}

// Returns equity for the board 
float GetEquity(const std::vector<int>& board)
{
    float equity = 0;

    for (int c1 = 0; c1 < card_count; c1++) // Player1 card
    {
        if (Contains(board, c1))
        {
            continue;
        }

        for (int c2 = 0; c2 < card_count; c2++)  // Player2 card 
        {
            if (c1 == c2 || Contains(board, c2))
            {
                continue;
            }

            size_t usedBoards = 0; // number of boards are possible for this players and board cards
            float currentEquity = 0;

            for (int b = 0; b < card_count; b++) // Iterating river board cards
            {
                if (Contains(board, b))
                {
                    continue;
                }

                if (b == c1 || b == c2) // Check that there are no conflict with players cards
                {
                    continue;
                }

                size_t p1stren = GetHandStrength(board, c1, b);
                size_t p2stren = GetHandStrength(board, c2, b);

                if (p1stren > p2stren)
                {
                    currentEquity += 1.0;
                }
                else if (p1stren < p2stren)
                {
                    currentEquity -= 1.0;
                }

                usedBoards++;
            }

            currentEquity /= usedBoards;
            equity += currentEquity;
        }
    }

    return equity;
}

int main()
{
    clock_t begin = clock();
    std::vector<int> board = { 0, 1, 2, 21 }; // Some turn random board (4 cards)
    float equity = GetEquity(board);;
    cout << "equity: " << equity <<  endl;
    return 0;
}

При переборе силы и совет карт мне нужно проверить, что совет уже не содержит карты, поэтому мне нужно перебрать карты снова и снова. Это делается по типу bool Contains(const std::vector<int>& board, int card) также проверяет, как если (b == c1 || b == c2) что вы можете предложить для оптимизации этой части?



391
5
задан 14 февраля 2018 в 10:02 Источник Поделиться
Комментарии
1 ответ

Поскольку вы делаете о(Н3) операции с линейный поиск, большой прирост производительности будет, если мы можем устранить этот поиск.

Есть два похожих способа пойти об этом; как заменить поиск индексированного поиска.


  • Изменить тип board от вектор, который держит карты в векторные (или array) из card_count слоты, который имеет счет этой карты в доску (используя счетчик для будущего расширения до нескольких колод).

  • В GetEquityзаполнить вектор или массив card_count элементы с количеством карт в boardтогда просто убедитесь, что контейнер для ненулевым, чтобы увидеть, если карта содержащиеся в доску. Это имеет дополнительное преимущество быть в состоянии добавить c1 и c2, так что внутренний цикл проверяет только нужно проверить одно условие (а не 2 или 3), чтобы увидеть, если карта доступна.

Вот обновленный GetEquity используя идеи из Вариант 2:

float GetEquity(const std::vector<int>& board)
{
std::vector<int> counts(card_count);
for (auto b: board)
++counts[b];

float equity = 0;

for (int c1 = 0; c1 < card_count; c1++) // Player1 card
{
if (counts[c1])
{
continue;
}
++counts[c1];

for (int c2 = 0; c2 < card_count; c2++) // Player2 card
{
if (counts[c2])
{
continue;
}
++counts[c2];

size_t usedBoards = 0; // number of boards are possible for this players and board cards
float currentEquity = 0;

for (int b = 0; b < card_count; b++) // Iterating river board cards
{
if (counts[b])
{
continue;
}

size_t p1stren = GetHandStrength(board, c1, b);
size_t p2stren = GetHandStrength(board, c2, b);

if (p1stren > p2stren)
{
currentEquity += 1.0;
}
else if (p1stren < p2stren)
{
currentEquity -= 1.0;
}

usedBoards++;
}

currentEquity /= usedBoards;
equity += currentEquity;

--counts[c2];
}
--counts[c1];
}

return equity;
}

5
ответ дан 15 февраля 2018 в 12:02 Источник Поделиться