Dynamic Programming Card Game

Question

Please check out this problem I have:

"You and your eight-year-old nephew Elmo decide to play a simple card game. At the beginning of the game, the cards are dealt face up in a long row. Each card is worth a different number of points. After all the cards are dealt, you and Elmo take turns removing either the leftmost or rightmost card from the row, until all the cards are gone. At each turn, you can decide which of the two cards to take. The winner of the game is the player that has collected the most points when the game ends. Having never taken an algorithms class, Elmo follows the obvious greedy strategy?when it?s his turn, Elmo always takes the card with the higher point value. Your task is to find a strategy that will beat Elmo whenever possible. (It might seem mean to beat up on a little kid like this, but Elmo absolutely hates it when grown-ups let him win.)

Describe and analyze an algorithm to determine, given the initial sequence of cards, the maximum number of points that you can collect playing against Elmo."

I've already done most of the theorical work in this problem. For instance, I've done the optimus substructure demonstration which is needed for DP, and I have defined the Recursive inefficient form, that explains how the game gets done. Now the next step is to design a bottom-up algorithm that solves this problem efficiently or, if it might help, a top-down memoization solution. I just can't do any of them. How would you solve this problem?

Answer 1

The algorithm is simple and you can use memoization and dynamic programming in this way:

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)

Output:

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

Answer 2

Here's a solution that allows you to select both player's strategies. You can use it to solve the problem as given, but you can also set both player's strategies to "optimal_strategy" to find the minimax solution.

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)