# * Hangman

## The Game of Hangman

"Defendant" picks a word, writes blanks for its letters, draws a gallows

`---- | | | | | | _ _ _ _ _ _ _ _`

"Prosecution" guesses letters of the word in turn. Guessing a letter not in the word causes a body part to be added to the gallows. Guessing a letter in the word fills in all occurrences

`---- z w | | | | O | | | _ _ _ _ _ _ i _`

"Trial" is over when word is completed or def is hanged

`---- z w e a o u | | | | O | /|\ | / \ _ _ _ _ _ _ i c`

## Hangman Prosecution and Utility

What letter should pros guess first?

Let's assume that def chose random 8-letter word from known dictionary

Let's further assume that a found letter has a uniform value of 1

Then find

`argmax [l in 'a'..'z'] (l in word) pr(word|dict)`

This is an easy calculation: 'e' occurs in 2/3 of the 8-letter words (see

`bestguess.py`

)

## Hangman: My Assumptions Are Weak

Problem: because 'e' is so common, hitting it doesn't necessarily narrow things down

*so*muchValue function should be based on expected chance of winning after hitting

*or missing*the letterProblem: Def isn't choosing uniformly — will pick "hard" words

Need to know probability given defense strategy

*pr(word|ds(dict))*So

`argmax [l in 'a'..'z'] v(win with word) pr(word|ds(dict))`

## Hangman: Nash Equilibrium

Ugh.

*ds(dict)*will depend on guessing strategy- "Good old rock. Can always count on rock"

Adversary games are hard. But Nash Equilibrium exists and can

*in principle*be calculatedCurrent research for me

## Information Theory

Consider these strings of bits

`0111111111111111 0101100010011011`

`x`

is boring and easy to describe. You could predict the "next value" pretty reliably`y`

is complicated

Shannon

*et al*:`x`

has "less information" than`y`

Information content can be viewed as a utility function. The

*entropy*of a set is given as`u(S) = sum [i in S] pr(i) lg 1/pr(i) = sum [i in S] - pr(i) lg pr(i)`

For our sets (strings)

`u(x) = - pr(0) lg pr(0) - pr(1) lg pr(1) = - (1/16) lg (1/16) - (15/16) lg (15/16) ~= 0.337 u(y) = - pr(0) lg pr(0) - pr(1) lg pr(1) = - 2 (8/16) lg (8/16) = -2 × 0.5 × -1 = 1`

## Hangman: Entropy-Based Prosecution

Pros wants to get to a state where there is only one choice

Standard trick: pick the letter that has the greatest expected chance of reducing the entropy the most

`argmax [l in 'a'..'z'] (1 - sum [p in part(l, dict)] u(l))) pr(l)`

Does this still produce 'e' as the initial guess? It does

We have taken into account the "cost of gathering information" as part of the utility: we don't want to make a guess that costs us a body part unless we get a lot of information from it

## Demonic Hangman

Consider "Demonic Hangman": Def cheats as desired by changing the word in a way consistent with the guesses so far

Now we almost

*have*to use entropy to narrow Def down to only one choice quickly