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

Question

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

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

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

Я уже проделал большую часть теоретической работы в этой проблеме. Например, я сделал демонстрацию подстроки optimus, которая необходима для 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)