出题的 AI

之前做的围棋、五子棋、黑白棋 AI 都是和人对弈的对手。填字游戏不一样。AI 既不解题，也不和人比赛，而是出题给人解。题目是韩语填字游戏，所以每个格子填一个韩文字（音节）。

网页沿用了和其他游戏相同的框架。

  • 地址是 crossword.mariago.kr。它运行在家里 Mac 的 3009 端口上，由 IDC 的 nginx 转发过来。
  • 在大厅选择难度并进入游戏房间后，就会生成一个新网格。
  • 网格和每一次输入都作为记录保存到 SQLite 中。

最初的顺序：单词 → 题目 → 网格

起初，它从词库中选出单词，给每个单词配上题目，然后把这些单词在网格上连接起来。如果和已经放好的单词有相同的字，就在那个位置交叉放置。

做出来的网格并不是填字游戏。

  • 12×12 的网格里只有 7~8 道题。网格大部分都是黑格。
  • 答案大多是两个字的。
  • 单词只靠首字和尾字连接，排成像斜着的楼梯一样。像 keuriseumaseu（圣诞节）和 alpeuseu（阿尔卑斯）在共同的字 seu 处交叉那样、通过中间的字交错的情况几乎没有。
  • 单词只集中在网格中间。
  • 连续玩了两局困难网格，结果除了一个单词以外，全都是上一局出现过的单词。

第一天保存的 24 个网格

记录数据库里还留着那天生成的 24 个网格，全都是 12×12 的困难网格。

  • 单词数为 6~8 个，平均 6.8 个。
  • 白格平均只占网格的 6.5%。
  • 答案中有 76% 是两个字的。
  • 没有一个网格是 180° 对称的。

24 个网格中，有 22 个一格都没填就又按了新网格。一看到网格就马上重新生成了。

尝试过的修改

  • 要求横向、纵向合计出 15 道题以上。测试通过了，但画面上出现的依然是 8 道题的网格。原来大厅一直在接着打开以前生成的网格。
  • 我们做了一个文本代理，直接运行生成器，把网格图和题目列表以文字形式打印出来。它也会一并检查记录数据库中的网格，如果有两个字的孤岛就标出来。
  • 还出现过一种反复用三个字的十字块来填满网格的方式，就是上方右边的图。题目数量增加了，但所有答案都是三个字，而且十字块之间互不相连。这是很有 AI 风格的想法，世界上并没有这样的填字游戏。

决定调换顺序

如果先放单词，网格形状只是随之产生的结果，根本无法控制。所以我们决定先做网格，再选出符合格子长度的单词，最后再出题。

这一阶段的实际代码

这是文本代理检查已保存网格的部分。如果平均长度太短，或者没有中间交叉，就打印出需要新游戏。

scripts/text-agent.tstypescript · 18 行
for (const row of rows) {
  let across = 0;
  let down = 0;
  let mid = 0;
  let avg = 0;
  try {
    const puzzle = JSON.parse(row.puzzle_json) as Puzzle;
    across = puzzle.across?.length ?? 0;
    down = puzzle.down?.length ?? 0;
    mid = countMiddleCrosses(puzzle);
    avg = avgWordLength(puzzle);
  } catch {
    /* ignore */
  }
  const mark = avg >= 2.7 && mid >= 1 ? "교차있음" : "2글자섬 ← 새 게임 필요";
  console.log(
    `${row.code} ${row.difficulty} ${row.size}×${row.size} ${row.status} 가로 ${across} 세로 ${down} 교차 ${mid} 평균 ${avg.toFixed(2)}  ${mark}  ${row.created_at}`,
  );

这是把单词连接起来的放置器的规则。新单词必须与已放好的单词恰好重叠一格，相邻的格子里不能挨着别的字。这个放置器现在仍作为备用路径保留着，第 3 篇中还会再次出现。

lib/gridFill.tstypescript · 5 行
  for (const [nr, nc] of neighbors) {
    if (inBoard(size, nr, nc) && grid[idx(size, nr, nc)] != null) return null;
  }
}
if (intersections !== 1 || newCells < 1) return null;

下一篇是“2. 先做网格，再填单词，最后出题”。