game theory

general
1

Given an array of positive numbers. There are two players A and B. In his/her turn a player can pick either one or two elements from the front end of the array and these elements are then removed from the array. Players play alternately
In the end values the players are holding are summed up. The player with larger sum value wins.
If both play optimally, find who wins
e.g.
5
{1 1 0 0 1} A wins ,
6
{1 5 6 3 2 9} B wins
4
{1 1 1 1} Game draws

2

This can be solved via top-down recursion with memoization.

Note that since the total sum of the array is constant,

let F(i) denote maximum value than can be obtained from A[i]…A[N] ie ith suffix of the array.

Now we form the recurrence

Note that if we take the first element ie A[0], second player is left with array A[1]…A[N] to play with. He will choose to maximise his score. Now he may possibly give us A[3]…A[N] by choosing only the second element or A[4]…A[N] by choosing both the second and the third element.

So if we take A[i], player B may take A[i+1] only and given us A[i+2]…A[N] to play with.

Or he may take both A[i] and A[i+1] and give us A[i+3]…A[N] to play with. Since array sum is constant, by maximising his score he will minimise our score. Hence we will leave us the array with which our score is minimised.

F(i) = max( A[i] + min( F(i+2), F(i+3) ) , A[i]+A[i+1] + min( F(i+3), F(i+4) );

Apply memoization on F(). F(0) will be your answer ie score of the first player A. Score of B is simply the total sum of the array minus the score of A.

2 Likes
3

A takes the first turn

4

There is an easy dp for this problem!

5

I’ve thinking thorugh DP but couldn’t come to a solution
Elaborate the DP approach

6

Thanks for the help
This info was quiet helpful(was the solution itself)