Pots of gold game: Two players A & B. There are pots of gold arranged in a line,

each containing some gold coins (the players can see how many coins are there in each gold pot - perfect information).

They get alternating turns in which the player can pick a pot from one of the ends of the line.

The winner is the player which has a higher number of coins at the end.

The objective is to “maximize” the number of coins collected by A, assuming B also plays optimally.

A starts the game.

The idea is to find an optimal strategy that makes A win knowing that B is playing optimally as well. How would you do that?

At the end I was asked to code this strategy!

구글전화 면접으로도 유명한, Pots of gold game

이 게임의 목표는 A가 먼저 게임을 시작할 때 A가 가장 많은(Maximize) 금화를 가질 수 있도록 하는 것이다.

B 역시 최적의 알고리즘으로 항아리를 선택한다고 가정한다.

탐색트리가 너무 많아서 depth가 커지는 경우가 발생한다..

pots = [...] cache = {}def optimal(left, right, player):    if left > right:        return 0    if (left, right, player) in cache:        return cache[(left, right, player)]    if player == 'A':        result = max(optimal(left + 1, right, 'B') + pots[left],                     optimal(left, right - 1, 'B') + pots[right])    else:        result = min(optimal(left + 1, right, 'A'),                     optimal(left, right - 1, 'A'))    cache[(left, right, player)] = result    return result answer = optimal(0, len(pots)-1, 'A')

참고

• https://www.quora.com/Dynamic-Programming-DP-How-do-you-solve-the-pots-of-gold-game