在程序化内容生成领域，为游戏中的实体赋予富有辨识度的名称始终是一个核心挑战。xs-of-y 项目展示了一种独特的解决思路：每次运行都为自己生成全新的名称，而非使用固定标题。这一自命名机制背后的技术基础正是马尔可夫链（Markov Chain）配合约束语法树的组合方案。本文将系统阐述这一技术在游戏标题生成场景下的工程实现路径，并给出可直接落地的参数建议。
马尔可夫链命名生成的核心原理
马尔可夫链在程序化命名中的核心思想相当直观：基于已有词汇库训练概率分布表，每次生成下一个字符时依据当前状态（历史字符序列）从概率分布中采样。这种方法的本质是将 “一个好名字应该长什么样” 这一主观判断转化为可计算的统计规律。具体实现中，N-gram 模型（N 元语法）是构建马尔可夫链的经典方式，其中 N 表示用于预测下一个字符的历史字符数量。当 N 取 3 时称为 trigram（三元组）模型，这是平衡生成质量与计算开销的实用选择。
以训练语料 "rogue" 和 "roguelike" 为例，当使用 trigram 模型时，系统首先将每个单词切分为重叠的三字符窗口：对于 "rogue"，会生成 "rog"、"ogu"、"gue" 三个片段。在离线训练阶段，系统遍历所有输入词汇，统计每个三字符序列后面跟随各字符的频率。例如，若训练语料中 "rog" 后面出现 "u"5 次、出现 "u" 与 "e" 各 2 次，则生成时的选择概率分别为 62.5% 和 25%。生成时从某个起始三元组出发，循环采样下一字符直到满足长度或终止条件。
trigram 模型在 N=4 时达到一个关键的平衡点。N 值过低会导致生成结果过于碎片化，常见字母组合如 "th"、"qu" 等难以稳定出现；N 值过高则会使模型过度拟合训练数据，生成结果趋向于直接复制已有词汇，缺乏创造性。N=4 恰好能在保持一定变化空间的同时，确保生成的单词具备可辨识的音节结构和自然的字母衔接。
约束语法树的过滤机制
纯粹的马尔可夫链生成存在一个显著问题：随机采样可能产生不符合目标语言命名习惯的结果。例如在游戏标题场景中，我们通常希望结果满足特定格式（如 "X of Y" 结构），或者符合代码命名规范的驼峰式 / 下划线式命名。约束语法树（Constrained Syntax Tree）正是为解决这一问题而设计的二次过滤层。
约束语法树的工作方式是在马尔可夫链生成结果之后，通过预定义的语法规则对候选名称进行校验与筛选。常见的约束条件包括：格式匹配（是否包含预期的介词或分隔符）、长度范围（过短难以辨识、过长增加记忆负担）、字符组成（是否包含数字或特殊符号）、以及词法有效性（首字符不能为数字、避免连续元音或辅音等）。以 xs-of-y 为例，其名称生成器需要确保输出遵循 "首字母大写的多单词标题" 这一格式约定，约束语法树会过滤掉所有不符合该模式的马尔可夫链输出。
更高级的实现还会引入语义层约束。通过引入词性标注和词向量相似度计算，系统可以引导马尔可夫链向特定语义方向演化。例如，在生成武器名称时强化包含力量感词汇的概率，在生成地名时优先选择具有地理特征的词汇。这要求在马尔可夫链的概率表之外额外维护一个语义权重矩阵，根据当前生成实体的类型标签动态调整各词素的采样概率。
频率表构建与平滑技术
频率表的构建质量直接决定了马尔可夫链的生成上限。在离线训练阶段，系统需要完成三个核心任务：词汇预处理（统一大小写、去除标点、标记词边界）、N-gram 片段提取（对于 trigram 模型，每次取连续 4 个字符）、以及概率权重计算。权重计算时采用拉普拉斯平滑（Laplace Smoothing）是常见做法，即为每个可能的下一个字符预设一个小的先验概率（如 0.01），防止某些字符因训练语料中从未出现而永远无法被选中。
平滑技术是频率表构建中的关键一环，原因在于再大的训练语料也难以覆盖所有可能的字符组合。那些只有单一出路的 N-gram 片段会产生 “确定性陷阱”—— 无论采样多少次，生成的字符序列都完全相同，严重损害结果多样性。一种有效的平滑策略是从这些受限片段出发，查找以其后缀字符开头的其他 N-gram，借用它们的下一个字符选项作为补充。以 "arn->u" 为例，若 "rn" 作为前缀还出现在其他词中，则可以将这些词中的后续字符（如 "n"、"d"）引入 "arn" 的候选集，从而为生成过程注入变化。这种技术的核心约束是：借用来的字符必须能够自然衔接到现有片段，避免生成无意义的断裂。
在实际工程中，频率表通常以哈希表形式存储以实现 O (1) 查找效率。键为 N-1 个字符的序列，值为一个小型概率分布结构（可以用数组或字典实现，键为候选字符，值为累积概率）。离线生成的频率表可以直接序列化为静态数据文件，在运行时加载到内存中，无需每次启动都重新训练。这种离线训练 + 运行时加载的架构使得生成器能够保持极低的运行时开销，非常适合游戏这类对帧率敏感的场景。
4kLoC 实现的可复用命名引擎架构
xs-of-y 项目用约 4000 行代码实现了一个完整的自命名 Roguelike，其命名引擎的设计思路值得借鉴。核心架构分为三个层次：数据层负责维护训练语料和预计算的频率表；生成层实现马尔可夫链的采样逻辑；约束层处理语法树过滤和格式校验。这种分层设计使得命名引擎本身与游戏逻辑解耦，可以独立提取出来复用于其他项目。
数据层的关键设计决策在于语料来源与组织方式。对于游戏标题生成，语料可以按主题分类组织（如武器名、地点名、角色名分别使用不同语料库），生成时根据实体类型动态切换。这种主题切换能力使得同一个马尔可夫链引擎能够产出风格迥异的名称，而无需为每种类型单独训练模型。语料规模方面，的经验法则是每个主题至少准备 500-1000 个高质量样本，样本质量比数量更重要 —— 嘈杂的语料会引入过多异常模式。
生成层的实现要点包括：随机数生成器的种子管理（可复现的生成结果对于调试至关重要）、长度控制策略（设置最大长度阈值防止无限循环、设置最小长度阈值确保生成结果有意义）、以及回退机制（当当前状态无法继续生成时，使用预设的默认值或重新开始）。持久数据结构的引入使得世界状态的保存与恢复成本极低，这与 roguelike 的经典 “永久死亡” 机制天然契合 —— 每次游戏结束时的命名数据可以无缝衔接到下一局存档中。
可落地参数配置清单
将上述技术方案投入实际项目时，以下参数配置可作为初始基准。训练语料规模建议每个主题类别不少于 800 个词汇来源，确保覆盖目标命名风格的主要特征。N-gram 阶数推荐从 N=3 或 N=4 开始实验，N=3 生成结果更具变化性但可能不够连贯，N=4 则倾向于产生更完整的音节结构但变化空间受限。长度控制方面，游戏标题建议控制在 15-40 个字符区间，物品名称建议 5-20 个字符区间。
平滑处理的阈值参数需要根据具体语料特性调校。拉普拉斯平滑的先验概率建议设为 0.005-0.02 之间，太高会让生成结果过于随机化，太低则平滑效果不明显。自定义平滑（如前文所述的借用策略）触发条件可以设定为：当某个 N-gram 的候选字符数少于 3 个时启动。格式约束规则的数量建议控制在 10-20 条以内，过多的约束会大幅降低有效输出率（通常需要生成 5-10 个候选才能得到 1 个通过约束的合格结果）。
资料来源
xs-of-y 自命名 Roguelike 的 Hacker News 讨论
Markovich: 基于 trigram 马尔可夫链的程序化命名生成器
内容声明：本文无广告投放、无付费植入。
如有事实性问题，欢迎发送勘误至 i@hotdrydog.com。