Solution in the doctor's exact framing from transcript 23 (cuckoo + coevolution intro), lines 425-585.
Instead of encoding "move tile 5 right", the doctor's preferred design encodes movement of the blank space. This forces the alphabet to exactly four symbols regardless of which numbered tile is being moved.
The question itself gives away the answer: the hardest 8-puzzle instance solves in 31 moves. So the chromosome is a fixed-length string of 31 genes:
Using exactly 31 ensures every chromosome can represent any solution. Shorter would lose hard instances; longer would inflate the search space unnecessarily.
Add a fifth symbol "STOP" so chromosomes can self-terminate if the goal is reached before move 31. Without it, a chromosome that solves the puzzle in 12 moves wastes the next 19 genes; with STOP, the GA can evolve shorter solutions naturally.
Never let two consecutive moves be a U-then-D or L-then-R pair - they cancel each other and waste 2 of your 31 slots.
Enforce after every mutation and crossover. If a dance pair appears, repair (re-mutate, or replace with a non-cancelling move).
Apply the chromosome's move sequence to the initial board, then measure the distance of the resulting board from the goal state. Minimisation.
| Option | How | Comment |
|---|---|---|
| Misplaced tiles | Count tiles not in their goal position. Maximum = 8. | Simple but coarse - many chromosomes get the same score. |
| Manhattan distance (preferred) | For each tile, sum (row distance + column distance) from current position to goal position. | Smoother gradient. Gives selection pressure something to bite on. Same "sensitivity to changes" principle the doctor applied to bin packing. |
Some chromosomes contain moves that are infeasible at runtime - e.g. L when the blank is already in the leftmost column. Four strategies the doctor walked through (lines 545-570):
| Strategy | How | When to choose |
|---|---|---|
| High penalty | Add the worst possible value to fitness for each invalid move encountered. | Simple to implement; loses gradient toward feasibility. |
| Stop early | When the first invalid move is hit, freeze the board and evaluate from there. | Cheap; chromosomes ending in invalid moves get penalised by remaining distance. |
| Repair | Transform the invalid move into a feasible one. The doctor's exact example: U U becomes U R. | Cleanest. Chromosome stays semantically meaningful. |
| Ignore / discard | Skip the invalid move and continue with the next gene. | Lightest to implement; effectively shortens the move sequence. |
Pick one gene at random and replace it with a different symbol from {U, D, L, R}.
The chromosome is not a permutation. Each gene is just a value over a 4-symbol alphabet, and the same symbol can repeat freely. So the natural mutation is to change one move into a different move.
Swap only rearranges the moves already in the chromosome - it never introduces a new direction. If the initial population happens to never contain a "U" at position 7 (which is exactly the position needed), swap mutation can never introduce one. It can only shuffle the existing moves around.
Default ~1/L = 1/31 ≈ 0.03 (one mutation per chromosome on average), or slightly higher (0.05-0.10) since the search space is small and exploration is cheap.
If mutation produces an immediate U-D or L-R dance pair, repair it (re-mutate or replace with a non-cancelling direction).
Single-point or two-point crossover on the move sequence at a moderate-to-high rate (~0.7-0.9).
The chromosome has positional semantics (move at step i is a specific event in time) but every position holds the same kind of value. Cuts are apple-to-apple - the slots are interchangeable. Single-point preserves large schemata of "useful move sub-sequences"; two-point lets you transplant a middle segment.
Uniform (per-gene flip-coin) crossover at 50/50 is essentially random sampling. Schemata are destroyed every generation.
For the 8-puzzle this is doubly bad: the offspring is likely to produce U-then-D or L-then-R dance pairs at the boundaries between inherited single-gene segments, wasting moves.
Those operators exist for permutation chromosomes (no duplicates allowed). This chromosome has no uniqueness constraint, so simple cut-and-paste crossovers are sufficient and faster.
~0.7 to 0.9 - moderate to high. The chromosome is long and parents must share material to make progress.
| Component | Choice | One-line reason |
|---|---|---|
| Chromosome | Length-31 string over {U, D, L, R} (+ optional STOP) | Worst-case length given by problem; 4 symbols span every blank-move |
| Objective | Manhattan distance to goal (minimise) | Smoother gradient than misplaced-count |
| Invalid moves | Repair (UU -> UR) or ignore | Keeps search space tight, chromosome stays meaningful |
| Selection | Tournament size-2 with replacement | Robust for minimisation; weak still has a chance |
| Crossover | 1-point or 2-point at rate ~0.8 | Apple-to-apple cuts; preserves move-sequence schemata |
| Mutation | Value replacement at rate ~1/31 | Swap loses reachability; value-replacement preserves it |
| Elitism | Small (1-3%) | Keep the best safe from operator noise |
| Population size | Moderate (50-100) | Balance exploration and refinement under fixed budget |
| Stopping | Manhattan distance = 0 (goal reached) OR budget exhausted | Standard |
The doctor introduced this immediately after the standard 8-puzzle GA solution (transcript 23 lines 570+, continued in transcript 24). If the final exam stacks a coevolution part on top:
Without these, the GA collapses everyone onto the easiest goal and wastes 2/3 of the budget.
I encode the 8-puzzle chromosome as a fixed-length sequence of 31 moves over the alphabet {U, D, L, R}, where each gene specifies a movement of the blank space (not of a numbered tile). I add an optional STOP sentinel so the chromosome can terminate early. The objective function is the Manhattan distance from the resulting board to the goal state after applying the move sequence, minimised. Invalid moves (e.g. moving the blank left when it is already in the leftmost column) are repaired into the nearest feasible move. For mutation I use value replacement on a randomly chosen gene at rate roughly 1/31; I do not use swap mutation because the chromosome is not a permutation and swap would lose reachability of any direction never seen in the initial population. For crossover I use single-point or two-point at rate around 0.8; I do not use uniform crossover because it shatters schemata and produces dance pairs of U-D and L-R at the segment boundaries. Selection is tournament size-2 with replacement; elitism is small (1-3%). The GA stops when Manhattan distance reaches zero or the budget is exhausted.