Ghost-Android-Game

Ghost is a word game in which players take turns to add letters to an incomplete word. The only constraint is to maintain a string which is a prefix of a valid English word. The player who forces his opponent to create a meaningful word wins the game. A dictionary of 60K+ words were implemented using Trie, which served quick lookups for optimized decision checks during the gameplay. The bot moves were implemented using order-3 Markov model.

System Details :
Android Studio 2.3.3
Build : 162.4069837
JRE : 1.8

Screenshot of App :

Game Rules:

1. Ghost is a word game in which players take turns adding letters to a growing word fragment, trying not to be the one to complete a valid word.
2. Each incomplete wordmust be the beginning of an actual word, and minmum length of a word that counts is 4 letters.
3. The player who completes a word lose the round.
4. A player is chosen at random to start the game, and begins by naming any letter of the alphabet.
5. Players then take turns to add letters to this fragment, with the aim being to avoid completing an actual word.
6. The player whose turn it is may :-
   • Instead of adding a letter, challenge the previous player to prove that the current fragment is actually the beginning of a word.
   • If the challenged player can name such a word, the challenger loses the round; otherwise the challenged player loses the round.
   • If a player bluffs, or completes a word without other players noticing, then play continues.

Ghost Strategy :-

A Sample Dictionary :-

1. there
2. any
3. answer
4. anyone
5. their
6. bye

Markov Model from Dictionary :-

Current State	Possible next character
the	{'r':1, 'i':1}
her	{'e':1}
ans	{'w':1}
nsw	{'e':1}
swe	{'r':1}
any	{'o':1}
nyo	{'n':1}
yon	{'e':1}
hei	{'r':1}

Ghost will use markov model to predict next char of word fragment.

Order of Markov model is 3, which means next character wil be decided from last 3 character.

How to check current word fragment is valid or complete :-

1. Binary Search :-

• Sort Dictionary lexicographically
• Search for current word in sorted dictionary using Binary search.
• Complexity : O( log₂(N)) where N is number of word in dictionary.

2. Trie :-

• The trie is a tree where each vertex represents a single word or a prefix.
• The tries can insert and find strings in O(L) time (where L represent the length of a single word). This is much faster than Binary search.

How Trie look like :-

LIst of words:

• Great
• Any
• Anyhow
• answer
• Greek
• Their
• there
• the