AI Game Playing – Zeesun – Medium

AI Game Playing – Zeesun – Medium

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

Read full article from AI Game Playing – Zeesun – Medium