Best Boggle board found (score: 4410)
January 2009

Written as my IB Extended Essay in Computer Science.

### Abstract

This paper's objective is to find efficient, parallelizable
techniques of solving global optimization problems. To do this, it
uses the specific problem of optimizing the score of a Boggle
board.

Global optimization problems deal with maximizing or minimizing a
given function. This has many practical applications, including
maximizing profit or performance, or minimizing raw materials or
cost.

Parallelization is splitting up an algorithm across many different
processors in a way that allows many pieces of work to run
simultaneously. As parallel hardware increases in popularity and
decreases in cost, algorithms should be parallelizable to maximize
efficiency.

Boggle is a board game in which lettered cubes are shaken onto a
4-by-4 grid. The objective is to find words spelled by paths through
the grid. The function to maximize is the sum of the scores of all
possible words in the board.

In this paper, the performance of two algorithms for global
optimization is investigated: hill climbing and genetic
algorithms. Genetic algorithms, which model evolution to find the
fittest solutions, are found to be more efficient because they are
non-greedy. In addition, a modified genetic algorithm called the
coarse-grained distributed genetic algorithm (DGA) is
investigated. This algorithm can take advantage of multiple computers,
running several semi-independent copies of the algorithm in parallel
to provide extra genetic diversity and better performance. The success
of the coarse-grained DGA shows that global optimization problems can
benefit significantly from parallelization.

Investigating these genetic algorithms revealed several
modifications that are beneficial to global optimization. These
modifications solve the problem of premature convergence (a loss of
genetic diversity). Several techniques to solve this problem are
investigated, notably incest prevention and migration control,
revealing a very significant performance increase.

### Download

Download this paper as
PDF or LaTeX

### Source code

The source code for DistBoggle, the collection of tools used in
this paper, is available on
GitHub.