目次

Topcoder Marathon Match 167「WordGame」に参加した。最終結果は 27 位であった。

解法は、毎ターン置ける手を全部列挙し、同時に「あと数枚の札が来れば置ける手」まで列挙して、その見込みで 1 手を選ぶ貪欲である。そこに、数ターン先の大きい手のための準備を評価する項をいくつか足していった。

この記事では、問題の性質と解法に加えて、数ターン先の大きい手を計画的に狙う形を最後まで作れなかったことを振り返る。

なお、この記事は、Claude Code が作業ログとソースコードから起草したものを、私が推敲している。数字は全て測定記録から引いた。

問題

問題の詳細は、公式ページへ。

• 盤面: $N \times N$ のマス目（$10 \le N \le 20$）。マスには文字倍率（×2・×3）と単語倍率（×2・×3）がランダムに置かれている。この記事では、1 本の行または列を線と呼ぶ。
• 札: 手札は $T$ 枚（$5 \le T \le 9$）で、次に来る札が $X$ 枚（$0 \le X \le 5$）見えている。札は全部で $N^2$ 枚あり、その列は最初に決まっているが、先は見えない。各文字の出る確率は辞書の文字の頻度に比例していて、これは公開されている。
• 操作: 毎ターン、辞書（約 17 万語）にある単語を 1 つ横か縦に置くか、手札を何枚か捨てる（1 回につき $D$ 点を引かれる。$0 \le D \le 5$）。
• 置き方: 2 手目以降は、盤に既にある文字を 1 つ以上含めて置く必要がある。この記事では、この既存の文字を足場と呼ぶ。新しく置いた札が直交方向に作る単語も、辞書に載っていなければならない。
• 得点: 作った単語ごとに（文字の値の和。新しく置いた札には文字倍率を掛ける）×（新しく置いた札が載った単語倍率の積）。倍率のマスが効くのは、最初に札が載ったときの 1 回だけである。
• 実行時間とテスト: 対話形式で、制限は 1 ケース 10 秒。評価は相対評価で、各ケースの「自分の得点 / 全参加者の最大」の和で決まる。暫定テストは 100 ケース、最終テストは 5000 ケース。

スクラブルをテーマにした問題だが、ルールが単純な一方で、先の札が少ししか見えない以上、単語を計画的に狙うのが難しく、最後まで良い方法は思いつかなかった。

問題の性質の分析

まず、毎ターン得点が最大の手を置くだけの貪欲を書いて、どこで点を取っているかを調べた。解法を考える上で重要だった性質は、次の 4 つである。

1. 盤は 7 割ほど埋まると置けなくなる。 貪欲では、どのケースでも盤の 62〜78% が埋まったところで置ける手が無くなった。この割合は、最後の版までほとんど変わらなかった。残りの札を全部、普通の手と同じくらいの点で置けたとしても、得点は 1.2 倍ほどにしかならないので、伸ばすべきなのは置く枚数ではなく、1 枚あたりの点である。
2. 得点のほとんどは、数回の大きい手から来る。 単語倍率は積で効くので、×3 のマスを 3 つ踏めば 27 倍になる。途中の版で 60 ケースを数えると、手札を全部使う手は手数の 2.3% しかないのに、得点の 58% を占めていた。残りの手のほとんどは、札 1 枚あたり 10 点に届かない。
3. 大きい手は、待てば来る。 貪欲の盤面で各ターンを調べると、手札に無い札が 1 枚あれば置ける手の最高点は、今置ける手の最高点のだいたい 2 倍であった。例えば seed 1 の 5 手目では、貪欲は 27 点の FARM を置くが、同じ場所に O が 1 枚あれば 216 点の FANDOM が置ける。そして FARM を置いてしまうと、その場所の最高点は 78 点まで下がる。
4. 置いた札は戻せない。 安い単語で倍率のマスを踏むと、その倍率は二度と使えない。捨てた札も戻らない。

まとめると、この問題は取り消せない確率的な逐次決定である。点を伸ばすには、倍率の高いマスに、長い単語を、新しい札で置ける状態を作る必要があり、そのために札を待ったり、足場を先に置いたり、倍率のマスを安く踏まないようにしたりすることになる。

一方で、貪欲は 10 秒のうち 0.06 秒しか使っていなかった。1 ターン分の合法手を全部列挙しても 1 ms かからないので、時間はかなり余っている。

解法

0. 全体の形

毎ターン、合法手と見込みを列挙して行動に値を付け、値が最大の行動を出す。札の列は先が見えないので、ターンをまたいで計画を持ち続けることはせず、毎ターン今の盤面と手札から決め直す。ただし、手札に依らない大きい手の表（4 節）だけは、ターンをまたいで持ち越している。

最終提出の解は、例えば次のようになる。seed 4 のケース（$N = 18$、$T = 7$）を、手元で時間の制限を外して走らせたもので、得点は 11350 点である。

このケースでは、得点の 84% を上位 3 手（7992 点・918 点・648 点）が占めている。性質 2 の通り、序盤の小さい手と捨てで盤と手札を整え、大きい手を数回置くという形になる。

1. 列挙と見込み

合法手を全部出すのと同時に、あと数枚の札が来れば置ける手も一覧にする。この一覧の手を見込みと呼ぶ。性質 3 の通り、大きい手は待てば来るので、待つかどうかを決めるためにこれが要る。

列挙は、線ごとに辞書のトライを辿る。このとき、手札に無い札を 2 枚まで（得点の大きい手は 3 枚まで）「持っているもの」として辿れば、合法手と見込みが 1 回の列挙で出る。

見込み $w$ の値は、その得点に、足りない札が次の 32 枚のうちに来る確率を掛けたものとする。

$$v(w) = \mathrm{score}(w) \times \prod_{\ell} P\bigl(\text{32 枚のうちに文字 } \ell \text{ が } c_\ell \text{ 枚以上来る}\bigr)$$

$c_\ell$ は、$w$ を置くのに足りない文字 $\ell$ の枚数である。先読みで見えている札は確定として手札に数え、その先は文字ごとに二項分布の確率を表にしておき、文字どうしは独立とみなして掛ける。

最初は、補充を乱数で引いて試す方法も考えた。しかし、大きい手は数 % の確率でしか揃わないので、数十回の試行ではまず拾えない。確率を直接計算する方が速く、ぶれも無い。

2. 行動の値と数え直し

列挙した行動に値を付けて、最大のものを出す。

この値は、次に置く 1 手の見込みしか見ていないので、数ターンかけた準備の良し悪しを測ることはできない。その上で、次のような性質を満たすようにした。

1. 大きい手を待てる。 今置ける小さい手より、少し待てば置ける大きい手の方が良いなら、待つ（捨てる）方が選ばれる。
2. 倍率のマスを安く潰さない。 倍率の高いマスを、それに見合わない手で踏むと損になる。
3. 札を温存する。 同じ得点なら、使う札が少ない手の方が、残った札で次の見込みを作れる。
4. 置いた後の盤を見る。 置いた手が作る足場や、新しく開く場所は、置いた後の盤でしか数えられない。

色々試して最終的にたどり着いたのが次の値である。置く手 $m$ と、捨てる行動 $d$ について

$$\mathrm{val}(m) = \mathrm{score}(m) - \mathrm{pen}(m) + \max\nolimits_{w \in W(m)} v(w)$$ $$\mathrm{val}(d) = -D + \max\nolimits_{w \in W(d)} v(w)$$

とする。$W(m)$ は $m$ を置いた後も置ける見込みの集合で、$W(d)$ は捨てた後の手札で数えた見込みの集合である。

値引き $\mathrm{pen}(m)$ は、単語倍率のマスを安く踏むことと、札を使うことへの値段である。マス $c$ を含む連続 $T$ マスの、空いている単語倍率の積の最大を $\mathrm{win}(c)$ と書くと、

$$\mathrm{pen}(m) = \sum_{c} \mathrm{win}(c) + 3 \times (m \text{ が置く札の枚数})$$

で、和は $m$ が踏む単語倍率のマスのうち、$m$ の倍率が $\mathrm{win}(c)$ の半分に届かないものについて取る。第 1 項は、残りの札が $N^2$ の 3 割を切ったら線形に弱めていく。

ただし、ここまでの値には、$m$ を置いたことで新しく生まれる見込みが入っていない。全部の手について置いた後の盤で列挙し直すのは重すぎるので、上の値で上位 32 手だけを選び、実際に置いた盤で（$m$ が変えた線だけ）列挙し直して $W(m)$ を数え直す。このとき、$m$ で空いた手札に必ず入る先読みの札は、手札に入れて数える。

4 つの性質は、次のように実現している。

性質	式での実現
1. 大きい手を待てる	置く手にも捨てる行動にも、見込みの最大を足す
2. 倍率を安く潰さない	$\mathrm{pen}$ の第 1 項
3. 札を温存する	$\mathrm{pen}$ の第 2 項
4. 置いた後の盤を見る	上位 32 手の数え直し

3. 仕込み

大きい手には、主単語の途中に足場が 1 つ要る形が多い。そこで、その足場を先に置いておく手（仕込み）を評価できるようにした。

列挙のとき、空きマスを 1 つ選んで「この文字が先に置いてある」とみなした手も、見込みと同じように一覧にする。これを仮の手と呼ぶ。仮の文字は、今の手札で直交方向の単語としてそのマスに置ける文字に限る。

• 仮の文字をちょうどそのマスに置く手には、仮の手の値をそのまま足す。
• それ以外の行動でも、仮の手を潰さないなら、値を 4 割に割り引いて見込みとして数える。

図3 の 63 ターン目は、結果としてこの形になっている。

58 ターン目に縦の ETERNE を置いたことで、10 行目の 9 列目に R が入った。その左の 7 マスは空いていて、ちょうど手札 7 枚で埋められる。5 ターン後、手札が UNITIZE の 7 文字に揃ったところで UNITIZER を置き、7992 点を取っている。

4. 狙う線の表

3 節の仮の手は、今の手札から 1 文字を足すだけなので、手札が揃っていない大きい手は見えない。そこで、空いている単語倍率のマスのうち上位 $T$ 個の積がいちばん大きい線を 1 本選び、その線の上に手札に依らずに置ける大きい手を表にしておく。これを狙う線の表と呼ぶ。

表に入れるのは、新しい札 $T$ 枚まで（どの文字でもよい）と、先に置いておく文字 5 個までで置ける手である。先に置く文字は線の上で連続していてもよく、その場合は、連続した部分がそれ自体辞書の単語になっていることを条件にする。こうすると、「線の真ん中に短い単語を先に置き、後でその両側に札を足して長い単語にする」という 2 段の手順を表に持てる。単語倍率のマスが連続 $T$ マスの中に収まらず、間に空きマスを挟んで散らばっているときに、これでまとめて踏めるようになる。

表は線の上の文字が変わるまで持ち越し、毎ターン今の手札で値を付けて、上位 64 件を 3 節の仮の手と同じように使う。値は（得点）×（0.6 の、まだ置いていない先置きの文字数乗）×（揃う確率）である。

表を作るのは重い処理なので、1 文字増えただけならそのマスを通る単語だけを作り直す。さらに、1 回分の時間が残りの予算の 15% を超えそうなら作らない。

先に置く文字のマスには、既存の文字から直交方向に 4 マス以内であることも条件にしていた。足場から遠いマスには先置きの文字を置けないと考えたためである。しかし最終日に調べると、この条件が表を大きく狭めていた（振り返りで書く）。最終提出では、この条件を外した遠い表を別に持ち、使う文字を絞って軽くしたうえで併用している。

5. 場所の値

図4 の R のように、既存の文字の隣に空きマスが $T$ 個並んでいて、手札を全部使えば単語が置けそうな所を場所と呼ぶ。正確には、両隣が空いている既存の文字と、それを含む長さ $T + 1$ の区間で、残りの $T$ マスとその直交方向の隣が空いているものとする。

場所の良し悪しは、その文字が単語の中のどの位置にあるかと、空きマスの倍率で決まる。そこで、開始時に辞書から表 $S[\ell][i]$ を作っておく。これは、文字 $\ell$ を $i$ 番目に持つ長さ $T + 1$ の単語について、残りの $T$ 文字が新しい手札 $T$ 枚とちょうど一致する確率に、文字の値の和を掛けて足したものである。場所の値は $S[\ell][i]$ に空きマスの単語倍率の積を掛けたものとし、盤の全部の場所についての和を $\Phi$ と書く。

2 節で数え直す上位 32 手には、置いた後の $\Phi$ から今の $\Phi$ を引いたものを値に足す。これで、良い場所を作る手が上がり、潰す手が下がる。

6. 時間の管理

時間は、テスタが毎ターン返してくる経過時間（ジャッジの計測）で管理し、予算は 8 秒とした。ジャッジはローカルより 2.6 倍ほど遅く、手元で測った時間はあてにならなかったためである。

1 ターンの持ち時間は、残りの予算を、時間を気にせずに走らせたときの 1 ターンの時間の形に比例して配る。この形は、札を 4 割使うまではほぼ一定で、6 割を過ぎると 1 割以下になる。列挙が持ち時間を超えそうなら、単語倍率の小さい線から見込みを数えるのをやめていき、最後は倍率の大きい上位 4 本の線だけで見込みを数える。

取り組み方

AI の利用

このコンテストは AI ツールの使用に特に制限が無かったので、測定の段取りを先に固定しておけば、見ていない間に実装から測定までを任せることもできた。

• Claude Code（Opus 5.5）: 実装・測定・集計など、普段の作業は全てこれに任せた。
• ChatGPT: アイデア出しに使った。4 節の遠い表は、ここから出た案である。

AHC072 と卒業研究で疲れ切っていたので、実装・考察の多くを AI に任せてしまった。今回は私の介入があまり改善につながらなかった。

提出する版は私が決めた。採否はローカルで、同じケースの集合での比較で決めた。新しい仕組みは、それを無効にした設定で前の版と出力が一致することを確かめてから有効にしている。

作業の土台

作業の土台は、AHC072 のときと同じ自作のテンプレート WaTeR-7/ahc-template（CC0）である。AI エージェント向けの作業規約と、測定のスクリプト一式、過去回の知見置き場が入っている。

振り返り

暫定の順位表では、首位とは最後まで 1.8 倍ほどの差があった。伸びのほとんどは初日に出ていて、初日の夜に 1・2 節の形を提出した時点で、暫定スコアは貪欲の 27.3 から 46.0 になっている。以後の 3 日間に足した 3〜5 節と遠い表は、どれも数 % ずつの積み上げであった。

日時	出来事
10/11 朝	貪欲で性質 1〜3 を確かめた。「大きい手は待てば来る」ことから、見込みで選ぶ形に進んだ
10/11 昼	1・2 節の形がまとまった。上位との差は「数ターンかけた準備」にありそうだと考え、狙う線を決めて足場を仕込む計画を次の候補に挙げた
10/11〜10/12	計画を、見込みに足す項（3 節の仕込み、4 節の狙う線の表）として入れた
10/13	取れている倍率が狙う線の上限の半分ほどであること、表の狙いが毎ターン入れ替わっていることを測った。場所の値（5 節）を入れた
10/14 朝	狙う線の表に上限の倍率の単語が入らない原因が、先置きの文字への足場の条件だと分かった

計画を項として入れたこと

初日の昼の時点で、差は大きい手の側にあり、それを取るには数ターンかけて足場と手札を揃える計画が要る、というところまでは見えていた。しかし、それを解法の本体にはせず、1 手ずつ選ぶ貪欲の値に足す項として入れた。

項として入れると、計画は「今の手札で値を付けた見込みの 1 つ」になる。10/13 に測ると、表の中で値が最大の手（狙い）は、6 割近くが 1 ターンで別の手に入れ替わっていて、実際に置かれたのは 1% ほどであった。入れ替わりの 3 分の 2 は、手札が変わって別の手の値が上に来たためで、4 分の 1 は自分の手で狙いの場所を潰したためである。取れている最大の倍率も、狙う線の上限の半分ほど（倍率の高いマスが多いケースでは 2 割前後）であった。

そこで、前のターンの狙いを引き継ぐ手の値を重くしてみたが、強くするほど悪化した。見込みの値を膨らませたり、狙いへの寄せを強めたりする変更も色々試したが、どれも悪化するか誤差の範囲であった。1 手ずつ選ぶ貪欲の中で、計画を守らせる規則を外から足しても上手くいかなかった。

狙う線と単語を先に決め、そのために何ターン捨てて何を待つかを決める、という計画を本体にした形は、最後まで作らなかった。そのため、そちらの方が強かったのかどうかも分からないまま終わっている。

自分で付けた条件

4 節の表には、先置きの文字は足場から 4 マス以内、という条件を付けていた。最終日の朝に、条件を緩めた表を影で作って比べると、線の上限の倍率に届く単語が表に入っていたのは 270 ケース中 94 ケースだけで、条件を外すと 229 ケースに増えた。表を細らせていたのは、問題の制約ではなく、自分で付けた条件であった。

条件を外した遠い表は、時間を気にしなければはっきり効いたが、表を作る時間が重かった。使う文字を絞って軽くした形を最終提出に入れたところで、会期が終わっている。この条件は 10/12 の朝に表を作ったときから入っていたので、表に何が入っていないかをその日のうちに数えていれば、2 日早く気づけたはずである。

学び

• 候補を絞る条件を自分で付けたら、その条件で落ちたものを数える。 表や一覧を作ったら、条件を緩めた影の版を一度作り、何が増えるかを見る。
• 次の解法クラスの候補が見えたら、今の解法に項として足すだけで済ませず、それを本体にした形も一度作って比べる。 項として足した形しか作らないと、案そのものが弱いのか、足し方が悪いのかを切り分けられない。

おわりに

コンテスト期間中はどうしても生活リズムが狂ってしまうし、体力も消耗する。本業の学業が忙しくなれば、かけられる時間も少なくなる。コンテストと学業・生活の両立って難しい。社会人で仕事をしながら参加し高得点を取っている方々を尊敬している。