Uncertainty in game trees: expectimax, expectiminimax, and MCTS with UCB1

Sources, conventions and the things that cost marks

• Chance node. Its value is the probability weighted sum of its children, never the maximum and never the minimum. Deck p.5: chance nodes "are like min nodes but the outcome is uncertain", so you "take weighted average (expectation) of children". That single substitution is the whole of the first half of Part 8.
• Sum to one. The arc probabilities leaving one chance node form a distribution, so a single missing arc is determined, not free. That is how X is found in archetype A14.
• Unambiguously. A strict inequality. At the boundary the two children tie, and a tie is not an unambiguous choice, so write Y < 4 and not Y < or = 4.
• UCB1(n) = U(n)/N(n) + C sqrt( log N(Parent(n)) / N(n) ). N(n) is the number of rollouts from n; U(n) is the total utility of those rollouts for Player(Parent(n)). Deck p.37.
• C is inferred, not printed. The deck prints C as a symbol and never gives it a number. C = sqrt(2) with natural logarithms reproduces all thirteen printed UCB labels in the exercise session figure, so this pack uses it and marks it as inferred. In an exam, write the C you used next to your answer; it costs one line and protects the mark.
• The root has no UCB1, because it has no parent and log N(Parent(root)) is undefined. Its visit counter still updates. The published solution says so explicitly, and it is an easy mark to drop.
• Selection stops at the first node that is not fully expanded, which can be a node that already has children. Running on to the deepest leaf is the classic mistake, and it is one of the mistake toggles above.
• At the end of UCT you play the child with the highest N, not the highest win rate and not the highest UCB1 (deck p.38).

"it captures relative uncertainty... when you propagate upwards... the siblings basically are going to ever so slightly increase because there's increased uncertainty now." (Exercise session, T8)

That sentence is the reason for the change column in this visualiser. When a rollout goes through one child, the arithmetic touches three groups of nodes: the visited path, where both terms move; the siblings of every node on that path, where only the exploration term moves, upward, because N(Parent) grew while N(n) stood still; and everyone else, unchanged. The newly added node c counts as a node on the path, so the children the expanded node already had are siblings of c and rise too.

Preloaded problems: Part 8 PDF pp.9, 10 and 29 from FAI_Part8_GameTreesWithUncertainty_25-26.pdf; exercise session 5 sections 3 and 5 from FAI_EXERCISES_Game_Trees.pdf with the published solutions in Oefenzitting05-games.pdf; two constructed problems, both labelled as constructed. Every trace in this file was generated by the engine below and diffed state by state against an independent Python implementation of the same two algorithms.