Ghost : A Father-Daughter Project, Part 1

Over the last Thanksgiving break, our oldest daughter Susan came home from college for a few days. She is studying web design and marketing, but has found herself more and more becoming a front-end UX designer. She's been spending a lot of time working on HTML/CSS/JavaScript projects with great success.

While we had a few days together, we decided it would be fun to collaborate on a project that would be useful for her coursework: a program that learns. She suggested implementing the game of GHOST that our family has always played, and that's what we did. The game is here.

Rules of GHOST

In case you're not familiar with it, GHOST is a game well-suited for car trips, sitting around the dinner table, or any other time you have 2 to N people sitting around with nothing to do. It's a spelling game, and if you make a valid word of 3 letters or more, you've lost the round. The first time you lose a round, you're a "G". The next time you lose a round, you're a "GH". Once you get all the way to "GHOST", you're out of the game. Here's a sample sequence or two to give you the idea:

Player 1: K
Player 2: N
Player 3: O
Player 1: C
Player 2: K
Player 3: "That's a word. You're a G."

Player 1: P
Player 2: A
Player 1: C
Player 2: I
Player 1: N
Player 2: A
Player 1: "I challenge you. What was your word?"
Player 2: "Ah, you got me. I didn't want to go out on PACING, so I bluffed. I'm a G-H-O."

Although GHOST is a simple game, there are nuances and strategy to it. Programming a competent player is not as simple to implement programatically as you might think.

Our Game

Our version of Ghost will be a two-player edition, human against computer.

Since Susan has done front-end development but not back-end or database work, I volunteered to put together a starting point program, and write the back-end code to her specifications. Since I spend much of my time with ASP.NET, I created a sample ASP.NET Model-View-Controller (MVC) project, and added web.config and code to connect to a SQL Server database.

Since this game is supposed to learn, it most definitely needs a database so it can grow its word list as it plays. This is just the simplest of databases: one table named Words containing one colum, Word. We initially seeded the word list with a couple dozen entries, but ever since the list has been growing as a result of game play. At the time of this writing, it has over 1400 words. We could of course license a dictionary, but that would defeat the learning purpose of this exercise.

Our first objective was to implement basic game play in order to arrive at a functional game, although not a very smart one. The basic algorithm for game play is this:

Basic Gameplay Flowchart (click to enlarge)

When it's the human's turn, he or she has 3 options:

1. Play: press a letter key to continue the word.
2. Challenge: click a Challenge button.
3. That's a Word: click a That's a Word button.

The Challenge and That's a Word buttons aren't visible unless at least 3 letters have been played.

Initially the human player goes first. In each new round, the game will flip who the starting player is.

Flow for Human Plays a Letter

When the human presses a letter key, the letter is added to the current word in play. Non-letter keys are ignored.

Next, a check is made to see whether the human player has just completed a word: if they have, they have lost the round. This is done with a call to the back end to look up the current word-in-play against the Ghost word list.

SELECT word FROM words WHERE word=@round

If the word is found in the word list, the game informs the player and a loss is scored for them. The player gets the next letter in G-H-O-S-T, and if T has been reached the game is over.

If the word was not found in the word list, the computer needs to make a turn. A query is made of the word list for winning words. Winning words that begin with the current word-in-play and are also the right length (odd or even) such that the computer will win if the word is played out. For example, let's say the current word in play is B A C. That means a winning word must begin with BAC and also be an odd-number of characters. The search for winning words would inlude BACON but not BACK or BACCARAT. If one or more winning words are found, one is randomly selected and the next letter is played.

A good algorithm for selecting a winning word took some thought and experimentation. The example query below shows how a winning word is selected if the human player went first. The first WHERE clause ensures the word selected begins with the word-in-play. The second clause ensures the word selected is longer than the word-in-play. The third clause ensures the selected word, when played out, will result in the human player making a complete word and not the computer. The ORDER BY clause tells SQL Server to select a random order.

SELECT TOP 1 Word from Words 
WHERE word LIKE @round + '%' 
AND LEN(word)>LEN(@round) 
AND ((LEN(word) % 2)=0) 
ORDER BY NEWID()

The above query is actually augmented further, because we don't want to target a winning word only to discover we accidentally made a losing word on the way; for example, planning to play P to pursue the word ZIPPER would be a mistake because ZIP is a losing word. To achieve this, more WHERE clauses are added to the query to ensure the computer does not select any word that could result in a losing position.

If no winning words are found, then the computer must either challenge the user or make a bluff. We came up with this rule: if the word-in-play is 3 letters or more in length and there are no losing words in the word list, a challenge is made. The human player can then admit they were bluffing, or tell the computer their word. If the human player was bluffing, a loss is scored for them. If a word is provided, the game adds the word to its word list and scores a loss for itself.

If not challenging, then the computer must bluff. Initiallly a random letter was selected for bluffing in our game, but that was often too obvious a bluff in game play, with nonsense letter combinations. Susan came up with the idea of scanning the word list for the next letter to play. This results in more credible letter sequences. The bluff letter is played.

Flow for Human Clicks Challenge Button

The human player can click a Challenge button if they don't believe the computer is making a valid word.

The game looks for a word in its word list that begins with the current word-in-play. If found, the user is informed what the word is, and then someone loses the round. Usually this is the human player, except in the case where the computer's word has been fully played: in that case, the computer has made a complete word and loses the round.

If the computer was bluffing (no matching word in the word list), it admits it was bluffing and takes a loss.

Flow for Human Clicks That's a Word Button

The human player can click a That's a Word button to indicate the computer has made a complete word. Since the Ghost game is designed to learn as it plays, it trusts the human player to be truthful (and a good speller), and adds the word to its word list database. Now it knows the new word for future play.

Of course, trusting the human player comes with risks. That's the reason for the next section we'll discuss, Administration.

Administration

Our game has a page for viewing the word list. If you add administrator credentials, this page also allows adding and removing words. This is important because our game trusts the human player in learning new words. If there's a typographic error, or a disallowed word (like a proper name), or profanity, we want to be able to correct it or remove it.

The back end of administrative functions are simple DELETE and INSERT queries to the database.

Summary

Well, that's our game--so far. From a learning / intelligence perspective, Ghost can:

• Learn new words
• Distinguish between potential winning and losing words
• Bluff convincingly

Susan is next going to re-do my placeholder front-end with her own UX design, which I'm sure will be highly creative. We'll cover that in a future Part 2.

I am greatly enjoying teaming up with my daughter on a project--something we haven't done since those middle school science project days that now seem so long ago.

Next: Ghost Game, Part 2: Voice-Enabling for Alexa