game tree
The branching tree of all possible move sequences in a game, which can be traversed with small memory to determine optimal play.
As defined in 99 | Scott Aaronson on Complexity, Computation, and Quantum Gravity
Where it comes up · 2
- Dwarkesh Patel Podcast - Eric Jang – Building AlphaGo from scratch1 claim
- 99 | Scott Aaronson on Complexity, Computation, and Quantum Gravity1 claim
Most important claims · 2 of 2Search all claims for “game tree” →
- AlphaGo's core conceptual breakthrough was using neural networks to make Go's search problem tractable by shrinking both the breadth (a ~361 branching factor) and depth (~300 moves) of an otherwise astronomically large game tree (on the order of 361^300, more than the atoms in the universe), a problem long thought intractable this century.Dwarkesh Patel Podcast - Eric Jang – Building AlphaGo from scratch
- If polynomial time equaled polynomial space, then perfectly playing two-player games of perfect information like chess or Go — which can be solved with small memory by traversing the exponentially large game tree — would also become solvable in a small amount of time, yielding a super-efficient algorithm to play any such game perfectly, which is why we doubt P equals PSPACE.99 | Scott Aaronson on Complexity, Computation, and Quantum Gravity