CS 188 Sp07 Discussion Note Week 6 – Game and Discrete Probability
by Nuttapong Chentanez
Game Playing
Types: Deterministic or Stochastic? One, two or more players? Perfect information?
Want an algorithm for calculating a strategy that recommends optimal move at each state.
Deterministic single player – Just search eg. Freecell, 8-Puzzle, Rubik
Deterministic two players – Minimax Search, pick move that maximize utility against
best play from the opponents
Zero-sum games – One player maximizes the result, the other minimizes it
May be too slow to go all the way to termination, instead search to a limited depth of tree and replace the terminal utilities with an evaluation function. This loses guarantee of optimal play. Depth = Ply, the more ply the better (if utilities is reasonable).
Ideal function: Return the true utility of the position (will be optimal play), only relative ordering is needed.
Alpha-Beta pruning : “If you have an idea which is surely bad, don’t take time to see how truly awful it is” ~ Pat Winston
How to write min-value function?
Stochastic game: This includes chance node, just take expected value on the chance not otherwise, the same as minimax. Correct ordering for utility function does not guarantee optimality anymore.
Exercises:
1. Consider a two-player game featuring a board with four locations, numbered 1 through 4 and arranged in a line. Each player has a single token. Player A starts with his token on space 1, and player B starts with his token on space 4. Player A moves first
The two players take turns moving, and each player must move his token to an open adjacent space in either direction. If the opponent occupies an adjacent space, then a player may jump over the opponent to the next open space if any. (For example, if A is on 3 and B is on 2, then A may move back to 1.) The game ends when one player reaches the opposite end of the board. If player A reaches space 4 first, then the value of the game
is +1; if player B reaches space 1 first, then the value of the game is 1.
a. Draw the complete game tree, using the following conventions:
Write each state as (sA ; sB ) where sA and sB denote the token locations.
Put the terminal states in square boxes, and annotate each with its game value in a circle.
Put loop states (states that already appear on the path to the root) in double square boxes. Since it is not clear how to assign values to loop states, annotate each with a “?" in a circle.
b. Now mark each node with its backed-up minimax value (also in a circle). Explain how you handled the “?" values, and why.
c. Explain why the standard minimax algorithm would fail on this game tree and brie
sketch how you might fix it, drawing on your answer to (b). Does your modified algorithm
give optimal decisions for all games with loops?
2. Here is the complete game tree with chance node for a very simple game. Assume that the leaf nodes are to be evaluated in lefttoright order, and that before a leaf node is evaluated, assume that we know nothing about its value---the range of possible values is -∞ to ∞.
a. Mark the value of all the internal nodes and indicate the best move at the root with an arrow.
b. True/False: Given the values of the first six leaves, the seventh and eighth leaves are irrelevant and need not be evaluated.
c. True/False: Given the values of the first seven leaves, the eighth leaf is irrelevant and need not be evaluated.
d. Now suppose all the leaf node values are known to lie between --2 and 2 inclusive. After evaluating the first two leaves, what range of values can be deduced for the lefthand chance node?
(i) -2 to 2 (ii) 0 to 1 (iii) 0 to 2
e. Circle all the leaves that need not be evaluated under the assumption in d.
Probability
Sample Space – Set of all possible outcome of some experiment
Random Variables – Function that assign a value to each outcome in a sample space
eg. If sample space S is the set of all students in this class,one could define a random variable A, measuring age. If p is a person, A(p) is his/her age.
Event- a set of outcomes that share property you are interested in. eg. For sample space S, J may be the set of juniors. Randomly picking a person may pr may not result in the event that he/she is a junior. P(J) denotes the probability that the event J occurs.
Events can be union, intersects, complement to define new events. Particular conditions on random variables such as A=6’1”, A<7’ can also be considered an event.
Conditional Probability – P(X|Y) = P(XY) / P(Y) is probability that event X occurs given that event Y occurs
Joint Distribution – P(A = a, B = b) denotes probability that A = a and B = b
Marginal Distribution – P(A = a) = P(A = a, B = b) This summation is called “marginalization”
b
Conditional distribution – P(A = a| B = b) gives conditional probability
Important Rules:
Chain Rules: P(X, Y) = P(X|Y)P(Y)
Bayes’s Rule: P(X|Y) = P(Y|X) P(X) / P(Y), very useful in AI
Axioms of probability
1. 0<= P(a) <= 1, for any proposition a,
2. P(true) =1 , P(false) = 1
3. P( a b) = P(a) + P(b) – P(a b)
Exercise:
- Show P(a| a b) = 1
- Consider the problem of dealing 5-card poker hands from a standard deck of 52 cards, assuming that the dealer is fair.
- How many atomic events are there in the joint probability distribution (how many 5-card hands are there)?
- What is the probability of each atomic event?
- What is the probability of dealt a royal straight flush? Four of a kind?
- From this table:
Toothache / ~ Toothache
Catch / ~Catch / Catch / ~Catch
Cavity / 0.108 / 0.012 / 0.072 / 0.008
~Cavity / 0.016 / 0.064 / 0.144 / 0.576
Compute
- P(toothache)
- P(Cavity)
- P(Toothache| cavity)
- P(Cavity| toothache catch)
4. After your yearly checkup, the doctor has bad news and good news. The bad news is that you tested positive for a serious disease and the test is 99% accurate (i.e. The probability of testing positive when you have the disease is 0.99). The good news is that this is a rare disease, striking only 1 in 100,000 people of your age. Why is it a good news that the disease is rare? What is the chance that you actually have the disease?