Author |
Topic: Maximal Sums In Optimal Play (Read 3547 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Maximal Sums In Optimal Play
« on: Dec 16th, 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 16th, 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: 13730
|
|
Re: Maximal Sums In Optimal Play
« Reply #1 on: Dec 17th, 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 17th, 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 17th, 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 N-1 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 move-list size by two. Associated with each scenario at our new (earlier-in-the-game) 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(N2) time, and O(N2) 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: 13730
|
|
Re: Maximal Sums In Optimal Play
« Reply #4 on: Dec 17th, 2002, 1:35pm » |
Quote Modify
|
on Dec 17th, 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 binary-choice problem, so for 2n numbers in the list you'll have 22n nodes to look at. Which is doable for n up to at least 10-20. 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 alpha-beta (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 chess-algorithm. 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 alpha-beta).
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: 13730
|
|
Re: Maximal Sums In Optimal Play
« Reply #5 on: Dec 17th, 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 18th, 2002, 12:09am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print