Project MLExAI: Projects - 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.)

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.

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.

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. Prentice Hall, Upper Saddle River, NJ, USA, 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:

Boggle product page.
The online WEBoggle game.

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.

A sample syllabus used at Middlebury College when this project was assigned is available at:
Syllabus for AI Course at Middlebury College

Additional readings are included in the Background section above.