Write a Hangman Solver You are required to write a Hangman solver. Testing against this English word list[1], the solver that solves the most number of words wins, with the number of total incorrect guesses being the tie-breaker. All words in the word list will be tested in random order.

[1]: This word list is taken from here, then the numbers are removed, then words with length 1 or with non-alphabetical characters are removed, then the most frequent 4096 unique words are chosen as this word list.

The details:

Your program will interact with the game program, which will give you through stdin the underscores and correctly guessed letters. Your program will give to stdout your guesses, and it has to infer from the input whether the previous guess was right or wrong. After being wrong for 6 times, your program loses. Your program must be ready for the next game after each game ends (after win or loss).

Your code length must be strictly less than 2048 bytes, and your program must not use any external resources (including but not limited to accessing the wordlist on local storage or from the Internet).

Example: (Input is preceded by &gt; here only for clarification - it is not actually present in the input)

&gt;_______         // 7 underscores
a                // Now you wait for input again
&gt;_a___a_
e
&gt;_a___a_         // Implies that your guess is wrong
&gt;_____           // new round, this will be given ONLY IF you already have 6 losses


Suppose you are wrong for 6 times, you will receive a final input which implies your guess is wrong, and your program must be ready to start a new round (i.e. take another input).

If you win,

&gt;_angman
h
&gt;hangman
&gt;_____           // new round


After knowing that you have won (because the input has no underscores), you must be ready to accept the next round.

Your program must terminate when it receives an input END.

If your program is not deterministic (depends on randomness, pseudorandomness, system time, ambient temperature, my mood etc.), you must explicitly state that in your submission, and your score will be taken 10 times (by me, unless otherwise instructed) and averaged.

Note: if you use languages like python, please explicitly flush your stdout after each print statement.

The game program is as follows (credit to nneonneo):

import sys, random, subprocess

proc = subprocess.Popen(sys.argv[1:], stdin=subprocess.PIPE, stdout=subprocess.PIPE)
def p(x):
    proc.stdin.write(x+'\n')
    proc.stdin.flush()

wordlist=[]
f=open('wordlist.txt', 'r')
for i in f:
    wordlist.append(i[:-1] if i[-1]=='\n' else i)
# wordlist=[i[:-1] for i in f]
random.shuffle(wordlist)

score=0
totalerr=0

for s in wordlist:
    s2=[]
    for i in s:
        s2.append('_')
    err=0
    p(''.join(s2))
    while err&lt;6 and '_' in s2:
        c=proc.stdout.readline().strip()
        nomatch=True
        for i in range(0, len(s)):
            if s[i]==c:
                s2[i]=c
                nomatch=False
        if nomatch:
            err+=1
            totalerr+=1
        p(''.join(s2))
    if err&lt;6:
        score+=1
p('END')
sys.stderr.write('score is '+str(score)+', totalerr is '+str(totalerr)+'\n')


Usage: python ./game.py [yoursolverprogram]

Example: python ./game.py ruby ./solver.rb

This should work like the old scoring program, but does not depend on named pipes, so it can work on other platforms. Refer to the revision history if you are interested in the old one.
Python: 2006 bytes, score=1501

1885 bytes, score=1337

1961 bytes, score=1207

Here's my submission:

import sys
b='eJwdVQuW4ygMvJdyGgwYtAGJQQKHOf2Wp9/rJqGxVaqP+HxUMlGx5F86/XoqsUuonzAz5cf5vqjJ6OlQudxOJR3ibJ8cwuSmsTX12daVht8ubj15miaEH/GrESXrQrXbl1K0m2hs6dRjMkp1PuS2/9JoVslkLmp2L6J6f5kij4s0nkSPni/5GZtixSuKcKd7lYvsfi7yNYxseKXqV6fURkc//KXe+P6Hc071xuZteixiSRtzMnavwNfqcydqSzb+9hMTlW/UQSNe5uRx1EVp1OhA7gXb0v+i0rKN1rYsGlWBufozlFbzP+i2KXCpNKNjfTwkytcBnv+OgoV6blJ/8NDjF6iqUd2ojqcbrScmIaurHJxs6yHjck96brZJwncsIOHhzwyemZurKFrkmpIX9yXSNGsKdF+F+rF2fam0+KAMj3YdoXFJR+nY7AL4y1jaopNuBhk6sl03pSd7x2IxoyeLO6dGedjp9V0inusji0EAyR4pBttN6dt+UR/SYBHCVwuxPZSvqNYpZhPIWXM3Segs30IFXKZKSzqDkcdORud59xVJ8o4WsJQelUqXnIAjV/2whDybo1mDmhYCeAjZV4552gSWOa5aSG3WZ0SaqZVe4Y+o7R+Ps5knum0pDGNxrKA3De3Lwo/si420aemw2g/tdq5sKN1HyltpLNeY/qPUYwsLatc/pwRq5eSwK4l5LhHEnSIZhhG9xsFqeqDMRctmTnVQRoamwUtloiLNrgV+a0uzHBKAyUYl61yD+m++GkgeW1eiuMDEoCR6504z32V9JHD25tPVHFyXOGOc+A2vABogIw9vfxWBatuHwaWggEELdS+8De8z7ZHhir70cLoQpYYDOgfMw+ASbrhnbrwQ27x4TNt/3qHBEPSmwzlagqlH5J4Bk2FBqEvc9fXORUnnnceiMAc2kALwNdOB4W87eAw2uAwsIncpu+IYutsJwsJ/JfusCZNipqyL8uwjNHuDN3MJQBSg/Sr1ppByfD9RWaAt/QhLGDDv2C1PxSvBbfyEFqNO5ZwZpE2yqd2PjEwueV1aJoBdGxNjSl8klx3nuWAAxgCxKePt0bykLrCcQWspM61K3qcNuJYa53VMBWKNJCsrYkzZGfZf49fotx3ZYURvyYQ+GR6iOVCfT6fB4hkehfOws/k3PjFo82ZgaE60TxccO4DqKEKDVXSsuknSmuzZwB8C+h7YBS3oaRPSyGvurfnNvM2bMustIxXMYsM/WdvAvLn8hIx5CMCJQxEM2P2yLuyWYHvZziC+T8IWooeMVWDnvoF6wcETdOUVYBFcFdCop/CJ07RpwyjNy1kslHYwdfNxGYGtX4lWduETDAFIeLJntoAk/sjHlLI5tIwp6mcLF5gxJOR2eugsO5/fey0EhMb72J+mrwyB3rkw2eT0cCPuAOUc5cw/b7mQi8942Eaig4nkYUE9xi3D+FTVRxd80XLL9MXhgISod0JBHxjPPCNirRsh/0TgWdrB/6u01zHbvUnBDc4yhknZxCXgrgSWdv8h1oQR3q8hjdbbE5zK6e4U9nhNkHxCwjCdN26sS9+BIMPe7+EDExPGccPLQYvC8+SY1ioz3AxVUWfdJi3RNjjEMyiWq31CjITE1cQPTO5En39bkFEzri7c2f8Dkow6qw=='.decode('base64').decode('zlib').split(';')
R=raw_input
def G(c):print c;sys.stdout.flush()
def P(w):
 if'END'==w:exit()
 d=b[len(w)].split(':');l=len(d[0]);p=f=0
 while p&lt;l:
  G(d[0][p]);x=R();r=w==x;w=x;f+=r;p+=p+1+r
  if'_'not in x:return
 for c in d[p-l+1]+'zq':
  G(c);x=R();r=w==x;w=x;f+=r
  if'_'not in x or f&gt;5:break
while 1:P(R())


Score output:

score is 1501, totalerr is 21608


This program is fully deterministic. The giant blob (which is a base-64-encoded chunk of zlib compressed data) is a list of decision trees (one tree per word length). Each decision tree encodes a complete binary tree with a depth between 2 and 5. Each internal node is a single character, and the decision proceeds based on whether the character is present or not in the hangman word.

Each leaf node of the binary tree contains an optimized frequency table specific to that branch of the tree search. The table is specifically optimized to favor completion of certain words, while completely ignoring others (which it cannot reach due to the limited "failure" budget). The table isn't optimized to minimize errors, and thus the totalerr count of the program is high despite its (relatively) good score.

The optimizer, which isn't shown, uses a nondeterministic nonlinear optimizer utilizing a randomized gradient descent strategy to produce the frequency tables.