Author 
Topic: Maximal Sums In Optimal Play (Read 3123 times) 

william wu
wu::riddles Administrator
Gender:
Posts: 1291


Maximal Sums In Optimal Play
« on: Dec 16^{th}, 2002, 11:32pm » 
Quote Modify

A cool problem adapted from the 2002 ACM Programming Contest at Berkeley. Two players play the following game. They start with a list containing an even number of integers. Each player in turn removes either the first or last remaining item in the list until all are removed. Each player attempts to get the largest possible sum using the numbers they removed (think of the numbers as representing numbers of gold coins). Your problem is to find a sequence of moves that would be made if both players played optimally (that is, so as to get the largest possible sum). For example, given the sequence 6; 12; 0; 8 the first player's best move is to remove the 8. Regardless of whether the second player chooses 6 or 0, the first player will get the 12, so as to give the first player a total of 20 and the second player 6. The output of your algorithm could be a string of characters, each of which is either 'F' or 'L' (for first and last, respectively). Thus the string "LFFF" corresponds to the first player choosing the last number, then the second player choosing the first number, and so on.

« Last Edit: Dec 16^{th}, 2002, 11:39pm by william wu » 
IP Logged 
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13640


Re: Maximal Sums In Optimal Play
« Reply #1 on: Dec 17^{th}, 2002, 1:18am » 
Quote Modify

Any reason why one couldn't just use minimax on this problem? (making a tree of all plays and working backwards, trimming away the worst choices for the player at that node)


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



James Fingas
Uberpuzzler
Gender:
Posts: 949


Re: Maximal Sums In Optimal Play
« Reply #2 on: Dec 17^{th}, 2002, 11:34am » 
Quote Modify

towr, Are you sure that would give the the optimal play? I imagine that in a game like this you might have to look a long ways into the future. Maybe there's a simplification we can make. For instance, we know that a sequence of our move and then the opposition's move can only remove three different sequences: two from the left, two from the right, or one from either end. This sequence will only grow as O(n), so maybe we can look way ahead and figure out where the optimal endgame is, and then work out the optimal way to get there. There must be a logical way to reduce this...What about the following problem: 1; 1; 1; 2000; 1; 1; 1; 1; 1; 1 Hmm...


IP Logged 
Doc, I'm addicted to advice! What should I do?



James Fingas
Uberpuzzler
Gender:
Posts: 949


Re: Maximal Sums In Optimal Play
« Reply #3 on: Dec 17^{th}, 2002, 1:27pm » 
Quote Modify

towr, I'm starting to see what you mean. Here's my algorithm (hopefully this will be understandable), which is probably exactly what you were thinking: We'll look at the problem backwards, and first form all possible ending scenarios. The way we do this is to compute the payout from optimal play for all possible endings (all sets of 2 consecutive integers). The payout for optimal play on a list where N is 2 is just the maximum of the two integers. For each of these endings, we will also list the moves that will (in optimal play) carry that list to the end. There are exactly N1 endings, where N is the size of the list (N is even). Now we do the recursive step, moving two moves backwards (one move for each player). In doing so, we will always eliminate exactly two scenarios from our list, and increase the movelist size by two. Associated with each scenario at our new (earlierinthegame) stage, we will have to consider three scenarios later in the game. Here is an example: ABXXXX..XXXXCD If we choose to take A, then our payout is A+min(payout(BX..XC), payout(X..XCD)). If we choose to take D, then our payout is D+min(payout(ABX..X), payout(BX..XC)). All these are easy to compute, especially since in the previous step we computed the payouts of the scenarios ABX..X, BX..XC, and X..XCD (among others). We repeat this inductive step until we are left with only a single scenario. Then we are done! Here is a chart of how I imagine the scenarios coming together. X1 X2 X3 X4 X5 X6 X7 X8 X9 \ \ /\ /\ /\ /\ /\ / / \/ \/ \/ \/ \/ \/ \/ Y1 Y2 Y3 Y4 Y5 Y6 Y7 \ \ /\ /\ /\ / / \/ \/ \/ \/ \/ Z1 Z2 Z3 Z4 Z5 Well, I hope that made some small amount of sense. This takes O(N^{2}) time, and O(N^{2}) memory, if we keep track of only two levels of scenarios at a time.


IP Logged 
Doc, I'm addicted to advice! What should I do?



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13640


Re: Maximal Sums In Optimal Play
« Reply #4 on: Dec 17^{th}, 2002, 1:35pm » 
Quote Modify

on Dec 17^{th}, 2002, 11:34am, James Fingas wrote:towr, Are you sure that would give the the optimal play? I imagine that in a game like this you might have to look a long ways into the future. 
 Well, it's a binarychoice problem, so for 2n numbers in the list you'll have 2^{2n} nodes to look at. Which is doable for n up to at least 1020. After that time may become a big issue. On the other hand it's guaranteed to give the very best answer all the time.. It's a standard/classic answer from AI, next to the derivative alphabeta (In which you don't look at the whole gametree, but only the first part, and use a heuristic to determine the score for the leaves at the end of the subtree. It's the basis for a basic chessalgorithm. If you have the whole gametree you know the score, so it's optimal. In chess that's impossible because the gametree is too large, so you're 'stuck' with alphabeta). For specific problems it's not always the best solution though.. Since time is a big constraint in some cases.. But there are numerous ways to optimize. Quote:What about the following problem: 1; 1; 1; 2000; 1; 1; 1; 1; 1; 1 
 if you can get to 1;2000;1 you win, since your opponent has to take a one, and you get the 2000. And since there's an uneven number of 1's you can thus win easily if you play first.


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13640


Re: Maximal Sums In Optimal Play
« Reply #5 on: Dec 17^{th}, 2002, 1:37pm » 
Quote Modify

That's a nice optimization you got there.. I wonder why I didn't immediately see that most states converge again.. [edit]hmm.. wait a minute.. It's the paths you need, since you sum over the paths.. If you only look at the end you don't know the sum each player has.. There may only be O(N) ends, but there or O(exp(N)) paths leading to those ends..[/edit] [edit2]I hope I'll someday remember not to post when I really ought to be sleeping.. obviously a path is the same whether you're walking it backwards or forwards.. You have an optimal play when you finish the play optimally from every state. Starting at the back that's easy to find..[/edit2]

« Last Edit: Dec 18^{th}, 2002, 12:09am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



