Fun and games - Data Structures and Problem Solving Using Java - page 440

IN PRACTICE
10.5

For the word search problem, replace the binary search with a sequen-
tial search. How does that change affect performance?

Compare the performance of the word search algorithm with and
without the prefix search.

10.6

Replace the HashMap with the TreeMap in the Tic-Tac-Toe program and
compare the performance of the two versions.

10.7

Even if the computer has a move that gives an immediate win, it may
not make it if it detects another move that is also guaranteed to win.
Some early chess programs had the problem that they would get into
a repetition of position when a forced win was detected, allowing the
opponent to claim a draw. In the Tic-Tac-Toe program this outcome is
not a problem because the program eventually will win. Modify the
Tic-Tac-Toe algorithm so that when a winning position is found, the
move that leads to the shortest win is always taken. You can do so by
adding 9-depth to COMPUTER_WIN , so that a quicker win gives the highest
value.

10.8

Compare the performance of the Tic-Tac-Toe program with and with-
out alpha-beta pruning.

10.9

Implement the Tic-Tac-Toe algorithm and measure the performance
when various depths are allowed to be stored in the transposition
table. Also measure the performance when no transposition table is
used. How are the results affected by alpha-beta pruning?

10.10

PROGRAMMING PROJECTS
10.11

Write a program to play 5 × 5 Tic-Tac-Toe, where 4 in a row wins.
Can you search to terminal nodes?

The game of Boggle consists of a grid of letters and a word list. The
object is to find words in the grid subject to the constraint that two
adjacent letters must be adjacent in the grid (i.e., north, south, east, or
west of each other) and each item in the grid can be used at most once
per word. Write a program to play Boggle.

10.12

Write a program to play MAXIT. The board is represented as an
N × N grid of numbers randomly placed at the start of the game. One
position is designated as the initial current position. Two players
alternate turns. At each turn, a player must select a grid element in the
current row or column. The value of the selected position is added to
the player's score, and that position becomes the current position and

10.13