동적 프로그래밍 카드 게임

Question

이 문제를 확인하시기 바랍니다 내가 가진 :

는 "당신과 당신의 여덟 살짜리 조카 엘모 간단한 카드 게임을하기로 결정 게임의 시작 에서 카드가 처리된다. 각 카드는 다른 숫자의 가치가 있습니다 포인트의 카드입니다. 모든 카드가 처리 된 후, 엘모는 모든 카드가 사라질 때까지 가장 왼쪽 또는 가장 가까운 카드를 제거합니다. 게임을 끝내면 중 가장 많은 점수를 얻은 플레이어가 알고리즘 클래스를 사용하지 않은 경우, E lmo는 명백한 욕심쟁이 전략을 따릅니다. 언제입니까? 그의 차례가되면 Elmo는 항상 더 높은 점수 값으로 카드를 가져옵니다. 가능한 한 언제든지 Elmo를 이길 전략 을 찾는 것입니다. (이런 어린 아이를 두들겨려는 의미로 보일지 모르지만, 어른이 어른이되면 그를 싫어한다.)

카드의 초기 순서가 주어지면 알고리즘을 기술하고 분석하여 Elmo와 플레이 할 수있는 최대 포인트 수 "

나는이 문제에 대한 이론적 인 작업을 이미 끝냈습니다. 예를 들어 DP에 필요한 optimus 하부 구조 데모를 수행했습니다. 나는 게임이 어떻게 끝나는지를 설명하는 재귀 비효율적 인 형태를 정의했다. 다음 단계는이 문제를 효율적으로 해결하는 상향식 알고리즘을 설계하는 것이거나, 도움이된다면 하향식 메모 솔루션이다. 그들 중 어떤 것도하지 마라. uld 당신이이 문제를 해결합니까?

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

가 여기에 두 선수의 전략을 선택할 수있는 솔루션입니다. 주어진 문제를 해결하기 위해 그것을 사용할 수 있지만 플레이어의 전략을 "optimal_strategy"로 설정하여 minimax 솔루션을 찾을 수도 있습니다.

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)