Generating Dense Boggle Boards with Genetic Algorithms
Overview
The problem of generating dense boards for the game of Boggle,
i.e., board configurations that have very high total scores, is a
challenging and fun domain for exploring local search methods. Some
methods, such as genetic algorithms, can be very effective for
manipulating board configurations to yield increasingly higher scores.
A genetic algorithm is a type of stochastic beam search in
which components from pairs of potential solutions from a population
at time t can be combined to produce new pairs of potential
solutions for the population at time t+1. Genetic algorithms
are well suited for finding dense Boggle boards since it is
impractical to exhaustively maintain an increasing number of candidate
solutions, and since information gained along one local search path
can be meaningfully integrated with information gained along other
paths.
The aim of this project is to develop a system for generating dense
Boggle boards. The project will focus on using genetic algorithms to
find such boards. (Of course, other approaches, such as simulated
annealing, can be very effective as well.)
Objectives
The learning objectives include the following:
- Understanding the general concepts of genetic algorithms
- Implementing those concepts in a program that finds dense Boggle boards
- Exploring how different representations as well as crossover
and mutation operators affect the performance of a genetic algorithm
Prerequisites
One should have an understanding of fundamental data structures,
including trees and hash tables, and how to use them in a high-level
language such as Java or Lisp. One should also understand basic
informed and uninformed search algorithms.
Background
For an introduction to genetic algorithms, one can read the
corresponding sections or chapters in an AI or machine learning
textbook. For example, one might assign one or both of the following:
- Stuart Russell and Peter Norvig. Artificial Intelligence: A
Modern Approach, 2nd edition, Section 4.3. Prentice Hall, 2003.
- Tom Mitchell. Machine Learning, Chapter 9. McGraw-Hill, 1997.
For an introduction to the game of Boggle, one can visit one or both
of the following sites:
Description
The detailed project description is available in the PDF file boggle_project.pdf. You
will need the free Adobe Acrobat Reader to view this file.
This project is customizable to accommodate different approaches to
teaching and different implementations. Additional exercises are also
included for students seeking more extended challenges.
Syllabus
A sample syllabus used at Middlebury College when this project was
assigned is available at: Syllabus
for AI Course at Middlebury College.