Home
パズル問題自動生成時代
ナンプレ
はじめに
プログラムで問題を解く
プログラムで問題を自動生成
- 手作りの方法
- 破綻の判定が欲しい
- 序盤の数字のばらまき方
- 多重解にならないために
- 中盤は統計的にごまかそう
- 終盤へのつなぎ方
- 良い問題を目指して
- 終盤は問題の選択
- 見かけが大切
- 隠れた工夫
- 面白さの実現について
- 自動生成プログラムのススメ
乱数の乱用だけでは限界
将来展望
- もしミリ秒で問題生成できたら
- 誰でも簡単に問題が作れたら
- 自動生成も多種多様
- 解き方を見て問題を提供
- パズル作家風の問題生成
- 自動生成プログラムの自動生成
- 多種パズルに適用可能な汎用的アルゴリズム
- いつごろ実現できるか (1)
- オープンソースでの公開
- パズル作家は何をすべきか
パズル問題自動生成時代 -- ナンプレ -- プログラムで問題を自動生成
自動生成プログラムのススメ
ナンプレの場合、問題を解くのはかなり簡単だ。 まあ、学校でプログラミングを教わった後の練習問題として 作ってみる程度と言ってもよい。
もちろん、どういう風に解くか、様々な工夫は考えられ、 速いだけでなく、まるで人間が解いているように解くとか、 難易度判定をいかにするかなど、より高度な分野はもちろんある。
しかし、やっぱり、パズルは、問題を作る方が解くより楽しい。 問題を作って、他人に解かせて楽しんでいる、あるいは苦しんでいる、 間違えてしまうのを眺めているのがパズルに対する望ましい姿勢ではないだろうか。
手作業で作るのは、ナンプレのように比較的単純なパズルでも大変だ。 慣れても、１問作るのに数十分かかる。 それも、かなり神経を集中させているから、一日中、問題を作り続けることはできない。 30分で１問できるとして、１日８時間労働で、毎日１６問作り、 １ヵ月２０日働くとして、３２０問作るという計算は絶対に成り立たない。
要するに、人が作っていたのでは、量産が絶対にできない。 もちろん、ナンプレの場合、全てを手作りしているパズル作家もまだいようが、 様々なコンピュータ支援を受けながらやっているパズル作家が少からずいる。 こんなことはパズル作家が言わなければ分からないことであり、 パズル会社の中には隠したがる所もあるが、もうそういう時代ではあるまい。
また、人間が作れる問題には、かなり限界がある。 ナンプレの場合だと、数字が少い問題をパズル作家が作るのは非常に困難だ。 本当に手作りだけで１８個しか数字のない問題をつくるのは極めて困難で、 実際、そのような問題が載っている問題集もほとんどない。
[/Japanese/NPProblems/Java18//１８ヒント問題集(全100問)] を公開しているが、この問題は自動生成で作ったものだ。 １８個しかヒントのない問題を惜しげもなく提供するには、 自動生成プログラムを作る以外に方法はないだろう。
人間ならとてもできないようなことを、 コンピュータお得意の超高速さを利用して克復することができる。 問題の作り方の基本のアイデアを人間が出し、 それをプログラムにして実行することで、 今までにない速度で、質の高い問題を作れるようになる。
そういう時代が着々と近づいてきている。 そして、そういう時代がくるのなら、 どんどん紹介し、後押ししようというのが本書の最大の狙いでもある。
アルゴリズムの研究に最適
今までは、パズルを解くプログラムを作ることがアルゴリズムの向上に役立つ、 ということがしばしば言われた。 確かに、それは間違いではないが、 ナンプレの場合には、問題を解くだけのプログラムなら、 まあ、入門書の練習問題で終ってしまうといってもよいだろう。
本当にアルゴリズムの勉強、というより研究になり、 アルゴリズムの腕を一気に上げるには、パズルの自動生成が適している。
何たって、問題を作ることは、問題を解くことよりははるかに困難だ。 困難なことを、アルゴリズムの工夫で何とかすることで、 本格派のアルゴリズムを習得できる。
パズルの場合、速度差が圧倒的に顕著に現われる。 10倍程度の差は微差で、アルゴリズムの良否で100倍、1000倍は普通だ。 これは、プログラミングテクニックによる改善などとは桁が違う。 こういう大差を思いっきり味わうことができるパズルの自動生成は 奥が深く、まだまだこれからの世界である。
速度がどんどん上昇した場合のことは、次の将来展望 で詳しく考察することにし、ここでは研究的側面だけを書くことにする。
自動生成のアルゴリズムも色々考えられよう。 本書で今まで紹介してきたものも、自動生成のアルゴリズムの１つに過ぎない。 もっと人間的な方法から、およそ人間では不可能な方法まで、 どんなアルゴリズムが現実に可能なのかはまだ良く分かっていない。
本当は、もうちょっと先まで分かりつつあるところなのであるが、 乞うご期待ということにしよう。
新しいアルゴリズムを考え出すには、今までとは異なったセンスが必要だ。 新しい奇抜なセンスで問題に取り組むことで、 新しいアルゴリズムが生まれてくる。
パズルの良いところは、結果の判断がかなりはっきりすることである。 自動生成でも、できあがった問題の質は、パズルを日頃から解いて 楽しんでいるパズラーの方々ならいとも簡単に質の評価が可能だ。
プログラムサイズは小さい
パズルのプログラムは、基本的に非常に小さなものだ。 事務処理など、実際の業務に拘わるプログラムの場合、 さまざまな条件がやたらに多く、本質的な部分よりも、 例外処理などが多くなってしまう。 また、プログラム規模が大きくなってしまうので、 多人数の共同開発しかなくなってしまう。
そうなると、アルゴリズムよりも、いかに作業を共通化するかとか、 共同開発の効率向上が最も重要な課題になってしまう。
アルゴリズムを本格的に研究するには、できることならというよりも、 やはり一人で全部を完全に掌握できるくらいの規模でないと難しい。
GUIを凝るとどんどん大きくなっていくのは他のソフトと同じだが、 それらは自動生成の本質部分ではない。 GUIは便利さをもたらすので重要ではあるが、 アルゴリズムの面から言えは枝葉末節に過ぎない。
問題の自動生成の本体、「自動生成エンジン」と呼ぶべき部分が アルゴリズムの塊になる。 ものすごい回数、ループしたり、再帰呼出しするなどして、 延々と問題作りのためにコンピュータを使い倒す部分である。
小さいけれど、計算処理量が莫大になりがち、 あるいは簡単に永久ループなどに陥ってしまうという情况は、 危険きわまりない分野である。 しかし、そういう危険な分野こそ、アルゴリズム研究対象としては理想的である。
普通にプログラムを追いかけてデバッグなどとてもできない分野というのは、 とても面白いものである。 課題は難しいが、良いアルゴリズムを発見すると、 一気に問題が解決してしまうことがある。 アルゴリズムの偉力が非常に明白に出る分野である。
もちろん、うまく行かないのが普通なので、 簡単には挫折しないように注意しなければいけない。 パズルの自動生成に関する情報はまだほとんどない。 問題を解くためのプログラムは、 インターネットでいくらでも集められるが、 問題を作る方となると、プログラムどころか、 考え方さえほとんど出ていない。 というより、ごく一部の情報を除いて、 役に立つと思われる情報すらない世界である。
つまり、いつでも世界の第一人者になれる夢の多い世界である。