The Topology of Choice
Branching Factor, Information Sets, and Equilibrium Selection in Non-Cooperative Games
Permanent Identifier: https://doi.org/10.5281/zenodo.1089202
Scholarly Abstract
We formalize the mathematical topology of decision spaces across sequential and simultaneous games. By examining the transition from discrete finite trees (Tic-Tac-Toe, Chess) to continuous and imperfect-information state spaces (Poker, StarCraft), we analyze how heuristic evaluation and deep reinforcement learning approximate Nash equilibria in computationally intractable game graphs.
1. Extensive-Form Trees & Information Partitions
In classical non-cooperative game theory, a game in extensive form is defined as a directed tree $T = (V, E)$ rooted at $v_0$. The vertex set $V$ is partitioned into player decision nodes $V_i$, chance nodes $V_c$, and terminal evaluation leaves $Z$. For games with imperfect information (e.g. Kuhn Poker or Kriegspiel), decision nodes are grouped into equivalence classes called information sets $I_{i,j}$, representing states indistinguishable to player $i$.
2. The Shannon Boundary and the Curse of Branching
Claude Shannon famously estimated the game-tree complexity of Chess at $10^{123}$ moves (the Shannon Number), driven by an average branching factor $b \approx 35$ over $d \approx 80$ plies. For Go ($b \approx 250, d \approx 150$), tree size reaches $10^{360}$, rendering traditional alpha-beta pruning completely obsolete.
\text{Leaves}(T) \approx b^d\text{AlphaBeta Complexity} = \mathcal{O}\left(b^{d/2}\right)