Greedy algorithm on a number choice game

Question

The problem is given as follows:

There is a game with a sequence of n numbers(a1, a2, a3,..,an) and two players. Players take numbers from the sequence; on each turn the player can choose either the first or last number in the sequence. When the sequence is emptied, the player with the larger total wins; if equal, the game is a draw.

The goal is to write an algorithm, that returns a sequence of choices to guarantee the best result (win or draw) for the first player, assuming that the second player will play optimally.

I came up with a recursive formula, which can be translated to dynamic programming solution:

For the sequence Ai, Ai+1,..., Aj:
If there is one number in the sequence - take it.
Otherwise, check both of possible choices, picking the one that gives the lower result for the second player through the end of the game.

Thus, the optimal sum for the first player is a sum of all numbers in the sequence minus this minimal sum that the second player will get. The formula looks as follows:

p(i,j) = Ai (if i=j)

p(i,j) = Ai + Ai+1 +...+ Aj - min{p(i+1,j), p(i,j-1)} (if j>i)

We use the same formula for computing the sum of the second player and the sum of the first player, because the second player also wants to get the maximum possible value.

The correctness can be easily proved inductively. Also, we can get the dynamic programming solution from it: First calculate values of p(i,j) for each pair (i,j) and save it in the table nxn. The solution takes O(n^3). Also, there is a way to perform pre-processing of sum A1 + Ai+1 +Ai+2 +...+ Aj: we can compute sums A1 +...+ Aj for each j and every time applying the formula p(i,j) can use sum(1,j) - sum(1,i) so that the solution will take O(n^2).

Is there a faster algorithm? In my solution I get the sequence of choices that gives the maximal sum for the first player, but it is too "strong": I was asked to get a sequence of chooses that bring to him a win, regardless of maximizing the final sum. So, undoubtedly, I performed some unnecessary steps.

The better solution seems to be a greedy algorithm, because I have seen the same problem, but with an even number of numbers in the sequence(here https://cs.stackexchange.com/questions/82351/optimizing-greedy-solution-for-choice-game/82450).

Can anybody give me some ideas or clues on how a greedy solution should look? Thank you in advance!

Prune Prune · Accepted Answer · 2018-12-05T21:54:25

"Greedy" is a simple concept: instead of looking through the entire game tree, consider only maximizing the short-term result for the present level. In this case, it means taking the larger of the two elements available, and not using recursion at all.

Your complete solution, maximizing the sum received, works; it's just a little overkill for the general situation.

A balance between the two might be useful, a heuristic that looks ahead a certain number of moves. For instance, play out the game only four moves ahead (two for each player), and pick the one that maximizes your difference.

Greedy algorithm on a number choice game

2 Answers