博士

ロボ子、Boggleの最高得点を計算機で証明したってニュースは知ってるかのじゃ？

ロボ子

はい、博士。総当たり探索は不可能なので、「分枝限定法」を使ったそうですね。

博士

そうそう！天文学的な組み合わせがあるから、全部試すのは無理なのじゃ。そこで、盤面をグループ化して、各グループの最高得点の上限を計算したらしいぞ。

ロボ子

上限が3625点未満のグループは破棄したんですね。効率的です。

博士

ENABLE2Kの単語リストだと、最高得点は3625点で、盤面は「P E R S / L A T G / S I N E / T E R S」らしいぞ。STRANGERSとかPLASTERINGとか作れるみたいじゃ。

ロボ子

1982年の論文では2047点が最高だったんですね。今回の研究で大幅に更新されたんですね。

博士

昔の手法は「hill climbing」って言って、局所的な最適解に陥りやすかったみたいじゃな。今回はもっと深い探索をしたらしいぞ。

ロボ子

一度に複数のセルを変更したり、複数の候補を追跡したりしたんですね。

博士

「分枝限定法」のために、「sum/choice」ツリーっていう独自のツリー構造を開発したらしいぞ。すごいじゃろ？

ロボ子

Google Cloudの192コアのインスタンスを5日間も使ったんですね。計算資源もすごいですね。

博士

コードはC++とPythonを使ったみたいじゃ。パフォーマンスが重要な部分はC++、それ以外はPythonって感じかの。

ロボ子

pybind11で連携したんですね。博士、AIは使ったんでしょうか？

博士

AIはほとんど使ってないらしいぞ！古典的なデータ構造とアルゴリズムを使ったみたいじゃ。GitHub Copilotはちょっと手伝ったみたいじゃけど。

ロボ子

OSPD Scrabble Dictionaryだと、最高の盤面は「splseaiertnrsges」で3827ポイントだそうですね。

博士

英語以外の言語でもできるみたいじゃぞ。ロボ子、日本語のBoggleで最高得点を目指してみるかの？

ロボ子

面白そうですね！でも、GPUアクセラレーションは向いていないみたいなので、時間がかかりそうですね。

博士

5x5や6x6のBoggleにも挑戦できるみたいじゃ。夢が広がるのじゃ！

ロボ子

計算費用は約1200ドルだったそうですね。結構かかりますね。

博士

ロボ子、今回の研究でBoggleの奥深さがわかったのじゃ。次はロボ子が最高得点を見つける番じゃぞ！

ロボ子

頑張ります！ところで博士、Boggleの盤面で一番多い文字は何だと思いますか？

博士

うーん、Eかの？

ロボ子

ブー！正解は…『ボ』です！