Hangman Solver: Character-BERT + Constrained Sampling + Information Gain

This project implements a high-accuracy Hangman solver that combines a character-level BERT language model with constrained sampling and an information-theoretic letter selection policy. The approach stays within the competition constraints by using only the provided 250k-word training dictionary to guide decisions.

Key Components

• Character-BERT (Char-BERT): A transformer-based masked language model trained at the character level to understand word structure and spelling regularities.
• Constrained Sampling: Generates candidate word completions for a partially revealed word while honoring already-guessed (banned) letters and mask positions.
• Information Gain (Infogain) Letter Selection: Chooses the next letter to guess by maximizing the expected reduction in uncertainty over candidate words.
• Frequency-based Fallback: Robust backup when modeling signals are weak or sampling fails.

---

Character-BERT

We use a character-level BERT (Char-BERT) masked language model with a compact configuration (sequence length ~32) suitable for single-word inputs. The tokenizer maps individual characters (a–z and apostrophe) plus special tokens ([CLS], [SEP], [MASK], [PAD], [UNK]) to IDs.

Given a partially revealed word, we create a masked sequence by replacing each unknown position with [MASK]. For example, for the masked word h_ll_ we construct:

h[MASK]ll[MASK]

The model is queried repeatedly to fill masks while respecting constraints (see next section). The model outputs logits over the character vocabulary for each position, from which we derive probabilities via softmax.

---

Constrained Sampling

The constrained sampler generates multiple plausible completions consistent with the current puzzle state:

1. Convert the masked word with underscores _ to a string with [MASK] tokens (one per unknown position).
2. Maintain a set of banned characters = letters already guessed that are known absent.
3. Iteratively fill one mask at a time:
   • Run Char-BERT to get logits at the selected mask position.
   • Softmax to probabilities.
   • Select the highest-probability character that is:
     • not in the banned set,
     • a valid single character (a–z or '),
     • and consistent with the character vocabulary.
   • Replace that [MASK] with the chosen character and continue until no masks remain.

We repeat the above K times (e.g., K=64–512) to obtain a list of samples: (completion_string, log_probability, normalized_weight). The normalized weights are derived from completion log-probabilities for downstream weighting.

---

Information Gain Letter Selection

Let S = {w_1, …, w_N} be the set of sampled completions and let p_i be the normalized weight for sample w_i (derived from model log-probabilities). The current uncertainty (entropy) over samples is

[ H(\mathbf{p}) = - \sum_{i=1}^{N} p_i \log_2 p_i. ]

For a candidate letter ℓ, the outcome partitions samples according to whether ℓ appears in each word and, if present, at which positions. Let the partition index set be \mathcal{O} (each outcome is either a position-set like (0, 2) or a special miss outcome). For an outcome o \in \mathcal{O}, define its probability and normalized conditional distribution as

[ P(o) = \sum_{i \in I_o} p_i, \quad \tilde{p}^{(o)}_i = \frac{p_i}{P(o)} ;; (i \in I_o), ]

where I_o is the index set of samples consistent with outcome o. The expected posterior entropy after guessing ℓ is

[ \mathbb{E}[H,|,\ell] = \sum_{o \in \mathcal{O}} P(o), H\big(\tilde{\mathbf{p}}^{(o)}\big). ]

The information gain (in bits) is

[ \mathrm{IG}(\ell) = H(\mathbf{p}) - \mathbb{E}[H,|,\ell]. ]

To balance exploration against the risk of a miss, we use a risk-adjusted score

[ \mathrm{Score}(\ell) = \mathrm{IG}(\ell),\big(1 - \alpha,P(\text{miss})\big), \quad \alpha \in [0,1], ]

and select the letter with the highest score among unguessed letters. In practice, \alpha is a small constant (e.g., 0.05–0.1).

This procedure focuses guesses on letters that most efficiently split the probability mass among candidate completions, accelerating convergence to the true word.

---

Deep Q-Network (DQN) Decision Layer

In addition to the core Char‑BERT + Infogain solver, we optionally add a learned decision layer that can make the final letter choice. This layer is a lightweight Deep Q‑Network (DQN) trained to map compact game states to letter actions.

State, Action, Masking

• State (73‑dim vector) per step:
  • 20 dims: masked word layout (1 for revealed letter, 0 for _), padded/truncated to 20
  • 26 dims: one‑hot of already‑guessed letters (a–z)
  • 1 dim: normalized lives lives / max_lives
  • 26 dims: belief over letters (uniform over unguessed in the basic variant)
• Action space: 26 discrete actions (letters a–z).
• Action mask: Letters already guessed are masked (set to −∞ before argmax).
• Infogain prior: If Infogain proposes letter ℓ*, we add a small bias to Q(ℓ*) before argmax so DQN can leverage the analytical signal when helpful.

Network and Targets

We use a small MLP (e.g., 73→128→128→26) with a target network. For a batch of sampled transitions (s, a, r, s', done), targets follow standard DQN:

[ y = r + \gamma , (1 - \mathbb{1}{\text{done}}) \max{a'} Q_{\text{target}}(s', a'), ]

and we minimize MSE between Q(s, a) and y.

Rewards

• Win bonus, loss penalty
• Efficiency bonus (fewer total guesses)
• Lives‑preservation bonus (more remaining lives)
• Small bonus for following Infogain when it leads to good outcomes

Training & Early Stopping

• Experience replay + target network updates
• Epsilon‑greedy exploration with decay
• Early stopping based on validation of training loss stability (e.g., patience, minimum loss threshold, recent std‑dev criterion)

Usage

1. Create a DQN agent, load a saved checkpoint if available.
2. Use the hybrid selector: Infogain proposes candidates; the DQN produces the final letter under action masking.
3. Training can be performed offline on local games; at inference time only the forward pass is required.

---

Dictionary Filtering and Fallback

Even though we sample from Char-BERT, we tightly couple the solver to the provided 250k-word training dictionary:

• Maintain a current plausible dictionary D_t filtered by word length and regex matching against the revealed pattern (e.g., h.ll. for h_ll_).
• When sampling yields few or low-confidence candidates, we fall back to classic frequency analysis over D_t and select the most frequent unguessed letter. If D_t is empty, we fall back to the global letter frequency over the full training dictionary.

---

End-to-End Flow

1. Receive the current masked word with underscores _ and the set of guessed letters.
2. Filter the training dictionary by length and regex compatibility to form D_t.
3. Build a masked string with [MASK] tokens and run constrained sampling with Char-BERT to produce (samples, weights).
4. Compute information gain for each unguessed letter and pick the best-scoring letter.
5. Use DQN to select a suitable letter given constrained samples and letter proposed by information gain.
6. If sampling fails or confidence is low, fall back to frequency-based selection over D_t (or global frequencies if needed).
7. Update guessed letters and repeat until the word is solved or lives run out.

---

Practical Notes

• Sequence Length: The Char-BERT sequence length is set (e.g., 32) to fully cover typical word lengths with special tokens and padding.
• Sampling Budget (K): Higher K improves coverage of plausible completions but increases latency. Reasonable defaults are K=64–512 depending on compute.
• Numerical Stability: When converting log-probabilities to weights, we stabilize by subtracting the maximum log-prob before exponentiation.
• Regex Matching: We treat _ as unknown and translate it to . (dot) for regex matching against candidate words.

---

Why This Works

• Char-BERT captures character-level spelling and morphology, making plausible, dictionary-like completions even for unseen words.
• Constrained sampling injects the current game state (known letters, banned letters) directly into generation.
• Information gain formalizes “which letter best splits the remaining candidates,” a principled criterion that tends to minimize the number of guesses.

---

Limitations & Future Improvements

• The belief vector in observations is currently a simple uniform prior over unguessed letters; it could be refined using sample-derived marginals.
• Position-aware priors (e.g., letter frequency by position) can further bias the scoring in early game states.
• Better calibration of model probabilities could improve weighting and stability of the infogain calculation.

---

Repro/Usage (High Level)

• Prepare the training dictionary (provided 250k list) at the expected path.
• Load the Char-BERT checkpoint and tokenizer.
• For each game step, convert _ to [MASK], run constrained sampling, and apply the infogain policy to choose the next letter.

---

The core system (Char‑BERT + constrained sampling + Infogain) operates independently and already provides strong performance. The DQN further adapts to empirical patterns (risk management, tie‑breaking, endgame heuristics) as more games are played.