Computing optimal play for the greedy coins game, part 2

I want to explain in more detail how we can think about computing the best possible score for Alice in the greedy coins game, assuming best play on the part of both players. I glossed over this too quickly in my previous post.

Recall that we were using this example game:

We can draw out the tree of all possible sequences of moves, like this:

Now, let’s work from the bottom up, computing the best score for Alice at each point. First, the bottom row of the tree corresponds to the point when there is only a single coin left, and it is Bob’s turn. Bob has no choice, and Alice can’t get any more coins. In general, we will put Alice’s best score in a blue square next to each node. Since Alice can’t get any coins at this point in the game, we put a zero next to each game on the bottom row:

Now consider the next row up. In these games, it is Alice’s turn. She wants to maximize her score, so she should pick the coin which gives her the biggest total. Her total will consist of the value of the coin plus the zero she will get from that point on—that is, just the value of the coin.

Notice how in each case we have highlighted Alice’s best move in blue, and written Alice’s best score from this point on in the blue square next to each game. So, for example, in the leftmost game, where only 1 and 2 are left, Alice should take the 2, and this will give her a total score of 2.

Considering the next row up, it will be Bob’s turn in these games: of course, he will play so as to minimize Alice’s total score (which is the same as maximizing his score, since the scores always add up to the total value of all the coins). So he should look at the scores Alice will get (i.e. the numbers in the little blue squares) and pick the move that will lead to the smallest number for Alice.

Notice how in the left-hand game (124), Bob’s best move is highlighted in green: he should take the 4, since this will lead to a game in which Alice will get a total of 2, which is better than his other choice, which will lead to Alice getting 4. In the right-hand game, it doesn’t matter what Bob picks: Alice will get 4 in either case. So neither move is highlighted for Bob.

We have again written the best score Alice can expect to get from this point on in a little blue square to the right of each game. From the discussion above we can see that for this row (and any even row in general) this will just be the minimum of Alice’s score values from the level below.

Finally, considering the top node, we can analyze Alice’s choices: she can either take the 3 on the right, which leads to a game in which we know she will get 2 more, for a total of 5; or she can take the 1 on the left, which leads to a game in which she will get 4 more, again for a total of 5. So in this case it doesn’t matter which move Alice picks. We write the total 5 in a little blue square to the right of the game, and highlight neither move since either one is optimal. The final analyzed tree looks like this:

Advertisements

About Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in computation, games, recursion and tagged , , , , , , , , , . Bookmark the permalink.

One Response to Computing optimal play for the greedy coins game, part 2

  1. Pingback: Computing optimal play for the greedy coins game, part 3 | The Math Less Traveled

Leave a reply. You can include LaTeX $latex like this$. Note you have to literally write 'latex' after the first dollar sign!

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s