Sheela
Sheela
Home
Add
Questions
Thinkers
Claims
People
Concepts
Jargon
Sources
Health
Predictions
Collections
Domain Landscape
Contribute
Review
Dedup
Topic requests
Settings
Help

← Jargon

Jargoncomputer science· 2 claims· 2 episodes

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