Games e ia

Disponível somente no TrabalhosFeitos
  • Páginas : 13 (3018 palavras )
  • Download(s) : 0
  • Publicado : 22 de abril de 2013
Ler documento completo
Amostra do texto
Help

Outline
Markov decision processes Definition Policy evaluation in MDPs Policy optimization in MDPs Value iteration Policy iteration Examples Games Policy evaluation in games Policy optimization in games Minimax Alpha­beta pruning Evaluation functions

Games: non­deterministic state space models
Markov decision processes Definition Policy evaluation in MDPs Policy optimization in MDPsValue iteration Policy iteration Examples Games Policy evaluation in games Policy optimization in games Minimax Alpha­beta pruning Evaluation functions
CS221: Artificial Intelligence (Autumn 2012) ­ Percy Liang

 

CS221: Artificial Intelligence (Autumn 2012) ­ Percy Liang

1

So far: deterministic state space models
Model:  F B
2 5 1

The real worldThe dynamics of the real world are not known... Robotics: decide where to move, but actuators can fail, hit unseen obstacles, etc.

S

A

3

D 2

1

C 3 2 7 E

G

Resource allocation: decide what to produce, don't know the customer demand for various products Agriculture: decide what to plant, but don't know weather and thus crop yield How to maximize utility in these situations?

When agent takes action  in state  , will end up in state   deterministically.

CS221: Artificial Intelligence (Autumn 2012) ­ Percy Liang

2

 

CS221: Artificial Intelligence (Autumn 2012) ­ Percy Liang

3

Game 1
You choose stay or quit. If quit, you get   and we stop. If stay, you get  . Then I roll a 6­sided dice. If dice results in 1 or 2, we stop. Otherwise, you get to play again.Suppose utility is money. Let's play! Clear Outcome: ­ Stay Quit Utility: 0

Computing the optimal solution
in stay: $4 (2/3) quit: $10 (1/3) ?

out

Let   be the expected utility if we always take action   (in state "in").

+

CS221: Artificial Intelligence (Autumn 2012) ­ Percy Liang

4

 

CS221: Artificial Intelligence (Autumn 2012) ­ Percy Liang

5

Markov property and statesWhat about strategy [stay, quit]? Expected utility:  Better than quit, but worse than always stay Can more complicated strategies do better in this game? Nope. Why? Important: optimal action only depends on current state (dice rolls are independent). Clear
+

Game 2
For  You choose stay or quit. If quit, you get   and we stop. If stay, you get  . Then I roll   6­sided die. If any dice results in 1 or 2, we stop.Otherwise, you play again. Suppose utility is money. Let's play! Stay Quit Utility: 0

Outcome: ­

CS221: Artificial Intelligence (Autumn 2012) ­ Percy Liang

6

 

CS221: Artificial Intelligence (Autumn 2012) ­ Percy Liang

7

Outline
Markov decision processes Definition Policy evaluation in MDPs Policy optimization in MDPs Value iteration Policy iteration Examples GamesPolicy evaluation in games Policy optimization in games Minimax Alpha­beta pruning Evaluation functions
CS221: Artificial Intelligence (Autumn 2012) ­ Percy Liang 8

Markov decision process
Definition: Markov decision process : the set of states : possible actions from state  : probability of   if take action   in state  : reward for taking action   in state  + : starting state : whether to stop + Key difference:Deterministic state space model:  Markov decision process: 

+

 

CS221: Artificial Intelligence (Autumn 2012) ­ Percy Liang

9

Transition distribution
: probability of   if take action   in state  Properties of probability distributions:

What does an agent output?
Deterministic state space model: Agent outputs a fixed sequence of actions  .Action sequence defines one path through state space graph. Utility:   (sum of edge rewards on that path) Markov decision process: Agent outputs a policy (might need action from any state).
Definition: Policy A policy   maps a state   to an action  .

Example:

Applying the policy yields a random path. Utility:   (sum of edge rewards on that path) Expected utility? Need to consider all possible paths......
tracking img