wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Maximal Sums In Optimal Play
        
(Message started by: william wu on Dec 16^th, 2002, 11:32pm)

Title: Maximal Sums In Optimal Play
Post by william wu on Dec 16^th, 2002, 11:32pm

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.

Title: Re: Maximal Sums In Optimal Play
Post by towr on Dec 17^th, 2002, 1:18am

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)

Title: Re: Maximal Sums In Optimal Play
Post by James Fingas on Dec 17^th, 2002, 11:34am

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...

Title: Re: Maximal Sums In Optimal Play
Post by James Fingas on Dec 17^th, 2002, 1:27pm

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(N²) time, and O(N²) memory, if we keep track of only two levels of scenarios at a time.

Title: Re: Maximal Sums In Optimal Play
Post by towr on Dec 17^th, 2002, 1:35pm

on 12/17/02 at 11:34:04, 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 2²ⁿ 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.

Title: Re: Maximal Sums In Optimal Play
Post by towr on Dec 17^th, 2002, 1:37pm

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]

Title: Re: Maximal Sums In Optimal Play
Post by william wu on Jan 31^st, 2003, 5:33am

Decided to move this to hard section since it doesn't really require a cs background.