【プログラミング連載】もじぴったん(PS2版)を解かせたい！【第１回】
わたしには夢があります！ 霧しゃまです。
今日は霧しゃまが「アルゴリズム」というものに興味を持つきっかけとなったゲームについて書いてみます。
競プロ界隈、機械学習界隈の方などには興味を持っていただけるのではないかと思います。どうぞお付き合いください！
忙しい人向けのまとめ
・霧しゃまがアルゴリズムに興味を持ったのは、「もじぴったん」というゲームを解くプログラムを作りたいと思ったのがきっかけだよ！
・かつてスコアを競っていた人たちの記録がほぼ失われてしまった現代、８年くらい研究を続けてきたよ！
・これからはAtCoderで言うアルゴリズム部門・ヒューリスティック部門の両面のアプローチで取り組みたいと思っているよ！
「もじぴったん」とは？
ここからはいつもの真面目モードで。
「もじぴったん」とは、文字（基本的にはひらがな）を並べて言葉を作るパズルゲームです。ここからは、ややこしい追加ルール（主に特定の文字を無限に使用できる制約）のないPS2版を中心に解説していきます。
競プロ的に言うと、$${H}$$行$${W}$$マスのグリッドが与えられ、それぞれのマスが白または黒で塗られているものを思い浮かべてください。
白マスに文字を置くことができます。開始時には必ず$${1}$$個以上の文字があらかじめ置かれているものとします。
$${N}$$個の文字が与えられます。これをゲーム内では「えらぶくん」と言います。文字は、すべての清音（あ～ん）、濁音半濁音（が～ぱ）、伸ばし棒（ー）の72種類のいずれかであり、重複もあります。ちなみに、「っ」「ゃ」「ゅ」「ょ」など小さい文字は、対応する大きい文字と同一視されます。（例：もじぴったん ＝ もじぴつたん）
通常時には、与えられた文字の中から任意の$${1}$$個を選び、その文字が、すでに置いてある文字と合わせて「言葉が成立する」ような白マスに置くことができます。置いた文字はえらぶくんから無くなります。
ステージごとに定められた条件を満たせばクリアです。条件には以下のようなものがあります（実際のゲームでは当然、与えられた盤面とえらぶくんに対して条件を達成できることが保証されています）。
文字を$${X}$$個置く
言葉を$${X}$$個作る（文字数の範囲が指定されることもある）
特定の文字を含む言葉を$${X}$$個作る
特定の言葉を$${X}$$個作る
$${C}$$連鎖を$${X}$$回作る（連鎖については後述）
すべての白マスを埋める、特定の白マスを埋める
「言葉を形成する」について説明します。
文字を置こうとしているマスを起点に上下方向・左右方向それぞれに連続している文字列（黒マスや空の白マスがあると途切れます）を、上から下へ、左から右へそれぞれ抜き出したときに、置こうとする文字を含む連続した部分文字列が$${1}$$個以上、「辞書」内の言葉のいずれかに一致するとき、言葉が成立します。
次に、連鎖と得点について説明します。
同時に$${2}$$個以上の言葉が成立した場合は連鎖となります。
その得点は、$${(連鎖数) \times (素点の総和)}$$です。
素点は、成立した言葉それぞれに対して与えられます。その計算式は、言葉の文字数を$${L}$$とすると、$${10 \times 2^{L-1}}$$点です。
ただし、「辞書」内の言葉はすべて$${2}$$文字以上$${9}$$文字以下です。
素点は$${2}$$文字の場合$${20}$$点、$${9}$$文字の場合は$${2560}$$点です。
得点がステージクリア自体の条件になることはありません。いわゆる「やりこみ要素」です。つまり、これを追い求めるのが永遠の課題です。
盤面の制約ですが、$${1 \leq H \leq 9}$$ $${1 \leq W \leq 13}$$かつ、$${2 \leq min(H, W) }$$が成り立ち、盤面には文字の置かれた白マスと、文字の置かれていない白マスがそれぞれ$${1}$$個以上存在します。
与えられる文字数は、おおよそ$${1 \leq N \leq 250}$$です。
最後に最も重要な「辞書」ですが、これはシリーズによって大きさが異なります。イメージとしては、ユニークな$${2}$$文字以上$${9}$$文字以下の文字列が約$${10^5}$$個入っていると考えてください。PS2版では$${75000}$$個くらいです。辞書の違いによって、同じ盤面のステージでも最適解が変わります。最適解を検討するときは、どのシリーズの辞書を前提とするかを決める必要があります。
研究の始まり、失われた遺産
PS2版の「もじぴったん」については、かつて2chや個人サイトなどでスコアアタックの研究が盛んに行われており、かなりやりこまれていたようです。
しかし、それは約20年前の話で（PS2版の発売から今年でちょうど20周年になるようです）、今となっては当時の記録、解法、行われていた研究の内容など、おおよそあらゆるものが跡形もなくなっています。ぶっちゃけ最新シリーズのほうが辞書もステージも充実していて、一般にPS2版は完全に終わったコンテンツです。
霧しゃまが「もじぴったん」の研究を始めたのは2015年頃からで、まだジオシティーズはなくなっていない頃でしたが、それでも最盛期の資料や記録はほぼ散逸していたと思います。攻略情報がやり取りされていたらしいBBSにはスパムが跋扈し、いくつかの拠点的な個人サイトもリンク切れでした。
そういう環境だったので、最初は本当に軽い気持ちで、自己満足的に、少し意識して稼ぐところから研究が始まりました。ただ、ゲーム内で作れた言葉、つまり「辞書」の記録はその頃から始めました。すべて手作業で、ちまちまと。
2020年頃、ライフスタイルの変化もあって、人力での研究に限界を感じ始めます。ちょうどその頃個人的プログラミングブームが来ていたので、勉強がてら、Pythonでもじぴったんを再現するシミュレータを作ってみました。それにしても、ただ再現するだけでは実機の下位互換にしかなりません。そこで、最終目標が「もじぴったんをプログラムで解くこと」になったのです。
これ、たぶんNP困難です
シミュレータを作り始めて3年、とりあえず「決めた手数をランダムに進める探索を反復し、その中で最も得点の高かったものを採用する」というアルゴリズムを独学で組み上げ、最も簡単な部類のステージくらいならプログラムで解けるようになりました。
しかし、所詮はランダムな探索なので、特定の強い（＝大連鎖になる）言葉を作ったり、最適な連鎖にするために文字を置く順序を工夫したり（同じ言葉でも、どの文字を最後に置くかで連鎖数が変わります）は全くできません。反復数を多くとれることだけが強みで、その他は譬えるなら5歳児レベルです。
いかんせん、アイデアがあったとしてもそれをプログラムとして実現するための知識が絶対的に足りませんでした。それが、アルゴリズムについて本格的に勉強しようと思い立ち、競プロを始めるに至った直接的なきっかけです。
例えば、盤面に強い言葉を可能な限り敷き詰めて、その完成形を目指して文字を置く順序を最適化するようなアプローチが考えられます。このどちらのステップも一筋縄ではいきそうにありません。愚直な全探索は本当に小さい盤面でしかできないと思います（ただ、$${4 \times 4}$$くらいの盤面なら人力でも得点の最大値を出すパターンを探し当てられると思います。それが最大値であることの証明は別として……）。
肌感覚ですが、巡回セールスマン問題的な重み付き経路の最適化要素があり、それ以前に盤面の最適化要素があることを考えると、NP困難に属する問題であることはほぼ間違いないと思います。
ただ、せっかくなのでヒューリスティック的手法でどうにかすることと、厳密なアルゴリズムでどうにかすることの両面から、様々なアプローチを検討していきたいと思っています。
おわりに
ということで、今回はイントロダクション的な記事でした！
もじぴったんの奥深さに、少しでも興味を持っていただければ幸いです(昔はここで公式の体験版flashを勧めるところでしたが、今はもうありません><)。
不定期連載ということで、今後も競プロ的な観点で引き続きもじぴったんを紹介していきたいと思います！
パズルが好きな皆様、ぜひもじぴったん沼にハマってみてください！