Description

In the game of Ghost, two players take turns building up a word from left to right. Each player contributes one letter per turn. The goal is to not complete the spelling of a word: if you add a letter that completes a word (of 4+ letters), or if you add a letter that produces a string that cannot be extended into a word, you lose. (Bluffing plays and "challenges" may be ignored for the purpose of this puzzle.)

Write a program that plays Ghost optimally against a human, given the following dictionary: WORD.LST. Allow the human to play first. If the computer thinks it will win, it should play randomly among all its winning moves; if the computer thinks it will lose, it should play so as to extend the game as long as possible (choosing randomly among choices that force the maximal game length). A simple console UI will suffice.

In your submission email, answer this question: if the human starts the game with 'n', and the computer plays according to the strategy above, what unique word will complete the human's victory?

Optional Bonus: Write a Java web application that provides a basic GUI to play Ghost against the optimal computer player on the web. Your web page should access a Java servlet using JavaScript's XMLHttpRequest object, and display the results using DOM manipulation.

If you do the bonus, please submit a WAR file, configuration instructions, your source code, and any comments on your approach. Your application will be tested with Tomcat 5.5.x on Sun's J2SE 6.0 and a recent version of Firefox.

(This puzzle description is © ITA Software.)

Solution

(To keep this description as concise as possible, JavaDoc comments are not included. They are available in the file ghost.tar.gz.)

The first step is to load the data from WORD.LST into an appropriate data structure. Only words of four or more letters should be loaded. Words that begin with shorter words should be either removed or not loaded at all.

package ita.ghost; import java.util.logging.Logger; public class GhostGame { private static Logger logger_ = Logger.getLogger(GhostGame.class.getName()); private GhostDictionary dictionary_ = null; public GhostGame(String fileName) { dictionary_ = new GhostDictionary(fileName); logger_.info("Dictionary of size " + dictionary_.size() + " created."); if (dictionary_.size() == 0) throw new RuntimeException("Unable to load dictionary from " + fileName + "."); } public static void main(String args[]) { if (args.length == 1) GhostGame game = new GhostGame(args[0]); else logger_.info("Usage: java " + GhostGame.class.getName() + " "); } } // end GhostGame

The obvious implementation is to build a tree of words, branching at each letter. Optimal play can be computed by traversing the tree.

The standard Java libraries don't provide tree and node classes, so I'll implement a simple, problem-specific LetterNode class for use of the GhostDictionary.

package ita.ghost; import java.util.HashMap; import java.io.BufferedReader; import java.io.FileNotFoundException; import java.io.FileReader; import java.io.IOException; import java.util.logging.Logger; public class GhostDictionary { private static final int MIN_WORD_LENGTH = 4; private static Logger logger_ = Logger.getLogger(GhostDictionary.class.getName()); private HashMap words_ = new HashMap(); private void addWord(String word) { if (word.length() >= MIN_WORD_LENGTH) { LetterNode node = words_.get(Character.valueOf(word.charAt(0))); if (node == null) words_.put(Character.valueOf(word.charAt(0)),new LetterNode(word)); else node.addWord(word); } } public GhostDictionary(String fileName) { try { BufferedReader reader = new BufferedReader(new FileReader(fileName)); String word = null; while ((word = reader.readLine()) != null) addWord(word); } catch (FileNotFoundException fileNotFoundException) { logger_.severe("File " + fileName + " not found."); } catch (IOException ioException) { logger_.severe("Error reading file: " + ioException.toString()); } } public int size() { int count = 0; for (LetterNode node : words_.values()) count += node.leafNodeCount(); return count; } } // end GhostDictionary

LetterNode is a simple n-ary tree node that holds a single character.

package ita.ghost; import java.util.HashMap; import java.lang.IllegalArgumentException; import java.util.logging.Logger; public class LetterNode { private static Logger logger_ = Logger.getLogger(LetterNode.class.getName()); private char letter_; private HashMap nodes_ = new HashMap(); public LetterNode(String word) { if (word.length() > 0) letter_ = word.charAt(0); if (word.length() > 1) nodes_.put(Character.valueOf(word.charAt(1)), new LetterNode(word.substring(1))); } public void addWord(String word) throws IllegalArgumentException { if (word.charAt(0) == letter_) { if (!nodes_.isEmpty()) { if (word.length() == 1) nodes_.clear(); else { LetterNode nextNode = nodes_.get(Character.valueOf(word.charAt(1))); if (nextNode == null) nodes_.put(Character.valueOf(word.charAt(1)), new LetterNode(word.substring(1))); else nextNode.addWord(word.substring(1)); } } } else throw new IllegalArgumentException("Invalid first letter."); } public boolean isLeafNode() { return nodes_.isEmpty(); } public int leafNodeCount() { int leaves = 0; if (isLeafNode()) leaves = 1; else for (LetterNode node : nodes_.values()) leaves += node.leafNodeCount(); return leaves; } } // end LetterNode

Compiling and running with java ita.ghost.GhostGame WORD.LST creates a dictionary of 43,622 words out of the 173,528 in WORD.LST.

The next step is the code for game play. GhostGame needs a few methods to mediate play via a very simple state machine that switches between two players as long as there is no winner:

private GhostPlayer[] players_ = new GhostPlayer[2]; private int currentPlayerIndex_ = 0; private StringBuffer wordInPlay_ = new StringBuffer(); private boolean gameOver_ = false; private GhostPlayer winner_ = null; . . . public GhostGame(String fileName,GhostPlayer playerOne,GhostPlayer playerTwo) { dictionary_ = new GhostDictionary(fileName); if (dictionary_.size() == 0) throw new RuntimeException("Unable to load dictionary from " + fileName + "."); players_[0] = playerOne; players_[1] = playerTwo; } private int switchPlayer() { return (currentPlayerIndex_ = ++currentPlayerIndex_ % 2); } private void addLetter(char letter) { wordInPlay_.append(letter); if (dictionary_.isFullWord(wordInPlay_.toString()) || !dictionary_.isWordStem(wordInPlay_.toString())) { gameOver_ = true; winner_ = players_[switchPlayer()]; } } public GhostPlayer play() { while (!gameOver_) { addLetter(players_[currentPlayerIndex_].play(wordInPlay_.toString())); switchPlayer(); } return winner_; }

The test harness has to change as well:

public static void main(String args[]) { if (args.length == 3) { try { GhostPlayer playerOne = (GhostPlayer)Class.forName(args[1]).newInstance(); GhostPlayer playerTwo = (GhostPlayer)Class.forName(args[2]).newInstance(); GhostGame game = new GhostGame(args[0],playerOne,playerTwo); GhostPlayer winner = game.play(); logger_.info(winner.name() + " wins!"); } catch (Exception e) { logger_.severe("Unable to initialize GhostGame: " + e.toString()); } } else logger_.info("Usage: java " + GhostGame.class.getName() + " word-list player-one player-two"); }

All players implement the GhostPlayer interface. I'll start with just a human player interacting via the console:

package ita.ghost; public interface GhostPlayer { public String name(); public char play(String wordInPlay); } // end GhostPlayer . . . package ita.ghost; import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.logging.Logger; public class HumanConsolePlayer implements GhostPlayer { private static Logger logger_ = Logger.getLogger(HumanConsolePlayer.class.getName()); private String name_ = "HumanConsole"; public HumanConsolePlayer() { } public String name() { return name_; } public char play(String wordInPlay) { if (wordInPlay.length() == 0) System.out.print("Pick your first letter: "); else System.out.print("Pick your next letter: " + wordInPlay); char letter = '\0'; try { BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); letter = (char)reader.read(); } catch (IOException e) { logger_.severe("Error reading from System.in: " + e.toString()); } return letter; } } // end HumanConsolePlayer

Running this with:

java ita.ghost.GhostGame WORD.LST ita.ghost.HumanConsolePlayer ita.ghost.HumanConsolePlayer

allows a game to be played from the console between two human players.

The final step is a simple matter of implementing the computer player.

According to the puzzle description, "If the computer thinks it will win, it should play randomly among all its winning moves; if the computer thinks it will lose, it should play so as to extend the game as long as possible (choosing randomly among choices that force the maximal game length)." A winning word for any player is one where that player can force the path through the tree of words to arrive at that word in the final turn.

My implementation plays the first forced win it finds. If no forced win is found, it plays the longest word available.

package ita.ghost; import java.util.Collection; import java.util.Iterator; import java.util.logging.Logger; public class ComputerPlayer implements GhostPlayer { private static final String DEFAULT_DICTIONARY_FILE = "WORD.LST"; private static Logger logger_ = Logger.getLogger(ComputerPlayer.class.getName()); private String name_ = "ComputerPlayer"; private GhostDictionary dictionary_ = new GhostDictionary(DEFAULT_DICTIONARY_FILE); public ComputerPlayer() { } public String name() { return name_; } public LetterNode forcedWin(LetterNode node) { LetterNode winningChild = null; for (LetterNode child : node.children().values()) { if (!child.isLeafNode()) { winningChild = child; for (LetterNode grandChild : child.children().values()) if (!(grandChild.isLeafNode() || (forcedWin(grandChild) != null))) { winningChild = null; break; } } if (winningChild != null) break; } return winningChild; } public LetterNode longestWord(LetterNode node) { LetterNode longestChild = null; for (LetterNode child : node.children().values()) if ((longestChild == null) || (child.maximumLength() > longestChild.maximumLength())) longestChild = child; return longestChild; } public char play(String wordInPlay) { char nextLetter = 'x'; LetterNode node = dictionary_.terminalNode(wordInPlay); if (node != null) { LetterNode forcedWin = forcedWin(node); if (forcedWin != null) nextLetter = forcedWin.letter(); else nextLetter = longestWord(node).letter(); } return nextLetter; } } // end ComputerPlayer

The forcedWin method implements the check for a forced win in the tree. A forced win occurs from a particular node when either a child node terminates a word or all of the grandchild nodes for a particular child node contain a forced win.

An alternative check for a forced win would be to determine if the strings reachable from the current node all have an odd length, but the recursive solution is more aligned with tree traversal. If the maximum depth of the tree were greater, the iterative approach would, of course, be preferred.

If a forced win is not found, the longestWord method finds the longest word available from the current string in play. These methods require some additions to LetterNode.

public int maximumLength() { int length = 0; int maximumLength = 0; for (LetterNode node : nodes_.values()) { length = node.maximumLength(); if (length > maximumLength) maximumLength = length; } return maximumLength + 1; } public LetterNode child(char letter) { return nodes_.get(Character.valueOf(letter)); } public char letter() { return letter_; } public HashMap children() { return nodes_; }

Running this with:

java ita.ghost.GhostGame WORD.LST ita.ghost.HumanConsolePlayer ita.ghost.ComputerPlayer

allows a game to be played from the console against the computer. This algorithm just picks the first matching word it finds for any given starting series of characters. For those playing along at home, "hebraization" is a sure winner for the human player.

Source Code

Acknowledgements

My thanks to Pedro Galan, Ryan Calme, Tim Pierce, Tom Turrell-Croft, and Pablo Medina for pointing out a bug in my previous implementation of this puzzle. Unit testing is great, but no debugging technique compares to risking public embarrassement. Seriously, thank you.

Please contact me by email if you have any questions, comments, or suggestions.

www.softwarematters.org