2
$\begingroup$

Want to create a hangman solver, So what is the best ml algorithm (lstm,reinforcement learning, or etc) to use? Do suggest any other optimal technique if you know?

$\endgroup$
1
  • $\begingroup$ Hi @jucikater, welcome to the site. If you find the answers to your question useful, please consider upvoting them (once you have enough reputation). Also, please consider accepting one (with the tick mark ✓ next to it) if you consider it correct or, alternatively, please describe in a comment why you consider it incorrect or not clear enough. $\endgroup$
    – noe
    Aug 7, 2023 at 8:42

3 Answers 3

3
$\begingroup$

As is often the case, training a machine learning from scratch would be very inefficient here, and you could achieve excellent results with much simpler methods.

The hangman problem breaks down to a few steps:

  • Start with a list of all eligible words (you can find the Scrabble dictionary online, which is a good start) and filter to keep only words of length $n$. This list isn't too long.

  • Decide on your next letter.

    • A simple way to to this is find the most common eligible word (there are lots of data sets that provide this) and pick any letter from this.
    • A better way would be to figure out the most likely letter directly. I provide an algorithm for this below.
  • Provide your guess, and update your list of eligable words accordingly.


Code Example

# Hangman
import numpy as np
import pandas as pd
import string

# Data from https://www.kaggle.com/datasets/rtatman/english-word-frequency?select=unigram_freq.csv
all_words = pd.read_csv('unigram_freq.csv').set_index('word')
all_words.index = all_words.index.map(str) # Ensure everything is a string
all_words['length'] = all_words.index.map(len)

target_n = 5
words = all_words[all_words['length'] == target_n].sort_values('count', ascending = False)

# Most likely letter, marginalising across words
letters = list(string.ascii_lowercase)
possibilities = np.zeros((target_n, len(letters)))

for i in range(target_n):
    for j, letter in enumerate(letters):
        # Get all eligable words with letter `letter` in position `i`
        letter_pos_words = words[words.index.map(lambda w: w[i] == letter)]
        possibilities[i, j] = letter_pos_words['count'].sum()

guess_position, guess_letter_index = (v[0] for v in np.where(possibilities == possibilities.max()))
guess_letter = letters[guess_letter_index]
print('Guess: "%s" in position %i' % (guess_letter, guess_position)) # NB - Position 0 is the first letter
## Guess: "s" in position 4

You can also visualise how these letter probabilities look:

import seaborn as sb
import matplotlib.pyplot as plt
viz_df = pd.DataFrame(possibilities, columns = letters)
fig, ax = plt.subplots(figsize = (9,8))
sb.heatmap(viz_df.T, cmap = 'jet', ax=ax)
plt.show()

enter image description here

$\endgroup$
3
  • $\begingroup$ Thanks, this was my initial approach but wanted to train the model on set of words and use the trained model to guess each letter step by step on a completely disjoint set of words, so I was asking for a ML solution which is much better compared to this on unseen data. $\endgroup$
    – juci kater
    Aug 7, 2023 at 17:50
  • $\begingroup$ Yes, but that's an extremely inefficient approach. There aren't that many words, we have frequency data on them all, and the target in Hangman is always a dictionary word, so "unseen data" isn't a concept that makes any sense here. $\endgroup$
    – Eoin
    Aug 8, 2023 at 9:14
  • $\begingroup$ There's an adage that the most important skill in ML is knowing when NOT to use ML. $\endgroup$
    – Eoin
    Aug 8, 2023 at 9:15
1
$\begingroup$

If you limit the model to propose letters and not entire words (which theoretically does not change the solution), you can just find the longest word in your alphabet, say $N$, and all the possible letters in a word, which usually are less than $35$, and create a state which is $N\times25$, add an additional $30$ dimensional vector to represent the already proposed letters, and a $10$ dimensional vector for the remaining lives, and use a NN to map it to a policy using RL with any Actor critic method, like A2C, PPO, TRPO, ACER, Rainbow and so on

Since you have a fixed size input ($N+35+30+10$) you can just use a FFNN with like 3/4 layers with an output-size of $30$ and you are good to go, and the architecture becomes close to irrelevant (you might still want to find the optimal number of layers and neurons, as in RL it has been shown that it's a very important aspect)

$\endgroup$
1
$\begingroup$

You can train a character-level masked language model. Like BERT, but with the following traits:

  • The token vocabulary of the model would be the characters that are allowed in the words (e.g. lowercase Latin script letters) plus special tokens like [MASK].
  • The input sequence would be a sequence of characters forming a word. Some characters would be replaced by a special token [MASK].
  • The expected output would be the same as the input sequence but without any masked tokens.
  • The loss would be the categorical cross-entropy between the actual model output and the expected output.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.