English subtitles

← Doubling Pigs - Design of Computer Programs

Get Embed Code
1 Language

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

  1. This exercise involves doubling in the games of Pig. What is doubling?
  2. If you're familiar with the game of backgammon, which is a gambling game with dice,
  3. doubling is a way to end the game early.
  4. And the idea is that when we start out, each game is worth 1 point.
  5. But in the course of the game, if 1 player is winning,
  6. then he can propose to double the stakes of the game
  7. so that it's worth 2 points--that it, say, costs $2 that the winner wins from the loser
  8. rather than $1 or âŹ2 or whatever currency we're playing with.
  9. Then when the player makes that move of doubling,
  10. then the opponent has a choice.
  11. He must immediately either accept or decline.
  12. If the opponent accepts, then we play the game and it's worth 2 points.
  13. If the opponent declines, then the proposer of the double immediately wins 1
  14. and the game is over.
  15. In backgammon, doubling can go on infinitely from 1 to 2 to 4 to 8 to 16 and so on.
  16. For Pig we're only going to allow 1 round of doubling.
  17. So the game is going to start off being worth 1 point
  18. and can go up to 2 points but no more than that.
  19. So we're going to define a whole new game.
  20. The top level function will be called playpigd--d for double--
  21. and all our functions will end in that d.
  22. A state in this game will be just like before, with 1 new value for the doubling amount.
  23. So a state will have the player to play, the score for me, the score for you,
  24. the pending score, and an extra field for the double.
  25. And the double can either be 1 or 2--
  26. and we said we're not going to allow it to go higher than that--
  27. or it can be the string double.
  28. It takes that value only at 1 point during the game.
  29. When the first player proposes a double and then the second player has the choice
  30. of accept or decline, that player will see double in the state field
  31. and then will have to reply.
  32. So what I want you to do is write these 2 functions: pigactionsd,
  33. which takes a state and returns all the legal actions from that state,
  34. and here's the description of what they can be;
  35. and I want you to define some strategy function, strategy_d,
  36. that gives a state which is a state in the doubling Pig game
  37. and returns a good action.
  38. What do I mean by good?
  39. It's got to be better than this strategy function, hold20d,
  40. which holds at 20 and always accepts when offers a double,
  41. never doubles, and holds it at 20 or rolls otherwise.
  42. You should define a strategy that's better than that.
  43. If you want, you can try to define the optimal strategy, but you're not required to do that.
  44. I have defined for you the main function, playpigd.
  45. It's similar to what we had before,
  46. except the result that's returned is 2 values now--
  47. both the winning strategy and the value of the game, which will be either 1 or 2.
  48. And then the other difference is we got rid of the roll and hold functions,
  49. and now we replaced it with just 1 do function, which takes an action and a state
  50. and it passes along the die rolls and then does that action.
  51. So this is really the definition of how the game works
  52. where the actions can be rolling, holding, doubling, declining, and accepting.
  53. Then die rolls are as before.
  54. We define the clueless function, which just takes a random choice
  55. from among the legal actions.
  56. You should definitely be able to beat that,
  57. but you've also got to be able to beat the whole 20 strategy.