Static Evaluation, Alpha-Beta Pruning, and Monte Carlo Tree Search

This module completes the game-playing story. First, we find out where all those numbers in the minimax game trees actually come from — the static evaluation function and the static evaluation value. Then we look at alpha-beta pruning, which is the same minimax algorithm with a small smart addition that skips parts of the tree without changing the answer. Then we meet Monte Carlo Tree Search, a probabilistic search algorithm that uses simulations to guide which parts of the game tree to grow. The session ends with a complete walkthrough of the mid-semester exam: format, syllabus, marking, and study advice.

The path of this session is easy to keep track of if you hold on to one thread: every tree diagram from the last session was full of numbers, and every one of those numbers was a static evaluation value computed from a board by a static evaluation function. Once you know how those numbers are produced (Section 8.1), you can ask the question that drives Section 8.2: does the search really need to look at every one of them? Alpha-beta pruning answers "no". Section 8.3 then asks an even bigger question: what if we do not want to evaluate every board at all, because each evaluation is too slow — and Monte Carlo Tree Search answers that with simulation and statistics. The last section switches from the algorithms to the exam itself, so the same material doubles as your revision checklist for the mid-semester paper.

8.1 Static Evaluation Functions and Values

8.1.1 Recap: Adversarial Search and Minimax

The last session finished the neuroevolution line (NEAT, Deep NEAT, and CoDeepNEAT) and then opened up game playing, or adversarial search. In the problems we solved before, the problem-solving agent was alone in the environment. In games, there are usually two or more players, and the situation gets interesting: in adversarial search one person's gain is another person's loss. These are zero-sum games — the total payoff to both players adds to zero, so a win for me is exactly a loss for you. The key point we made: each agent does not just ask "which action gets me closer to my goal"; it also asks "what will my opponent do to reduce my chance of success, and how do I respond to that?" That second question is what adversarial search is really about.

The most important algorithm from that session is minimax. Minimax never promised to take you to the best reward or the best utility. Its guarantee is narrower and more defensive: it will never take you to the worst possible outcome. If you attend every class, I do not promise you will top the course — but I do promise you will not fail the course. That is exactly minimax's mindset: it will not necessarily find the best path, but it guarantees you will not end up in the worst state. Keep this promise straight, because a later question in this session turns on it: minimax is a "not the worst" guarantee, not a "definitely the best" one.

We propagated values through the trees using a traversal. Which traversal was it? Depth-first search, which in this tree setting is the in-order traversal: go all the way down to the left end, then start filling values up, and complete the whole tree that way. We solved several examples this way and stopped at one open question: why do we not search the whole tree? For small games like tic-tac-toe, a complete search is still possible. For large games like chess, the game tree is enormous — the branching factor is about 35 and games can run roughly 80 ply deep, which means far more positions than any machine could ever visit. We simply cannot afford to predict "if I do this move, the opponent will do this move, and so on" to full depth. Instead we use a depth limit (only a few depths) plus a static evaluation function, and that is where we had stopped.

One clarification about the numbers in all those tree diagrams: the values written at the nodes are not the final utility. Final utility just says who is winning the game — in zero-sum games it is one of a few outcomes, for example win/lose/draw as $+1/0/-1$ or a similar scheme. The intermediate values are static evaluation values, and in the entire last session we took those values for granted and never asked where they come from. This session answers exactly that question.

8.1.2 What the Static Evaluation Function Is

A static evaluation function estimates the utility of a non-terminal game state. That small sentence carries a lot of weight, so unpack it. A terminal state is the goal state — the game is over. For tic-tac-toe, the goal states are: X has won, O has won, or the whole board is filled and nobody has won. For all the intermediate, non-terminal states — "I have just started playing, there are many moves possible for me" — we want an estimate of the utility. The static evaluation function provides that estimate.

Why "static"? Because it evaluates the board position as it is, without searching further. It does not look ahead; it looks at the current configuration and scores it. That score answers the question "among the options available to me, which one is most promising?" A promising move is one that leads to a better utility for me — or, equivalently, one that will not lead my opponent to a better utility. The static evaluation value is more like a reward or a heuristic: how good is this particular board for me, right now.

The utility is the final thing you get when the game ends: $+1$ if you won, $-1$ if you lost, $0$ if the game was a draw. In zero-sum games like chess and tic-tac-toe, exactly these three results are possible — you win, you lose, or it is a draw. Utility is what you get at the end; the static evaluation value is what you compute at every intermediate stage.

8.1.3 Properties of a Good Evaluation Function

A good evaluation function should satisfy four things:

1. Give higher values to better states for the max player.
2. Give lower values to better states for the min player.
3. Be fast to compute.
4. Correlate reasonably well with the actual chance of winning.

The first two properties make the score usable by minimax: whichever player is at a node, the number ranks the state from that player's perspective. The third property matters because the whole reason we use static evaluation is that searching deep is too expensive — an evaluation that takes a minute per board would defeat its own purpose. The fourth property is what makes the score meaningful — a score that disagrees with the real chance of winning would mislead the search.

The fourth property also has a textbook meaning worth knowing. For terminal states, a good evaluation must agree exactly with utility: $EVAL(\text{terminal})=UTILITY(\text{terminal})$. For non-terminal states, the evaluation must sit somewhere between a loss and a win. One clean way to think about a good evaluation: imagine it returns the expected value of the game from this state — if 82% of similar positions lead to a win $(+1)$, 2% to a loss $(-1)$, and 16% to a draw $(0)$, a good evaluation for the category is $(0.82\times 1)+(0.02\times -1)+(0.16\times 0)=0.80$. In practice we cannot estimate such probabilities for every category of board, so we add up feature contributions instead — which is exactly the material-counting function of the next section.

8.1.4 Worked Examples: Chess Material Counting

The simplest evaluation function for chess counts material. First we need a table of piece values. These values are empirical: some experts, or an algorithm that has played chess many times, settled on them. The values used in the example:

The static evaluation value is computed as:

$$SEV(\text{board})=\sum _{\text{max player’s pieces}}U(\text{piece})-\sum _{\text{min player’s pieces}}U(\text{piece})$$

In words: the static evaluation value is nothing but the summation of the utility of the max player minus the summation of the utility of the min player. If I am the white player, I take white as max and black as min, I total up the white pieces using the table, total up the black pieces, and subtract. Positive scores are good for max; negative scores are good for min.

The narrative while filling these boards: first add up the white coins — "this horse will give me three, this bishop will give me three, this soldier will give me one" — then add up the black coins, then subtract. Once the table is known, computing the static evaluation value for any board is quick: total the max side, total the min side, subtract.

Why is this significant? Suppose I am the white player and I have four possible board configurations to choose from (there are many more — the "dot dot dot"). The static evaluation value tells me which configuration is more promising. Minimax will never take me to the worst one — for example a configuration at −9, where black still has a queen, a horse, and a soldier while I have lost my queen. It will steer me away from the −7 configurations too. So the values we saw in every earlier tree diagram are computed exactly this way: someone defined a utility function, evaluated each board, and produced those numbers.

There is also a weighted variant. Instead of just subtracting, you can assign weights to the two sides and multiply:

$$EVAL(\text{board})=w_{\max }\cdot \sum U_{\max }+w_{\min }\cdot \sum U_{\min }$$

The weights $w_{\max }$ and $w_{\min }$ are parameters; per configuration you can assign some weights, multiply, and the final value is that board's score. The professor's example phrasing: "maybe here it's five, here it's three" — the weight on one side is 5, the other 3, and you multiply before combining.

Real-world: this exact material count is the base evaluation of essentially every chess engine — Stockfish and similar engines use piece values of the same shape as the table above (often tuned to slightly different numbers, like 3.05 for a knight) and then layer positional features on top. Material counting is also how chess engines "know" that trading a bishop for a pawn is bad unless there is a tactical reason — the static score drops by two points, and only the search can justify it.

8.1.5 Worked Example: Tic-Tac-Toe Winning Configurations

Chess counting is straightforward because you can count coins. In tic-tac-toe you cannot, so a different static evaluation works. The example board has six cells already filled: an O, an O, an X, an X, an O, and an X, with three empty cells left. (The exact layout of the filled cells is not needed for the method — what matters is what the counting produces, exactly as in class.)

Why fill the empty cells with X or O instead of counting X's and O's directly? Because the number of X's versus O's is not a good metric in tic-tac-toe. In chess you can eliminate pieces and throw them off the board; in tic-tac-toe you cannot — every cell gives both players equal opportunity, and the nine grids get filled turn by turn. So we count win possibilities instead.

A second way to reason about the same board: go through each winning line that is still open (rows, columns, diagonals that do not already contain both symbols) and check who already occupies it. The first row is gone — nobody can win there. The second row is gone too. The third row is still open, and it already has an X — X has even more chances. The principal diagonal is gone (it has both O and X already). The other diagonal is still open, and it also has an X. In every open win possibility you see X's and no O's — so X is at an advantage, and you can award points accordingly. That is the same conclusion, $2-1=1$, reached by a different route.

8.1.6 A Two-Player Tile Game

A different flavor: the tile game (the sliding-tile puzzle, like the 8-puzzle) played with two players. In single-player search we used heuristics like the number of tiles out of place for this game. Now take the same tile game with two players: one board, and both players race to the same goal configuration — whoever first achieves the goal pattern wins, and the other player loses. I might move the 8 tile here, my opponent moves another tile there to block or catch up, and so on.

There is only one board; all players play on that same board. The static evaluation value again tells us how good or bad the current board is for each player — in this case, the same score assigned to the current board shows how good or bad it is for the player. Think of a Sudoku handed to two people where you are competing, not cooperating: I put a number, my opponent blocks that number, and so on. Who is reaching the goal faster — or who is positioned to — is the question the evaluation function scores.

8.1.7 Student Questions and Answers

8.1.8 Exam Notes

8.2 Alpha-Beta Pruning

8.2.1 The Motivation: Minimax Inspects Everything

Before alpha-beta, recall exactly what minimax does. Take a tree with three min nodes under a max root:

The first min node looks at leaves 3, 12, and 8 and picks 3 — the minimum. The second looks at 2, 4, and 6 and picks 2. The third looks at 14, 5, and 2 and picks 2. The max root then picks the maximum among 3, 2, and 2, which is 3.

The straightforward question: to fill in the intermediate nodes and the root, did we touch every static evaluation value? Yes. We went to every leaf, picked the min among each group, then the max at the top. If the tree is big, that is computationally intensive — we inspected all the leaf nodes. Worse, the cost grows exponentially: with branching factor $b$ (moves per state) and depth $m$ (plies searched), minimax visits $O(b^m)$ leaves — every extra ply multiplies the work by $b$. So the question naturally becomes: can we do better?

8.2.2 What Alpha-Beta Pruning Is

Alpha-beta pruning is the same minimax algorithm, only with a small addition that is smarter. It is an improved minimax using a heuristic: it stops evaluating a move when it makes sure that the move is worse than a previously examined move. Such moves need not be evaluated further — you prune them. Pruning is a simple computer-science concept: you do not want to go down that branch at all, you do not want to evaluate it, you just ignore it.

When added to a plain minimax algorithm, alpha-beta gives the same output but cuts off certain branches that cannot possibly affect the final decision, dramatically improving performance. Give a tree to minimax, or give the same tree to alpha-beta: the final answer is identical. The difference is in the details — minimax does no pruning and checks every evaluation value; alpha-beta does some smart thinking and eliminates certain branches. The algorithm was discovered independently by a few researchers in the mid-1900s.

Where does the improvement come from? In the best case, with good move ordering, alpha-beta inspects only $O(b^{m/2})$ leaves instead of $O(b^m)$ — it can solve a tree about twice as deep in the same time. In the worst case, when nothing can be pruned, it inspects exactly as many leaves as minimax. So applying alpha-beta is never worse than minimax — the professor's rule: "applying alpha-beta is always at least as good."

8.2.3 Alpha, Beta, and the Two Pruning Formulas

Two variables carry the pruning knowledge.

The association is fixed: max nodes are associated with alpha, min nodes are associated with beta. This cannot change — max is always alpha and min is always beta. What can change is the order of layers: the root may be max or min; it will be given to you, or you infer it from the node shapes.

Speaking of shapes: the convention in the textbook and in many question papers is that a square means a max node and a circle means a min node. If the node types are not written, you should interpret the diagram using that convention. These subtle conventions in the slides and materials deserve attention — the instructor repeatedly stressed them.

The general principle of alpha-beta pruning: at a node $N$, if the player has a better option at the parent of $N$, or further up the path, then there is no meaning in exploring $N$'s children — that node will never be chosen, so you prune the entire subtree rooted at $N$. The two formulas tell you exactly when that condition holds:

• After an alpha update (a max node's alpha value changes): check whether

$${\beta }_{\text{parent}}\le {\alpha }_{\text{current}}$$ If true, prune — the current max node can only deliver $\ge {\alpha }_{\text{current}}$, which the parent min node (wanting less than ${\beta }_{\text{parent}}$) will never pick.

• After a beta update (a min node's beta value changes): check whether

$${\beta }_{\text{current}}\le {\alpha }_{\text{parent}}$$ If true, prune — the current min node can only deliver $\le {\beta }_{\text{current}}$, which the parent max node (wanting more than ${\alpha }_{\text{parent}}$) will never pick.

Whenever you update an alpha, go check the first property; if it holds, you can prune. Whenever you update a beta, check the second; if it holds, you can prune. If the property does not hold, you cannot prune and you must keep exploring.

If the root is a min node instead of a max node, the formulas still work as long as you keep the intuition straight — the direction of the inequality (or the parent/current roles) flips. The instructor's advice was to prefer the intuition over the formulas: the parent–child contradiction is the same no matter which player is at the root.

8.2.4 Worked Example 1: Pruning the 10

The tree: root $A$ is a max node with two min children, $B$ and $C$. Each of those has two max children. Leaves under the first max child of $B$: 6 and 5. Leaves under the second max child of $B$: 8 and 10. Under $C$'s first max child: 2 and one more value. Under $C$'s second max child: unknown values.

A discussion moment during the walkthrough: what if the pruned leaf were 4 instead of 10? Irrelevant. The max node already has alpha 8 and delivers at least 8; the min parent wants less than 6. Whether the leaf is 4, 1, or 100, that branch is never picked — the contradiction is already established, so the value does not matter. If it had been 4, the max node would not have adopted it anyway (4 is not greater than 8), and exploring it would have been wasted computation.

8.2.5 Worked Example 2: The Classic Deck Tree

The second example is the one traditionally used in the course deck: root max node with three min children. The first min child has leaves 3 and 4. The second min child has leaves 2 and 1. The third min child, $D$, has two max children: the first has leaves 7 and 8 (and then more unlisted children), and the second, $F$, has two min children — one with leaves 2 and 11, one with leaf 1 (and then more unlisted children). The stated leaves are 3, 4, 2, 1, 7, 8, 11, 2, and 1, with the remaining children hidden behind "dot dot dot". This walkthrough follows the narrated sequence exactly.

Practice tip from the session: redo this tree from the left side on your own — the two formulas are your backup, but the intuition is the real tool.

8.2.6 The Heart of the Algorithm: The Parent–Child Contradiction

The formulas are fine, but this is the heart of alpha-beta pruning. A min node is trying to find something less than its beta value. A max node is trying to find something greater than its alpha value. When a parent and its child want opposite things, the child's whole search becomes pointless:

• The parent min node already holds a path to value $x$ and will only pick something less than $x$.
• The child max node already holds alpha $y\ge x$ and is searching for something greater than $y$.
• Even if the child succeeds — even if it finds 100, or 8, or anything — that result will never be picked by the parent, because the parent is looking for something less than $x$ and the child can only deliver at least $y$.

That contradiction is the prune signal. Say it again slowly with example 1: the min node has beta 6 and wants something less than 6. Below it, a max node has alpha 8 and wants something greater than 8. These two goals contradict each other. Do not bother searching — whatever the max node digs up will be thrown away by the min node above it. The same pattern repeats in the other direction: a max parent holding alpha 3, and below it a min node holding beta 2 — the min node wants less than 2, the max parent wants more than 3; if the min node succeeds, the max parent still prefers its guaranteed 3. Prune.

The very first time you update a value, you cannot prune, because you have no parent values to compare against — the parent's beta is still $+\infty$ or the parent's alpha is still $-\infty$. The leftmost child of the tree can never be pruned, because that is where the traversal starts. After that, every update is followed by a pause and a retrospect: what is this node looking for, what is its parent looking for, do they contradict?

8.2.7 Student Questions and Answers

8.2.8 Exam Notes

Real-world: alpha-beta pruning is the reason chess engines can search 30–40 ply deep in the few seconds of a blitz game. With move ordering (try captures and checks first), the best case $O(b^{m/2})$ is nearly reached in practice — the same tree that would take minimax a million positions takes alpha-beta a few thousand. The technique generalizes far beyond games: any two-sided optimization where one side maximizes and the other minimizes (negotiation systems, adversarial planning, minimax control) can use the same cut.

8.3 Monte Carlo Tree Search

8.3.1 What Monte Carlo Tree Search Is

Monte Carlo Tree Search (MCTS) is a heuristic search algorithm for decision processes, most notably employed for games. Unlike minimax and alpha-beta — which contain no probability at all — MCTS is probabilistic. It is a heuristic search that relies on intelligent search, and it combines classic tree search alongside machine-learning principles like reinforcement learning.

The motivating picture is a game like Go. From the current board state I can make several moves; from each resulting state, more moves; and finally I reach outcomes. The leaves of the full tree are terminal states — utilities: black wins, black loses, and so on. A full expansion of that tree is exactly what we cannot afford. MCTS's answer: do not draw the whole search tree first and then search it. Instead, run simulations, and use the results of those simulations to guide the growth of the game tree. That is the key idea in one line: the tree grows where the simulations say it is promising, not everywhere.

8.3.2 Why Naive Simulation-Based Evaluation Is Too Expensive

A naive approach would be to use simulations directly as an evaluation function for alpha-beta: for a given board, generate all possible moves and all the children they lead to, simulate the game from each, and then apply alpha-beta over that tree. Why is that a bad idea? Three reasons. First, a single simulation is very noisy — one random play-through is a poor estimate of a position's value. Second, running many simulations for one evaluation is very slow. Third, doing this for every node of the tree is computationally very expensive.

The numbers make it concrete. Typical chess programs evaluate about a million positions per second. Go can generate about a million moves per second, with something like 400 moves per simulation. When your "evaluation" is a full simulation, you end up being able to do only about 25 evaluations per second — the practical budget the session quoted.

That is why Monte Carlo was ignored for over 10 years — nobody cared about it while it seemed this costly. Monte Carlo methods are used across computing in many places, and you have met them in the deep reinforcement learning course, but in game search it took this simulation-guided form to become practical.

8.3.3 Exploitation versus Exploration

MCTS is driven by two opposing goals. Exploitation means focusing on promising moves — the ones the simulations so far suggest are good. Exploration means focusing on moves where the uncertainty about the evaluation is high — moves that have not really shown their quality yet, but might surprise you. These two are the heart of the algorithm: you do both. You capitalize on your strengths most of the time, but once in a while you step outside your comfort zone.

Mechanically, selection picks each node with probability proportional to a quantity called the upper confidence bound (UCB). You have already learned UCB in your deep reinforcement learning or reinforcement learning course, so the session did not go deep into the formula — the intuition is what matters here.

8.3.4 Perfect Information and Combinatorial Games

Where does MCTS apply? It is used in combinatorial games — sequential games with perfect information. The perfect information requirement is important: both agents know the complete configuration at every step, so games like chess, tic-tac-toe, and Go qualify. These approaches cannot be used in games with imperfect information — football, for example, where one person is doing something while another player cannot fully see it.

The preconditions for a combinatorial game: it must be a two-player game (sometimes multiplayer); it must be sequential, with players taking turns; and it must have a finite set of well-defined moves. Examples are chess, Go, tic-tac-toe, checkers, and so on. Finite moves matter: I cannot do something random, and everything is fully known — the whole configuration is visible to both agents.

8.3.5 The Four Phases: Selection, Expansion, Simulation, Back Propagation

MCTS searches only a few layers deep — a key property — and prioritizes which parts of the tree to explore. It simulates the outcome rather than exhaustively expanding the search tree. In doing so it limits how many evaluations it has to make. The individual evaluation relies on a playout, or simulation, in which the algorithm effectively plays the game from the given starting point all the way to a leaf state by making completely random decisions. When it completes a simulation, it selects the state that has the best rollout.

The algorithm works in four phases, repeated until a set time has elapsed (you set a time budget; until the time lapses you keep iterating, hunting for promising paths instead of exploring the whole tree). The four steps:

1. Selection. Start from the root and choose the most promising child node repeatedly, using a balance between exploitation and exploration. The selection uses UCB1, which you already know: each node is picked with probability proportional to its upper confidence bound. The result of selection is a leaf to work on.

2. Expansion. At the selected node — specifically a node where not all possible moves have been explored — add a new child node for one unexplored legal move, and try to build out from there, with the hope that this move will turn out better. Example from tic-tac-toe: the selected board state still has three legal moves — X can be placed in the top right, the middle left, or the bottom center, all still empty. MCTS chooses one unexplored move; in the example it picks the top right, puts the X there — which gives birth to a new board configuration — and adds this as a new state, initialized to 0 wins out of 0 plays. Then it explores that state further.

3. Simulation (rollout). From the newly expanded node, the algorithm plays the game until the end — only that one state, not all the possible children. The moves during the simulation may be completely random, or they may use some simple rules, or a lightweight heuristic.

4. Back propagation. Once the simulation ends, the result is sent back through all the nodes visited in that iteration — only that path, not everywhere. Each node on the path is updated: the visit count, the win score, the average win rate, and so on. In symbols, if $N(v)$ is the number of times node $v$ has been visited and $W(v)$ is its win count, the back-propagation step is

$$N(v)\leftarrow N(v)+1,W(v)\leftarrow W(v)+1\text{ when the player wins}$$

Over many iterations, the counts on the promising paths grow, and the counts tell you where to look next.

8.3.6 Worked Example 1: Win-to-Play Ratios

Every circle in the example tree contains two numbers: wins over times played. That is the win/play ratio $\frac{w}{p}$, the wins $w$ in the numerator and the plays $p$ in the denominator — a node labelled $\frac{2}{3}$ means I have won twice out of three times played (said aloud as "2 by 3"). This is the whole tree drawn from one player's perspective.

8.3.7 Worked Example 2: The Go Tree from the White Perspective

The second example tree is drawn from the point of view of the white player; all the win counts record white's wins. The root shows 37 wins out of 101 plays — "37 represents that white has won 37 times out of the 101 times I played." The tree is the same shape as the classic example from the reference text (which draws it from black's point of view with the root at 37 wins out of 100 plays); the counts here match the narration of the session.

After the time budget runs out, the counts tell you which paths are most promising to explore, and you restrict further play — and any alpha-beta search — to exactly those paths.

8.3.8 The MCTS Loop and Handoff to Alpha-Beta

The algorithm in full: start with the tree at the current state. While time remains, (1) select — pick a leaf via UCB1; (2) expand — add a child under it for an unexplored move (you can pick any node to treat as a leaf, and expansion is nothing but adding that child — the exploration step); (3) simulate — play a full game from that child to a terminal result; (4) back propagate — push the result up the visited path, updating win and play counts. Keep doing this until the timer expires.

tree <- node for the current state
while time remains:
    leaf   <- SELECT(tree)          # UCB1: exploit promising, explore uncertain
    child  <- EXPAND(leaf)          # add one unexplored move as a new 0/0 node
    result <- SIMULATE(child)       # random/light playout to a terminal state
    BACK-PROPAGATE(result, child)   # increment win and play counts on the path
return the move whose node has the highest number of playouts

At the end, return the move whose node has the highest number of playouts — the configuration where the simulations said you win most often. Then, if you want to use alpha-beta, you apply it only in those promising parts of the tree, not everywhere. This is what the example tree was showing: the tree itself is many games' worth of statistics — some paths have three games behind them, some two, some one — and the statistics decide which of those sub-trees deserve the full search.

8.3.9 Student Questions and Answers

8.3.10 Exam Notes

Real-world: MCTS is the algorithm behind modern game AI at the highest level — AlphaGo and its successors combine MCTS with neural networks that guide both selection and the playout policy, and the same simulation-guided search is used in program synthesis, robotics planning, and dialogue systems. The exploitation-versus-exploration trade-off it balances is the same one that drives recommendation systems, A/B testing platforms, and any system that must choose between what is known to work and what might work better.

8.4 The Mid-Semester Exam

8.4.1 Exam Format and Logistics

The mid-semester exam covers everything from classes 1 through 8, plus the webinar sessions. It is two hours long, for 30 marks, and it is a fully subjective exam — there are no MCQs. The exam is written online, but at an exam center: you get a hall ticket telling you where to go, and you go there to write the exam on a machine. There is no code — you will not write Python programs or any program. You may be asked to comment on something or to write an algorithm — a pseudo-code style answer is possible, but not programming.

The exam is closed book, and formulas will not be given to you. There are very few formulas to memorize in this course — the advice is that in no class is there a formula you truly need to mug up. Even in alpha-beta pruning, if you understand the logic — the parent node is trying to go up, the child node is trying to find something lesser, there is a contradiction, so you prune — you do not need to memorize the formula.

The detailed syllabus and a sample or past paper will be posted as an announcement on the same day as this session. Have a look at that announcement — it has all the details. But do not treat the past paper as a prediction: do not apply correlation logic to it.

8.4.2 What to Expect: Paper Structure and Difficulty

It will be a tight paper. Tight means you will not have the liberty to think for an hour and write for 10 minutes: if you are prepared well, the paper will take you about 1 hour 50 minutes to 1 hour 55 minutes to complete. This matters especially for working professionals — every week there were practice questions in the course materials, and the concern is that students have not solved them, so their speed has slowed down. If that is the case, you might end up not completing the paper.

It will be a well-balanced paper. The instructor does not believe in papers that are only algorithms, only code, or only one type of question. Expect a balance of theory, practical, numerical, and formula questions. The number of questions will vary — anywhere between 6 and 10 questions, small, medium, or one big question and another with two small parts.

The paper follows Bloom's taxonomy — a technique for assessing exams at different cognitive levels. Concretely: there will be some easy questions that everybody will know; if you do not answer those correctly, something is wrong with the teaching — the instructor takes that on himself. There will be questions you learned in class and then apply. And there will be some questions that push your boundaries. That mix is the design.

The regular exam and the makeup exam will be almost the same, with slight variations — the makeup will not be identical to the regular paper. Within the regular exam itself, there may be sets: different students may get different questions. Do not worry about that. After all the exams are over, a complete solution with rubrics will be released, and from there, reevaluation concerns can be taken forward. Assignment results will not be released before the exam — assignments are still being evaluated, and they take time because there are more than 250 groups and the code is actually run to evaluate it.

8.4.3 What Is Covered: The Full Course Recap

You can expect any question from any topic — not every small topic, but from all the big pictures there will be questions. The recap of the whole course so far:

• The fundamentals of AI — the basics from the first classes: for a given problem, can you come up with a PEAS specification, an environment specification, and what else the problem needs.
• The problem-solving agent — how do you represent an agent, and the different types of agents.
• A bunch of search techniques — mostly informed search: A-star, GBFS, and the concepts around them.
• Within search, local search — hill climbing, genetic algorithms, ACO (ant colony optimization), and related ideas.
• For large search trees — pattern databases, relaxed constraints, and similar techniques.
• NAS — neural architecture search as an application of genetic algorithms: NEAT, Deep NEAT, and CoDeepNEAT, with theory and examples.
• Game playing — the material you have just covered: adversarial search, minimax, alpha-beta pruning, and Monte Carlo Tree Search.

Questions will come from all of these big areas.

8.4.4 Study Advice

Concentrate on all of it — there will be questions from every big topic. Keep solving: every set of course materials has sample problems, and a full-fledged practice paper will be uploaded. The more you solve, the faster you get; if your speed increases, you do justice to a tight paper. It should feel like: you see the question, you start answering. Do not solve slowly, get stuck, and run out of time.

8.4.5 Student Questions and Answers

Exam Guidance Summary

Everything said in this session about the mid-semester exam, in one place:

• Format: two hours, 30 marks, fully subjective, no MCQs. Written online at an exam center with a hall ticket. No code — no Python programs; algorithm or pseudo-code answers are possible.
• Syllabus: everything from classes 1 through 8 plus the webinars — fundamentals of AI, PEAS and environment specifications, problem-solving agents and agent types, informed search (A-star, GBFS), local search (hill climbing, genetic algorithms, ACO), pattern databases and relaxed constraints, NAS/NEAT/Deep NEAT/CoDeepNEAT, and game playing (minimax, alpha-beta, Monte Carlo Tree Search). Questions come from all the big topics, so concentrate on all of it.
• Materials: the detailed syllabus and a sample/past paper are posted the day of this session. Do not treat the past paper as a prediction — the syllabus changed considerably (DFS and BFS are no longer in the course), so prepare the whole syllabus and glance at the past paper only.
• Closed book: no formulas given; very few formulas to memorize. Alpha-beta is logic, not memorization: parent wants to go up, child wants something lesser, contradiction, prune.
• Pacing: it is a tight paper — well prepared, expect 1 hour 50 minutes to 1 hour 55 minutes of writing. Solve the weekly practice problems to build speed; the goal is "see the question, start answering."
• Structure: a balanced mix of theory, practical, numerical, and formula questions; 6 to 10 questions of small and medium size, or one big question plus a two-part question. Bloom's taxonomy design: easy questions everyone knows, applied questions from class, and boundary-pushing questions.
• Marking: step marking for some questions, zero-or-one for others; a mistake at a step loses that step's marks, and evaluation stops at the first mistake — pruning applied to your answer sheet. Solutions with rubrics are released after all exams.
• Variants: the makeup exam is not identical to the regular paper; sets within the regular exam are possible.
• Mindset: other components (assignment two, quiz two, final exam) carry more weight; enjoy the paper, use the forced preparation as a learning opportunity, and do not use marks as the metric for learning.

Key Industry Applications

• Chess engines: typical chess programs evaluate about 1,000,000 positions per second — static evaluation plus search is the engine behind computer chess. The material-count evaluation of this lecture is the ancestor of the tuned evaluation functions in modern engines like Stockfish, which layer dozens of positional features on top of the same piece values.
• Go engines: Go needs about 1,000,000 moves per second with roughly 400 moves per simulation; full-game simulation as evaluation is far too slow — which is exactly the cost problem that made Monte Carlo search unpopular for over 10 years, until simulation-guided tree search (and later neural-network guidance, as in AlphaGo) made it practical.
• Real-world: simulation-guided search. The idea of letting simulation results guide which part of a search tree to grow — instead of expanding everything — is MCTS's contribution, and the same exploitation/exploration trade-off shows up across decision-making systems: recommenders, A/B testing, robotics planning, and drug-design search pipelines all allocate their next experiment to the most promising and the most uncertain options.
• Real-world: UCB in reinforcement learning. The upper confidence bound used for MCTS selection is standard material in deep reinforcement learning courses and is used broadly in bandit-style decision problems — any setting where a system must balance taking the action that works with trying the action it knows little about.
• Real-world: career decisions. The exploitation-versus-exploration trade-off is a life skill: capitalize on your strengths most of the time, and occasionally explore outside your comfort zone — the office-job-versus-PhD example — because exploration can find something even better.
• Real-world: competitive board gaming. Two-player tile games and Sudoku-style competitions — one board, several players racing for the same goal — are direct real-world settings for adversarial evaluation.
• Real-world: combinatorial games. Chess, Go, tic-tac-toe, and checkers are the canonical perfect-information games for which minimax, alpha-beta, and MCTS are designed; imperfect-information settings such as football cannot use them, because the tree structure encodes what a player is allowed to know as well as what they are allowed to do.