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

問題の自動生成に使うアルゴリズム

2012年10月15日

パズルの問題を自動生成するのに、どのようなアルゴリズムを使うか秘密を暴露しようと思う。 というか、そんなもの、実は秘密でも何でもない気がする。

ただし、前提条件として、パズル、プログラミング、アルゴリズムなどには、ある程度精通していると仮定する。 このあたりを仮定しないと、延々と説明しなくてはいけないので、そんな面倒なことはできない。

普通は、多重解になるかもしれない問題を、初期問題としてでっち上げる。 その問題には、変更可能なところがあり、適当に変更すると、一意の解が得られる、と考えるのだ。

ナンプレを例に説明しよう。 まず、問題の数字の場所(パターン)を決める。 そして、全マス数字が埋まっている答えと、このパターンを重ね合わせて、パターンの部分だけ残す。 すると、問題ができ、この問題は少なくとも1つの解を持つ。 もちろん、ほとんど確実に多重解になってしまうわけだが。

さて、ここから調整を行って、解が1つだけにしてしまうのだ。 そのためには、いろいろな方法が考えられる。 多くの人は、自分の頭で考えようとするようだが、 天才でもないかぎり、そんなことをしても無駄に終わることが多い。

こういう場合に利用できるアルゴリズムというのが、昔からいくつか決まっている。 数字をすこしずついじりながら、解が1つかどうか、決める。 このとき、評価関数というか、ゴール(解が1つ)までの距離を示す関数をでっち上げるのだ。 多くの場合、未決定マスの数を関数の値とする。 実際には、これでは細かい調整には向かなかったり、情報不足だったりするが、とりあえず無視しよう。

ある関数があたえられたとき、その関数が最小値(空きマス数だから、問題完成は最小値0の時)になるように、 問題の数字を調整する。 このとき、いくつかのアルゴリズムが使えるのだ。局所的最適化(山登り法、山下り法?)、貪欲法、遺伝的アルゴリズムなどだ。 実際には、パズルの性質に合わせて適度にアレンジするのも構わない。

もちろん、これらは、最適解を保証するものでもないし、本当はその配置での問題作成が可能なのに、作成に失敗することもある。 いずれにしても、偶然に頼る、とてもいい加減な方法であるが、かなりうまく行くことが多い。

いずれの方法を使うにしても、問題を少しずつ変更しては解き直すのを繰り返す。 数字を何でもよいから適当の入れ替えるだけだと、解の無い問題になってしまう可能性もあり、 次第に解がユニークな問題に近づけようとしているのに、破綻に近づいてしまうことがある。 そのため、できることなら、解が1つ以上存在するという条件を満たしながら変更した方が良いことが多い。

しかし、いろいろな条件を満たしながら変更しようとすると、 プログラムが複雑になったり、そのための調整に時間がかかったりするようになるので、痛し痒しである。 まあ、そのあたりは、適当なところで妥協するのが現実的な方法だ。

どの方法で行うにしても、何度も、何十度、あるいは何百度も少しずつ違う問題を解くという作業がある。 そのためには、まず、問題を解くプログラムが、相当高速でなくてはならない。 普通、ソルバーは1問1ミリ秒程度で結果を出さないと、 十分な性能を持った自動生成プログラム(ジェネレータ)はできない。

さあ、ここまで読んだら、パズル問題の自動生成がどんなものか分かったのではないだろうか。 おおよそでも分かったら、あとは自分で手を動かして作ってみることだ。 うまくいかなかったら、そこでちょっと頭も使うと、自動生成が動き出すかもしれない。 さあ、やってみよう。


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