CSCE 315 Lecture 17

« previous | Wednesday, February 29, 2012 | next »

Games with Chance

• Minimax trees work well when game is deterministic
• Chance nodes included in tree to evaluate possible chances

For each move, "roll a die" and determine every possible move after each possible result.

Choosing a Maximum

• Evaluate moves from ALL chance nodes
• Find Expected Value for that move
• Choose largest expected value (Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle E(x) = \sum x P(x)} ) to store at each chance node

Other approaches

• Maximize worst case value and avoid catastrophe
• Give weight if a very good position is available
• simulation of large range of states
• be competent, not always win

Time explodes to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(b^m n^m)} where $b$ is branching ratio, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} is number of chances, and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m} is tree depth.

State Diagrams

List of possible states one can reach in the game (nodes)

Describe ways of moving from one state to another (edges)

Often cyclic and complex, but try to hide those to prevent infinite loops

Exploring State Diagrams

Look for solutions using Breadth-First Search and Depth-First Search.

Iterative deepening search (DFS 1 level deep, then 2 levels (repeat first level), 3 levels, etc.)

Use bidirectional search (start from end and meet halfway; like a maze)

Order nodes based on distance to goal node.

A* Algorithm

Avoid expanding paths that are already expensive:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n) = g(n) + h(n)} , where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(n)} is cost from start to node Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle h(n)} is estimate of remaining distance to goal.

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle h(n)} should never overestimate the actual cost of the best solution

Apply best-first search with lowest value of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} ; value of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} should only increase.