Combinatorial Games: Introduction & Examples | Game Theory Course

Added:

Classical Game Theory and Bounded Rationality

While Combinatorial Game Theory (CGT) offers deterministic mathematical solutions for two-player games of perfect information (like Nim and Hex), it has significant limitations in broader strategic contexts. Critics point out that CGT fails to address real-world scenarios characterized by uncertainty, imperfect information, simultaneous moves, and cooperation, which are instead modeled by Classical Game Theory using concepts like Nash Equilibria. Furthermore, from a cognitive and computational standpoint, theories of Bounded Rationality argue that human players (and often computers) cannot compute the vast decision trees required by CGT. Instead, real-world decision-making relies on heuristics, probabilistic reasoning, and behavioral economics rather than perfect mathematical optimization.

Basic concepts of set theory and propositional logic, including binary states and truth values.
Elementary discrete mathematics, specifically mathematical induction and recursive relations.
The conceptual distinction between games of perfect information and games of chance or hidden information.
Fundamentals of graph theory, particularly how to represent sequential states using directed acyclic graphs and game trees.
The Sprague-Grundy Theorem and the algebraic analysis of impartial games using nim-sums.
Conway's Combinatorial Game Theory framework, including partisan games and the definition of surreal numbers.
Mathematical modeling of complex partisan games such as Hackenbush, Domineering, and Chess.
Computational implementation of search algorithms, including the Minimax algorithm and Alpha-Beta pruning for AI game-playing.
14.1K views95likes24:22@IITBombayJulyOriginal Release: 2019-07-27

Combinatorial games are sequential, deterministic games with perfect information where players take turns making moves, and the last player to make a move typically wins (normal play); unlike economic games where decisions are simultaneous and payoffs depend on others' choices, combinatorial games include examples like tic-tac-toe, dominoes, chomp, and hex, where players develop winning strategies through backward induction and analysis of game states.