Cassandra

About
-----

Cassandra uses the Kelly criterion to determine the optimum betting
amount for a Texas hold 'em player during betting rounds.

Execution
---------

Cassandra handles only a single play of a poker hand; Cassandra must be
restarted for consecutive plays.

The first two prompts respectively request the player's current bankroll
and the retained pot of the current round; unsigned integer values are
expected. Even if the player has a blind (small or big) for the current
play, both the bankroll value and the pot value must reflect the state
of the game at the player's first turn to act -- i.e. after the blinds
have been posted.

The retained pot value is determined by multiplying the player's
previous bet amount by the number of bets placed by the opponents. Since
blinds are forced bets and result in a delayed first turn to act, the
retained pot value is only greater than zero when the player has a
blind; in all other situations, there are no previous bets placed by the
player when it is his or her first turn to act, so the retained pot
amount is 0 (0 * number_of_opponent_bets = 0).

Example 1:

    There are 4 opponents. The player has a bankroll of 5000 before
    the play of the hand. The betting order is such: Opponent 1,
    Opponent 2, Opponent 3, Player, and Opponent 4.

    Sample play:
        Opponent 1 posts small blind of 15.
        Opponent 2 posts big blind of 30.
        Opponent 3 raises 60.
        Player's turn to act.

    This is the point where Cassandra may be executed. The bankroll
    prompt input would be 5000 since the player has yet to place a
    bet. The pot prompt input would be 0 since the player has not
    made a previous bet.

Example 2:

    There are 4 opponents. The player has a bankroll of 5000 before
    the play of the hand. The betting order is such: Opponent 1,
    Player, Opponent 2, Opponent 3, and Opponent 4.

    Sample play:
        Opponent 1 posts small blind of 15.
        Player posts big blind of 30.
        Opponent 2 calls 30.
        Opponent 3 raises 60.
        Opponent 4 folds.
        Opponent 1 calls 45.
        Player's turn to act.

    This is the point where Cassandra may be executed. The bankroll
    prompt input would be 4970 since the player posted a blind of 30
    previously (5000 - 30 = 4970). The pot prompt input would be 90
    since the player's previous bet amount is 30 and the number of
    opponent bets since the player's last bet is 3 (30 * 3 = 90);
    only 3 opponents (Opponent 2, Opponent 3, and Opponent 1) placed
    bets since the player's previous bet (the big blind of 30). Note
    that Opponent 3's raise has no affect on the pot prompt input
    value -- it has the same effect as a call; in contrast,
    Opponent 4's fold did affect the pot prompt input value by being
    one less opponent bet to consider.

Example 3:

    There are 4 opponents. The player has a bankroll of 5000 before
    the play of the hand. The betting order is such: Player,
    Opponent 1, Opponent 2, Opponent 3, and Opponent 4.

    Sample play:
        Player posts small blind of 15.
        Opponent 1 posts big blind of 30.
        Opponent 2 calls 30.
        Opponent 3 folds.
        Opponent 4 folds.
        Player's turn to act.

    This is the point where Cassandra may be executed. The bankroll
    prompt input would be 4985 since the player posted a blind of 15
    previously (5000 - 15 = 4985). The pot prompt input would be 30
    since the player's previous bet amount is 15 and the number of
    opponent bets since the player's last bet is 2 (15 * 2 = 30);
    only 2 opponents (Opponent 1 and Opponent 2) placed bets since
    the player's previous bet (the small blind of 15).

At the start of each betting round, the relevant cards for that round
are requested. A single card is input at a time in a particular format:
the card rank followed by the card suit. The card rank is represented by
an unsigned integer between 1 and 13; where integers 2-10 correspond to
the respective card ranks -- and integers 1, 11, 12, and 13 correspond
to the Ace, Jack, Queen, and King card ranks respectively. The card suit
is represented by one of four characters; where the characters "c," "d,"
"h," and "s" correspond to the Club, Diamond, Heart, and Spade suits
respectively.

Example 4:
    
    The player is dealt the following hole cards: Queen of Diamond
    and the Three of Heart.

    Cassandra excerpt:
        ==Hole Cards==
        Input card: 12d
        Input card: 3h

    The Queen rank is represented by the integer "12," and the
    Diamond suit is represented by the character "d;" so the player
    inputs "12d" to represent the Queen of Diamond. The Three rank
    is represented by the integer "3," and the Heart suit is
    represented by the character "h;" so the player inputs "3h" to
    represent the Three of Heart.

Example 5:

    The player is dealt the following hole cards: Ace of Club and
    the Ace of Spade.

    Cassandra excerpt:
        ==Hole Cards==
        Input card: 1c
        Input card: 1s

    The Ace rank is represented by the integer "1," and the Club
    suit is represented by the character "c;" so the player inputs
    "1c" to represent the Ace of Club. The Ace rank is represented
    by the integer "1," and the Spade suit is represented by the
    character "s;" so the player inputs "1s" to represent the Ace of
    Spade.

At the start of every cycle of a betting round, the number of opponents
is requested and must be given as an unsigned integer. The suggested
player bet amount for the current turn to act is then printed. Next, the
player's actual bet amount is requested and must be given as an unsigned
integer. The integer 0 for the bet amount prompt is used to represent a
check by the player, or the end of the betting round.

Cassandra then requests the bet amount of each opponent; all opponent
bet amounts are expected as unsigned integers. An opponent check or fold
is represented by a respective bet amount of 0. After all opponent bet
amounts have been entered, the betting cycle repeats by requesting the
number of opponents again. At this point, the integer 0 may be entered
to end the betting round. At the end of the betting round, the current
pot value is printed. Next betting round, if any, begins after the
previous ends.

Example 6:

    It is the start of a cycle of the Flop betting round. The
    current pot is 100. There are 3 opponents. The player begins
    the cycle with a check.
    
    Cassandra excerpt:
        Number of Opponents: 3
        You should bet: 1538
        Bet Amount: 0
        Check? [Y/n]: y
        Player #3: 0
        Player #2: 50
        Player #1: 50
        Number of Opponents: 3
        You should bet: 1555
        Bet Amount: 50
        Player #3: 100
        Player #2: 0
        Player #1: 50
        Number of Opponents: 2
        You should bet: 2151
        Bet Amount: 50
        Player #2: 0
        Player #1: 0
        Number of Opponents: 0
        Pot: 450
        ==Turn==
        Input card:

    The betting round can be summed as such:
        Player checks.
        Opponent 3 checks.
        Opponent 2 raises 50.
        Opponent 1 calls 50.
        Player calls 50.
        Opponent 3 raises 100.
        Opponent 2 folds.
        Opponent 1 calls 50.
        Player calls 50.
        Flop betting round ends.
        Turn betting round begins.

    Notice how the player chose to bet less than the suggested
    betting amount in all three turns to act; a player does not have
    to bet the suggested betting amount. The number of opponents
    drops to 2 in the player's third turn to act since Opponent 2
    folded in the previous cycle. It is important to note that even
    though the betting round ends when the player calls in the
    player's third turn to act, 0 must be entered for each remaining
    opponent, since Cassandra lacks the ability to end the betting
    round at that point. Also note that the pot is adjusted
    automatically throughout the round, allowing the current pot
    value to be printed at the end (100 + 50+50+50+100+50+50 = 450).

Algorithm
---------

A 52-card deck is represented in memory as a 52-bit value, where each
bit represents a unique discrete card. The card suits are broken into
four groups of contiguous bits, where each group consists of 13 bits
respectively representing the 13 discrete cards of the suit.

The suits in order from least significant bit to most significant bit
are Club (bit 0 to bit 12), Diamond (bit 13 to bit 25), Heart (bit 26
to bit 38), and Spade (bit 39 to bit 51). Similarly, the card ranks are
ordered from least significant bit to most significant bit: Ace is
represented by the least significant bit, Two is represented by the next
bit, and the rest of the ranks onward by their respective bits, all the
way to King being represented by the most significant bit (12 bits from
the respective bit for the Ace rank); each card suit consists of its own
13 bits representing the respective 13 card ranks of that card suit.

Example 7:

    The Seven of Diamond is represented by bit 19.

    0000000000000 0000000000000 0000001000000 0000000000000

    Assuming the least significant bit is on the right, the Diamond
    suit is the second group of 13 bits from the right. The Seven
    rank is the seventh bit of its group, which in this case is bit
    19. In memory, this value would be 0x80000 (524288).

Since each bit represents a unique discrete card in a 52-card deck, any
legal hand may be represented by setting the respective bits for the
cards in the hand.

Example 8:

    The Jack of Club and Two of Heart are given as hole cards.

    0000000000000 0000000000010 0000000000000 0010000000000

    Assuming the least significant bit is on the right, the Club
    suit is the first group of 13 bits from the right, and the Heart
    suit is the third group of 13 bits from the right. The Two rank
    is the second bit of its group, and the Jack rank is the
    eleventh bit of its group. The Jack of Club is represented by
    bit 10, and the Two of Heart is represented by bit 27. Setting
    these two bits in memory results in the value 0x8000400
    (134218752).

The binary representation of a hand allows for efficient determination
of the hand rank via bitwise operations. A hand is initially assumed to
be of High Card rank (the lowest hand rank). The hand rank is determined
by analyzing the binary representation of the hand for certain bitwise
criteria; the highest hand rank, whose bitwise criteria the binary
representative of the hand satisfies, is determined to be the hand's
rank. Most of the bitwise criteria are simple bitmask operations; this
method bypasses the usual latencies associated with traditional card
abstraction algorithms (e.g. typical object-oriented approaches
involving card classes).

There are 1326 (52 choose 2) possible combinations of hole cards which a
player may be dealt at the start of a play; 2 cards out of the 52 card
deck are chosen. This leaves 50 cards from which 5 are dealt as
community cards; there are 2118760 (50 choose 5) combinations of
community cards which are possible after the player's hole cards are
known. Finally, if the player's hole cards and the community cards are
known, there remains 990 (45 choose 2) combinations of possible hole
cards an opponent may have been dealt from the remaining 45 cards of
the deck.

As the betting rounds progress, the number of unknown community cards
decreases, until all community cards are known by the last betting
round. As such, the possible combinations of community cards converges
to a single combination; whereas from 5 unknown community cards there
were 2118760 (50 choose 5) combinations prior to the flop betting round,
from 2 unknown community cards there are 1081 (47 choose 2) combinations
at the flop betting round, from 1 unknown community card there are 46
(46 choose 1) combinations at the turn betting round, there remains only
a single combination at the river betting round where all community
cards are known.

The number of possible one-on-one showdowns at any betting round, for
any given combination for a player's hole cards can be determined as
such:

    Pre-Flop:   (50 choose 5) * (45 choose 2)   = 2097572400
    Flop:       (47 choose 2) * (45 choose 2)   = 1070190
    Turn:       (46 choose 1) * (45 choose 2)   = 45540
    River:      (45 choose 2)                   = 990

Note how the number of possible combinations of community cards at any
given betting round is multiplied by the number of combinations of
possible hole cards an opponent may have been dealt. This is because
for any combination of community cards, the number of possible
one-on-one showdown combinations is wholly dependent on which hole cards
the opponent could possibly have been dealt (i.e. the number of
combinations of possible hole cards an opponent may have been dealt);
this becomes rather apparent in the last betting round where all the
community cards are known.

Cassandra simulates all possible one-on-one showdowns, between an
opponent and the player, for the respective betting round. It
accumulates the number of possible winning, losing, and split showdowns,
thus allowing it to calculate the probability of the player's hole cards
winning the play of the hand. In the first betting round however,
Cassandra does not perform the usual showdown simulations, but rather
uses a precompiled lookup table containing the simulation results of all
possible hole cards in order to provide a faster response time.

The probability of winning a one-on-one showdown does not necessarily
match the probability of winning the play of the hand; the play of the
hand may result in a showdown involving more than one opponent. Rather,
the probability of winning the play of the hand can be expressed as the
probability of winning consecutive one-on-one showdowns (one for each
opponent). This is a geometric distribution (i.e. an urn problem without
replacement) and the probability of winning the play of the hand can be
estimated by the following multiplication equation using Capital Pi
notation, where "PI" is the multiplication function, "i" is from 0 to
the number of opponents, "num_win" is the number of possible winning
showdowns for the respective betting round, and "COMB" is the total
number of possible showdowns for the respective betting round:

    win_probability = PI((num_win - i)/(COMB - i))

The actual win probability will be higher than this estimate since while
opponent hole card combinations overlap, actual players' hole cards do
not. For example, if one opponent has a Seven of Diamonds, then no other
opponent has a Seven of Diamonds; i.e. all Seven of Diamonds opponent
hole card combinations (rather than just one) are thereafter eliminated
from consideration when calculating the player win probability.

Similarly, the probability of splitting the play of the hand with all
opponents can be estimated by the following multiplication equation
using Capital Pi notation, where "PI" is the multiplication function,
"j" is from 0 to the number of opponents, "num_split" is the number of
possible winning showdowns for the respective betting round, and "COMB"
is the total number of possible showdowns for the respective betting
round:

    split_probability = PI((num_split - j)/(COMB - j))

However, a player may win against only some of the opponents and
ultimately split the play of the hand with only a portion of the number
of opponents. To estimate the effective probability for a given
win-split combination, the the following multiplication equation
using Capital Pi notation, where "PI" is the multiplication function,
"i" is from 0 to the number of wins against the opponents, "j" is from 0
to the number of splits with the opponents, "num_win" is the number of
possible winning showdowns for the respective betting round, "num_split"
is the number of possible winning showdowns for the respective betting
round, "COMB" is the total number of possible showdowns for the
respective betting round, and "num_opponents" is the total number of
opponents:

    win-split_probability = (num_opponents choose i) *
                            PI((num_win - i)/(COMB - i)) *
                            PI((num_split - j)/(COMB - j))

The reason for the multiplication by the binomial coefficient
(num_opponents choose i) is to account for the permutations of a
particular win-split combination. For example, if there are two
opponents, there will be four possible win-split combinations: SS, SW,
WS, and WW, where S represents a split and W represents a WIN. In this
scenario, SW and WS are different permutations of the same win-split
combination, and should be accounted accordingly.

In Texas hold 'em, the net odds received on the wager is dependent on
the state of the pot during the showdown. In particular, when not
considering split pots, the payout to the winner of a play of the hand
will be equal to sum of the amount retained in the pot from all
participants during the previous betting cycles, and the amount the
player bet in the current betting cycle multiplied by the number of
opponents remaining (since all opponents must match each others bets in
order to stay in play for the showdown). In this case, assuming no side
pots, the net gain can be expressed by the following equation:

    net_gain = bet_amount * num_opponents + retained_pot_amount

Cassandra uses the Kelly criterion to determine the suggested bet amount
for the player. The Kelly criterion formula returns the optimal bet
amount as a fraction of the player's current bankroll. As such, net gain
must first be normalized to the player's current bankroll:

    net_gain/bankroll = (bet_amount/bankroll) * num_opponents
                        + retained_pot_amount/bankroll

The Kelly criterion formula also expects the net odds received on the
wager, which means that the net gain needs to be expressed in units of
the wager. Dividing the net gain equation by the normalized optimal bet
amount gives us the net odds received on the wager, where "f" is the
normalized wager (bet amount), "n" is the number of opponents, "c" is
the normalized retained pot amount, and "b" is the net odds received on
the wager:

    f = bet_amount/bankroll
    n = num_opponents
    c = retained_pot_amount/bankroll

    b = net_odds = (net_gain/bankroll)/f = net_gain/bet_amount
    b = n + c/f

In a split pot situation, the pot is split between the tied players.
Accounting for splits in the net odds equation follows simply as
adding the player's portion (1 since the wagers are normalized) and
dividing by the number of players tied (number of opponents tied plus
the player), then finally subtracting out the player's portion to get
the net odds where a split pot has been considered. The following
equation, where "z" is the net odds considering a split pot, "b" is the
net odds without considering a split pot, and "s" is the number of
opponents tied with the player:

    z = win-split_net_odds = (1 + b)/(1 + s) - 1

The probability of losing the play of the hand is simply probability of
neither winning nor splitting the play of the hand; the probability of
losing can be computed by subtracting the cumulative win-split
probability from 1). The net odds for losing the play of the hand in
Texas hold 'em is -1 since the player simply loses their wager.

Going back to the definition of the Kelly criterion, we can take into
account both the win and split pot probabilities and their respective
net odds, in the following expression; where SIGMA is the summation
function (iterating through all possible win-split combinations), "p" is
the win-split probability for a respective win-split combination, "z" is
the net odds for a respective win-split combination, "q" is the
probability of losing the play of the hand, and "x" is the Kelly
criterion:

    SIGMA(p*log(1 + z*x)) + q*log(1-x)

After plugging in the known values, the optimum bet amount is that which
maximizes the value of the expression. The maximum of the expression can
be computed by solving for the root of the derivative of the expression:

    0 = SIGMA(p*z/(1 + z*x)) - q/(1-x)

Results and Musings
-------------------

Unfortunately, testing Cassandra against computer opponents didn't
result in winning the entire game of Texas hold 'em poker. I suspect
this is mainly due to the blinds: they force a minimum bet which may be
greater than Cassandra's suggested bet amount allows. This, coupled with
the multiplicative decay of the win-split probability when accounting
for multiple opponents, often lead to a condition where possessing a
small bankroll meant little chance of growing the bankroll -- instead,
gradually losing more and more of the bankroll until eventually going
broke.

Interestingly, betting strictly close to the optimum bet for each round
may give away damning information about a player's hand. For example, a
player may progressively bet higher and higher, until the river is
revealed, and then bet a relatively low amount. An opponent may then
realize that the river card significantly reduced the possible win
probability for the player; the opponent may then raise a large amount,
which the player is unable to match safely, thus forcing a fold.
Similarly, an opponent may realize the player who bets strictly close to
the Kelly criterion will never take a risky call, thus allowing the
opponent to go all-in repeatedly without fear of competition, resulting
in consistent folds for the player.

It is important to note that Cassandra currently assumes no side pots,
and the computation of a win-split probability for a win-split
combination is only an estimate (the win/split outcomes are not
reevaluated as each possible opponent outcome is selected for a
win-split combination, but instead estimated using a geometric
distribution model). Furthermore, all opponents are assumed to last
until the showdown.

Due to the algorithm choosen to determine the Kelly criterion in
Cassandra, the Kelly criterions 0 and 1 cannot be directly verified (a
division by 0 occurs in the computation for such inputs). As such, a
low bound of 0.001 and high bound of 0.999 are used when searching for
the actual Kelly criterion. If both bounds return negative values for
the derivative of the Kelly criterion expression, the criterion is
assumed to be 0; similarly if both bounds respectively return positive
values, the Kelly criterion is assumed to be the high bound.

All these assumptions drive the suggested bet amount lower than the true
Kelly criterion since a worst case scenario is assumed.

The fact that using this lower bet amount didn't result in the winning
of the entire Texas hold 'em poker game may very well be a testament to
the aspect of skill required in playing poker -- it is more than a
simple game of luck.

Licensing
---------

Cassandra is free software released under version 3 of the GNU General
Public License.

See the file COPYING for copying conditions.

Contact
-------

William Breathitt Gray <[email protected]>