Neural Architecture Search and Game Playing

Neural Architecture Search and Game Playing

This module covers two big ideas. First, how genetic algorithms can design deep neural networks automatically — the line of work from NEAT through Deep NEAT to CoDeepNEAT — with a full worked example. Second, game playing through adversarial search: how to think about games where two or more agents oppose each other, the game tree, the minimax algorithm, and static evaluation functions.

The first half of the lecture finishes the neuroevolution topic: why hand-designing networks hits a human bottleneck, how NEAT evolves networks neuron by neuron, how Deep NEAT raises the level from neurons to whole layers, and how CoDeepNEAT splits evolution into blueprints (macro structure) and modules (micro building blocks). Two worked examples — cat vs dog classification and image captioning — run the whole pipeline from genotype through phenotype construction to deployment. The second half switches to adversarial search: games as formal problems, zero-sum games, game trees, the minimax algorithm with fully worked trees, and static evaluation functions. The lecture ends with exam guidance and the industry applications that tie both halves together.

7.1 Neural Architecture Search and Neuroevolution

7.1.1 Recap of the Last Session

The previous session completed genetic algorithms, applied ant colony optimization (ACO) to the traveling salesman problem, and just started neuroevolution. ACO on TSP is a straightforward problem: if you know all the formulas, you just apply them step by step and you are done — the full TSP example was worked through in that session, step by step with real numbers. The genetic algorithm material from two weeks ago — population generation, fitness evaluation, selection, crossover, mutation — is the vocabulary today's topic is built on, so it is worth recalling it now, because everything in this first half of the lecture is "the same genetic algorithm, applied to a new object: the architecture of a network."

Today we finish the neuroevolution topic (about 45 minutes), then take a break and switch to game playing — a completely separate topic that will fill the second half of the session. Keep the genetic-algorithm loop in mind while reading 7.1; keep it in the drawer while reading 7.2 onwards.

7.1.2 What Neural Architecture Search Is

Neural architecture search (NAS) is nothing but an application of genetic algorithms: the whole technique is about automatically designing models. You already know the manual way from your deep learning background — humans design architectures by hand: they choose how many convolution layers, what kernel sizes, where to place pooling, how wide the dense layers are. NAS is the family of approaches that automates that design, and the course handout links two research papers on this: the Deep NEAT paper and the CoDeepNEAT paper. Both treat architecture design as an optimization problem and solve it with evolutionary search instead of human intuition.

CoDeepNEAT is an automated method for designing deep neural networks. Traditional AI relies on human experts to design architectures manually; CoDeepNEAT replaces that with evolutionary search, and it is, of course, inspired by natural evolution. Because it uses genetic algorithms, it is an application of genetic algorithms to automatically create deep neural network architectures. Nothing mystical: the same operators you used for function optimization are now applied to network structures.

Why do we need this at all? Two reasons the lecture gives, and both are about limits of the human designer.

Reason 1 — the human bottleneck. Designing architectures manually is genuinely challenging, and humans rely on trial and error plus prior knowledge. That prior knowledge itself limits the exploration of novel architectures. The trap is subtle: the more a designer "knows" about what works, the more the search is confined to variations of known patterns. For example, in medical fields, AI has come up with novel architectures that doctors had never thought of — because humans always think in terms of what they already know, and that prior knowledge can be a bottleneck on creativity. An algorithm applying mutation and crossover keeps creating architectures, and sometimes it stumbles onto something more creative than a human would. An evolutionary search has no "taste" and no preconceptions; it keeps trying combinations a human would discard immediately.

Reason 2 — network complexity. When network complexity increases, manual optimization becomes really impractical — the network is huge and manual tuning is simply not possible. A modern CNN has dozens of layers, each with hyperparameters like filter count, kernel size, stride, padding, activation, and dropout; the number of combinations explodes combinatorially. Nobody can hand-tune that space. That is why we adopt CoDeepNEAT.

Real-world: the same human-bottleneck argument applies broadly in industry — any domain where expert-designed solutions repeat known patterns, an evolutionary search can explore beyond them. Automated machine learning (AutoML) systems in production today ship exactly this promise: the pipeline and architecture are searched automatically, and the human sets the budget and the metric.

7.1.3 Neuroevolution in One Word

Neuroevolution is, in a single word, using genetic algorithms to evolve neural networks — deep neural networks specifically. Here is how it works: first create many neural networks — that is the population, created randomly for your problem. Then train each network. Measure their performance — in other words, the fitness. Select the best ones, then perform crossover and mutation. Do these steps look familiar? Population generation, fitness check, selection of a parent, crossover, mutation — this is exactly genetic algorithms, but the genetic algorithm is being used to create a deep neural network automatically.

Three terms carry over from the genetic algorithm material, and it is worth fixing their exact meaning in this setting:

• Population — a set of networks (candidate architectures), generated at random to start, not one network. The population is the search's collection of "individuals."
• Fitness — how good that network performs for a given problem (not generic networks — for your problem). It is a number measured on data, typically classification accuracy on a validation set, so it measures generalization rather than memorization.
• Generation — one cycle of this process: evaluate fitness of the current population, select parents, apply crossover and mutation, form the children that become the next population. Running 50 generations means running this cycle 50 times.

The loop is the same loop from the genetic algorithm lecture; only the "individual" has changed from a bit string to a network architecture.

7.1.4 NEAT: NeuroEvolution of Augmenting Topologies

NEAT stands for NeuroEvolution of Augmenting Topologies: NE stands for neuroevolution, and AT stands for augmenting topologies, because the method is creating networks, and every network can have a different topology — the way it looks. "Augmenting" means the topology grows: the search starts tiny and adds structure over the generations. NEAT is a method for evolving neural networks automatically instead of designing them manually.

A neural network is represented as a graph — you know graphs from data structures: a graph is a set of nodes and edges. Here nodes represent neurons and edges represent the connections between them. That representation choice is the whole trick: if a network is a graph, then evolving a network means evolving a graph, and graph mutation means adding a node or an edge.

NEAT starts with a very simple network having minimal connections, and over generations it gradually adds new nodes and new connections to increase complexity. New types of nodes keep getting added, and that adds flavor to the new type of network being created. Two ideas in NEAT deserve emphasis:

• Minimal start. Begin with the smallest possible structure (input connected to output, few or no hidden neurons). Complexity is earned, generation by generation, instead of assumed at the start.
• Speciation. Similar networks are grouped into species — this is slightly different from vanilla genetic algorithms: among the generated children, they group those that have similar characteristics, so that in the next evolution the diversity is maintained; the next generation is drawn from different groups of species, not only from one.

NEAT has limitations, and they matter. NEAT performs well for small and simple neural networks, but it is not effective for deep learning models with many layers. Modern AI systems use deep architectures such as CNNs and LSTMs, which require layer-wise design and complex structures. The key point: NEAT evolves individual neurons and connections, but not fully layered architecture. It works at the individual neuron level, or the connection level, but not at the full-fledged architecture level — and modern AI has moved on to deep architectures. So NEAT can be used for small neural networks, but not for a deep neural network with a complex architecture.

Think about what that means concretely: a deep CNN has millions of parameters arranged in dozens of layers; evolving neuron-by-neuron would take an astronomical number of generations to assemble something like a ResNet block, and the search would mostly wander in useless topologies. This limitation led to advanced approaches: Deep NEAT and CoDeepNEAT. The progression is a ladder: NEAT evolves neurons, Deep NEAT evolves layers, CoDeepNEAT evolves reusable modules plus the blueprint that arranges them.

7.1.5 Deep NEAT: Layers as Nodes

Deep NEAT extends NEAT to evolve deep neural networks with complex, multi-layer architectures. It also uses genetic algorithms. The striking difference is this: in NEAT, nodes represent individual neurons; in Deep NEAT, each node represents an entire layer. Every time we keep generating, we get new types of layers.

Each node stores layer details, including the type — it could be a convolution layer, a dense layer, an LSTM, and so on — and it could also store the hyperparameters used, such as filter size. So the chromosome's node is a mini-specification of a layer. Edges define how layers are connected and represent the flow of data between them. One modification: in NEAT we also store the weights, but here we are not very interested in the weights on the edges; we store the weights at a macro level and the generations are not worried about the weights. The evolution searches structure (which layers, how connected, what hyperparameters) and leaves the millions of weight values to gradient descent — the bi-level split from 7.1.2, now visible concretely: evolution decides the skeleton, training decides the weights.

How Deep NEAT builds a network: the process starts with a chromosome represented as a graph — that is the initial population. For each node, a corresponding neural network layer is created. All layers are connected based on the graph structure. Two wiring problems need rules:

• Multiple inputs. When multiple inputs occur (a layer receives data from several parent layers), they are combined using either a concatenation operation or a summation operation. Concatenation stacks the tensors along the channel dimension; summation adds them element-wise. Which one applies is part of the node's design.
• Size mismatch. When there is a size mismatch (parent layers produce outputs of different sizes), you use either pooling or downsampling to fit it. The parent outputs are brought down to the smallest size so the merge is well defined.

The final output is a complete deep neural network built from the evolved structure.

The problem with Deep NEAT: networks generated by Deep NEAT tend to be random — they are complex and lack clear structure. In contrast, modern models like ResNet or GoogLeNet use repeated and well-organized blocks, with modular design. That modularity is missing in Deep NEAT, because Deep NEAT does not reuse learned structures. Suppose you have created a layer and it is benefiting you — why not reuse it again and again? That is exactly what ResNet and other modern models do, but Deep NEAT does not: it keeps randomly generating new layers generation after generation and never reuses what was learned. That leads to a failure to create repeatable patterns.

The observation is the seed of the next step: successful deep architectures in the wild are made of repeated building blocks. So the need for reusable building blocks to design structured, efficient networks — and that is why CoDeepNEAT came into the picture.

Real-world: ResNet and GoogLeNet are the canonical examples of modular, reusable-block architectures in production deep learning — the same design philosophy CoDeepNEAT tries to learn automatically. A ResNet is, quite literally, the same residual block repeated dozens of times with a few connecting layers; GoogLeNet repeats inception modules. Deep NEAT cannot discover such repetition because nothing in its representation rewards "this module worked, use it again."

7.1.6 CoDeepNEAT: Blueprints, Modules, Genotype, and Phenotype

CoDeepNEAT is an improvisation of Deep NEAT. The full flow: initially everything was manual. Then we came up with using genetic algorithms to automatically build a neural network — that was NEAT. NEAT had its own problems, because it is not really applicable to the real world where we need deep architectures. So we went to Deep NEAT, which was promising — it could generate full layers, not just neurons. But there was one problem: it was just randomly generating layers and not giving importance to the reuse factor. So some authors improvised it — and that is CoDeepNEAT.

CoDeepNEAT improves Deep NEAT by separating evolution into two parts, enabling better structure and reuse. The two parts: the blueprint and the module. The blueprint defines the overall network structure and acts as a skeleton for organizing components. The module is a small neural network that serves as a reusable building block. This approach reflects real-world deep networks — it is similar to ResNet and other models — so it is more scalable, more efficient, and more structured, and it exploits the fact that we are reusing what we had already learned.

The genotype is the representation used in CoDeepNEAT, composed of the two things just discussed: blueprints and modules. The blueprints define the overall network structure; the modules define the reusable neural subnetwork. The blueprint is more like an empty slot — it is not the actual layer, just placeholders — and once we have the modules, we plug and play them into those placeholders however we want. The modules contain the actual layers and the hyperparameters.

The blueprint can also be called the macro structure — macro means bigger, not micro. It represents the high-level structure of the network: input on one side, output on the other, and in between the numbered placeholders (1, 2, 1, 3, and so on) — these are not actual layers; they are only placeholders. Each node represents a module species ID: those numbers are module IDs, and a node does not represent a direct layer — later we plug a whole layer into that empty slot. The edges define the data flow: from input it goes here, and from here on. The modules are the micro architectures: small neural subnetworks — one could be convolutional, one could be an LSTM, they can have different filters, and so on. Modules are evolved independently using subpopulations.

The phenotype is the whole assembly. Once you have completed the two steps — the blueprint, and the individual modules generated using genetic algorithms — you put them together, and that is phenotype construction. The phenotype is the actual neural network used for training; it is built by replacing the blueprint nodes with the selected modules and connecting the modules based on the blueprint edges. The assembly process: you select a blueprint (several blueprints were also generated; for each node, meaning each empty slot, there are choices), choose a module from its species, replace the node with the module, connect them — and you have a full network.

Innovation numbers: in that blueprint there were numbers — those are called innovation numbers. In simple words, an innovation number is just a unique ID assigned to the structural mutations. We have to know which module is which: this module has this ID, that module has that ID, so that when we want to place them in the blueprint, the unique IDs help. Simply put, for every child we generate, or every module we generate, we give it a unique innovation number — it is more like a primary key. Why is it important? Because it helps in correct alignment during crossover. We do not want two modules that are the same to be used for crossover; meaningful recombinations occur when we combine two different modules with different unique innovation numbers. When two parent chromosomes meet for crossover, matching components line up by their innovation numbers, and components present in only one parent are simply inherited. The resulting network gives deep architectures, reusable patterns, and efficient search-space exploration.

Real-world: the whole idea — small modules assembled like building blocks — is like microservices: different people (or teams) can develop different modules using genetic algorithms, and when we do phenotype construction we think about which modules to pick. One person has a bunch of modules ready; another has a macro structure; that person decides which modules to plug in.

The phenotype-construction diagram: the diamond represents the input — where we start — and the bottom blue node is the output, the final prediction or output layer. White nodes represent intermediate connections and flow; yellow nodes are the most important — they indicate the module insertions. Each yellow node is an expanded module or subnetwork: originally each yellow node was a single blueprint node, just a circle, but now it is replaced by a complex module generated using genetic algorithms. The modules can be reused — the same module can be repeated at different positions. So if a module proves fruitful and has good accuracy, we keep reusing it. A module itself is actually a neural network, and connections between modules follow the blueprint structure. In NEAT or Deep NEAT we did not have this concept of blueprint plus modules, and that hampered our ability to reuse things — that is why CoDeepNEAT became more popular.

7.1.7 The Genetic Algorithm Steps Inside CoDeepNEAT

We now apply the genetic algorithm itself to generate the modules, generation by generation. This is a procedure, so we walk it as one: what it is for, what goes in and out, and each step with its rationale.

Step 3 — Selection. Parent architectures are selected using a probabilistic approach based on fitness value — the roulette wheel, the same parent selection we used in genetic algorithms. Take two networks: network A with 90% accuracy and network B with 50%. Convert to proportions — 0.9 and 0.5 — and build the roulette wheel; we normalize with the total fitness value. Each architecture gets a selection probability proportional to its share of the total fitness:

$$p_i=\frac{f_i}{{\sum }_j{f}_j}$$

where $p_i$ is the probability that architecture $i$ is selected as a parent, $f_i$ (fitness) is the validation performance of architecture $i$, and the sum ${\sum }_j{f}_j$ in the denominator runs over the whole population. Every symbol is named: $i$ indexes one candidate, $j$ indexes all candidates, $p$ is a probability so it always lands in $[0,1]$, and the probabilities of the whole population sum to exactly 1. A will occupy most of the pie chart, B a small slice. Spinning the wheel will land on A most of the time — and that is what we want, because A has the higher fitness.

Step 4 — Crossover. Two selected parent architectures are combined to produce a new architecture. Simple example: parent one is convolution → pooling → dense; parent two is convolution → convolution → dense. Apply a one-point crossover: draw the line, and you get one child as convolution → convolution → dense and another child as convolution → pooling → dense. One of the children inherits the deeper feature-extraction capability. You can apply any crossover technique; the point is that from the parent architectures you reproduce and build new children. The children are also neural networks, so we assign each child an innovation number so it can be used during phenotype construction — when we replace a module in the blueprint we know which one we are placing and can reuse it again. Each structural component is assigned an innovation number; during crossover, matching components are aligned based on their identifiers — for example, if both parents contain a convolutional layer with similar function, they get aligned together; an extra layer present in only one parent is inherited if it is beneficial. We do eliminate children that are exactly like the parent — same as in genetic algorithms, where the child and parent should not be identical.

Step 5 — Mutation. Mutation introduces changes to explore new architectures. What mutations can we do on a neural network? Add a new layer in the child after crossover — say a new convolutional layer. Add a new connection — a skip connection or something similar. Or modify some parameters — filter size, activation function, and so on. Example: in the parent the filter size was 3×3; in the child we change it to 5×5. That brings the new flavor. Just like in the genetic algorithm material two weeks ago, where we randomly changed bits (1 to 2, 3 to 4) to bring in new flavor, mutation here serves the same purpose. If the original architecture was convolution 3×3 + pooling + dense, during mutation we change to 5×5 — the improved ability to capture larger patterns may increase validation accuracy from 85 to 92, so the child might be more promising than the parent. Keep generating like this.

Step 6 — Speciation. This step alone is slightly extra — it is not in vanilla genetic algorithms; it was introduced by the authors. After the children are generated, we group them into species based on similarity metrics. For example, a bunch of children that are shallow networks (one or two layers) go into one species; deeper networks (three to five layers) go into another species. Why? Because the next step of the genetic algorithm is the next iteration: the children become parents, and we again apply crossover, mutation, and so on. We want to be sure that when children become parents, not everybody is picked only from one species — we pick some parents from species one, some from species two, and so on, preserving diversity. This step is peculiar to this approach; in vanilla genetic algorithms we do not create species.

Step 7 — Generations. The whole generational evolution process repeats across multiple generations; each generation again includes fitness evaluation, selection of parents, crossover, mutation, and putting children into species. Example for cat vs dog classification: in generation one, all the children give roughly 50% accuracy. Keep applying the genetic algorithm: by the 20th generation, around 75% accuracy; by the 50th generation, around 95%. The final architecture is selected based on the highest validation performance — go to the 50th generation, take the modules or children from there, and use them in phenotype construction.

7.1.8 Worked Example: Cat vs Dog Classification

Let us run a full pass through the whole pipeline: input, genotype (module generation via genetic algorithms), phenotype construction, training, and deployment. The example is a two-class image classifier: cat vs dog.

Step D — What happens during training. If the prediction is wrong — for example the true label is dog but the model predicted cat — we calculate the error. That is nothing but the loss. The loss is predicted minus actual — $L=\hat{y}-y$, where $\hat{y}$ (y-hat) is the predicted value and $y$ is the actual label — and the weights are updated using gradient descent. The lecture states this simple form deliberately, as a signed error: it tells you the size of the mistake and its direction (over-predicted, +; under-predicted, −). Standard training loss functions build on exactly this difference:

• Squared error $L=(\hat{y}-y{)}^2$ — used for regression; it makes large errors cost much more than small ones and removes the sign.
• Cross-entropy $L=-\log p(\text{true class})$ — used for classification with softmax outputs; it punishes confident wrong answers heavily.

The relationship: all three are smallest when $\hat{y}$ matches $y$, and all three are minimized by gradient descent, so the professor's simplified form captures the essential mechanics (direction and size of the error) that the standard forms refine. In this pipeline, gradient descent updates each weight $w$ by a step proportional to the derivative of the loss with respect to it, $w\leftarrow w-\eta \frac{\partial L}{\partial w}$, with $\eta$ (eta) the learning rate. All of this happens while we are creating the node — that node itself is nothing but the module creation. When we use genetic algorithms and create a new child, we evaluate that new child's fitness value; that is what these steps are — testing with sample validation data.

Step E — Evolution picks the best. During evolution, suppose there was a network A that can only detect edges, with accuracy 60, and a network B that detects both fur and ears, with accuracy 85. What would we do? And there is a network C, after mutation: we picked these as parents, mutated, and after mutation it adds a skip connection and the accuracy becomes 92. Evolution selects network C as the best, and again it generates the next generations, and so on.

7.1.9 Worked Example: Image Captioning with CoDeepNEAT

A company wants to automatically generate captions for uploaded images using CoDeepNEAT. The system evolves CNN modules for image feature extraction, LSTM modules for text generation, and blueprints for arranging the modules. Three modules are already with us: a CNN feature-extraction module, an LSTM layer, and a dense plus softmax block. A blueprint is also given, with placeholders M1, M2, M3 — we should replace those M1, M2, M3 with the modules. The initial validation scores are given as BLEU scores — BLEU is the bilingual evaluation understudy, the caption score. For each candidate you have the scores. (BLEU compares a generated caption against reference captions by counting matching word n-grams — a score in $[0,1]$ — so it is a natural fitness measure for caption quality.)

What is asked in this problem: how do we identify whether we need blueprint evolution or module evolution only? It will be given to us. In most cases we generate the modules only using evolution, because that is the heart of it — the blueprint is just plugging things in. We can use some existing blueprints; very rarely do we generate the blueprint as well. Then: show the first iteration of phenotype construction, fitness evaluation, selection, crossover, and mutation.

The exam-style version of this problem asks you to do this whole first iteration yourself: assume a random initial population, calculate the fitness, keep doing selection, crossover, mutation — the exact sequence worked above.

After several generations, CoDeepNEAT discovers optimal modules and the best blueprint structure. From this we sometimes evolve the blueprint too, and sometimes the blueprint stays fixed and only the modules are evolved. After that it can also tune the hyperparameters — every iteration is tweaking them — so it can give a high-performing deep neural network architecture automatically. This type of network is deployed for tasks like image generation, classification, speech recognition, medical analysis, and so on.

7.1.10 Summary of the Topic

Module = reusable subnetwork (a neural network in itself). Blueprint = macro architecture with empty-slot nodes. Genotype = creating the blueprint plus generating modules using evolution; in genotype construction, modules are identified and trained, their fitness is found, and then we apply the genetic algorithm on that fitness — we create patterns, do crossover, and generate new children (children are also called modules in this work). Phenotype = assembling it all: replacing the blueprint placeholders with selected modules. Fitness calculation is nothing but the actual performance of that small module. The blueprint can also be evolved — different types of macro architectures can be constructed — but in the scope of this paper we are more bothered about the modules being generated using evolution. When you find the fitness and apply the genetic algorithm, you create newer types of children; the most promising ones get plugged into the blueprint.

The ladder, in one breath: NEAT evolved neurons → Deep NEAT evolved layers → CoDeepNEAT evolves reusable modules plus a blueprint that arranges them, reusing what evolution already learned. The fitness is validation performance; the machinery is the genetic algorithm from earlier lectures; the payoff is architecture search without the human bottleneck.

Real-world: CoDeepNEAT-style automatic architecture search is applied to image generation, image classification, speech recognition, and medical analysis; the module-reuse philosophy mirrors how ResNet-style blocks are reused across production networks, and the division of labor (someone evolves modules, someone else assembles them) mirrors microservices development. The original CoDeepNEAT paper's own deployment is a working image-captioning system for a magazine website, where the evolved architecture (repeated LSTM modules with summing merges and skip connections) beat a hand-tuned baseline on BLEU and CIDEr scores.

7.2 Adversarial Search and Game Playing

7.2.1 What Adversarial Search Is

In all the problems we have seen so far — the search problems — how many agents were there? Only one: that agent was searching for the path, for the goal, and all of that. Now we ask: what if the number of agents is more than one? What if the environment is not fully observable? That is the fundamental difference.

Adversarial search is searching in a setting where two or more agents have conflicting goals. Think of two people playing tic-tac-toe. A girl says: by placing tic-tac-toe, I am learning about chess. Why? Because she knows that if she cannot win, she will make sure the other person is not winning. In chess, that is exactly what we do: we start with the ambition to win, but at some point, if we realize we cannot win, we at least start playing defensively and ensure the other person also does not win — and they go into a draw. (And the other player says: quit stalling and move already.)

So the conflicting goal is not only about attaining the goal yourself; you are also focused on the other agent not reaching the goal. Formally: adversarial search is a branch of AI focused on solving problems where two or more agents or players have opposing goals. In such environments, one player's gain is another's loss — competition. In such problems, an agent cannot plan only by asking: what action gets me closer to my goal? It must also ask: what will my opponent do to reduce my chance of success? This is not only about the final goal — it is not just the goal part; across the whole process, every time you want to make a move, you will think: if I do this, what will that agent do? The whole technique changes. It is not just that if I have won, the other person has lost — that is the outcome. In the process itself, I will keep looking ahead and make sure the other person is not getting closer to the goal than me.

Real-world: adversarial search matters because many use cases have multiple agents with conflicting views. In today's world, people are coming up with multi-agent architectures where one agent has to critique the other — if it successfully critiques, it gets a utility; if the other is not able to, it gets negative utility, and so on. Those all sit in the direction of adversarial search: multiple agents actually competing.

Examples of adversarial problems: tic-tac-toe, chess, Go, checkers — all competitive games. Notice what they share: deterministic rules, clear legal moves, and a definite winner or draw — the ideal laboratory for search.

Why study games at all? The study and design of games enables computers to model the ways in which humans think and act, and simulates human intelligence. Real-world games have a lot of strategy behind them, and AI can learn from that: not just "how do I win," but "what might the opponent move that hampers my winning chances — so I should block that." There is a whole separate field of AI for gaming — interesting and challenging problems, larger search spaces, smaller solutions, exploring better HCI interactions — but that is a completely different field and not what we are covering here. This is a scope warning worth writing down: we study games in AI (search over game trees), not AI for games (designing entertainment software).

Historical note: the old computer chess games from around the year 2000 — those games were designed using the same principles? They were a form of AI but more rule-based: they used rule engines, and that is why it was difficult to beat the computer even back then. The same minimax-style principles, implemented as hand-coded rules rather than learned models.

Characteristics of games that matter: observability — not all games are fully observable (some are fully observable, some partially); stochasticity (is there chance, like dice, or is it deterministic?); time granularity — do we have a time constraint or not; and the number of players. All of these come into play — they decide which game-solving technique applies.

7.2.2 Normal Search vs Adversarial Search

The contrast with everything we learned before:

The rows read as a checklist for classifying any problem: count the agents, check who controls the next action, and the rest follows. If a second agent controls half the moves, "plan the path and walk it" stops working — the path may be blocked before you take the second step.

Also remember the other type of search: in one type, the state itself was the goal — that is local search. Local search is about the state itself being the answer, the solution; not the path towards the goal. In adversarial search the main issue is choosing a move while anticipating the opponent's best response. Three-way contrast to keep straight: path search (normal search) finds a route to a goal; local search finds the goal state itself (optimization over states); adversarial search finds a move under an opponent's best response.

7.2.3 A Game as a Formal Problem

When we say "game" in this AI sense, we mean the following six components:

1. Initial state — the starting board or situation (call it $S_0$).
2. Player function — tells whose turn it is (first X, then O, alternating).
3. Action function — gives the legal moves from a state.
4. Result function — gives the new state after a move.
5. Terminal test — checks whether the game is over or not.
6. Utility function — assigns a final value to the outcome: if I win, plus one; if I lose, minus one; if I draw, zero.

Worked through for tic-tac-toe: the initial state is $S_0$. The max player is going to put an X; the min player is going to put an O. At the first move, how many children are possible? Nine — we can put the X in any of the nine cells, and each placement gives a different child. Then we have to put the O. The only constraint: we cannot put the O on top of the X — some other position. How many options? Eight. And similarly, under each of the nine branches, there are eight options where we can put the O, and like this the game keeps going. Wherever we put an X or an O, that becomes our transition and we get the next state. The full tic-tac-toe tree is small enough to draw in principle: fewer than $9!$ terminal leaves (with many duplicates), which is why it is the standard teaching game.

What is a terminal state in tic-tac-toe? Either X has achieved a row, column, or diagonal, or O has achieved a row, column, or diagonal — if any player achieved those, that is a terminal state. Or the whole board is filled and nobody has won — that is also a terminal state. So the terminal test is: is there a completed row/column/diagonal, or is the board full? — and in both cases the game stops.

What is the utility? From the max player's point of view: if X has won, max gets +1. If it is a draw (nobody won), 0. If O has won (say O completed a column), then from max's point of view it is negative — max gets −1. Written from the min player's point of view, the same three boards flip: the board where X won is −1 for min, the draw is 0, and the board where O won is +1 for min. The utility function always carries the "from whose point of view" qualifier — a board does not have a value in itself, it has a value for each player.

So the full formalization of tic-tac-toe: states $S_0,S_1,S_2,\dots$ (just names); two players, X then O alternating; actions = place an X or an O, but in an empty cell only — never on an already existing mark; result = the new state after the action; terminal states = someone completes a row/column/diagonal, or the board fills with no winner; utility = −1, 0, or +1.

This is exactly the problem-solving agent depiction: initial state, action, transition, utility. The game formalization is the search-problem formalization from earlier lectures with two additions — a second player alternating turns, and a utility that scores terminal states instead of a single goal check.

7.2.4 Two-Player Zero-Sum Games

Many classic AI game-playing examples assume a two-player, zero-sum game. What does that mean? Two players — that is what "two-player" means. One player's gain is the other player's loss. The players have exactly opposite goals: both want to win, which means the goals are opposite.

We call the players Max and Min. Max is the player trying to maximize the score. Min is the opponent trying to minimize Max's score. Very important: Min is not trying to win directly — Min is trying to minimize Max's score, and by doing that, indirectly maximizing his own chance of winning. If Max gets +1, Min effectively gets −1. Examples: tic-tac-toe, chess, checkers — all two-player games where one player's gain is another person's loss.

The naming is worth dwelling on: "Max" and "Min" describe optimization behaviour, not personalities. Max runs the max operation, Min runs the min operation — and because the scores are opposite, minimizing Max's score is identical to maximizing Min's own. In a zero-sum game the two goals collapse into one number.

Real-world: many life situations are zero-sum — an interview where three people compete for one position; a promotion. One person's gain is another person's loss. A three-player game might not be zero-sum — but it is still, in a way, one player's gain being the other two players' loss. (Technically: in two-player zero-sum games the payoffs of any terminal state add to zero, so a single number describes both players; with three or more players you need a utility tuple, one component per player — the lecture returns to this in 7.3.)

How is tic-tac-toe zero-sum at each step when the results come at the end? At each step, you are trying to make a move that benefits you — or, in other words, makes the benefit smaller for the opponent. Suppose someone has a configuration with two marks in a row; it is your chance with the O. Where do you put the O? You put it to block their victory. They can still win later — that is a different story — but you try to block them in every move so that they also do not end up moving towards victory. That is why it is a zero-sum game: in every move you carry the notion that ultimately you want to win, or at least you want to make sure the opponent is not going towards victory.

7.2.5 Game Trees

A game tree represents all possible sequences of moves; at each level, the players alternate. In tic-tac-toe we start from the initial state and go all the way to a terminal state; from the first state there are nine branches, each with eight options, and if you draw the full thing, that tree is called the game tree. The operations vary per level: first a max chance, then a min chance, then a max chance, then a min chance, alternating like that. At max nodes, choose the largest value — because Max is trying to maximize. At min nodes, choose the smallest value — because by minimizing you are minimizing the chance of the max node to win. The values at the leaves represent the final outcomes or estimated scores.

Think of the tree's layout: the root is the initial state; each edge is one legal move; each child is the state after that move; players alternate level by level (level 0: Max, level 1: Min, level 2: Max, ...); and the leaves are terminal states carrying utility values. Reading a game tree is reading a game's entire future at once — which is exactly why the size explodes: tic-tac-toe stays drawable, but chess has a branching factor of about 35 and games run about 80 moves deep, so the full tree has roughly $35^{80}$ nodes — a number with more than a hundred digits.

For small problems this game tree can be drawn — not a problem. For larger problems, drawing the full game tree is not possible. But the game tree is very important, because a lot of expert players are believed to visualize several levels in their minds: call this level 0, level 1, level 2, level 3 — some experts, like the chess grandmaster Pragyananda, are able to visualize up to, say, level 2 in their mind, for all combinations, so they are always very proactive: if I make this move, what will he move? That is why they are champions. Computers on the other hand — Deep Blue and so on — can visualize even more levels. But the point here is not to completely generate the search tree. The point is that even if we generate only a little, we carry this notion — my loss is his win, his win is my loss — and with that in mind we try to take paths or moves. That is what adversarial search is.

Real-world: Deep Blue (the chess computer) searched many more levels of the game tree than human grandmasters; grandmasters like Pragyananda compensate with pattern knowledge and anticipation. And note: a minimax-style approach is what the old rule-based chess programs of the early 2000s approximated — the same underlying principles, but with rule engines.

7.2.6 Student Questions and Answers

7.3 The Minimax Algorithm

7.3.1 The Core Idea

The minimax algorithm (some people call it mini-max) is the first algorithm we look at for game playing. Minimax chooses the move that gives the best guaranteed outcome, assuming the opponent also plays optimally. Some casual opponents might not play optimally — they might place the X or the O incorrectly and lose the game — but if someone is playing optimally, they will definitely make sure the game ends in a draw, or they win.

The idea: Max chooses the move with the maximum value; Min chooses the move with the minimum value. This value is a utility or static evaluation value (we will learn where those come from after the examples). The values are backed up from the leaves to the root: a max node takes the maximum of its children's values and a min node takes the minimum:

$$v(n)=\underset{c\in \text{children}(n)}{\max }v(c)\text{at a max node,}v(n)=\underset{c\in \text{children}(n)}{\min }v(c)\text{at a min node.}$$

Every symbol is named: $v(n)$ is the backed-up value of node $n$, $c$ indexes a child of $n$, $\text{children}(n)$ is the set of $n$'s children, and $\max$/$\min$ pick the largest/smallest of those child values. The recursion starts at the leaves (their values are given by the utility function for terminal states, or by static evaluation for cut-off states) and climbs to the root; the move chosen at the root is the one leading to the child with the root's value.

Minimax is one of the oldest algorithms in AI, used generally for two players. We assign one player as Max, who chooses the maximum from the given set of choices; the other player is Min, who chooses the minimum from the same collection. A tree data structure is used; we designate each level as alternating between min and max, and at each level the decision is made by the player. The last level has all the potential outcomes of the game — or it might be given to you as some static values. It is a recursive algorithm.

Why "worst-case best"? The guarantee rests on a bet about the opponent: minimax assumes Min is perfect. Under that assumption, any branch whose worst leaf is bad is a branch that will actually deliver that bad leaf, because Min will steer there. So Max's only rational choice is the branch whose worst leaf is as high as possible — the best guaranteed outcome. If Min turns out to be weaker than perfect, Max only does better; the guarantee never erodes.

Cost of the full tree. Minimax explores the whole game tree down to the leaves. If the maximum depth is $m$ and there are $b$ legal moves at every point, the time complexity is $O(b^m)$ — exponential in depth. That is why the lecture emphasizes partial trees: for chess ($b\approx 35$, $m\approx 80$ moves) the full tree is physically impossible, and real programs cut the tree at some depth and evaluate the cut nodes with static evaluation functions (the topic of 7.4).

7.3.2 Worked Example 1: A Small Tree

Here is a manual game tree with static evaluation values given at the leaves (assume for now these values are given to you; we will see how they are computed later). The root is a max node; its two children are min nodes; each min node has two leaves.

The goal of the minimax algorithm is not to take you to the 7 — the largest. It tells you: I will not take you to the worst. Values are always built from the bottom up.

7.3.3 The Working: In-Order Traversal with Minus and Plus Infinity

Let us work a full tree step by step with the traversal machinery, because this is a very important concept in minimax. The tree: root A (max node) with children B and C (min nodes); B has children D and E (max nodes); C has children F and G (max nodes). Leaves: D has −1 and 8; E has −3 and −1; F has 2 and 1; G has −3 and 4. That is seven nodes (A, B, C, D, E, F, G), with the layer pattern max → min → max → leaves.

We use two concepts: depth-first search, and in-order traversal. In-order traversal means: if there is a node, we first visit the left child, then the root, then the right child — left, root, right. Combined with depth-first search, this fixes the exact order in which nodes are visited: go left as deep as you can, then come back up one level, then go right.

Then apply the traversal and fill the values.

The small trick (but understand the traversal, do not just apply the trick blindly): at a max node pick the maximum of its children, at a min node pick the minimum, and back the values up: max(children of D) = max(−1, 8) = 8; max(children of E) = max(−3, −1) = −1; min(8, −1) = −1; max(2, 1) = 2; max(−3, 4) = 4; min(2, 4) = 2; max(−1, 2) = 2. Same numbers, both routes — the trick is a shortcut for the traversal, not a substitute for understanding why the min node refuses the 8.

What does this tell us? The worst outcomes: if max ends up in the −1 subtree, the leaves are −1 and −3 — even worse for max. Minimax says: I will not take you there. Minimax takes you to 2. It never promised the 8, but it promises you will not end up in the worst possible thing.

7.3.4 Worked Example 2: A Deeper Tree

Now a tree with more layers: the layers alternate max, min, max, min. The leaf pairs, as narrated in the walkthrough, are read at max nodes:

What is the worst utility value here? −10 — and note that −10 was eliminated early: it came up inside the first min node and was cut off there because that was a minimizer node. What is the best possibility? 15. Minimax tells us: I will not take you to 15 — if you go there it is good for you — but I promise you will not end up at −10. How? Because at each step we alternated between the players' moves: max layers picked the maximum of their child pairs, min layers picked the minimum, and that propagation is exactly what eliminated the −10 at the first min level.

The guarantee: minimax will not dump you into the worst possibility. You might end up at the best (15) if the opponent plays badly, but you will never be forced into the worst — and if you do not get the worst or the best but a reasonable choice, that is still better for you. This is exactly what you do in tic-tac-toe: you start the game wanting to win; after a point you say — fine, even if I don't win, I will make sure this person doesn't win. At the start you know you are the maximizer: if you get the 15, grateful, you win. But what if you end up at −10? Then you have lost. So the aim is: let me not go to −10; let me go to 15 if possible; or let me land on 8 or 4 — at least I have not lost the game.

7.3.5 Worked Example 3: A Tree with Three Children

A similar example with multiple children per node.

The in-order traversal story: we go to the first child, update to 3; then 12 is not less than 3, so we do not update; 8 is not less than 3, so we do not update; the moment this part is done, 3 gets updated at the min node. Then we come to the second min node, put the 2, and so on. We are actually doing in-order traversal and putting the numbers, but as a trick it is simpler to directly pick the minimum values and put them, and the max layer picks the maximum. Notice the traversal detail: at a min node, a child value only overwrites the stored value when it is smaller — 12 and 8 both lose to the 3 already stored, and the node's final value is set only after all children are visited.

7.3.6 Layer Ordering and Multiplayer Games

Does the sequence of min and max layers change as per the use case? No. It depends on where you start: if you start with max, it will be max, min, max, min, max, min...; if you started with min, it will be min, max, min, max, and so on. You cannot change them in between. The alternation is forced by who moves when: the player who moves first determines the root's type, and turns strictly alternate from there — a game cannot hand two consecutive moves to the same player.

Will it always be max-min, or could the decision tree have even more depth? It could be the full tree, but we will always focus on some partial part of the tree — what we show can be a part of a full bigger tree. Every example in this section is a slice of a larger tree: the values that matter are the ones in the shown subtree; the full tree simply continues below (or beside) it.

Multiplayer games (three or more players) are not in scope for this course, but they exist. In a three-player game, the outcome is a tuple of utilities, one per player. Player A looks at the first component, player B at the second, player C at the third, and each chooses the move maximizing their own component.

7.3.7 Student Questions and Answers

7.4 Static Evaluation Functions

7.4.1 What a Static Evaluation Function Is

In all the minimax examples, the leaf values were given to us. Where do those values come from? That is the job of the static evaluation function. It is pretty simple — very, very simple to compute. And to be explicit: it is not a heuristic. It is a scoring convention that must be defined for each game — it has to be defined per game, and we pre-compute the notion of how we are calculating it. You can call it very similar to your heuristic values or fitness values: prior itself, we determine and compute it, and for each node we compute the value and see.

The vocabulary correction matters here, because a student's instinct is to call it a heuristic:

In some games you can just count things: the number of X's and O's; from a position, you can compute which positions are better and how many positions you are away from victory. In richer games you assign point values to pieces.

Formally, a static evaluation takes a position and returns a score estimating how favourable the position is for the player whose side is being evaluated. Most practical evaluation functions are weighted sums of features:

$$EVAL(s)=\sum _{i=1}^n{w}_i{f}_i(s)$$

where $s$ is the position, $f_i(s)$ is the $i$-th feature of the position (for example "number of white bishops", "number of black queens"), and $w_i$ is the weight that says how important feature $i$ is. The chess material count below is exactly this formula with one feature per piece type: $f_i$ = count of that piece, $w_i$ = its point value.

7.4.2 Worked Example: Chess Material Count

Take chess, from heuristic evaluations: if there is a queen on the board, give it 9 points; if there is a bishop, give it 3 points; if there is a pawn (soldier), give it 1 point. (These are the classic chess material values — in full, pawn = 1, knight or bishop = 3, rook = 5, queen = 9 — the lecture uses the queen/bishop/pawn subset.)

7.4.3 Student Questions and Answers

Exam note: static evaluation values are handed to you in minimax problems — but you must know how they are computed (piece counts, material values, distance-from-victory counts) because next session starts exactly from here: how these values come about, and then alpha-beta pruning. Alpha-beta pruning is the technique that lets minimax skip whole subtrees (like the second and third children of a node whose fate is already decided) without changing the answer — the lecture announced it as the natural next step after static evaluations.

Exam Guidance Summary

Syllabus and scope. The mid-semester syllabus runs until everything covered by the next session: the Introduction to AI module, the Problem Solving Agent using Search module, and this Game Playing module (neural architecture search, adversarial search, game trees, static evaluation, minimax — plus whatever remains next session). Right after the eighth session, the sample papers and the detailed exam syllabus announcement will be posted — give them a glance, but do not take them too seriously: questions are never repeated from past papers, and there is a lot of reverse engineering that can happen when students see sample questions early. The sample papers are intentionally not shared in advance because students get biased by seeing sample questions. The topics get marks proportional to the class time spent on them; the game playing module is examinable for the mid-semester.

Practice material. Every set of course materials has exercises at the end; there is a minimax practice question, and the image captioning problem is the worked practice for CoDeepNEAT — work the first iteration fully yourself (phenotype construction, fitness evaluation, selection, crossover, mutation). The extra numericals are the same style as the exam. Expect the algorithmic search material (A, and variants — vanilla algorithms have variants like IDA, or beam search with restart and best K) and expect a minimax-style computation with static evaluation values: back the values up through a small tree by hand — practice the in-order traversal with ±∞ initialization and the direct min/max trick. For the minimax numericals, the static evaluation values are given in the problem and are precomputed per game.

Course logistics. After game playing, the remaining modules (logic, probability, reasoning over time, ethics) are post-mid-semester. There are no extra classes planned — the course is on track; if needed, the syllabus will be reduced rather than rushed. The quiz policy: the quiz grade is the best of two quizzes, and plagiarism is monitored by the system — several cases were already spotted, so do not do it.

The assignment. The design document should explain your design approach — what the problem statement asks, how you arrived at the algorithm, what data structures you used, why you chose that algorithm over alternatives (for example, why A* and not BFS), screenshots of your outputs, and the performance of your solution. If complexity analysis is asked in the problem statement, do it in one of two ways: asymptotic with Big-O notation, or time it in your Python function over multiple runs and give the average. Implement generically — never hardcode the example; one input file holds one test case; if the graph has multiple equal-cost optimal paths, print both. If the expected output pattern is missing from a problem statement, state your assumption in the design document and provide your own input.txt/output.txt pair in the zip.

How to use this section. For each concept in this lecture, ask: can I work the numerical (minimax tree, roulette-wheel probabilities, image-captioning first iteration) from scratch? The exam favours exactly the numericals that were shown in class — the minimax computation with static evaluation values and the genetic-algorithm first iteration for CoDeepNEAT.

Key Industry Applications

• Automatic architecture design (CoDeepNEAT): deployed for image generation, image classification, speech recognition, and medical analysis. The medical example is the strongest: evolutionary search has produced novel architectures that human doctors and engineers never conceived, because humans are limited by prior knowledge. The original CoDeepNEAT paper itself shipped a working production system — an image-captioning service for a major online magazine, where the evolved network (repeated LSTM modules, summing merges, skip connections) outperformed a hand-tuned baseline on BLEU and CIDEr metrics.
• Modular deep learning: ResNet and GoogLeNet are production examples of repeated, well-organized blocks; CoDeepNEAT's blueprint-module split automates exactly this reuse philosophy. When a module proves itself during evolution, it can be plugged into any blueprint that points to its species — the same way ResNet blocks are repeated dozens of times in production models.
• Microservices-style collaboration: modules evolved by different people or teams can be assembled by someone else at phenotype-construction time — the same division of labor as microservices development. Module development, like service development, is parallelizable across teams; assembly happens against a fixed blueprint contract.
• Image captioning: CNN feature extraction + LSTM text generation + dense+softmax modules, scored by BLEU (bilingual evaluation understudy) — a realistic production pipeline for automatic captions. Beyond captions, the same module repertoire (feature extraction, sequence generator, classifier head) appears in image search, video description, and accessibility tooling for screen readers.
• Game AI history: Deep Blue searching deeper game trees than human grandmasters; early-2000s rule-based computer chess using the same minimax-style principles through rule engines; the Transformers/ChatGPT wave made AI a buzzword, but game-playing AI is decades old. Grandmasters like Pragyananda compensate with pattern knowledge and anticipation, where machines compensate with raw search depth.
• Multi-agent systems: adversarial search underpins modern multi-agent critique architectures, where one agent earns utility for successfully critiquing another. The zero-sum logic of the lecture (my gain is your loss, block the opponent's best response) appears in everything from adversarial training of generative models to multi-agent systems with competing objectives.
• Zero-sum thinking in life: interviews, promotions — situations where one person's gain is another's loss, modeled directly by two-player zero-sum games. The minimax discipline applies to them too: when you cannot guarantee winning, the rational objective is the best guaranteed outcome — ensure the other person is not winning.