ホームページ目次2012-09-20(前)2012-10-09(次)

パズルに関する論文は、難易度判定から自動生成レベルに切り替えよう

2012年10月1日

教育研究機関において、パズルがいろいろ利用されているのはよいことだ。 これだけパズルが流行ってしまったこと、元々アルゴリズムの教育研究に向いた素材であることを考えれば当然である。

実際、検索エンジンで、「パズル」「論文」で検索すると、結構な件数がひっかかってくる。 学会では、情報処理学会、電子情報通信学会、OR学会の3つが中心のようだ。 もちろん、情報処理学会が割合的には相当多いようだが。

そして、どんな文字がタイトルに含まれているかというと、「難易度」の「判定」になるのだ。 要するに、パズルの問題を解いて、その問題がどのくらい難しいのかの判定を、なんとか合理的に行おうというものである。

このところ、パソコンの性能は非常に高くなっており、難易度判定程度なら、普通のパソコンまで持ち出さなくても、スマートフォン上でもできるくらい性能が向上している。

難易度の判定は、非常に純粋に数学的と言うか、なんらかの根拠、方針を立てて、 それにしたがって計算しようとしたものが多いようだ。 まあ、論文だから、根拠を求められるので、そうなるのだろう。 しかし、人間の難易度感覚にどこまで近づいているか、そういう比較は実は結構少ない気がする。

難易度を判定するには、とりあえず、問題を解くプログラムを作らねばならない。 手作業で解く方法がはっきりしているならば、これはほとんどの場合、単なるプログラミング作業である。 要するに、プログラミングの練習にしか過ぎない。 プログラミング言語の本の後ろの方に、発展問題として、以下のルールのパズルの問題を解くプログラムを作りなさい、などというのはあってしかるべきだ。

そういうことで、パズルを解くプログラムを作るのは、学部での、プログラミング演習として適当かと思う。

しかし、そこで止まっては、ダメである。 パズルを解いて喜んでいてはいけない。 パズルの問題を解いたのなら、その問題はどうやって作られたのか考えなければいけない。

パズル作家が手作業で作ったかもしれない。あるいは、コンピュータの支援を受けて作ったかもしれない。 あるいは、もう、コンピュータにたよりきった、自動生成にて作られて、人間は遊ばされているのかもしれない。

ということで、パズルの問題の自動生成をやろうではないか。 このために必要な能力は、パズルを解くプログラムを書ける必要がある。 そのあたりは、ホイホイとできてしまわないといけない。 なぜなら、そこから先が本当のプログラミングの世界なのだ。

最初は、乱数で力づくでやろうとしたり、答えから問題を作ろうとする人が多いようだ。 が、それではさっぱりのはずだ。できたとしても、愚問しかできないはずだ。

パズル作家は、パズルの注文を受けて、どのくらい苦労しているのか、ホイホイ作っているのか知らないが、 コンピュータで作るにしても、パズル作家の作った問題と同レベルくらいは作らないと評価対象外だろう。 できることなら、作家の作った問題と、コンピュータで作った問題を混ぜて、 それぞれの問題を人かコンピュータか、どちらが作ったか当ててもあるなどやるべきだろう。

問題を解くプログラムを「ソルバー」と呼び、問題を生成するプログラムを「ゼネレータ」と呼ぶ。 通常、ゼネレータの中にはソルバーが組み込まれている。 ソルバーもいろいろあるが、とにかく高速に解くものと、詳細な評価をするものがある。 もちろん、難易度の判定に関わる機能はとても重要だ。 問題生成時に使われるソルバーはとにかく高速でなくてはならない。 たった1つの問題を作るのに、何度となく、つまり数百回、数千回、数万回程度繰り替えしてソルバーで解くこともある。 だから、ミリ秒以下くらいで解けないと使い物にならないことが多い。

パズル作家が問題を作る場合、途中で破綻しないように注意しながら作っていく。 ということで、あまり無理ができないのである。 ナンプレで、ヒント数(問題の数字)が少ない問題は、パズル作家が手作りするのは非常に困難であった。

パズル作家のように問題を作ることは可能だ。 パズル作家の作問ノウハウをそのままプログラムするだけである。 このとき困難なことは、ノウハウがほとんどの場合、系統立ててまとまっていなくて、 なんとなくパズル作家の頭の中にあるだけに過ぎないことが多い。 また、パズル作家がプログラマでもある場合はよいのだが、別の人間であると、 その間のコミュニケーションが困難を極めることが多々ある。

しかし、コンピュータが、どんどん高速に評価する、さらに人間と違って疲れることを知らないのを利用して、 どんどん作っては解かせることを繰り替えして、問題として完成させることができる。 このおかげで、今ではヒント数が18個の問題を誰もが楽しめるようになった。 そして、20以下の非常にヒントが少ない問題で、やさしい問題から難しい問題まで揃えられるようになった。 それ以外にも、特徴ある問題をどんどん作られるようになった。

これは、基本的には、ナンプレだけではなく、当然他の多くのパズルにも応用できる。


ホームページ目次2012-09-20(前)2012-10-09(次)