Tip:
Highlight text to annotate it
X
This unit is about probability,
which is a tool for dealing with uncertainty.
Once you understand probability,
you'll be able to tackle a much broader range of problems than you could
with programs that don't understand probability.
Often when we have problems with uncertainty, we're dealing with search problems.
Recall, in a search problem, we are in a current state.
There are other states that we can transition into,
and we're trying to achieve some goal,
but we can't do it all in one step.
We have to paste together a sequence of steps.
In doing that, we're building up a search frontier that we're continuing to explore from.
Now, uncertainty can come into play in two ways.
One, we can be uncertain about the current state.
Rather than knowing exactly where we are,
it may be that we start off in one of four possible states and
all we know is that we're somewhere in there, but we're not sure exactly where we are.
The other place uncertainty can come in is when we apply an action,
say this action here--action A--it may be that we don't get to
one specific state but, rather, we're uncertain as to what the action will do,
and we might end up in this state or this state or this state
instead of the one that we were aiming at.
And so we'll see techniques for dealing with both of these types of uncertainty.
Now, one place where people are used to dealing with uncertainty
is in playing games that employ dice.
And that's what we're going to deal with.
In particular, we're going to play a dice game which is called Pig.
I don't know why the game is called Pig.
I can guarantee no porcine creatures were harmed in the creation of this unit.
Here's how the game works.
There are two players, although you could play with more.
The players take turns, and on his turn a player has the option
to roll the dice--a single die--as often as he wants or to hold--to stop rolling.
And the object of the game is to score a certain number of points.
We're going to say 50 points; 100 is more common, but 50 will be easier
on the Udacity servers in terms of the amount of computation required.
And so it's my turn, and we have a score.
So here's a scoreboard; we'll have players with the imaginative names
of player 0 and player 1.
And the score starts off 0 to 0.
Now there's another part of the scoreboard that is not part of the player's score.
We'll call that the pending score.
Let's say it's my turn.
I pick up the die, I roll it, and let's say I get a 5.
Then 5 goes into the pending score,
but I don't score any points yet.
Now it's my turn again.
Do I roll or do I hold--stop rolling?
Let's say I want to roll again.
This time I get a 2, so I add 2 to the pending score; I get 7.
Let's say I roll again.
I'm lucky. I get a 6. I add 6 to the pending; I get 13.
And I'm going great, so I roll again, and this time I get a 1.
And a 1 is special.
A 1 is called a pig out, and when you roll a pig out it means
you lose all the pending points, and for your hand you score
not this total, but just the 1.
So my score would be just the 1.
Now the other player, player number 1, goes.
Let's say player number 1 says, "I'm going to roll," gets a 3.
"I'm going to roll again," gets a 4.
"I'm going to roll again," gets a 5.
So now we have 12 in the pending, and now player number 1 says,
"I think I've had enough; I'm going to hold,"
and that means we take these points from the pending, the 12 points,
put them up on the board for player 1's score.
And now player 1's turn ends, and it's player 0's turn.
So your turn continues until you either hold or pig out,
and your score for the turn is the sum of your rolls, if you didn't pig out,
if you decided to hold, and the score is just 1 if you pigged out.
And you keep on taking turns until somebody reaches the target--here, 50.
So that's how the game of Pig works.
Now let's go to try to describe the game in a form that we can program.