Optimal strategy for two player coin games

user_13681569 0
Viewed 791

Two players take turns choosing one of the outer coins. At the end we calculate the difference between the score two players get, given that they play optimally. The greedy strategy of getting the max. value of coin often does not lead to the best results in my case.

Now I developed an algorithm:

Sample:{9,1,15,22,4,8}

  1. We calculate the sum of coins in even index and that of coins in odd index.

  2. Compare the two sum, (9+15+4)<(1+22+8) so sum of odd is greater. We then pick the coin with odd index, in our sample that would be 8.

  3. the opponent, who plays optimally, will try to pick the greater coin, e.g. 9.

  4. There is always a coin at odd index after the opponent finished, so we keep picking the coins at odd index, that would be 1.

  5. looping the above steps we will get a difference of (8+1+22) - (9+15+4) = 3.

6.vice versa if sum of even is greater in step 2.

I have compared the results generated by my algorithm with a 2nd algorithm similar to below one: https://www.geeksforgeeks.org/optimal-strategy-for-a-game-set-2/?ref=rp

And the results were congruent, until my test generated a random long array: [6, 14, 6, 8, 6, 3, 14, 5, 18, 6, 19, 17, 10, 11, 14, 16, 15, 18, 7, 8, 6, 9, 0, 15, 7, 4, 19, 9, 5, 2, 0, 18, 2, 8, 19, 14, 4, 8, 11, 2, 6, 16, 16, 13, 10, 19, 6, 17, 13, 13, 15, 3, 18, 2, 14, 13, 3, 4, 2, 13, 17, 14, 3, 4, 14, 1, 15, 10, 2, 19, 2, 6, 16, 7, 16, 14, 7, 0, 9, 4, 9, 6, 15, 9, 3, 15, 11, 19, 7, 3, 18, 14, 11, 10, 2, 3, 7, 3, 18, 7, 7, 14, 6, 4, 6, 12, 4, 19, 15, 19, 17, 3, 3, 1, 9, 19, 12, 6, 7, 1, 6, 6, 19, 7, 15, 1, 1, 6]

My algorithm generated 26 as the result, while the 2nd algorithm generated 36. Mine is nothing about dynamic programming and it requires less memory, whereas i also implemented the 2nd one with memoization. This is confusing since mine is correct with most of the array cases until this one. Any help would be appreciated!

greedy dynamic-programming recursion algorithm
1 Answers

If the array is of even length, your algorithm tries to produce a guaranteed win. You can prove that quite easily. But it doesn't necessarily produce the optimal win. In particular it won't find strategies where you want some coins that are on even indexes and others on odd indexes.

The following short example illustrates the point.

[10, 1, 1, 20, 1, 1]

Your algorithm will look at evens vs odds, realize that 10+1+1 < 1+20+1 and take the last element first. Guaranteeing a win by 10.

But you want both the 10 and the 20. Therefore the optimal strategy is to take the 10 leaving 1, 1, 20, 1, 1, whichever side the other person takes you take the other to get to 1, 20, 1, and then whichever side the other takes you take the middle. Resulting in you getting 10, 1, 20 and the other person getting 1, 1, 1. Guaranteeing a win by 28.

user_5854110
Related