Динамическое программирование карточной игры

Question

Пожалуйста, проверьте эту проблему у меня есть:

"Вы и ваш восьмилетний племянник Элмо решили сыграть в простую карточную игру. В начале игры карты раздаются в длинном ряду. Каждая карта приносит разное количество очков. карты раздаются, вы и Элмо по очереди убираете крайнюю левую или правую карту из ряда, пока все карты не исчезнут. На каждом ходу вы можете решить, какую из двух карт взять. Победителем игры становится игрок когда игра заканчивается, она набрала наибольшее количество очков. Никогда не посещая класс алгоритмов, Элмо следует очевидной жадной стратегии: когда наступает его очередь, Элмо всегда берет карту с более высоким значением очков. Ваша задача - найти стратегию это побьет Элмо всякий раз, когда это возможно. (Может показаться, что это значит избивать такого маленького ребенка, но Элмо абсолютно ненавидит, когда взрослые позволяют ему побеждать).

Опишите и проанализируйте алгоритм, чтобы определить, учитывая начальную последовательность карт, максимальное количество очков, которое вы можете набрать, играя против Элмо."

Я уже проделал большую часть теоретической работы по этой проблеме. Например, я провел демонстрацию оптимальной подструктуры, которая необходима для DP, и я определил рекурсивную неэффективную форму, которая объясняет, как делается игра. Теперь следующим шагом является разработка алгоритма "снизу вверх", который эффективно решает эту проблему, или, если это может помочь, нисходящего решения для запоминания. Я просто не могу сделать ни одного из них. Как бы вы решили эту проблему?

Answer 1

Алгоритм прост, и вы можете использовать запоминание и динамическое программирование следующим образом:

def findMax(mem, cards, myTurn):
    maxValue = 0
    if(not cards):
        return 0
    if str(cards) in mem: #If we have already compute this state
        return mem[str(cards)]
    elif not myTurn: #turn of Elmo
        if cards[0] > cards[len(cards) - 1]:
            maxValue = findMax(mem, cards[1:], True)
        else:
            maxValue = findMax(mem, cards[:-1], True)
    else: #your turn
        maxValue = max(cards[0] + findMax(mem, cards[1:], False), cards[len(cards) - 1] + findMax(mem, cards[:-1], False))
    mem[str(cards)] = maxValue  #Store the max value for this state
    return maxValue

import random
size = int(10 + random.randint(0,1))
cards = [random.randint(0,50) for x in range(size)]
print "Cards" + str(cards)
print findMax({}, cards, True)

Выход:

Cards: [28, 33, 48, 0, 26, 1, 3, 11, 22, 32, 12]
Max value: 120

Answer 2

Вот решение, которое позволяет вам выбрать стратегии обоих игроков. Вы можете использовать его для решения поставленной задачи, но вы также можете установить стратегии обоих игроков на "optim_strategy", чтобы найти минимаксное решение.

import random

def greedy_strategy(s0, s1, cards, i, j, cache):
    if i == j: return 0
    if cards[i] >= cards[j - 1]:
        return cards[i] - s1(s1, s0, cards, i + 1, j, cache)
    else:
        return cards[j - 1] - s1(s1, s0, cards, i, j - 1, cache)

def optimal_strategy(s0, s1, cards, i, j, cache):
    if i == j: return 0
    key = (i, j)
    if key not in cache:
        left = cards[i] - s1(s1, s0, cards, i + 1, j, cache)
        right = cards[j - 1] - s1(s1, s0, cards, i, j - 1, cache)
        cache[key] = max(left, right)
    return cache[key]

def score_play(cards, s0, s1):
    # How many points you'll win by
    adv = s0(s0, s1, cards, 0, len(cards), {})
    # my_score + opp_score = sum(cards)
    # my_score - opp_score = adv
    # adding: 2 * my_score = sum(cards) + adv
    # Therefore my_score is this...
    return (sum(cards) + adv) // 2

for _ in xrange(10):
    cards = range(20)
    random.shuffle(cards)
    print cards, score_play(cards, optimal_strategy, greedy_strategy)