noitu/plans/reports/research-260904-1058-noi-tu-game.md

Research Report: Vietnamese "Nối Từ" Word-Chain Game

Conducted: 2026-09-04 10:58 (Asia/Saigon) · Repo: D:/tiennm99dev/noitu (empty, initial commit)

Table of Contents

1. Executive Summary
2. Methodology
3. Game Rules
4. Data Model & Core Algorithms
5. Bot AI
6. Vietnamese Text Normalization
7. Dictionary Sources
8. Implementation Recommendations
9. Common Pitfalls
10. References
11. Open Questions

Executive Summary

Nối từ = Vietnamese word-chain. Player says a 2-syllable meaningful word; next player must say a 2-syllable word whose first syllable equals the previous word's last syllable. No reuse. Fail to answer in time → lose. Example: ngôn ngữ → ngữ pháp → pháp luật → luật lệ.

Implementation is trivial as a game loop; the hard 20% is (a) getting a clean 2-syllable Vietnamese word list, (b) Unicode/tone normalization, (c) a bot that doesn't feel dumb. Model it as a directed graph: nodes = syllables, edges = words (a→b for word "a b"). A move = traverse an unused edge from the current node. This is exactly Directed Edge Geography — PSPACE-complete, so no cheap perfect solver; use heuristic + depth-limited search.

Best data source: minhqnd/Noi-Tu-Discord → src/assets/wordPairs.json (MIT, ~60k word pairs, already keyed firstSyllable → [lastSyllables] — the exact index the game needs). Fallback/expansion: duyet/vietnamese-wordlist Viet74K (74k raw, filter to 2-syllable) and vi.wiktionary dumps.

Methodology

• Sources: 4 web searches + 1 repo fetch (skill cap 5)
• Date range: 2020–2026; dictionaries current as of Jan 2026 (Wiktionary copy)
• Terms: luật chơi nối từ, vietnamese wordlist github json, github bot nối từ thuật toán, Viet74K vietnamese two-syllable dataset

---

1. Game Rules

Core rule: next word's first syllable == previous word's last syllable.

Rule	Standard	Notes
Word length	exactly 2 syllables (từ ghép)	most online implementations enforce 2 strictly; some allow ≥2
Validity	must exist in dictionary, meaningful	typically noun/adj compounds
Reuse	banned within a round	track a used-set
Timeout	10–30s per turn	loss condition
Chain link	on syllable, not letter	despite folk phrasing "chữ cái cuối"
Start word	random or player-chosen	pick a high-out-degree node so game doesn't die instantly

Loss conditions: timeout, invalid/unknown word, wrong first syllable, repeated word, no legal move remains.

Modes seen in the wild (Nối từ tiếng Việt app, gamevui, vuanoitu.fun, wordfight.online):

• Thử thách — solo, N rounds vs clock + target score
• Thách đấu — 1v1 alternating
• Đấu trường — 4 players round-robin

Design decision needed early: does the bot lose when it has no move (fair), or does it get to challenge a rare word? Most implementations: no move = bot loses.

2. Data Model & Core Algorithms

Graph model

word "pháp luật"  =>  edge  pháp ──"pháp luật"──> luật
state = (currentSyllable, usedWords:Set)
legalMoves(s) = { w in adj[s] : w not in usedWords }

Index structure (build once at load)

// Map<firstSyllable, string[]>  -- full words (or last syllables)
{ "pháp": ["pháp luật", "pháp lý", "pháp danh", ...], "luật": ["luật lệ", "luật sư", ...] }

Lookup O(1); validation O(1) with a Set<string> of full normalized words.

Validation pipeline

input -> trim -> NFC -> lowercase -> collapse spaces
      -> split on space; assert length === 2
      -> assert syllables[0] === currentSyllable
      -> assert dictionary.has(word)
      -> assert !used.has(word)

Dead-end precomputation

• outDegree[syllable] = number of words starting with it.
• Killer syllables: outDegree === 0 (or very low) — rare endings. Precompute the list; moving there is an instant win.
• Syllables with outDegree 0 make the next player lose immediately. Mark them at build time.

3. Bot AI

Perfect play = Directed Edge Geography, PSPACE-complete → no exact solver at 60k edges. Practical ladder:

Difficulty	Strategy
Easy	random legal move
Medium	prefer moves ending in a low out-degree syllable; avoid handing the player a hub
Hard	1) instant win: any move to outDegree==0; 2) negamax depth 3–5 with alpha-beta over remaining edges, eval = -log(remaining moves for opponent); 3) fall back to Medium heuristic
Cruel	opening book of known trap chains

Cost control: at depth d, branching = out-degree of visited syllables (often <50). Depth 4 is cheap; order moves by ascending opponent out-degree and cap node count.

Anti-frustration: cap the bot below always-play-the-killer, or players quit.

4. Vietnamese Text Normalization (the real bug source)

1. Unicode form — normalize to NFC. ữ can be one codepoint or ư + combining tilde. Mismatch = false rejections.
2. Tone placement variants — hoà/hòa, thuý/thúy, quí/quý. Old-style vs new-style placement are different codepoints. Build an alias map or a tone-position canonicalizer, else valid words get rejected.
3. Case & whitespace — lowercase, collapse multiple/NBSP spaces.
4. Syllable split — Vietnamese syllables are space-delimited; split(/\s+/) is correct. Do NOT use a word-segmenter here.
5. Used-set keying — key on the normalized full word.
6. Encoding — Viet74K ships Unicode and TCVN3/ABC variants; take the Unicode one.

5. Dictionary Sources (ranked)

#	Source	Content	Format	License	Verdict
1	minhqnd/Noi-Tu-Discord src/assets/wordPairs.json + customWords.json	~60k 2-syllable pairs, purpose-built for nối từ	JSON {"từ_đầu": ["từ_cuối", ...]}	MIT	Start here. Already the exact index shape; MIT-safe to vendor
2	duyet/vietnamese-wordlist — Viet74K.txt	74k words, all lengths, dictionary-sorted	plain txt, Unicode + TCVN3	unclear/aggregated	Expansion set; filter split(' ').length===2
3	undertheseanlp/dictionary	consolidated VN dictionary from the underthesea NLP group	JSON/txt	check repo	Good for definitions / POS filtering (noun+adj only)
4	viet-yomitan	Từ Điển Tiếng Việt Thông Dụng, 42,012 entries	Yomitan dict (JSON in zip)	check	High-quality curated monolingual entries
5	Trannosaur/published_dicts	vi.wiktionary + en.wiktionary derived, Jan 2026	JSON	CC BY-SA (Wiktionary)	Attribution required; largest coverage
6	vntk/dictionary	Node package, lookup + examples	npm	check	Runtime lookup, not bulk list
7	NNBnh/noi-tu, lvdat/bot-noi-tu	reference implementations + wordlists	—	check	Cross-check coverage / borrow trap lists
8	titoBouzout/Dictionaries	spellcheck syllable list	txt	—	Syllable validation only, not compounds

Recommended pipeline: vendor #1 as base → union with 2-syllable filter of #2 → optionally POS-filter with #3 → dedupe after NFC normalization → emit words.json (Set) and word-index.json (adjacency). Keep the build script in-repo so the dataset is reproducible.

Licensing: MIT (#1) is safe to redistribute with attribution. Wiktionary-derived (#5) is CC BY-SA — attribute and isolate in a clearly-marked file if used.

6. Implementation Recommendations

Suggested layout (stack-agnostic; repo is empty so nothing is imposed yet)

data/
  raw/                 # downloaded sources
  words.json           # normalized Set of valid 2-syllable words
  word-index.json      # { firstSyllable: [word, ...] }
scripts/
  build-dictionary.mjs # raw -> normalized artifacts, reproducible
src/
  normalize.js         # NFC, tone-variant canonicalization, split
  dictionary.js        # load, has(), movesFrom()
  game-engine.js       # state, applyMove, validate, win/lose
  bot.js               # difficulty strategies

Minimal engine sketch

export function createGame({ index, words, startWord }) {
  const used = new Set([startWord]);
  let current = startWord.split(' ')[1];
  return {
    play(raw) {
      const w = normalize(raw);
      const s = w.split(' ');
      if (s.length !== 2)   return { ok: false, reason: 'NOT_TWO_SYLLABLES' };
      if (s[0] !== current) return { ok: false, reason: 'WRONG_LINK' };
      if (!words.has(w))    return { ok: false, reason: 'NOT_IN_DICTIONARY' };
      if (used.has(w))      return { ok: false, reason: 'ALREADY_USED' };
      used.add(w); current = s[1];
      return { ok: true, current };
    },
    moves: () => (index[current] ?? []).filter(w => !used.has(w)),
  };
}

Build order

1. build-dictionary.mjs + normalization — everything depends on data quality.
2. Engine + unit tests on rules (wrong link, reuse, unknown word, timeout).
3. CLI loop (1 human vs bot).
4. Bot difficulty ladder.
5. UI / multiplayer / timer / scoring if in scope.

7. Common Pitfalls

• Linking on last letter instead of last syllable — folk description says "chữ cái cuối", real play links syllables.
• Skipping NFC → valid words rejected; unreproducible across OS/keyboards.
• Ignoring hoà/hòa tone-placement variants → biggest source of "my word IS real!" complaints.
• Dictionary full of 1- and 3+-syllable entries → filter at build time, not runtime.
• Bot always plays the killer syllable → unwinnable; players leave.
• Reloading a 60k-entry JSON per request in a server context → load once at boot.
• No per-session used-set → infinite a→b→a→b loops.
• Client-side-only validation in multiplayer → cheatable; validate server-side.

References

• Rules: luatchoi.edu.vn/noi-tu · gamevui.vn · hoanghamobile roundup
• Live games: vuanoitu.fun · wordfight.online · App Store: Nối từ tiếng Việt
• Implementations: minhqnd/Noi-Tu-Discord · NNBnh/noi-tu · lvdat/bot-noi-tu
• Data: duyet/vietnamese-wordlist · Viet74K.txt · undertheseanlp/dictionary · viet-yomitan · Trannosaur/published_dicts · vntk/dictionary · titoBouzout/Dictionaries
• NLP resources: vndee/awsome-vietnamese-nlp

Next Steps

1. Decide stack + target (CLI, web, Discord bot, mobile) — nothing in repo constrains this yet.
2. Vendor wordPairs.json from Noi-Tu-Discord (MIT) into data/raw/, write build-dictionary.mjs, verify entry count and 2-syllable purity.
3. Implement normalize.js with NFC + tone-placement canonicalization; unit-test hoà/hòa, thuý/thúy, quí/quý.
4. Implement engine + rule tests, then a CLI loop before any UI.
5. Add bot ladder once the engine is green.

Open Questions

1. Target platform: CLI, web app, Discord bot, or mobile?
2. Strict 2-syllable only, or allow ≥2-syllable words?
3. Single-player vs bot, or real-time multiplayer? (multiplayer needs a server + authoritative validation — big architecture delta)
4. Are word definitions in scope? (pushes toward source #3/#4/#5)
5. Should max-difficulty bot be beatable, or is "cruel mode" wanted?
6. Vietnamese-only UI, or bilingual?