Эффективные алгоритмы заказа карточного покера "5 из 7" (не стрит / не флеш) Руки | Разделяй и властвуй
Рассмотрим отсортированные списки длиной 7, где каждая запись x является числом 2 <= x <= 14, и число дубликатов любой записи не может превышать 4. Предполагается, что высокопроизводительный алгоритм уже определил, что у нас есть не прямая / не флеш рука.
Онлайн покерные сайты будут заинтересованы в высокопроизводительных алгоритмах, которые позаботятся о следующем шаге получения 5 лучших карт в этом контексте.
Написание программы на Python, которая не импортирует модули, является отличным способом создания прототипов таких алгоритмов.
Скорее всего, онлайн-покерные сайты размером с монстра не нуждаются в нашей помощи, но было бы интересно увидеть алгоритмы, разработанные для скорости. В вопросе
с 2010 года это было рассмотрено, но многие ссылки не работают. Было бы неплохо узнать состояние самых быстрых известных алгоритмов, используемых сегодня.
Вопрос: Известен ли алгоритм, обсуждаемый ниже? Определен ли какой-либо алгоритм как выдающийся для производительности?
Моя работа
Я заметил, что список длины 7 имеет середину и что есть "комбинаторная симметрия" и структура, которую алгоритм может включать. Мы реализуем эту логику в следующем коде. Можно вспомнить быструю молниеносную программу, написанную на ассемблере, которая вычисляет GOTO смещение числа с решением.
Примечание: у меня также есть процедура сортировки за один проход, которая берет любые 7 карт и определяет, можно ли делать стрит или флеш. Но мне посоветовали держать мои вопросы более сфокусированными, чтобы это не обсуждалось здесь.
Программа Python:
hand=[2,2,7,7,8,11,12]
hand=[2,3,4,7,7,7,11]
start_spot = 3
end_spot = 3
if hand[3] == hand[4]:
if hand[4] == hand[5]:
if hand[5] == hand[6]:
end_spot = 6
else:
end_spot = 5
else:
end_spot = 4
if hand[3] == hand[2]:
if hand[2] == hand[1]:
if hand[1] == hand[0]:
start_spot = 0
else:
start_spot = 1
else:
start_spot = 2
if end_spot - start_spot == 3:
if end_spot == 6:
Kick = hand[start_spot-1]
else:
Kick = hand[6]
best5 = [Kick,hand[start_spot],hand[start_spot+1],hand[start_spot+2],hand[start_spot+3]]
print(hand, best5, 'four of a kind')
raise SystemExit
else:
pass
def multCount(c1,c2,c3):
pc = 0
if c1 == c2: pc = pc + 1
if c2 == c3: pc = pc + 10
return pc
pc_r = multCount(hand[4],hand[5],hand[6])
pc_l = multCount(hand[2],hand[1],hand[0])
if start_spot == 3 and end_spot == 3:
if pc_l == 0 and pc_r == 0:
best5 = [hand[2],hand[3],hand[4],hand[5],hand[6]]
print(hand, best5, 'no pair')
raise SystemExit
elif pc_l == 0 and pc_r == 1:
best5 = [hand[2],hand[3],hand[6],hand[4],hand[5]]
print(hand, best5, 'one pair')
raise SystemExit
elif pc_l == 0 and pc_r == 10:
best5 = [hand[2],hand[3],hand[4],hand[5],hand[6]]
print(hand, best5, 'one pair')
raise SystemExit
elif pc_l == 0 and pc_r == 11:
best5 = [hand[2],hand[3],hand[4],hand[5],hand[6]]
print(hand, best5, 'trips')
raise SystemExit
elif pc_l == 1 and pc_r == 0:
best5 = [hand[4],hand[5],hand[6],hand[1],hand[2]]
print(hand, best5, 'one pair')
raise SystemExit
elif pc_l == 1 and pc_r == 1:
best5 = [hand[6],hand[1],hand[2],hand[4],hand[5]]
print(hand, best5, 'two pair')
raise SystemExit
elif pc_l == 1 and pc_r == 10:
best5 = [hand[4],hand[1],hand[2],hand[5],hand[6]]
print(hand, best5, 'two pair')
raise SystemExit
elif pc_l == 1 and pc_r == 11:
best5 = [hand[1],hand[2],hand[4],hand[5],hand[6]]
print(hand, best5, 'full house')
raise SystemExit
elif pc_l == 10 and pc_r == 0:
best5 = [hand[4],hand[5],hand[6],hand[0],hand[1]]
print(hand, best5, 'one pair')
raise SystemExit
elif pc_l == 10 and pc_r == 1:
best5 = [hand[6],hand[0],hand[1],hand[4],hand[5]]
print(hand, best5, 'two pair')
raise SystemExit
elif pc_l == 10 and pc_r == 10:
best5 = [hand[4],hand[0],hand[1],hand[5],hand[6]]
print(hand, best5, 'two pair')
raise SystemExit
elif pc_l == 10 and pc_r == 11:
best5 = [hand[0],hand[1],hand[4],hand[5],hand[6]]
print(hand, best5, 'full house')
raise SystemExit
elif pc_l == 11 and pc_r == 0:
best5 = [hand[5],hand[6],hand[0],hand[1],hand[2]]
print(hand, best5, 'trips')
raise SystemExit
elif pc_l == 11 and pc_r == 1:
best5 = [hand[4],hand[5],hand[0],hand[1],hand[2]]
print(hand, best5, 'full house')
raise SystemExit
elif pc_l == 11 and pc_r == 10:
best5 = [hand[5],hand[6],hand[0],hand[1],hand[2]]
print(hand, best5, 'full house')
raise SystemExit
elif pc_l == 11 and pc_r == 11:
best5 = [hand[1],hand[2],hand[4],hand[5],hand[6]]
print(hand, best5, 'full house')
raise SystemExit
else:
pass
if start_spot == 3 and end_spot == 4:
if pc_l == 0 and pc_r == 0:
best5 = [hand[2],hand[5],hand[6],hand[3],hand[4]]
print(hand, best5, 'one pair')
raise SystemExit
elif pc_l == 0 and pc_r == 1:
print("ERROR 1")
pass # can't happen
raise SystemExit
elif pc_l == 0 and pc_r == 10:
best5 = [hand[2],hand[3],hand[4],hand[5],hand[6]]
print(hand, best5, 'two pair')
raise SystemExit
elif pc_l == 0 and pc_r == 11:
print("ERROR 2")
pass # can't happen
raise SystemExit
elif pc_l == 1 and pc_r == 0:
best5 = [hand[6],hand[1],hand[2],hand[3],hand[4]]
print(hand, best5, 'two pair')
raise SystemExit
elif pc_l == 1 and pc_r == 1:
print("ERROR 3")
pass # can't happen
raise SystemExit
elif pc_l == 1 and pc_r == 10:
best5 = [hand[2],hand[3],hand[4],hand[5],hand[6]]
print(hand, best5, 'two pair')
raise SystemExit
elif pc_l == 1 and pc_r == 11:
print("ERROR 4")
pass # can't happen
raise SystemExit
elif pc_l == 10 and pc_r == 0:
best5 = [hand[6],hand[0],hand[1],hand[3],hand[4]]
print(hand, best5, 'two pair')
raise SystemExit
elif pc_l == 10 and pc_r == 1:
print("ERROR 5")
pass # can't happen
raise SystemExit
elif pc_l == 10 and pc_r == 10:
best5 = [hand[4],hand[0],hand[1],hand[5],hand[6]]
print(hand, best5, 'two pair')
raise SystemExit
elif pc_l == 10 and pc_r == 11:
print("ERROR 6")
pass # can't happen
raise SystemExit
elif pc_l == 11 and pc_r == 0:
best5 = [hand[3],hand[4],hand[0],hand[1],hand[2]]
print(hand, best5, 'full house')
raise SystemExit
elif pc_l == 11 and pc_r == 1:
print("ERROR 7")
pass # can't happen
raise SystemExit
elif pc_l == 11 and pc_r == 10:
best5 = [hand[5],hand[6],hand[0],hand[1],hand[2]]
print(hand, best5, 'full house')
raise SystemExit
elif pc_l == 11 and pc_r == 11:
print("ERROR 8")
pass # can't happen
raise SystemExit
else:
pass
if start_spot == 2 and end_spot == 3:
if pc_l == 0 and pc_r == 0:
best5 = [hand[4],hand[5],hand[6],hand[2],hand[3]]
print(hand, best5, 'one pair')
raise SystemExit
elif pc_l == 0 and pc_r == 1:
best5 = [hand[6],hand[2],hand[3],hand[4],hand[5]]
print(hand, best5, 'two pair')
raise SystemExit
elif pc_l == 0 and pc_r == 10:
best5 = [hand[4],hand[2],hand[3],hand[5],hand[6]]
print(hand, best5, 'two pair')
raise SystemExit
elif pc_l == 0 and pc_r == 11:
print("ERROR 9")
pass # can't happen
raise SystemExit
elif pc_l == 1 and pc_r == 0:
print("ERROR 10")
pass # can't happen
raise SystemExit
elif pc_l == 1 and pc_r == 1:
print("ERROR 11")
pass # can't happen
raise SystemExit
elif pc_l == 1 and pc_r == 10:
print("ERROR 12")
pass # can't happen
raise SystemExit
elif pc_l == 1 and pc_r == 11:
print("ERROR 13")
pass # can't happen
raise SystemExit
elif pc_l == 10 and pc_r == 0:
best5 = [hand[6],hand[0],hand[1],hand[2],hand[3]]
print(hand, best5, 'two pair')
raise SystemExit
elif pc_l == 10 and pc_r == 1:
best5 = [hand[6],hand[2],hand[3],hand[4],hand[5]]
print(hand, best5, 'two pair')
raise SystemExit
elif pc_l == 10 and pc_r == 10:
best5 = [hand[4],hand[2],hand[3],hand[5],hand[6]]
print(hand, best5, 'two pair')
raise SystemExit
elif pc_l == 10 and pc_r == 11:
print("ERROR 14")
pass # can't happen
raise SystemExit
elif pc_l == 11 and pc_r == 0:
print("ERROR 15")
pass # can't happen
raise SystemExit
elif pc_l == 11 and pc_r == 1:
print("ERROR 16")
pass # can't happen
raise SystemExit
elif pc_l == 11 and pc_r == 10:
print("ERROR 17")
pass # can't happen
raise SystemExit
elif pc_l == 11 and pc_r == 11:
print("ERROR 18")
pass # can't happen
raise SystemExit
else:
pass
if start_spot == 2 and end_spot == 4:
if pc_l == 0 and pc_r == 0:
best5 = [hand[5],hand[6],hand[2],hand[3],hand[4]]
print(hand, best5, 'trips')
raise SystemExit
elif pc_l == 0 and pc_r == 1:
print("ERROR 19")
pass # can't happen
raise SystemExit
elif pc_l == 0 and pc_r == 10:
best5 = [hand[5],hand[6],hand[2],hand[3],hand[4]]
print(hand, best5, 'full house')
raise SystemExit
elif pc_l == 0 and pc_r == 11:
print("ERROR 20")
pass # can't happen
raise SystemExit
elif pc_l == 1 and pc_r == 0:
print("ERROR 21")
pass # can't happen
raise SystemExit
elif pc_l == 1 and pc_r == 1:
print("ERROR 22")
pass # can't happen
raise SystemExit
elif pc_l == 1 and pc_r == 10:
print("ERROR 23")
pass # can't happen
raise SystemExit
elif pc_l == 1 and pc_r == 11:
print("ERROR 24")
pass # can't happen
raise SystemExit
elif pc_l == 10 and pc_r == 0:
best5 = [hand[0],hand[1],hand[2],hand[3],hand[4]]
print(hand, best5, 'full house')
raise SystemExit
elif pc_l == 10 and pc_r == 1:
print("ERROR 25")
pass # can't happen
raise SystemExit
elif pc_l == 10 and pc_r == 10:
best5 = [hand[5],hand[6],hand[2],hand[3],hand[4]]
print(hand, best5, 'full house')
raise SystemExit
elif pc_l == 10 and pc_r == 11:
print("ERROR 26")
pass # can't happen
raise SystemExit
elif pc_l == 11 and pc_r == 0:
print("ERROR 27")
pass # can't happen
raise SystemExit
elif pc_l == 11 and pc_r == 1:
print("ERROR 28")
pass # can't happen
raise SystemExit
elif pc_l == 11 and pc_r == 10:
print("ERROR 29")
pass # can't happen
raise SystemExit
elif pc_l == 11 and pc_r == 11:
print("ERROR 30")
pass # can't happen
raise SystemExit
else:
pass
if start_spot == 1 and end_spot == 3:
if pc_r == 0:
best5 = [hand[5],hand[6],hand[1],hand[2],hand[3]]
print(hand, best5, 'trips')
raise SystemExit
elif pc_r == 1:
best5 = [hand[4],hand[5],hand[1],hand[2],hand[3]]
print(hand, best5, 'full house')
raise SystemExit
elif pc_r == 10:
best5 = [hand[5],hand[6],hand[1],hand[2],hand[3]]
print(hand, best5, 'full house')
raise SystemExit
elif pc_r == 11:
best5 = [hand[2],hand[3],hand[4],hand[5],hand[6]]
print(hand, best5, 'full house')
raise SystemExit
else:
pass
if start_spot == 3 and end_spot == 5:
if pc_l == 0:
best5 = [hand[2],hand[6],hand[3],hand[4],hand[5]]
print(hand, best5, 'trips')
raise SystemExit
elif pc_l == 1:
best5 = [hand[1],hand[2],hand[3],hand[4],hand[5]]
print(hand, best5, 'full house')
raise SystemExit
elif pc_l == 10:
best5 = [hand[0],hand[1],hand[3],hand[4],hand[5]]
print(hand, best5, 'full house')
raise SystemExit
elif pc_l == 11:
best5 = [hand[1],hand[2],hand[4],hand[5],hand[6]]
print(hand, best5, 'full house')
raise SystemExit
else:
pass
print("ERROR 99")
pass # can't happen
raise SystemExit
2 ответа
Решение
Я полагаю, что реализовал указанный вами алгоритм, но очень легко ошибиться, поэтому дайте мне знать, если есть какие-либо проблемы. Я просто делаю четыре основных оценки под рукой
- Это прямо?
- Это флеш?
- Сколько k-пар в нем содержится?
- Какой размер самой большой k-пары?
Из них я определяю лучшую руку, которую может составить конкретная комбинация из 5 карт в серии операторов if, и сортирую карты соответственно. Затем я создаю список всех 5-карточных комбинаций из набора из 7, определяю максимальную / лучшую руку, используя эту логику (я переставляю порядок счета и руки, чтобы выполнить это), и возвращаю эту руку.
from collections import Counter
from itertools import combinations
def num_of_kind(cards):
return Counter(c[0] for c in cards)
def count_pairs(cards):
return sum(i > 1 for i in num_of_kind(cards).values())
def largest_pair(cards):
return max(num_of_kind(cards).values())
def is_straight(cards):
values = [c[0] for c in cards]
index = "A23456789TJQKA"["K" in values:].index
indices = sorted(index(v) for v in values)
return all(x == y for x, y in enumerate(indices, indices[0]))
def is_flush(cards):
suit_pop = Counter(c[1] for c in cards)
return any(s > 4 for s in suit_pop.values())
def straight_sort(cards):
values = [c[0] for c in cards]
index = "A23456789TJQKA"["K" in values:].index
return sorted(cards, key=lambda x:index(x[0]), reverse=True)
def flush_sort(cards):
suit_pop = Counter(c[1] for c in cards)
return sorted(cards, key=lambda x: suit_pop[x[1]], reverse=True)
def pair_sort(cards):
num = num_of_kind(cards)
return sorted(cards, key=lambda x: num[x[0]], reverse=True)
def card_vals(cards):
return [c[0] for c in cards]
def score_hand(cards):
pairs = count_pairs(cards)
largest = largest_pair(cards)
straight = is_straight(cards)
flush = is_flush(cards)
cards = straight_sort(cards)
hand_score = 0
if flush and straight:
hand_score, cards = 8, flush_sort(cards)
elif largest == 4:
hand_score, cards = 7, pair_sort(cards)
elif pairs == 2 and largest == 3:
hand_score, cards = 6, pair_sort(cards)
elif flush:
hand_score, cards = 5, flush_sort(cards)
elif straight:
hand_score = 4
elif largest == 3:
hand_score, cards = 3, pair_sort(cards)
else:
hand_score, cards = pairs, pair_sort(cards)
return hand_score, card_vals(cards), cards
def best_hand(cards):
cards = max(list(combinations(cards, 5)), key=score_hand)
score, _, hand = score_hand(cards)
return hand[::-1], score
def main():
hand = ['2c','Ah','3d', '5s','4h','5d', '3h']
print(*best_hand(hand))
if __name__ == "__main__":
main()
Я мог бы утомить вас деталями каждого метода, но я чувствую, что все довольно очевидно. Единственный сложный момент в is_straight()и это всего лишь некоторая хитрость индексации, чтобы определить, можно ли упорядочить значения карт в последовательном порядке.
Вот несколько соображений, которые вы можете учесть при разработке алгоритма поиска лучшей руки:
- Все сравнения имеют дело со сравнением стоимости (числа) и / или масти карты. Поэтому вы можете рассмотреть возможность составления списка номеров карт и списка мастей карт. Или посмотрите на хитрости, которые
itertoolsМодуль имеет. - Флеш и стрит-флеш - единственные руки, где важен костюм. В противном случае вы смотрите только на номера карт.
- Стрит и стрит-флеш - единственные руки, где вам нужно искать 5 последовательных чисел. Имейте в виду, что это могут быть тузы и лицевые карты. Кроме того, если туз включен, то он должен быть в начале или в конце (например, "Q K A 2 3" не считается прямой). Вы также можете заглянуть в модуль more_itertools.consecutive_groups.
- Другие руки (одна пара, две пары, три в своем роде, фулл-хаус, четыре в своем роде) основаны на том, как часто появляются одинаковые числа. Если значение появляется 4 раза, то нет необходимости проверять другие руки в этом списке. Если один появляется 3 раза, то проверьте, можете ли вы сделать фулл-хаус, иначе это три типа. Вы можете продолжать проверять этот список, как этот, с самой высокой руки до самой низкой, останавливаясь, когда вы получаете совпадение.
- Вы можете даже подумать о создании класса под названием
Cardи подавать свои карты как объекты типа "Карта". Тогда у вас могут быть функции в классе для возврата масти или числового значения карты.