# AI Game Playing

This note is about the game playing chapters of Udacity AI Nanodegree

#### Type of AI problems

- Fully Observable vs Partially Observable
- Deterministic vs Stochastic
- Discrete vs Continuous
- Benign (only one person is taking action) vs Adversarial

#### Minimax Algorithm

- Choose a winning strategy. In an isolation game, the winning strategy can be maximizing the possible moves at each level of the game tree.
- At each level of the game tree, it is assumed that player will choose the branch that maximizes the benefits (opponent will choose a branch to minimize the effect of the winning strategy)

#### Branching Factor

- how many branches each node will have on average

#### Depth-Limited Search

- Using the branch factor and the limitation of the number of nodes can be searched every turn, we can determine how deep the search can go

#### Quiescent Search

- If the decision varies a lot at two neighbor levels, that means a critical decision is made between those two levels
- Thus, we will use quiescent search to search deeper

#### Iterative Deepening

- After finishing searching depth N, then researching the tree with depth N+1
- Since time complexity is dominated by the last level search, iterative deepening will not increase time complexity compared to regular search

#### Horizon Effect

- Choices that are obvious to human beings might not be obvious for AI

#### Alpha Beta Pruning

- adversarial search algorithm, which seeks to decrease the number of nodes in the search tree.
- Improve efficiency
- It does not work well with multi-players

#### Thad’s Asides

- AI = Clever Solutions to Exponential Problems