#optimal strategy

[random-xpressions]

Optimal strategy - find what clicks for you & clock on it. Let the world call you insane, crazy, wild. Do it. Do what works for you. That's the legacy you could leave behind. To have lived a life that may have not made any sense to anybody but to you it meant the world. Go for it, your most optimal strategy...

Random Xpressions

[cloakedmonk]

Dinosaurs, Chess, Evolution, And Wonder

Dinosaurs, Chess, Evolution, And Wonder

I have been reading for at least the second time, maybe the third, Richard Dawkins’ magisterial book about evolution, The Greatest Show on Earth (hereafter Show). Like the other one or two times I have read Dawkins’ book, it was an exhilarating ride. Until I read the appendix, which pertains to how the theory of evolution is, to this day, received in the US and non-Scandinavian Europe. That…

View On WordPress

[codingdragon]

Optimal Strategy for a Game

Consider a row of n coins of values V1 . . . Vn, where n is even. We play a game against an opponent by alternating turns. In each turn, a player selects either the first or last coin from the row, removes it from the row permanently, and receives the value of the coin. Determine the maximum possible amount of money we can definitely win if we move first. Solution: Let's say at some stage of the game, the sequence of coins is Vi,Vi+1.....Vj-1,Vj and it's player A's turn. Now player A can either pick Vi or Vj. Also assume M[i][j] is the maximum sum that a player can obtain for this sequence of coins.

Case 1: He picks Vi. Now Player B will either pick Vi+1 or Vj. Since player Bd is equally smart he'll choose the coin that will lead to minimum sum for player A. So M[i][j] = Vi+Minimum(M[i+2][j], M[i+1][j-1]) Case 2: He picks Vj. Now Player B will either pick Vi or Vj-1. Similar to case 1 M[i][j] = Vj+Minimum(M[i+1][j-1], M[i][j-2]) But hey! Player is very smart, he'll choose the value of M[i][j] that yields maximum amount. So M[i][j] = Maximum( Vi+Minimum(M[i+2][j], M[i+1][j-1]),  Vj+Minimum(M[i+1][j-1], M[i][j-2]) ) This is a recurrence relation that could be used to obtain the maximum amount money. I use dynamic programming to get the result optimally. C++ implementation follows:

https://gist.github.com/nirvana-attained/7280435

Analysis: Worst case time complexity is O(n^2) and space complexity is also O(n^2) where n is the number of coins.

Observation: For even number of coins, if both the players play optimally the player who'll make the first move is guaranteed to not loose. Proof: Assume the following arrangement of coins, notice the positions marked 0 and positions marked 1: V1 V2 V3 V4...V2n-1 V2n 0    1  0   1 ...  0        1 If I make the first move I can easily force the second player to pick all the coins at 0 positions or all the coins at 1 positions. If Summation of all the coins at position 0 is greater than those at position 1, I'd force the second player to pick all the coins at position 1 and vice versa. This is one strategy that guarantees a Win or Draw (draw occurs when sum of 0 coins is same as sum of 1 coins) outcome for me. Now this strategy is an ad-hoc strategy and not better than the dynamic programming strategy discussed above. This means the dynamic programming strategy is at least as good as this ad-hoc strategy. Hence dynamic programming strategy will ensure no loss for the player who makes the first move with even number of coins.