English subtitles

← Improving Optimal - Design of Computer Programs

Get Embed Code
1 Language

Showing Revision 3 created 05/25/2016 by Udacity Robot.

  1. This homework is about improving on the optimal strategy function.
  2. It may seem like that's impossible.
  3. How could we be better than optimal?
  4. And in fact, we can't in the sense that we can't come up with a function
  5. that produces better results, but we can come up with a function that's faster.
  6. One thing that bothered me about the optimal function
  7. is a big part of it was defining this probability of winning from a given state.
  8. And if we give it some random state like, say, 0, 7, 13, 19,
  9. it turns out that the value of this state--whatever that is--
  10. is exactly equal to the state where the other player's turn is to play.
  11. So here Player 0 goes first, here Player 1 goes first,
  12. but the probability of winning for an optimal function is symmetric
  13. because we're assuming that the opponent is also playing optimally.
  14. So if 0 goes first against an optimal opponent or 1 goes first against the optimal opponent,
  15. that probability of winning is going to be exactly the same.
  16. But the way we define Pwin, it computes both of these and stores both of these.
  17. That's wasteful.
  18. So in this exercise, we're going to get rid of that waste. How wasteful is it?
  19. I'm going to do a timed call for the Pwin function, and I'm going to pass it a state
  20. and pass it this starting state.
  21. And so the first time you pass it the starting state, it has to do the complete computation
  22. to get all the way to the end.
  23. So that's going to be a lot of work, and it turns out that it takes about 他 of a second
  24. to do that work when the goal is 40, and the probability that's returned is 54%.
  25. So there's a slight advantage--over 50%--for going first.
  26. That tells us about the time. How about the space?
  27. I can look at the cache that the memo function has computed.
  28. It stored it at Pwin.cache.
  29. I can compute that length, and it works out to 86,000 entries.
  30. So I should be able to cut this time down, and I should be able to cut this size of the cache
  31. roughly in half by working more efficiently and having a better version of Pwin.
  32. We're going to do that by defining a function Pwin2
  33. which is going to have the same signature as Pwin.
  34. It performs the same function, only it's going to do it a little bit better.
  35. And the way it works is it breaks out this state, throws away the player to play
  36. because we know it's symmetric--we don't need that--
  37. and then it calls Pwin3, which we name because it takes 3 arguments--
  38. the only ones that matter--my score, your score, and the pending score,
  39. and that's what I want you to do.
  40. Go ahead and write the code for Pwin3 that will efficiently do this computation.
  41. Make sure here that you don't get stuck in an infinite loop.
  42. Take care when the value of pending is 0. That's a special case to deal with.
  43. Remember that the probability that I win from a position
  44. is always 1 minus the probability that my opponent wins.
  45. You may need that in your definition.