A Ruby script to solve the word game Ghost. It prints a short crib sheet describing a winning strategy.
Combinatorial game theory
Combinatorial game theory describes two player, turn-based, deterministic games where a player loses if he can't make a move. Chess, Go and Ghost are all combinatorial games. In particular, Ghost is an impartial game, meaning the same moves are avaliable to both players. Chess is not impartial because Black cannot move the white pieces. Nim is a famous impartial game played with matchsticks. The Sprague-Grundy theorem (1) demonstrates that every impartial game is equivalent to a Nim-heap of some height.
This script determines the height of the Nim-heap equivalent to Ghost.
- Conway, Berlekamp, Guy (1982). Winning Ways for your Mathematical Plays
Randall Munroe (xkcd artist) solved Ghost too.
git clone https://github.com/hickford/ghost.git cd ghost bundle install
Assuming you have a word list at
Otherwise, to use your own word list, say
ruby ghost.rb web2.txt
You can download the free Web2 word list courtesy of FreeBSD. (2.4MB text file)
On a 2.5MB word list (250,000 words) the script takes about 1 minute to run on my computer.