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