こんにちは
今回は私が運営として参加している進化計算コンペティションについて紹介します。
進化計算コンペティションとは？
進化計算コンペティションは、最適化のコンペティションです。
2017年進化計算学会の実世界ベンチマーク問題分科会から始まりました。
現在も毎年進化計算シンポジウムというイベントと一緒に行われていますが、問題を解くためには必ずしも進化計算アルゴリズムを使う必要はありません。
毎年、様々なテーマを取り上げ、大学関係者・企業・個人など様々な参加者は各自の工夫で最適化の課題を解きます。
今年の進化計算コンペ2024では、難易度と面白さを考慮したナンプレの自動作成問題を主題としています。
この問題は、ナンプレの出版分野で豊富な実績を持つタイムインターメディア様と協力して作成しました。
私も問題作成者の一員として参加しています。
コンペでは、出題者が設定した条件に合うナンプレの問題を作成していきます。
参加者はサーバーに何度か解を送り、評価値を受け取ることができ、最終的に評価基準に従って表彰されます。
進化計算コンペティションは、プログラミングコンテストの一種です。参加者は最適化問題を解くためのアルゴリズムを実装し、その性能によって順位が決まります。
進化計算コンペティションの目的は、最適化の実問題に対する知見を産学で共有することです。そのため、産業や科学の現場で実際に使われているリアルな実問題が出題されます。例年、幅広い分野から多種多様な実問題がピックアップされています。
過去の問題例は以下の通りです：
- 2017年：複数車種の同時設計最適化問題
- 2018年：月着陸ミッションの最適着陸地点の選定問題
- 2019年：風力発電用風車の設計問題
- 2020年：ゲーム用乱数の設計
- 2021年：経済支援施策の設計
- 2022年：発生交通量推定
- 2023年：自動化が進んだ製造工場における機械加工スケジューリング問題
- 2024年：難易度と面白さを考慮したナンプレの自動作成問題
このように、進化計算コンペティションは実問題を通じて、産業界や学術界における最適化技術の進展に寄与しています。
ナンプレ
今年のテーマであるナンプレについて少し解説します。
ナンプレは、ご存じの通り、3×3のブロックに区切られた9×9の正方形の枠内に1〜9までの数字を入れるパズルです。
縦横ブロックでそれぞれの数字が一つだけ入るという制約があり、最初に埋められたヒントの数字を元にして推理して数字を埋めていきます。
詳しくは
Wikipedia などご参照ください。
ナンプレ解法探索
「解ける」ナンプレを作るためには、ナンプレを解くプログラムを作成することが必要です。
コンピュータで数理最適化問題として数値的にナンプレを解くのは実はそれほど難しくなく、
ほとんどの問題は秒もかからずに解けます。
しかし、今回注目したのは面白さや難易度という指標です。
つまり、実際世間にあるパズルはいかにして楽しむかを目指して作られています。
そのためこのコンペでも、人が解いてほどほどに難しく、単調ではなく面白いナンプレを作ることを目指しました。
そのため、コンペの問題作成委員として実際に多くのナンプレを解きつつ、解法テクニックをメンバーで議論し、できるだけ人と近い方法で解く解法シミュレータプログラムを開発しました。
ナンプレの解法テクニック
ナンプレを解くためには、いくつかの基本的なテクニックがあり、それぞれ一般的な名前がついています。世界中にファンがいるのでテクニックには標準的なかっこいい英語名もついています。
簡単に概要を紹介します：
-
単一候補法, naked singles：
各セルに入る可能性のある数字を絞り込み、唯一の候補が残った場合にその数字を確定させる方法です。 -
隠れた単一候補法, hidden singles：
特定の行、列、またはブロック内で特定の数字が入る可能性が一つしかない場合、その数字を確定させる方法です。 -
ペア・トリプレット法, naked/hidden pairs/triples：
行、列、またはブロック内で特定の数字の組み合わせが決まっている場合、それらの数字を他のセルから除外する方法です。 -
井桁理論, X-wing：
特定の数字が2つの行と2つの列に交差する形で現れる場合、その数字を他のセルから除外する方法です。 -
ソードフィッシュ(swordfish)：
Xウィングの拡張版で、特定の数字が3つの行と3つの列に交差する形で現れる場合に適用される方法です。
１，２は比較的誰でも思いつく手法で初級だとすると、３ぐらいから中級、
４，５のX-WingやSwordfishなどは上級の手法です。
つまり４，５の手法がわからないといわゆる上級のパズルは解けません。
これらのテクニックを利用して解くことで、
人間が解く際に感じる楽しさや挑戦を加味した評価を行うことができると考えています。
コンペの状況
コンペは11月16日から開始し、現在進行中です。
12月21日の最終プレゼンを経て表彰されます。
最終プレゼンは進化計算学会シンポジウムというイベントの一部としておこなわれ、チームごとにプレゼンしていきます。
12月10日現在、評価値を計算するサーバーがうまく動かない、参加登録されていないなど日々トラブルもありつつ、なんとか運営しています。
状況が知りたい方はコンペのサイトへどうぞ
解法シミュレータの実装の苦労についても解説したいのですが、コンペ期間中ということもあり、終了後に再度解説記事を書きたいと思います。
パズル
難易度の高い問題を作るのは結構難しいです。
ヒント数が少なくなってくるとそもそも解けない組み合わせが大量に出てきます。
コンペでは決められたヒントパターン（２０，２４個）の制約で問題を作る課題です。
比較的簡単に解けるナンプレパズルを難易度別に用意しましたので挑戦してみてください。
英字記号は行列の記号です。ヒント数はいずれも28個です。
「面白さ」という観点では、あなたはどの盤面が好みですか？
初級
| J | K | L | M | N | O | P | Q | R | |
|---|---|---|---|---|---|---|---|---|---|
| A | 1 | 5 | 7 | ||||||
| B | 7 | 3 | |||||||
| C | 8 | 3 | 4 | ||||||
| D | 6 | 4 | |||||||
| E | 4 | 2 | |||||||
| F | 7 | 9 | 6 | ||||||
| G | 4 | 1 | 2 | 7 | 9 | 5 | |||
| H | 3 | 5 | 2 | ||||||
| I | 6 | 1 | 3 | 2 |
アルゴリズムで解く人のために直列につなげたものも載せておきます。０は空白を意味しています。
100050700007300000800000304600004000004000020079000006412070950305200000060010032
中級
| J | K | L | M | N | O | P | Q | R | |
|---|---|---|---|---|---|---|---|---|---|
| A | 3 | 5 | 6 | 9 | |||||
| B | 3 | 2 | |||||||
| C | 5 | 6 | 9 | 3 | 1 | ||||
| D | 8 | 4 | 9 | ||||||
| E | 6 | 7 | 1 | ||||||
| F | 7 | 9 | 5 | ||||||
| G | 4 | 1 | 8 | ||||||
| H | 5 | 4 | 1 | ||||||
| I | 7 | 3 |
003056009000300200056090310000804090000067100079005000410000008005040001700000030
上級
| J | K | L | M | N | O | P | Q | R | |
|---|---|---|---|---|---|---|---|---|---|
| A | 6 | 7 | 8 | ||||||
| B | 4 | 3 | |||||||
| C | 5 | 6 | 7 | 9 | 4 | ||||
| D | 3 | 8 | |||||||
| E | 6 | 1 | |||||||
| F | 7 | 5 | |||||||
| G | 4 | 2 | 7 | 9 | |||||
| H | 2 | 8 | 6 | 7 | |||||
| I | 7 | 8 | 9 | 2 |
000006780040300000056790004030800000000060100070005000402070900000208670708009002
Discussion