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
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.
To keep this description as concise as possible, JavaDoc comments are
not included. They are available in the file
ghost.tar.gz.
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
An ideal implementation would build a tree of the words, branching at
each letter and computing optimal play by traversing that tree.
Rather than implementing that data structure immediately, I'll see
what can be accomplished with the standard Java libraries.
Assuming that the words are provided in alphabetical order, a
LinkedList of Strings makes it easy to add
those words that meet the minimum length criteria and that don't begin
with a word that's already in the list:
package ita.ghost;
import java.util.LinkedList;
import java.util.NoSuchElementException;
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 LinkedList wordList_ = new LinkedList();
private void addWord(String word)
{
String lastWord = null;
if (word.length() >= MIN_WORD_LENGTH)
{
try { lastWord = wordList_.getLast(); }
catch (NoSuchElementException e) { }
if ((lastWord == null) || !word.startsWith(lastWord))
wordList_.addLast(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 long size()
{
return wordList_.size();
}
} // end GhostDictionary
Compiling with java Ghost*.java and running with
java ita.ghost.GhostGame WORD.LST creates a dictionary of
43622 words out of the 173528 in WORD.LST. Knowing that the human
player will always go first, I could break this down further by the
initial letter of the word, but I'll leave that for a later
optimization.
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);
dictionary_ = new GhostDictionary(dictionary_,wordInPlay_.toString());
if (dictionary_.size() == 0)
{
gameOver_ = true;
winner_ = players_[switchPlayer()];
}
else if ((dictionary_.size() == 1)
&& dictionary_.firstWord().equals(wordInPlay_.toString()))
{
gameOver_ = true;
winner_ = players_[currentPlayerIndex_];
}
}
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()
+ "
");
}
Some enhancements to the GhostDictionary class are
required by the changes to GhostGame. In particular,
there is a new constructor that creates a new dictionary from a subset
of an existing dictionary. This is used by GhostGame to
determine when the game is over. It also has obvious applications in
some computer player implementations. While not as efficient as a
tree structure, it should work fine for this problem.
public GhostDictionary(GhostDictionary dictionary,String start)
{
ListIterator iterator = dictionary.wordList_.listIterator(0);
String word = null;
while (iterator.hasNext())
if ((word = iterator.next()).startsWith(start))
wordList_.addLast(word);
}
. . .
public String firstWord()
{
String firstWord = null;
try { firstWord = wordList_.getFirst(); }
catch (NoSuchElementException e) { }
return firstWord;
}
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.
The final step is a simple matter of implementing the computer player.
I'll start with a naive implementation:
package ita.ghost;
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 GhostDictionary dictionary_
= new GhostDictionary(DEFAULT_DICTIONARY_FILE);
private String name_ = "ComputerPlayer";
public ComputerPlayer()
{
}
public String name() { return name_; }
public char play(String wordInPlay)
{
dictionary_ = new GhostDictionary(dictionary_,wordInPlay);
String word = dictionary_.firstWord();
return word.charAt(wordInPlay.length());
}
} // end ComputerPlayer
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,
"bagatelle" is a sure winner for the human 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. This clearly calls for an
alpha-beta pruning
strategy combined with a search for the longest word in a losing
position. Before I can implement alpha-beta pruning, I'll need to get
the words into a tree.
package ita.ghost;
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.ListIterator;
import java.util.logging.Logger;
public class WordNode
{
private static Logger logger_ = Logger.getLogger(WordNode.class.getName());
private String string_ = null;
private HashMap childNodes_
= new HashMap();
private void addTerminal(WordNode node)
{
if (node.string_.length() == (string_.length() + 1))
childNodes_.put(node.string_,node);
else
{
String key = node.string_.substring(0,string_.length() + 1);
WordNode child = childNodes_.get(key);
if (child == null)
{
child = new WordNode(key);
childNodes_.put(key,child);
}
child.addTerminal(node);
}
}
public WordNode(String baseString,ListIterator iterator)
{
string_ = baseString;
while (iterator.hasNext())
addTerminal(new WordNode(iterator.next()));
}
public WordNode(String word)
{
string_ = word;
}
public long numberOfChildren() { return childNodes_.size(); }
public WordNode childNode(String start)
{
WordNode node = null;
if (string_.equals(start))
node = this;
else if ((string_.length() < start.length())
&& ((node = childNodes_.get(
start.substring(0,string_.length() + 1)))
!= null))
node = node.childNode(start);
return node;
}
public String baseString() { return string_; }
public Collection childNodes()
{
return childNodes_.values();
}
} // end WordNode
The computer player must be modified to use this data structure:
private WordNode currentNode_ = null;
. . .
private WordNode wordNode(String start)
{
if (currentNode_ == null)
{
dictionary_ = new GhostDictionary(dictionary_,start);
currentNode_ = new WordNode(start,dictionary_.listIterator());
}
else
currentNode_ = currentNode_.childNode(start);
return currentNode_;
}
. . .
public char play(String wordInPlay)
{
WordNode wordNode = wordNode(wordInPlay);
if ((wordNode == null) || (wordNode.numberOfChildren() == 0))
throw new RuntimeException("No matching word found.");
String word = findWinner(wordNode);
if (word == null)
word = wordNode.longestWord();
return word.charAt(wordInPlay.length());
}
It all comes down to the findWinner method. I don't need
to implement full alpha-beta pruning because the score for each node
is either plus or minus infinity -- win or lose. A further
simplification is that the computer player only needs to find one
winning word and can then immediately stop searching.
A forced win occurs from a particular node when either a child node is
a terminal or all of the grandchild nodes for a particular child node
contain a forced win.
private String findWinner(WordNode wordNode)
{
String winningWord = null;
Collection childNodes = wordNode.childNodes();
Iterator children = childNodes.iterator();
WordNode childNode = null;
while ((winningWord == null) && children.hasNext())
{
childNode = children.next();
if (childNode.isTerminal())
winningWord = childNode.baseString();
else
{
boolean forcedWin = true;
WordNode grandchildNode = null;
Collection grandchildNodes = childNode.childNodes();
Iterator grandchildren = grandchildNodes.iterator();
while (forcedWin && grandchildren.hasNext())
if ((winningWord = findWinner(grandchildren.next())) == null)
forcedWin = false;
}
}
return winningWord;
}
This finds forced wins efficiently, but it doesn't help identify the
longest losing string if no win is forced. Rather than writing
another tree traversing method, I'll wait for the first request to
find a winner and annotate the tree once. That requires some changes
to ComputerPlayer:
private void findForcedWins(WordNode wordNode)
{
boolean forcedWin = false;
Collection childNodes = wordNode.childNodes();
Iterator children = childNodes.iterator();
WordNode child = null;
while (children.hasNext())
{
child = children.next();
boolean childForcedWin = true;
if (!child.isTerminalNode())
{
WordNode grandchild = null;
Iterator grandchildren = child.childNodes().iterator();
while (grandchildren.hasNext())
{
grandchild = grandchildren.next();
if (grandchild.isTerminalNode())
grandchild.flagForcedWin(false);
else
findForcedWins(grandchild);
if (!grandchild.isForcedWin())
childForcedWin = false;
}
}
child.flagForcedWin(childForcedWin);
if (child.isForcedWin())
forcedWin = true;
}
wordNode.flagForcedWin(forcedWin);
}
private String chooseWord(WordNode wordNode)
{
if (wordNode.isForcedWin() == null)
findForcedWins(wordNode);
return wordNode.isForcedWin() ? wordNode.firstWinningWord()
: wordNode.longestLosingWord();
}
public char play(String wordInPlay)
{
WordNode wordNode = wordNode(wordInPlay);
if (wordNode == null)
logger_.info("No node found for " + wordInPlay + ".");
else
logger_.info("Node with " + wordNode.numberOfChildren() + " found.");
if ((wordNode == null) || (wordNode.numberOfChildren() == 0))
throw new RuntimeException("No matching word found.");
return chooseWord(wordNode).charAt(wordInPlay.length());
}
The findForcedWins method is a bit longer than I'd like,
but breaking out the grandchild processing into a separate method
probably won't add significantly to its maintainability. These
changes require some support from the WordNode class:
private Boolean forcedWin_ = null;
private String longestLosingWord_ = null;
. . .
public boolean isTerminalNode() { return childNodes_.isEmpty(); }
public void flagForcedWin(boolean forced)
{
forcedWin_ = new Boolean(forced);
}
public Boolean isForcedWin() { return forcedWin_; }
public String firstWinningWord()
{
String word = null;
if (isTerminalNode() && isForcedWin())
word = string_;
else
{
Iterator keyIterator = childNodes_.keySet().iterator();
while ((word == null) && (keyIterator.hasNext()))
word = childNodes_.get(keyIterator.next()).firstWinningWord();
}
return word;
}
public String longestLosingWord()
{
if (longestLosingWord_ == null)
{
longestLosingWord_ = string_;
Iterator keyIterator = childNodes_.keySet().iterator();
WordNode child = null;
while (keyIterator.hasNext())
{
child = childNodes_.get(keyIterator.next());
if (!child.isForcedWin()
&& (child.longestLosingWord().length()
> longestLosingWord_.length()))
longestLosingWord_ = child.longestLosingWord();
}
}
return longestLosingWord_;
}
Answer
Some judicious logging shows that, if the human starts the game with
'n' and the computer plays according to the specified rules, the human
will win with the word "nefarious."
Source Code
Please contact me by
email if you have any
questions, comments, or suggestions.
www.softwarematters.org