COMP 3200 - Intro to Artificial Intelligence - Lecture 14 - Assignment 4
Overview
Dave Churchill explains COMP 3200 Assignment 4, which uses a genetic algorithm to evolve Sudoku boards and asks students to implement evolution, roulette-wheel selection, crossover, mutation, and a stronger Sudoku fitness function. The same JavaScript algorithm also drives demonstrations such as cars, trebuchets, pole-cart policies, lunar landers, and image reconstruction, illustrating how representation, fitness, selection pressure, diversity, and local optima affect optimization.
Key takeaways
- A 9×9 Sudoku board can reach a high default score of up to 243 even when randomly generated, leaving the best candidate less than twice as likely as the worst to be selected by roulette wheel; a useful fitness redesign must sharply increase selection pressure.
- Elitism preserves the best known individual across generations, while random insertion protects diversity; eliminating either mechanism can respectively lose progress or leave the population with too little variation.
- Genetic algorithm performance depends on representation as well as operators: discretizing the pole-cart state space into two bins can make a policy easier to find than using four bins, even though the coarser policy has less detail.
- The same genetic algorithm can optimize Sudoku boards, simulated vehicle designs, trebuchet parameters, game policies, and image primitives by changing the genome representation and fitness function.
- For 81-gene Sudoku genomes, half-and-half crossover must deliberately handle the odd length, and mutation must recalculate cached fitness after changing a gene.
Chapters
- A standard 9×9 Sudoku solution uses the numbers 1 through 9 once in every row, column, and 3×3 box.
- Unlike a human Sudoku puzzle, Assignment 4 provides no prefilled clues: the genetic algorithm must evolve a complete valid board.
- Churchill uses Sudoku because its genome-to-board mapping and conflicts are easy to inspect, while reaching a complete solution remains difficult.
- The interface colors cells according to conflicts in their row, column, and 3×3 box: white means no conflicts and darker red means more.
- The color visualization is diagnostic only; it does not determine the genetic algorithm’s fitness.
- Sudoku can have boards that look close to solved but require disruptive changes, creating local optima that make progress to a complete solution difficult.
- The graph plots maximum, average, and minimum population fitness against generation number.
- The interface runs one generation per frame by default, about 60 generations per second, and can run multiple generations per frame.
- The maximum fitness often rises quickly and then plateaus, demonstrating how a Sudoku population can get stuck near a local optimum.
- A larger population can increase genetic diversity and improvement per generation, but approximately increases the computation required per generation as well.
- Mutation rate controls the chance that an individual is changed; a 25% rate corresponds to testing whether a random value from 0 to 1 is below 0.25.
- Random-gene insertion adds wholly new individuals, while elitism copies the highest-fitness individuals into the next generation.
- With elitism above zero, the historical maximum fitness cannot decrease; without it, the maximum can fluctuate downward.
- For a population of 100 with 10% random insertion and 5% elitism, the next generation starts with 10 random individuals and 5 copied elites, then adds 85 offspring.
- The interface can swap the fitness function without changing the genetic algorithm, demonstrating that the algorithm optimizes whichever objective it is given.
- Test objectives include maximizing array values, matching row or column indices, and creating a checkerboard pattern; these are easier convex-style tasks than Sudoku.
- The default Sudoku score awards up to three points per cell for uniqueness in its row, column, and box, with a maximum of 243 for a 9×9 board.
- Random boards can receive more than half the maximum score, so roulette-wheel selection may make the best individual less than twice as likely to be selected as the worst.
- Students must devise a stronger nonnegative fitness function that creates more selection pressure without using population-wide statistics or simply raising scores to an exponent.
- The interface includes Sudoku, cars, trebuchets, pole-cart, lunar lander, triangles, and brushstrokes.
- Students are graded primarily on Sudoku and the test fitness functions, but the other environments demonstrate that the same genetic algorithm can optimize very different representations.
- Each environment supplies its own genotype and fitness function through the settings interface.
- A car genome controls the body shape, chassis density, wheel radii, wheel attachment locations, and wheel densities.
- A physics simulation evaluates each design by how far it travels along the track.
- Track difficulty changes with terrain height; more hills make the task harder, and apparently sensible designs can perform poorly because the physics interactions are nonlinear.
- The trebuchet genome encodes arm lengths, axle height, counterweight mass and hanger length, sling length, and release angle.
- A simulation measures the flight path and rewards designs that throw farther; some individuals throw backward or fail to release.
- The example illustrates how genetic optimization could help explore an engineering design before constructing a physical device, assuming the simulation is accurate.
- The pole-cart task changes the genome from a designed object to a policy mapping environment states to left, right, or no action.
- The state includes cart position and velocity, pole angle, and pole angular velocity; continuous values are divided into bins to make a finite policy table.
- More bins provide finer control but greatly expand the search space; fewer bins are faster to search but can lose useful distinctions.
- Churchill demonstrates that a coarse two-bin representation can balance the pole better than a four-bin version because the smaller policy space is easier to explore.
- The lunar lander policy chooses left, right, and upward thrust based on binned position, velocity, angle, and angular velocity.
- The handcrafted score awards up to 40 points for landing near the center, up to 40 for low landing speed, and 100 additional points for surviving.
- The interface shows an evolved policy landing a spacecraft despite the genetic algorithm receiving only integer-valued policy genes, not explicit rocket-physics knowledge.
- Each triangle encodes vertex coordinates and color, and the population evolves a layered approximation of a loaded image.
- Using only 10 triangles limits image detail, while increasing the count, for example to 90, expands the search and slows optimization.
- Churchill shows his cat Stella as an example and notes that a long run can produce recognizable details through unexpected triangle placements.
- A brushstroke genome encodes each stroke’s position, angle, thickness, and color to approximate a target image.
- Random brushstrokes have very low fitness compared with a good reconstruction, creating a much larger fitness gap than the default Sudoku score.
- Removing elitism can still lower the maximum score, but the brushstroke population is less destabilized because good and random individuals have more distinct fitness values.
- Increasing random insertion lowers average fitness; removing random insertion raises the minimum but also reduces diversity needed for recombination.
- Adding more random individuals lowers the average fitness because weak random candidates make up a larger share of the population.
- Removing random individuals raises the minimum fitness and, consequently, the average, but can leave too little genetic diversity.
- Increasing elitism can improve the average by copying strong individuals, yet an overly elite-heavy population may lack variation for producing better offspring.
- The assignment includes environment files, but students can focus on the Sudoku environment and GA student code.
- The required functions are GA evolution, roulette-wheel selection, crossover, individual mutation, and a revised Sudoku fitness function.
- The user interface initializes random populations and runs generations indefinitely; students implement the core evolution steps rather than the UI loop.
- The Sudoku environment stores a board as a one-dimensional array of size squared; a 9×9 board therefore contains 81 values.
- Its get and set helpers map row and column coordinates to array indices; row corresponds to the vertical coordinate and column to the horizontal coordinate.
- GA settings provide population size, mutation and elitism ratios, a fitness-function reference, individual size, and legal gene values.
- For standard Sudoku, legal gene values are 1 through 9, and the settings helper can return a random legal value for initialization or mutation.
- The starter Sudoku fitness sums each cell’s uniqueness in its row, column, and box, producing a score from 0 to 243 for a standard board.
- The revised score must remain nonnegative and assign higher fitness to better boards because roulette-wheel selection uses fitness proportionally.
- Each population member is a JavaScript object containing a gene array and its cached fitness value, rather than a bare array.
- A changed gene must have its fitness recalculated so selection and graph values stay consistent.
- GA evolution creates a new population, sorts the current population by descending fitness, and copies the requested number of top individuals as elites.
- The number of elites and random individuals is computed by multiplying the population size by the corresponding ratio.
- Random individuals are built by filling an array of individual size with values from the settings helper, then computing their fitness.
- The remaining slots are filled with offspring until the new population reaches its target size.
- The sum of current population fitnesses is computed once and passed to repeated roulette-wheel selections to avoid redundant summation.
- Two parents are chosen independently, so the same individual may be selected twice.
- Crossover creates two children by combining the first half of one parent with the second half of the other, then reversing the parent order for the second child.
- For an 81-value Sudoku genome, crossover must split at 40/41 or 41/40 so every child retains exactly 81 genes.
- Mutation tests a random number from 0 to 1 against the mutation rate; when triggered, it changes one random gene position to a random legal value.
- Mutation modifies the individual in place, so its fitness must be recalculated only after a mutation occurs.
- Each parent pair produces two children, but the evolution loop must skip the second child when only one population slot remains.
- The simple random-value mutation works across environments, while swapping Sudoku cells could help Sudoku but harm other genome types.
- The genetic algorithm should solve 2×2 Sudoku easily, make visible progress on 9×9 Sudoku, and solve the non-Sudoku test fitness functions.
- The fitness-over-time graph should behave intuitively as population, mutation, random insertion, and elitism settings change.
- All core functions must work together: a broken roulette-wheel selector or crossover can prevent the algorithm from earning performance marks.
- Churchill advises prioritizing a clear, stronger Sudoku fitness function and observable progress over attempting to force a full 9×9 solution.
Transcript excerpt
0:00 Let's get into assignment four. But before I show the assignment, I'm going to quickly go over some Sudoku stuff. So, uh, I have, uh, not I guess not a surprise because it would only be a surprise if you were expecting something, but assignment four will still be about Sudoku, but I'll have a little bit of a surprise on the end. Uh, a bit of a cooler part to the assignment as well in addition to Sudoku. But the reason we're using um a genetic algorithm for sudoku solving is because I believe it's a very intuitive easy way to understand what's going on. The genotype to phenom phenotype mapping is very simple and intuitive. You all can get a 2D array and translate in uh that into a 1D array pretty easily. Um and I'll show the actual assignment, but
0:47 just very quickly who here has uh who has ever done a sudoku? Hopefully pretty much everybody. Okay, I'm going to for the one or two people who maybe haven't, I'm going to very quickly go over the rules to Sudoku and explain how our assignment is producing a Sudoku board, but it's not the same as a Sudoku like this where um so Sudoku typically played on a 9 by9 grid. And the way that it works is that your end result that you want is to have the the numbers 1 through nine um each appear in each row, each column, and each 3x3 square um within the board. And the typical way that a sudoku problem is given to you is that you are given a partially filled out sudoku board and then you have to as
1:35 the human figure out where the numbers go um around these numbers that are already put in there. So that's not
This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.
In this course
Related notes
Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Dave Churchill.