Как решить блэкджек с помощью динамического программирования? - PullRequest
Новая
       27

Как решить блэкджек с помощью динамического программирования?

1 голос
/ 19 мая 2019

Этот вопрос из книги Ежедневная проблема кодирования , и является слегка измененной версией проблемы, описанной в этом видео MIT. Вопрос в следующем:

Блэкджек - карточная игра для двух игроков, правила которой следующие:

  • Игрок, а затем дилер получают по две карты.
  • Игрок может затем «ударить» или запросить произвольно много дополнительных карт, чтобы его общая сумма не превышала 21.
  • Затем дилер должен ударить, если его или ее общее количество составляет 16 или ниже, в противном случае пройти.
  • Наконец, два сравниваемых итога, и тот, чья наибольшая сумма не превышает 21, становится победителем.

Для этой проблемы мы упрощаем значения карт следующим образом: каждый карта от 2 до 10 считается их номиналом, а лицевые карты считаются 10, и тузы считаются 1.

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

Книга имеет следующий код: 

import random


class Deck:
    def __init__(self, seed=None):
        self.cards = [i for i in range(1, 10)] * 4 + [10] * 16
        random.seed(seed)
        random.shuffle(self.cards)

    def deal(self, start, n):
        return self.cards[start:start + n]


class Player:
    def __init__(self, hand):
        self.hand = hand
        self.total = 0

    def deal(self, cards):
        self.hand.extend(cards)
        self.total = sum(self.hand)


def cmp(x, y):
    return (x > y) - (x < y)


def play(deck, start, scores):
    player = Player(deck.deal(start, 2))
    dealer = Player(deck.deal(start + 2, 2))
    results = []

    for i in range(49 - start):
        count = start + 4
        player.deal(deck.deal(count, i))
        count += i

        if player.total > 21:
            results.append((-1, count))
            break

        while dealer.total < 17 and count < 52:
            dealer.deal(deck.deal(count, 1))
            count += 1
        if dealer.total > 21:
            results.append((1, count))
        else:
            results.append((cmp(player.total, dealer.total), count))

    options = []
    for score, next_start in results:
        options.append(score +
                       scores[next_start] if next_start <= 48 else score)
    scores[start] = max(options)


def blackjack(seed=None):
    deck = Deck(seed)
    scores = [0 for _ in range(52)]

    for start in range(48, -1, -1):
        play(deck, start, scores)

    return scores[0]

Как правило, для суффикса колоды, начинающейся с карты n (1 <= n <= 52), код проверяет все возможности игрока, принимающего от <code>0 до 52 - n ударов, пока они не обанкротятся. и затем дилер получает хиты, пока их оценка <= 16. </p>

Для каждой итерации цикла for i in range(49 - start) значение count = "количество использованных карт" сбрасывается на start + 4, что имеет смысл, поскольку мы моделируем игрока, который совершает иное количество ударов, отличных от прошлого раза. Однако, меня беспокоит игрок, и руки дилера не сбрасываются . На мой взгляд, для каждой итерации этого цикла мы должны начинать с того, что игроку и дилеру сдаются по две карты, а не сохранять последнюю руку.

Правильно ли я понимаю?

...