3

First a disclaimer: I am a medical professional who plays with both Python and poker as a hobby. I have no formal training in neither of those and I am not aware of what is in the curriculum of a computer science class. The computer that I use is a desktop i7-4790 3.6 Ghz with 16 GB of RAM along with Jupyter Notebooks.

My goal was to code the equivalent of pokerstrategy.com Equilab  or https://www.cardschat.com/poker-odds-calculator.php for me. I would stick to Texas Holdem only.

In order to to that I needed to code an evaluator for any 5 card combination.I did that and it does the job perfectly, considers every card in a hand and produces a tuple as an output, for example:

('2h', '3c', '4s', '6s', 'Jh'): (0, 11, 6, 4, 3, 2)
High-card hand, kickers J, 6, 4, 3, 2

('7c', 'Ad', 'Kd', 'Kh', 'Tc'): (1, 13, 14, 10, 7)
One pair, pair of kings, kickers A, T, 7

('2c', '3c', '4c', '5c', 'Ac'): (8, 5)
Straight flush, 5 high

So it differentiates between A 9 8 7 3 and A 9 8 7 5 flush or high-hand. I checked with theoretical number of royal flushes, quads, full houses etc. over all 2 598 960 card ccombinations and the frequencies check out (https://www.quora.com/How-many-possible-hands-are-there-in-a-five-card-poker-game)

Now I tried to evaluate every possible 5-card combination out of those 2.6 millions and it took disappointing 51 seconds.

I kind of expected that thinking my 5-card evaluator can't be the champion of algorithm competitions and surely there is a better way to do it (I can post it here if it is of relevance), but I thought never mind. Once all 5-card combinations are evaluated I will save them in a dictionary and next time I will load the dictionary and when I have any 5-card combination I will simply look up the result.

Another disappointment. 10 000 000 (10 million) board searches takes approx. 23-24 seconds.This is a a part that I do not understand!!!I have basically a database that has 2.6 mil. rows x 2 columns and the search is SO PROHIBITIVELY slow. How do then billion record databases get anything accomplished?My whole dictionary when saved to a file takes 88 Mb - is that a HUGE database?

And finally I made a full hand vs. hand evaluator that in pseudo-code does this:

  • Given 2 hands, for example AhAs vs. 6d6h

  • list all boards that can be dealt with those 2 "dead" cards, which is 1 712 304 boards

  • list all 21 combinations of hand1 with board 1,

  • search the ranked_hands dictionary with those 21 combinations and return the best possible outcome (21 combinations because in texas holdem you can use one, two or no cards from your hand with any of the 5 community cards on board)

  • do the same with hand2 and board1

  • compare best outcome of hand1 with best outcome of hand2

  • count if the outcome favours hand1, hand2 or if it is a tie

  • go to next board

This algorithm does approximately 71 million dictionary lookups - each of 1.7 million boards x 42 (every hand's 21 combinations twice).

Now, THIS IS A DISASTER. Approximately 80 seconds per hand vs. hand matchup. With those speeds there is nothing I can begin. So, any input would be appreciated as to how I can make this better?

Is it me and my lack of proper computer science and algorithm knowledge?

Is it Python? Is it Jupyter Notebooks inside of Chrome?

Any other suggestions?

Code as requested:

import collections
import random
import itertools
import timeit
import time

ranks = ['2','3','4','5','6','7','8','9','T','J','Q','K','A']

names ="Deuces Threes Fours Fives Sixes Sevens Eights Nines Tens Jacks Queens Kings Aces"
cardnames = names.split() 
cardnames
suitsall = "hearts spades diamonds clubs"
suitnames = suitsall.split()
suitnames

suits = ['h','s','d','c']

cards = []

# Create all cards from suits and ranks

for suit in suits:
    for rank in ranks:
        cards.append(rank + suit)



# Create all possible flops by chosing 3 cards out of a deck

flops = list(itertools.combinations(cards, 3))

# Create all possible boards by chosing 5 cards out of a deck

boards = list(itertools.combinations(cards, 5))


# Create all possible starting hands

startingHands = list(itertools.combinations(cards, 2))



# Function dict_hand_rank ranks every board and returns a tuple (board) (value)

def hand_rank_dict(hand):

    suits = []
    ranks_alphabetical = []
    ranks_numerical = []
    ranks_histogram = []
    kickers = []
    kickers_text = []

    isFlush = False
    isStraight = False
    isStraightFlush = False
    handrankValue = 0 

    straightHeight = -1
    straightName = "No straight"
    handName = "none yet"

    for card in hand:
        suits.append(card[1])
        ranks_alphabetical.append(card[0])

    # create ranks_histogram where from A 2 ... J Q K A every card has the corresponding number of occurencies, A double counted

    ranks_histogram.append(str(ranks_alphabetical.count('A')))

    for rank in ranks:
        ranks_histogram.append(str(ranks_alphabetical.count(rank)))

    joined_histogram = ''.join(ranks_histogram)

    # create ranks numerical instead of T, J, Q, K A

    for card in hand:
        ranks_numerical.append(ranks.index(card[0])+2)

    # create kickers

    kickers = sorted([x for x in ranks_numerical if ranks_numerical.count(x) <2], reverse = True)

    # check if a hand is a straight

    if '11111' in joined_histogram:
        isStraight = True
        straightHeight = joined_histogram.find('11111') + 5
        straightName = cardnames[straightHeight - 2]
        handName = "Straight"
        handrankValue = (4,) + (straightHeight,)

    # check if a hand is a flush

    if all(x == suits[0] for x in suits):
        isFlush = True
        handName = "Flush " + cardnames[kickers[0] - 2] + " " + cardnames[kickers[1] - 2] \
              + " " + cardnames[kickers[2] - 2] +  " " + cardnames[kickers[3] - 2] + " " + cardnames[kickers[4] - 2] 
        handrankValue = (5,) + tuple(kickers)

    # check if a hand is a straight and a flush

    if isFlush & isStraight:
        isStraightFlush = True
        handName = "Straight Flush"
        handrankValue = (8,) + (straightHeight,)

    # check if a hand is four of a kind
    if '4' in  joined_histogram:
        fourofakindcard = (joined_histogram[1:].find('4') + 2)
        handName = "Four of a Kind " + cardnames[fourofakindcard -2] + " " + cardnames[kickers[0] - 2] + " kicker"
        handrankValue = (7,) + ((joined_histogram[1:].find('4') + 2),) + tuple(kickers)

    # check if a hand is a full house
    if ('3' in joined_histogram) & ('2' in joined_histogram):
        handName = "Full house"
        handrankValue = (6,) + ((joined_histogram[1:].find('3') + 2),) + ((joined_histogram[1:].find('2') + 2),) + tuple(kickers)


    # check if a hand is three of a kind
    if ('3' in joined_histogram) & (len(kickers) == 2):
        threeofakindcard = (joined_histogram[1:].find('3') + 2)
        handName = "Three of a Kind " + cardnames[threeofakindcard -2] + " " + cardnames[kickers[0] - 2] + \
            " " + cardnames[kickers[1] - 2]
        handrankValue = (3,) + ((joined_histogram[1:].find('3') + 2),) + tuple(kickers)    

    # check if a hand is two pairs 
    if ('2' in joined_histogram) & (len(kickers) == 1):        
        lowerpair = (joined_histogram[1:].find('2') + 2)
        higherpair = (joined_histogram[lowerpair:].find('2') + 1 + lowerpair)
        handName = "Two pair " + cardnames[higherpair -2] + " and " + cardnames[lowerpair - 2] + " " + \
            cardnames[kickers[0] - 2] + " kicker"
        handrankValue = (2,) + (higherpair, lowerpair) + tuple(kickers)    

    # check if a hand is one pair
    if ('2' in joined_histogram) & (len(kickers) == 3):        
        lowerpair = (joined_histogram[1:].find('2') + 2)
        handName = "One pair " + cardnames[lowerpair - 2] + " kickers " + cardnames[kickers[0] - 2] \
            + " " + cardnames[kickers[1] - 2] +  " " + cardnames[kickers[2] - 2]
        handrankValue = (1,) + (lowerpair,) + tuple(kickers)    


    # evaluate high card hand
    if (len(ranks_numerical) == len(set(ranks_numerical))) & (isStraight == False) & (isFlush == False):
        handName = "High card " + cardnames[kickers[0] - 2] + " " + cardnames[kickers[1] - 2] \
            + " " + cardnames[kickers[2] - 2] +  " " + cardnames[kickers[3] - 2] + " " + cardnames[kickers[4] - 2] 
        handrankValue = (0,) + tuple(kickers)

    return {tuple(sorted(hand)) : handrankValue}






ranked_hands_dict = {}

t0 = time.time()

for board in boards:
    ranked_hands_dict.update(hand_rank_dict(board))

t1 = time.time()

total = t1-t0    

# print(total) 


# Function that given board and 2 cards gives back tuple of the best possible hand by searching through ranked_hands_dict keys

def find_the_best_hand(board, card1, card2):

    seven_card_hand = board + (card1,) + (card2,)
    evaluated_all_possible_hands = []

    if (card1 in board) or (card2 in board):
        return "Illegal board"
    else:
        all_possible_hands = list(itertools.combinations(seven_card_hand, 5))
        for hand in all_possible_hands:
            evaluated_all_possible_hands.append(ranked_hands_dict[tuple(sorted(hand))])

        return max(evaluated_all_possible_hands)


# Function that returns a list of possible boards given the dead cards

def create_allowed_boards(cards):

    list_of_allowed_boards = []

    for board in boards:
        if not any(karta in cards for karta in board):
            list_of_allowed_boards.append(board)

    return list_of_allowed_boards

hand1 = ['2h','7d']
hand2 = ['Ad','Ah']

# HAND vs. HAND EVALUATOR 

t0 = time.time()

one = 0
two = 0
tie = 0

deadcards= hand1 + hand2
list_of_possible_boards = create_allowed_boards(deadcards)

for board in list_of_possible_boards:


    hand1rank = find_the_best_hand(board, hand1[0], hand1[1])
    hand2rank = find_the_best_hand(board, hand2[0], hand2[1])

    if hand1rank > hand2rank:
        one = one + 1

    if hand1rank < hand2rank:
        two = two + 1

    if hand1rank == hand2rank:
        tie = tie + 1

onepercent = (one/len(list_of_possible_boards))*100
twopercent = (two/len(list_of_possible_boards))*100
tiepercent = (tie/len(list_of_possible_boards))*100

print(onepercent, twopercent, tiepercent)


t1 = time.time()

total = t1-t0    

print(total)

Maybe one print(total) to many but was originally in Jupyter Notebook

rioZg
  • 530
  • 1
  • 6
  • 17
  • 1
    Where's the code? – Z4-tier Dec 21 '19 at 10:27
  • 1
    Perhaps better suited to [codereview.se] although they'll require code to review. – Sayse Dec 21 '19 at 10:31
  • I'd be interested to see and review the code but might be better on Code Review as pointed out by @Sayse as this is very broad for a SO question. If you choose to post on CR please link here and I'll take a look. Using a dictionary is often a good idea for these kind of combinatorics problems but it sounds like in your case you have a dictionary which is not especially usefully structured. – Simon Notley Dec 21 '19 at 13:23
  • Sorry. I wasn't aware that there are different platforms for asking different questions, lilke StackOverflow and Code Review. As said, a hobbyist. Code added. – rioZg Dec 21 '19 at 14:41
  • @ rioZg I added a comment on my answer with some run times for this algorithm using multiprocessing Python and Go. – Simon Notley Jan 07 '20 at 14:58

3 Answers3

3

I am noticing one broad theme in your approach that might be something to reevaluate, as it could make a substantial difference in the performance.

It sounds like you are trying to brute force this problem. If I asked you to compare 2 hands right now (no computers, just your brain), are you going to reference a pre-computed list of every possible poker hand that you have stored in memory? Have you ever even looked at such a list (actually sat and read through each line)?? I hope not, and I am guessing the answer to both of those questions will be "NO".

So why are you choosing that strategy to solve the same problem with your program? Instead, can you write a program that includes abstract definitions of each type of poker hand? So that your program would be able to identify "royal flush" or "full house"? Then it would only need to compute the relative value of the 2 hands in question, and compare the results to determine the better hand. No big lookup tables to scan, and I bet it could be done without too much more code than what you already have (but you'll probably need to scrap what you've got and start over).

If you still want to pursue the strategy of using a pre-computed lookup table, here are a couple suggestions:

  • Delete all of the un-playable hands out of the table. Since you're storing the data anyway, you'll only need to do this once. Then you can default every failed lookup to a score of zero. At the very least, this will save space and reduce the time it takes if you need to do a linear scan of all elements. Speaking of which....
  • Python dictionaries basically use a hash table as the underlying implementation to map keys to the associated values: { key : value }. This means that when a record is accessed by specifying the whole key and nothing else (my_dict[key]), the operation can be done in a fixed amount of time that does not increase as the table grows (as opposed to a list, which requires the list to be traversed linearly until either a matching record is found, or all records have been checked without a match). When you create a dictionary, make sure that the way the key is constructed matches exactly the way it will later be accessed.

And, regardless of the approach you choose:

  • since you are doing this as a learning exercise, I would strongly recommend that you not use itertools and possibly also collections. While these are extremely handy libraries, they also hide some very fundamental and important aspects of algorithm design. If this was being assigned as a homework assignment in an undergraduate computer science course, those libraries would very likely not be allowed. This article explains it better than I could (and it's Joel from 2001, what more can you ask for?).
  • Again, since this is for learning, I would recommend that you do learn to use Python's debugging tools. Specifically, learn how to set breakpoints and pause your program during execution, which enables you to step through the code line-by-line. This will help reveal hot spots in the code so you know where your time would be best spent to improve performance.

EDIT

Here is a class that implements a poker hand, and imparts an order on any set of hands by direct comparison of two instances using ">", "<" and "=". No lookup tables.

from collections import Counter, namedtuple

SUITS = ['d', 'h', 's', 'c']
RANKS = [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
Card = namedtuple('Card', ['suit', 'rank'])

class Hand:
    def __init__(self, hand):
        self.hand = hand
        self.catg = None
        self.high_card_ranks = []
        self.hand.sort(key=(lambda c: c.rank), reverse=True)
        self._classify_hand()

    def __eq__(self, x_hand):
        return self._comp_hand(x_hand) == 'EQ'

    def __lt__(self, x_hand):
        return self._comp_hand(x_hand) == 'LT'

    def __gt__(self, x_hand):
        return self._comp_hand(x_hand) == 'GT'

    def __repr__(self):
        face_cards = {1: 'A', 11: 'J', 12: 'Q', 13: 'K', 14: 'A'}
        repr_str = ''
        for n in range(0, 5):
            repr_str += str(face_cards.get(self.hand[n].rank,
                                           self.hand[n].rank)) \
                        + self.hand[n].suit + ' '
        return repr_str

    def _classify_hand(self):
        rank_freq = list(Counter(card.rank for card in self.hand).values())
        suit_freq = list(Counter(card.suit for card in self.hand).values())
        rank_freq.sort()
        suit_freq.sort()
        if self._is_straight() and suit_freq[0] == 5:
            self.catg = 'SF'
            self.high_card_ranks = [c.rank for c in self.hand]
            self._wheel_check()
        elif rank_freq[1] == 4:
            self.catg = '4K'
            self.high_card_ranks = [self.hand[2].rank,
                                    (self.hand[0].rank
                                     if self.hand[0].rank != self.hand[2].rank
                                     else self.hand[4].rank)]
        elif rank_freq[1] == 3:
            self.catg = 'FH'
            self.high_card_ranks = [self.hand[2].rank,
                                    (self.hand[3].rank
                                     if self.hand[3].rank != self.hand[2].rank
                                     else self.hand[1].rank)]
        elif suit_freq[0] == 5:
            self.catg = 'F'
            self.high_card_ranks = [c.rank for c in self.hand]
        elif self._is_straight():
            self.catg = 'S'
            self.high_card_ranks = [c.rank for c in self.hand]
            self._wheel_check()
        elif rank_freq[2] == 3:
            self.catg = '3K'
            self.high_card_ranks = [self.hand[4].rank, self.hand[0].rank]
            self.high_card_ranks.append(self.hand[3].rank
                                        if self.hand[1].rank in self.high_card_ranks
                                        else self.hand[1].rank)
        elif rank_freq[2] == 2:
            self.catg = '2K2'
            self.high_card_ranks = [self.hand[0].rank,
                                    self.hand[2].rank,
                                    self.hand[4].rank]
        elif rank_freq[3] == 2:
            self.catg = '2K'
            self.high_card_ranks = list(set(c.rank for c in self.hand))
        else:
            self.catg = None
            self.high_card_ranks = [c.rank for c in self.hand]

    def _is_straight(self):
        return ((False not in [(self.hand[n].rank == self.hand[n+1].rank + 1)
                               for n in (0, 1, 2, 3)])
                or ([c.rank for c in self.hand] == [14, 5, 4, 3, 2]))

    def _wheel_check(self):
        # allows for the correct ordering of low ace ("wheel") straight
        if (self.catg in ['SF', 'S']
                    and self.high_card_ranks == [14, 5, 4, 3, 2]):
            self.high_card_ranks.pop(0)
            self.high_card_ranks.append(1)

    def _comp_hand(self, comp_hand):
        ret_val = 'EQ'
        catg_order = [None, '2K', '2K2', '3K', 'S', 'F', 'FH', '4K', 'SF']
        curr_hand_catg = catg_order.index(self.catg)
        comp_hand_catg = catg_order.index(comp_hand.catg)
        if curr_hand_catg > comp_hand_catg:
            ret_val = 'GT'
        elif curr_hand_catg < comp_hand_catg:
            ret_val = 'LT'
        else:
            for curr_high_card, comp_high_card in \
                        zip(self.high_card_ranks, comp_hand.high_card_ranks):
                if curr_high_card > comp_high_card:
                    ret_val = 'GT'
                    break
                elif curr_high_card < comp_high_card:
                    ret_val = 'LT'
                    break
        return ret_val


>>> from poker_hand import *
>>> h1=Hand([Card('s', 2), Card('s', 3), Card('s', 4), Card('s', 5), Card('s', 6)])
>>> h2=Hand([Card('c', 2), Card('c', 3), Card('c', 4), Card('c', 5), Card('c', 6)])
>>> h3=Hand([Card('c', 2), Card('c', 3), Card('c', 4), Card('c', 5), Card('c', 14)])
>>> h4=Hand([Card('d', 2), Card('d', 3), Card('d', 4), Card('d', 5), Card('d', 14)])
>>> h1
6s 5s 4s 3s 2s
>>> h3
Ac 5c 4c 3c 2c
>>> h1>h3
True
>>> h3>h1
False
>>> h1==h1
True
>>> h3==h4
True
>>> h2==h1
True

That can then be used to construct a simulator for Texas Hold 'Em for an arbitrary number of players and decks:

from itertools import combinations, product
from random import sample, shuffle
import poker_hand


class Texas_Hold_Em(object):
    def __init__(self, player_count=2):
        self.player_count = player_count
        self.players = []
        self.comm_cards = []
        self.deck = [poker_hand.Card(*c) 
                     for c in product(poker_hand.SUITS, poker_hand.RANKS)]

    def __str__(self):
        face_cards = {1: 'A', 11: 'J', 12: 'Q', 13: 'K', 14: 'A'}
        comm_cards = ""
        for c in self.comm_cards:
            comm_cards += str(face_cards.get(c.rank, c.rank)) + c.suit + " "
        rv =  "-" * 40 + f"\n\nCommunity Cards:\n{comm_cards}\n" + "*" * 20 + "\n"
        for ct, player_hand in enumerate(self.players):
            player_cards = ""
            for c in player_hand:
                player_cards += str(face_cards.get(c.rank, c.rank)) + c.suit + " "
            rv += f"Player {str(ct)}: {player_cards}\n"
        winners = self.who_wins()
        rv += "*" * 20 + "\n"
        for winner in winners:
            rv += f"Player {str(winner[0])} wins: {str(winner[1])}\n"
        rv += "\n" + "-" * 40
        return rv

    def deal_cards(self):
        self.comm_cards.clear()
        self.players.clear()
        shuffle(self.deck)
        dealt_cards = sample(self.deck, (2 * self.player_count) + 5)
        for player in range(self.player_count):
            self.players.append([dealt_cards.pop(n) for n in range(2)])
            self.players[player].sort()
        self.comm_cards.extend(dealt_cards)
        self.comm_cards.sort()

    def who_wins(self):
        highest_hands = []
        for player, hand in enumerate(self.players):
            card_pool = self.comm_cards.copy()
            card_pool.extend(hand)
            card_combinations = [list(cards) for cards in combinations(card_pool, 5)]
            highest_hands.append(max([poker_hand.Hand(h) for h in card_combinations]))
        winning_hand = max(highest_hands)
        winners = []
        for player in range(highest_hands.count(winning_hand)):
            idx = highest_hands.index(winning_hand)
            winners.append((idx, highest_hands.pop(idx)))
        return winners

Then it can be played:

>>> import texas_hold_em
>>> th=texas_hold_em.Texas_Hold_Em()
>>> for _ in range(10):
...   th.deal_cards()
...   print(th)
...
----------------------------------------

Community Cards:
3c 6c 2s 7s Js
********************
Player 0: Jc Jd
Player 1: 4c Ks
********************
Player 0 wins: Js Jc Jd 7s 6c  (3K)

----------------------------------------

[etc...]
Z4-tier
  • 7,287
  • 3
  • 26
  • 42
  • That was my initial idea but if you look at the link in the original question to Quora statitistics page you will see that a very small minority of hands constitute anything else but "nothing" and "one pair" and for those hands you need complete evaluation down to last kicker. So I thought any "shortcut" would be more work than it was worth. – rioZg Dec 21 '19 at 14:36
  • @rioZg having so few playable hands out the set of all possible hands is exactly the thing that makes it advantageous to do this computation on-the-fly. All that is needed is to code some functions that will determine if their input matches a certain pattern, and then return the details (probably suit/high card) needed to assign a numerical score to the input. Even better: there are only 8 cases that all playable hands will fall into, and they are all easy to express in Python code. I think if you try this approach you'll find it is a very straightforward solution. – Z4-tier Dec 22 '19 at 03:57
  • No need to evaluate any given hand past those 8 special cases: if a hand doesn't fall into one of them, it is automatically a zero score. – Z4-tier Dec 22 '19 at 03:59
  • Not true Z4-tier. The board is 9 8 7 3 2 , one player holds A6 the other A4, the best possible hand for player 1 is A 9 8 7 6, for player 2 A 9 8 7 4, player 1 wins on the last kicker. The board is As 3s 4s 5s Qd , player1 is holding 2s2d, player 2 is holding KsKd, player 3 is holding 8s7s, you need more than just player 2 has flush, player 3 has flush because player 2 beats player 3 but loses to player one who has straight flus. So knowing that hand is zero score is not sufficient. – rioZg Dec 22 '19 at 08:07
  • I just updated this answer with a working example that should work for any hand. It first assigns a hand to a category (ie. SF, FH, 3K, etc...) and then maintains a list of the cards that can be used to determine the relative order of 2 hands within the same category. This takes advantage of the fact that tie breakers follow the same algorithm regardless of the hand category; the only thing that changes are the specific cards that are compared. Variants of this problem are frequently used in programming competitions. – Z4-tier Dec 27 '19 at 16:13
  • Thanks. I get the the general idea behind it, but the specifics are above my current level of understanding (as soon as you delve into OOP). The other problem that I see is that your evaluator does 5-card hand vs. another 5-card hand evaluation. If you do extensive calculation of hand vs. hand in Texas Holdem (ie 2 cards vs. 2 cards) on every possible board runout you have 21 ways each hand can combine with the "community" board. Since your evaluator does not produce the ranked output there would be a lot of comparing going on first among one hand and then... – rioZg Jan 02 '20 at 12:51
  • @rioZg That observation is absolutely correct. This gives the most atomic building blocks (the poker 'Hand' class) and creates an ordering on the set of all poker hands, but it doesn't create any higher level "game" construct. If I wanted to build Texas Hold 'Em on top of this, I would probably start with a class that created a standard deck of card objects and handled the logic of dealing those cards to N players. For each player construct Hand objects for all possible hands and compare them, picking the one with the highest value. Then compare between each player to determine the winner. – Z4-tier Jan 02 '20 at 19:21
0

I've read through your code more carefully now. I think the approach of pre-calculating the rank of every hand is viable even though it seems very brute-force. Your point about having to evaluate every kicker in most cases seems reasonable justification for this approach.

EDIT - some online research suggests this is not a trivial problem and the best current solution is the '2+2' method which is actually based on lookups but with some heavy optimisation. https://web.archive.org/web/20111103160502/http://www.codingthewheel.com/archives/poker-hand-evaluator-roundup#2p2

Some general points:

  • I haven't really tried to optimise your hand_rank_dict function as it only needs running once.
  • That being said. There's nothing to be gained from converting the itertools iterators to lists, you're just hogging memory by keeping them all around. I got a fairly substantial improvement in the run-time to build the dictionary just by changing this

However, I have struggled to squeeze any more speed out of the code. In fact I think it's now a fraction slower! I neatened things up a bit by using sets where possible and removing a few unnecessary intermediate variables but fundamentally it seems that the vast majority of the run-time is consumed by the dictionary look-ups. Each one is very fast but there are so many it all adds up. For what it's worth here is my version of your code. I'm not using Jupyter so I refactored slightly to save the dictionary to disk. I haven't thought of an algorithm that's any better than yours so I'll keep thinking!

import itertools
import time
import pickle

ranks = ['2','3','4','5','6','7','8','9','T','J','Q','K','A']
names ="Deuces Threes Fours Fives Sixes Sevens Eights Nines Tens Jacks Queens Kings Aces"
cardnames = names.split()
suitsall = "hearts spades diamonds clubs"
suitnames = suitsall.split()
suits = ['h','s','d','c']
cards = set()

# Create all cards from suits and ranks
for suit in suits:
    for rank in ranks:
        cards.add(rank + suit)


# Function dict_hand_rank ranks every board and returns a tuple (board) (value)
def hand_rank_dict(hand):

    suits = []
    ranks_alphabetical = []
    ranks_numerical = []
    ranks_histogram = []
    kickers = []
    kickers_text = []

    isFlush = False
    isStraight = False
    isStraightFlush = False
    handrankValue = 0

    straightHeight = -1
    straightName = "No straight"
    handName = "none yet"

    for card in hand:
        suits.append(card[1])
        ranks_alphabetical.append(card[0])

    # create ranks_histogram where from A 2 ... J Q K A every card has the corresponding number of occurencies, A double counted

    ranks_histogram.append(str(ranks_alphabetical.count('A')))

    for rank in ranks:
        ranks_histogram.append(str(ranks_alphabetical.count(rank)))

    joined_histogram = ''.join(ranks_histogram)

    # create ranks numerical instead of T, J, Q, K A

    for card in hand:
        ranks_numerical.append(ranks.index(card[0])+2)

    # create kickers

    kickers = sorted([x for x in ranks_numerical if ranks_numerical.count(x) <2], reverse = True)

    # check if a hand is a straight

    if '11111' in joined_histogram:
        isStraight = True
        straightHeight = joined_histogram.find('11111') + 5
        straightName = cardnames[straightHeight - 2]
        handName = "Straight"
        handrankValue = (4,) + (straightHeight,)

    # check if a hand is a flush

    if all(x == suits[0] for x in suits):
        isFlush = True
        handName = "Flush " + cardnames[kickers[0] - 2] + " " + cardnames[kickers[1] - 2] \
              + " " + cardnames[kickers[2] - 2] +  " " + cardnames[kickers[3] - 2] + " " + cardnames[kickers[4] - 2]
        handrankValue = (5,) + tuple(kickers)

    # check if a hand is a straight and a flush

    if isFlush & isStraight:
        isStraightFlush = True
        handName = "Straight Flush"
        handrankValue = (8,) + (straightHeight,)

    # check if a hand is four of a kind
    if '4' in  joined_histogram:
        fourofakindcard = (joined_histogram[1:].find('4') + 2)
        handName = "Four of a Kind " + cardnames[fourofakindcard -2] + " " + cardnames[kickers[0] - 2] + " kicker"
        handrankValue = (7,) + ((joined_histogram[1:].find('4') + 2),) + tuple(kickers)

    # check if a hand is a full house
    if ('3' in joined_histogram) & ('2' in joined_histogram):
        handName = "Full house"
        handrankValue = (6,) + ((joined_histogram[1:].find('3') + 2),) + ((joined_histogram[1:].find('2') + 2),) + tuple(kickers)


    # check if a hand is three of a kind
    if ('3' in joined_histogram) & (len(kickers) == 2):
        threeofakindcard = (joined_histogram[1:].find('3') + 2)
        handName = "Three of a Kind " + cardnames[threeofakindcard -2] + " " + cardnames[kickers[0] - 2] + \
            " " + cardnames[kickers[1] - 2]
        handrankValue = (3,) + ((joined_histogram[1:].find('3') + 2),) + tuple(kickers)

    # check if a hand is two pairs
    if ('2' in joined_histogram) & (len(kickers) == 1):
        lowerpair = (joined_histogram[1:].find('2') + 2)
        higherpair = (joined_histogram[lowerpair:].find('2') + 1 + lowerpair)
        handName = "Two pair " + cardnames[higherpair -2] + " and " + cardnames[lowerpair - 2] + " " + \
            cardnames[kickers[0] - 2] + " kicker"
        handrankValue = (2,) + (higherpair, lowerpair) + tuple(kickers)

    # check if a hand is one pair
    if ('2' in joined_histogram) & (len(kickers) == 3):
        lowerpair = (joined_histogram[1:].find('2') + 2)
        handName = "One pair " + cardnames[lowerpair - 2] + " kickers " + cardnames[kickers[0] - 2] \
            + " " + cardnames[kickers[1] - 2] +  " " + cardnames[kickers[2] - 2]
        handrankValue = (1,) + (lowerpair,) + tuple(kickers)


    # evaluate high card hand
    if (len(ranks_numerical) == len(set(ranks_numerical))) & (isStraight == False) & (isFlush == False):
        handName = "High card " + cardnames[kickers[0] - 2] + " " + cardnames[kickers[1] - 2] \
            + " " + cardnames[kickers[2] - 2] +  " " + cardnames[kickers[3] - 2] + " " + cardnames[kickers[4] - 2]
        handrankValue = (0,) + tuple(kickers)

    return {tuple(sorted(hand)) : handrankValue}


def build_hands_dict(cards, path):

    ranked_hands_dict = {}
    t0 = time.time()
    for board in itertools.combinations(cards, 5):
        ranked_hands_dict.update(hand_rank_dict(board))
    t1 = time.time()
    total = t1-t0
    print(total)
    with open(path,'wb') as f:
        pickle.dump(ranked_hands_dict, f)

# Uncomment this to build the pre-calculated dict of hand ranks
# build_hands_dict(cards, r'D:\hands.p')

with open(r'D:\hands.p','rb') as f:
    ranked_hands_dict = pickle.load(f)

# Function that given board and 2 cards gives back tuple of the best possible hand by searching through ranked_hands_dict keys
def find_the_best_hand(board, hand):

    seven_card_hand = set(board) | hand
    evaluated_all_possible_hands = []

    all_possible_hands = itertools.combinations(seven_card_hand, 5)
    for hand in all_possible_hands:
        evaluated_all_possible_hands.append(ranked_hands_dict[tuple(sorted(hand))])

    return max(evaluated_all_possible_hands)


hand1 = {'2h', '7d'}
hand2 = {'Ad', 'Ah'}

# HAND vs. HAND EVALUATOR

t0 = time.time()

one = 0
two = 0
tie = 0

deadcards = hand1 | hand2
possible_boards = itertools.combinations(cards - deadcards, 5)

n = 0
for board in possible_boards:

    hand1rank = find_the_best_hand(board, hand1)
    hand2rank = find_the_best_hand(board, hand2)

    if hand1rank > hand2rank:
        one = one + 1

    elif hand1rank < hand2rank:
        two = two + 1

    else: #hand1rank == hand2rank:
        tie = tie + 1

    n += 1

onepercent = (one/n)*100
twopercent = (two/n)*100
tiepercent = (tie/n)*100

print(onepercent, twopercent, tiepercent)


t1 = time.time()

total = t1-t0

print(total)
Simon Notley
  • 2,070
  • 3
  • 12
  • 18
  • ...hand vs. hand or range equity is the essential tool in every players toolbox. You are doing it almost in every hand you get involved in. – rioZg Dec 22 '19 at 08:06
  • Ok, I don't really know anything about poker but I thought as your hand is only visible to you then hand Vs hand is more of an academic exercise than an in-play tool. – Simon Notley Dec 22 '19 at 08:51
  • Thanks for the link. Very useful. But it seems to be above my competence level especially given that all are in programming languages not familiar to me so I can not easily evaluate how they did it. But if they managed 15-16 million evaluations per second on old computers in 2006. that would be very acceptable to me. Full evaluation of hand vs. hand on all possible boards is around 72 million evaluations. – rioZg Dec 23 '19 at 21:09
  • I have to admit that I haven't got my head round it yet either but it's enough to convince me that we're not going to get easy improvements in your existing algorithm. It's looks like a very elaborate system of lookups optimised to take advantage of the exact characteristics of poker hands. Having said that you could probably get your existing algorithm quite a bit faster if you optimised it for multiprocessing (Python only uses one CPU thread by default) and/or used a faster language. I love Python but if you are looking for fastest possible execution it's far from the best choice. – Simon Notley Dec 23 '19 at 21:20
  • Thanks SimonN. It occured to me through looking for the solution that leaving Python for 'greener pastures' might be the only solution. – rioZg Dec 24 '19 at 14:07
  • Python can do *multiprocessing* just as well as any other language. You are probably thinking of *multithreading*, where python does have limitations in situations where the GIL becomes a bottleneck (ie. grinding on the processor without any IO calls, which probably includes this situation). This problem can definitely be parallelized using the multiproc library, but that is probably overkill. – Z4-tier Dec 27 '19 at 10:59
  • I actually tried this using multiprocessing. The best I got was a factor of two improvement. Whilst multiprocessing does provide a way round the limitations of multithreading and the GIL it comes with huge overheads – Simon Notley Dec 27 '19 at 12:54
  • As long as the input data is partitioned carefully before forking off the worker processes, it should be possible to get a factor of `n` improvement for an `n` cpu system, assuming each process has affinity for a different CPU (https://stackoverflow.com/questions/36172101/designate-specific-cpu-for-a-process-python-multiprocessing). More than `n` workers (or not pinning processes to separate CPU's) and the overhead will be worse than the GIL, relying on the OS to swap between the workers with repeated context switches. – Z4-tier Dec 27 '19 at 16:30
  • Thanks for the tip on affinity, I'll check it out. The issue I was seeing is that each process takes around 5 seconds to spawn and this happens sequentially meaning I have an execution time of order 5n+80/n which minimises at approx 50% of the value at n=1. – Simon Notley Dec 27 '19 at 17:47
  • In case anyone is interested I have done some more work on this. I found that Python multiprocessing is much faster in Linux than MacOS or Windows so in that OS my multiprocessing version does hand v hand in 17 seconds on a mid range system (4 core, hyperthreaded => 8 parallel CPU threads). I also rewrote the same algorithm in Go. That brings the execution time down to 4.5 seconds. – Simon Notley Jan 07 '20 at 10:01
0

You could use the dbm module (see https://docs.python.org/3/library/dbm.html) , or bsddb in python 2.x, to store your entire lookup table in a database file, if it's too large to fit in memory in a dict. Then it might take some time to fill out the table, but you'd only need to do that once.

greggo
  • 3,009
  • 2
  • 23
  • 22