Game Playing

Zero-sum: one player's loss is the other's gain
Discrete: states and decisions have discrete values
Finite: countable number of states and decisions
Deterministic: not up to chance (like dice rolls or coin flips)
Perfect information: each player can see the complete game state, no simultaneous decisions
Game Theoretic Value (minimax value) = the score of the terminal node that will be reached if both players play optimally

Minimax Algorithm

The minimax algorithm is implemented as a modified version of DFS. Game theoretic value is computed from the bottom up, with the Max player choosing the highest score possible and the Min player choosing the lowest score.

Time Complexity: O(b^m)
Space Complexity: O(bm)

Alpha-Beta Pruning

Alpha-beta is a search algorithm that restricts the set of possible solutions based on the portion of the search tree that has already been seen.

α = the maximum lower bound of possible solutions, the best Max can do

β = the minimum upper bound of possible solutions, the best Min can do