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 ($E(x)=\sum xP(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 $O(b^{m}n^{m})$ where $b$ is branching ratio, $n$ is number of chances, and $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:

$f(n)=g(n)+h(n)$, where $g(n)$ is cost from start to node $n$ and $h(n)$ is estimate of remaining distance to goal.

$h(n)$ should never overestimate the actual cost of the best solution

Apply best-first search with lowest value of $f$; value of $f$ should only increase.