Poker equity calculation algorithm

Question

I writing some specific poker equity calculator. Basically, equity calculator tells how much one hand is more profitable than other. I have written such calculator and it works, works fast, but there is a one not optimal place where a lot of time is spent and it definitely can be optimized. I am asking you about the advice how to optimize it.

Below is the simplified structure of poker equity calculator. For sample purpose, I have made it for the game when both Players hands contain one from 52 cards, 4 cards are on board(turn), one(river) board card left. Let say that player who's sum of the board and hand card is higher - wins.

#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;
}

When iterating over the hand and board cards I need to check that board doesn't already contains the card, so I need to iterate over the board cards again and again. This is done by the bool Contains(const std::vector<int>& board, int card) also checks like if (b == c1 || b == c2) What can you suggest to optimize this part?

Answer 1

Since you're doing an O(N³) operation, with a linear search, a big performance boost will happen if we can eliminate that search.

There are two similar ways to go about it; both replace the search with an indexed lookup.

• Change the type of board from a vector that holds the cards to a vector (or array) of card_count slots that holds a count of how many of that card is in the board (using a count for future expansion to multiple decks).

• In GetEquity, fill a vector or array of card_count elements with counts for the cards in board, then just check that container for a nonzero to see if the card is contained in the board. This has the additional advantage of being able to add c1 and c2, so the inner loop checks only need to check one condition (rather than 2 or 3) to see if a card is available.

Here's an updated GetEquity using ideas from option 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;
}

Answer 2

Two player equity on the river can be calculated with the single loop through possible player's holdings.

Here is a pseudo-code of a general idea.

foreach (board in all_possible_boards) {
    all_cards = all cards except for those on board
    ordered_hands = sort(all_cards, compare hands by hand strength on a given board)

    win_probabilities = dictionary Hand -> Value;

    for (i=0; i< len(ordered_hands); i++) {
       win_probabilities[ordered_hands[i]] = i / (len(ordered_hands) -1); 
    }
    sum up the results
}

This code assumes that all hands have different hand strength, but it can be relatively easily adjusted to handle ties. Handling more complex games like two-card poker or even four-card poker is a bit trickier but also possible. Extending it for multi-player scenarios is something even more tricky.