
Title:
Improving Optimal  Design of Computer Programs

Description:

This homework is about improving on the optimal strategy function.

It may seem like that's impossible.

How could we be better than optimal?

And in fact, we can't in the sense that we can't come up with a function

that produces better results, but we can come up with a function that's faster.

One thing that bothered me about the optimal function

is a big part of it was defining this probability of winning from a given state.

And if we give it some random state like, say, 0, 7, 13, 19,

it turns out that the value of this statewhatever that is

is exactly equal to the state where the other player's turn is to play.

So here Player 0 goes first, here Player 1 goes first,

but the probability of winning for an optimal function is symmetric

because we're assuming that the opponent is also playing optimally.

So if 0 goes first against an optimal opponent or 1 goes first against the optimal opponent,

that probability of winning is going to be exactly the same.

But the way we define Pwin, it computes both of these and stores both of these.

That's wasteful.

So in this exercise, we're going to get rid of that waste. How wasteful is it?

I'm going to do a timed call for the Pwin function, and I'm going to pass it a state

and pass it this starting state.

And so the first time you pass it the starting state, it has to do the complete computation

to get all the way to the end.

So that's going to be a lot of work, and it turns out that it takes about 他 of a second

to do that work when the goal is 40, and the probability that's returned is 54%.

So there's a slight advantageover 50%for going first.

That tells us about the time. How about the space?

I can look at the cache that the memo function has computed.

It stored it at Pwin.cache.

I can compute that length, and it works out to 86,000 entries.

So I should be able to cut this time down, and I should be able to cut this size of the cache

roughly in half by working more efficiently and having a better version of Pwin.

We're going to do that by defining a function Pwin2

which is going to have the same signature as Pwin.

It performs the same function, only it's going to do it a little bit better.

And the way it works is it breaks out this state, throws away the player to play

because we know it's symmetricwe don't need that

and then it calls Pwin3, which we name because it takes 3 arguments

the only ones that mattermy score, your score, and the pending score,

and that's what I want you to do.

Go ahead and write the code for Pwin3 that will efficiently do this computation.

Make sure here that you don't get stuck in an infinite loop.

Take care when the value of pending is 0. That's a special case to deal with.

Remember that the probability that I win from a position

is always 1 minus the probability that my opponent wins.

You may need that in your definition.