A game is played as follows. Coins with value $x_1, . . . , x_n$ are laid on a table in a row. Two players alternate turns taking a coin from either end of what’s left of the row of coins until the coins are gone. The object is to accumulate as much value as possible. For example, there may be n = 6 coins worth ($x_1, x_2, x_3, x_4, x_5, x_6$) = (2, 5, 3, 1, 4, 3). Let us agree that a game has value V to the player who goes first (first player) if: (i) no matter how second player plays, first player can obtain coins worth V ; and (ii) no matter how first player plays, second player can make sure first player gets coins worth no more than V . Let $V (i, j) (1 ≤ i ≤ j ≤ n)$ denote this value if there are $j − i + 1$ coins in the game and they are worth ($x_i, . . . , x_j$ ). For example, in our sample game: $V (5, 5) = 4$ (there’s only one coin, worth 4, and the player who goes first gets it); V (2, 3) = 5 (there are two coins, worth 5 and 3, and the player who goes first will pick the 5); and V (4, 6) = 4 (there are three coins, worth 1, 4, and 3, and the player who goes first picks the 3 and then the 1 after second player takes the 4).
Suppose I play randomly: each time it’s my turn I choose a coin independently from either end each with probability $1/2$.(If there’s only one coin left when it’s my turn, obviously I take it with probability 1.) Furthermore suppose you know I’m going to do this. As above, but assuming my random strategy, let W(i, j) denote the expected value to you assuming you play optimally to maximize expected value if you go first and the coins are $(x_i, . . . , x_j)$. For $j ≥ i + 2$, find a recursive formula for $W(i, j)$ in terms of $W(i, j − 2)$, $W(i + 1, j − 1)$, and $W(i + 2, j)$. Indicate the boundary conditions.
How would I go about finding such a formula
If you take the coin from the front, the value is $x_i+W(i+1,j-1)$ or $x_i+W(i+2,j)$ with equal probability. If you take the coin from the end, the value is $x_j+W(i,j-2)$ or $x_j+W(i+1,j-1)$ with equal probability.