In a game-move tree with 3 legal moves per position, what does searching one ply deeper cost?
answer
- Write the count beside each ply
- 1, 3, 9, 27 going down
- Where do most of the nodes live?
- One more ply multiplies, it does not add
- Branching factor sits in the exponent's base
basics
~20 sOne extra ply multiplies the whole search by about three: each position at the current frontier fans out into three more. Depth-limited search cost is dominated by the deepest level, so deepening is a multiplication, never an increment.
solid answer
~50 sDraw the tree: 1 root position, 3 at ply 1, 9 at ply 2, 27 at ply 3 — the frontier is 3^d positions at depth d. Adding one ply replaces that frontier with a new one three times larger, so total work triples. Two consequences follow from the drawing. First, the deepest level holds about two-thirds of all nodes, so the search is essentially its leaves and micro-optimising the root does nothing. Second, the branching factor is the more powerful lever: cutting candidate moves from 3 to 2 at depth 10 shrinks the frontier from roughly 59,000 positions to about 1,000 — a factor of nearly 60, far more than any per-node speedup buys you. That is why real search work goes into pruning moves and capping depth rather than making each position evaluation faster.
go deeper
Be able to write the per-ply counts 1, 3, 9, 27 and say that the count at depth d is the branching factor to the power d. Know that deepening multiplies the work.
Explain that cost compounds branching across depth, that the deepest ply holds most of the nodes, and why a per-node speedup cannot compete with removing a branch.
Show the operational judgment: pick the depth cap and the pruning rules as the real levers, and state honestly when a varying fan-out makes the estimate an order of magnitude rather than a count.
Own the budget conversation — given a fixed latency budget per move, decide the depth the product can afford, and what quality is traded away when the branching factor grows on harder positions.
## The tree you draw Model a turn-based game where each position offers three candidate moves and you explore every move sequence to a fixed depth d. The recursion tree is uniform: one root, three children per node, all the way down. | ply | positions at that ply | |---|---| | 0 | 1 | | 1 | 3 | | 2 | 9 | | 3 | 27 | | 4 | 81 | | d | 3^d | Two readings come straight off the table. **Deepening multiplies.** Going from depth 4 to depth 5 does not add 81 positions; it adds 243, and every subsequent ply multiplies again by three. "Just one more level" is the most expensive sentence in search work. **The leaves are the search.** Summing the plies above depth d gives roughly half of 3^d, so the deepest level holds about two-thirds of every node in the tree. Whatever you do at the frontier is what your search costs. Conversely, cutting the depth limit by one removes two-thirds of the work in a single decision — which is why depth limiting is the first control anyone reaches for. ## Branching factor beats constant factors Because the frontier is branching-factor-to-the-depth, the branching factor sits in the base of an exponent while a per-node speedup sits in the constant out front. They are not comparable levers. At depth 10: three moves per position gives 59,049 leaf positions; two moves gives 1,024. Eliminating one candidate move per position cut the work by a factor of about 58. Making each position evaluation twice as fast cuts it by a factor of two. This asymmetry is the whole reason move ordering, dominated-move elimination and pruning rules exist: they attack the base of the exponent. ## Depth and breadth are separate questions When you draw any recursion tree, take two independent readings: - **Branching factor** — how many children per node. This sets how fast the tree widens per level. - **Depth** — how many levels before the base case. Here it is a hard limit you chose; in argument-shrinking recursions it is set by how fast the argument shrinks. The cost is roughly the branching factor compounded across the depth. Both readings are needed: a tree with a huge branching factor and depth 2 is trivial, and a tree of depth 40 with one child per node is trivial too. Only their combination is expensive. Candidates who report only one of the two — "it's three-way branching, so it's expensive" — have not actually read the tree. ## An important non-cost The drawing shows every position that will ever be visited, and there can be tens of thousands of them, but a depth-first exploration is only ever partway down one path at a time. The picture is a map of the work, not a snapshot of what is held at any instant — a distinction worth stating explicitly so nobody confuses the number of nodes with the amount of memory in flight. ## Common traps - **Treating one more ply as a small increment.** It multiplies the frontier by the branching factor. - **Optimising near the root.** Two-thirds of the nodes are at the bottom; the root's cost is noise. - **Reporting branching without depth, or depth without branching.** Neither number alone predicts the cost. - **Assuming a uniform branching factor when the real one varies.** If some positions offer six moves and some offer one, the effective branching factor is somewhere in between, and the drawing is an estimate — say so rather than quoting a false precision. - **Confusing the node count with memory.** The drawn tree is the work performed over time, not data held simultaneously.
- Which helps more at depth 10: halving the cost of evaluating a position, or eliminating one of the three candidate moves?Eliminating a move, by a wide margin. Dropping from three moves to two takes the frontier at depth 10 from about 59,000 positions to about 1,000 — nearly a 60-fold reduction — while halving the per-position cost buys a factor of two. The branching factor sits in the base of an exponent; per-node cost is only a constant multiplier.
- Roughly what share of the nodes sit on the deepest ply, and why does that matter?About two-thirds, since every ply is three times the one above and the levels above sum to roughly half the last one. It matters because it tells you where to spend effort: the frontier is the search. Trimming the depth limit by one removes most of the work, while shaving cost off the shallow plies changes almost nothing.
- The real game has a varying number of legal moves per position. Does the reading still hold?Yes, as an estimate. You reason with an effective average branching factor and the shape of the conclusion is unchanged: cost still compounds across depth, deepening still multiplies, and leaves still dominate. What you lose is precision, so quote it as an order of magnitude rather than a count, and say out loud that the figure assumes an average fan-out.
Adding a ply is not one more step down the corridor; it is discovering that every door you had already opened leads to three more.
saying these in an interview costs you the question
- Treats one more ply as a small additive cost
- Quotes branching factor without depth, or the reverse
- Optimises per-node cost to fight exponential growth
- Assumes work is spread evenly across the levels
- Confuses total nodes visited with memory held at once