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

summary

In this chapter we introduced an application of binary search and some algo-
rithmic techniques that are commonly used in solving word search puzzles
and in game-playing programs such as Chess, Checkers, and Othello. The top
programs for these games are all world class. The game of Go, however,
appears too complex for computer searching.

key concepts

alpha-beta pruning A technique used to reduce the number of positions that
are evaluated in a minimax search. Alpha is the value that the human
player has to refute, and beta is the value that the computer has to refute.
(431)
minimax strategy A recursive strategy that allows the computer to select an
optimal move in a game of Tic-Tac-Toe. (427)
refutation A countermove that proves that a proposed move is not an improve-
ment over moves previously considered. If we find a refutation, we do not
have to examine any more moves and the recursive call can return. (428)
terminal position A position in a game that can be evaluated immediately.
(428)
transposition table A map that stores previously evaluated positions. (431)
word search puzzle A program that requires searching for words in a two-
dimensional grid of letters. Words may be oriented in one of eight direc-
tions. (422)

common errors

When using a transposition table, you should limit the number of stored
positions to avoid running out of memory.

1.

Verifying your assumptions is important. For instance, in the word search
puzzle, be sure that the dictionary is sorted. A common error is to forget
to check your assumptions.

2.

on the internet

Both the word search and the game Tic-Tac-Toe are completely coded,
although the interface for the latter leaves a little to be desired.

WordSearch.java Contains the word search puzzle algorithm.