Home
パズル問題自動生成時代
ナンプレ
はじめに
プログラムで問題を解く
プログラムで問題を自動生成
- 手作りの方法
- 破綻の判定が欲しい
- 序盤の数字のばらまき方
- 多重解にならないために
- 中盤は統計的にごまかそう
- 終盤へのつなぎ方
- 良い問題を目指して
- 終盤は問題の選択
- 見かけが大切
- 隠れた工夫
- 面白さの実現について
- 自動生成プログラムのススメ
乱数の乱用だけでは限界
将来展望
- もしミリ秒で問題生成できたら
- 誰でも簡単に問題が作れたら
- 自動生成も多種多様
- 解き方を見て問題を提供
- パズル作家風の問題生成
- 自動生成プログラムの自動生成
- 多種パズルに適用可能な汎用的アルゴリズム
- いつごろ実現できるか (1)
- オープンソースでの公開
- パズル作家は何をすべきか
パズル問題自動生成時代 -- ナンプレ -- プログラムで問題を自動生成
終盤は問題の選択
ユニーク解の数
終盤に到達したところで、解の総数は指定数(10000)を下まわっている。 そして、ユニーク解の個数も決まっている。その中から、最終的に 良い解を選んで、空色マスの位置だけを残したものを問題とする。
さて、そのとき、ユニーク解の個数がどのような感じになるか考えてみよう。 ユニーク解は、かなり互いに似ている問題が多いので、 捨てるのはもったいないからと複数個を問題として採用してしまうと、 解く方は同じような問題を解いたような感覚に陥り、面白さをなくす。 そのため、一回の作成では、１つだけしか残さない方がよい。
では、実際にどの位のユニーク解が終盤で残っているか、確認してみよう。
例によって次のパターンで考えてみる。
乱数を使っているので結果は毎回異なるが、 調査する解の上限数を10000で調べてみたら、 次のところまで決定した段階で中盤を終えた。
未決定空色マスの個数が５個になっている。
解の総数は、9395個数になった。
さて、これで、ユニーク解の個数はいくつになっただろうか。
ユニーク解は３個
ユニーク解の個数があまり多いと、その中から適当なものを選ぶのに、 あれこれしっかり調べてから判断しようとすると時間がかかる。
逆に、１個しかないと、選ぶ余地がない。 ユニークであるだけで、論理的手法だけでは解けないような問題の可能性もあり、 そういう場合には、たった１個のユニーク解も捨てないといけない。
さて、今回得られた３問はどうだったであろうか。
No.1
No.2
No.3
難易度の調査
３問の難易度の差はどうだったであろうか。
| No.1 | Level 5 |
| No.2 | Level 10 |
| No.3 | Level 13 |
表の示すところによると、No.1の問題は、中級問題の典型的なレベルであり、 問題としても、まあ妥当なものであろう。
No.2 は、難問中の難問であると言っている。 もちろん、判断するソフトが正しいとしての話であり、 判断するソフトは私が作ったので自分でも書いていながら自信がない。 それで、実際に解いてみようとして途中で破綻したので、 確かにとても難しい問題だろう。
No.3 は、あまりにも困難で、破綻するところまでも辿りつけなかった。
ということで、この３つから選ぶのだったら、普通なら No.1 を選ぶことになろう。 選び方は、そのときそのときで欲しい問題の基準が違うから簡単には説明できないが、 普通はやさしい問題を選ぶのが順当なことが多い。
さて、今回は、解総数9395個からユニーク解が３個になるという とても扱いやすいパターンだった。
表出２４の問題だったら、この位が相場とも言えるのだが、 入門的な問題で、たとえば次のような 表出２８の問題ではどういう傾向が出てくるだろうか。
メモリが足りない
解の総数が10000を切ったとき、次図の状態になった。
このとき、解の総数は5042個であった。
残りの空色マスは、まだ１２個も残っているので、自由度ありまくりである。
そして、ユニーク解の総数は、1995となった。
これだけユニーク解が存在すると、コンピュータでも評価に時間がかかる。 １つの問題候補を1/100秒で評価しても、19.95秒もかかる。待っていられない。 でも、いい加減な評価では不味いしどうしようと思っていたら、 もっと重大な事件が起きていた。
java.lang.OutOfMemoryError: Java heap space
一体何が起きたのだろうか？
メモリを使い尽くしてしまったようだ。 Javaなんだから、メモリのことなど気にしなくても大丈夫というのは 甘かったようだ。
そもそも、ユニーク解を評価するとき、今のシステムでは、 人間が解いたら実際にどのように解いていくか、そのとき、どういう途中経過を 辿るかなど、途中の情報を捨てることなくユニーク解毎に保持している。
そして、全部のユニーク解の詳細な評価が終ったとき、 全ユニーク解の保持データを比較検討し、 指定条件範囲内で一番適切を思われるものを問題として選択している。
本当は、最後まで詳細な情報をユニーク解毎に保持しなくても、 それまでの最適なものを１つだけ保持しておけば良いのだが、 ユニーク解全体の傾向を知りたかったので、保持してしまった。
ユニーク解の個数が多くなった場合、もう１つの問題が発生する。 評価に時間がかかるようになる。ユニーク解の個数に比例して 処理時間が増えて行く。 1995個ユニーク解があったので、1/100秒で１問を評価しても、 約20秒待たされてしまう。
ということで、解の総数が一定以下になったらユニーク解を求め、 各ユニーク解について詳細に調べるという方法には少々無理があるようだ。
ユニーク解の上限数も決めて、なんらかの対策を取らねばならないようだ。 どうすれば良いだろうか。
メモリ不足対策
ユニーク解の数が多過ぎるとメモリ不足を起こすようだから、 何等かの対策を打たねばならない。
色々な方法があるが、ここでは、ユニーク解の数を減らすという 安直な方法を選んだ。メモリ不足を起こさない程度の数のユニーク解 だけを評価し、後は捨てるという手も有りそうだったが、 ちょっとやり方に問題が有りすぎるのではと思い、その方法は躊躇した。
実際に行なったのは、もう空色マスをもっと決めて、 ユニーク解の総数が１００個以下になるまで空色マスを決めることにした。
ここでは、次の図のように、左下の４を決めることにした。
これで、もう大丈夫になっただろうか。
まだユニーク解の数が100個以上ある。
空色マスがまだ11マスも残っているのだから、自由度が高過ぎて、 可能な入れ方が有りすぎる。
それで、さらにもう１つ空色マスを決定することにした。
しかし、これでもユニーク解が100個数を切らないので、 さらに次のように(5,5)を7に決めた。
今回は、次々に白マスも決まった。 (3,3)の空色マスまで6に決まってしまったが、空色マスの数は充分にあるので、 大丈夫だろう。
もう、ユニーク解の個数も随分減ったのではないだろうか？ そして、解の総数も減ったと思われるが。
現盤面のまとめ
現在の盤面の状態をまとめておこう。
| 空色数字マス | 20 |
| 白色数字マス | 9 |
| 空色アキマス | 8 |
既に、盤面上には、29個もの数字が置かれている状態だ。
これで試してみると、
| 解の総数 | 52 |
| ユニーク解の数 | 16 |
となる。解の総数が52ととても少くなっているにも拘わらず、 まだ16個ものユニーク解が存在する。
この16個の中から気に入ったのを選ぶだけなので、詳しい話は省略し、 ユニーク解から1つだけ選んだものを載せておく。
現在行なっている終盤の方法をまとめておこう。
- 解の総数が10000を超える場合、10000の解集合から、 次に決める空色マスを選ぶ。
- 解の総数が10000以下になったら、ユニーク解の総数を求める。
- ユニーク解の総数が100を超えるようなら、得られた解集合から 次に決める空色マスを選ぶ。
- ユニーク解の総数が100以下になったら、ユニーク解を評価し、 もっとも問題として適切なものを１つ選ぶ。
今回は、なかなかユニーク解の数が減らない場合を例としたが、 通常は100を超えるユニーク解があっても、もう１つ空色マスを決めると、 それでいくつものマスが決まり、ユニーク解も一気に100以下になるのが普通である。
レベルの指定
問題は一応できるようになった。 しかし、それだけではいけない。
一番最初に問題になるのは、希望に応じた難易度の問題を作ることである。 これができないようでは、パズル作家はやっていけないだろう。
ナンプレが初めての人が多い場合は異常にやさしく、 慣れている人が多い場合には普通に、 上級者だとうぬぼれている人には難しい問題を提供することで、 どのレベルの人にも満足を与えることができる。
さて、どうすれば、希望の難易度の問題ができるであろうか。
空色マスの数が増えれば易しくなり、減れば難しくなる。
さて、これで正しいだろうか。 とりあえず標準的な表出２４の問題を示しておく。 難易度は、Level 7 であった。
ちょっと難しいかな、という程度で、２４マスならよくあるパターン。
解けるかな？
では、次回は１８マスの場合の難易度について検討しようと思うので、 これから作成しよう。
パターンを示す。 このパターンは、１８マスにしては問題が作りやすい。 次回までに、自分でも問題を作ってみよう。
たった１８個
１８個しか空色マスがなければ、 相当の難問しか出来ないような気がしないだろうか。
実際にできた問題の中には、次の問題が入っていた。
難易度をどう感じるであろうか。
確認のために実際に解いてみたが、 基本的な解き方さえ知っていれば確実に解ける中級レベルの問題である。 プログラムによる評価でも、Level 6 であり、やはり中級問題である ことを示している。
空色マスの数が減ると、確かに極端に易しい問題はできないようだが、 急に難問ばかりになる訳ではない。 １８で初級問題の作成は難しいだろうが、 中級(Level ４〜６)の問題も充分に作れるようだ。
どちらかというと、できあがった問題の難易度が上がるよりも、 問題が出来る(ユニーク解が存在する)ことの方が難しくなる。 つまり、ユニーク解を発見する確率が大幅に落ちてしまうようだ。
しかし、コンピュータに計算させているのだから、 何時間でも、寝ている間も走らせておけば、そのうち結果が出る。
* 問題の作り方のまとめ
さて、欲しい難易度の問題を作るのはどうすれば良いか分かっただろうか。
馬鹿独を利用して、最後は全探索を行なって、全てのユニーク解が分かる。 多くの場合、ユニーク解は複数個見つかる。 ときには、ユニーク解が多過ぎて処理に困ることがある。 そういうときには、ユニーク解が処理可能な程度に減少させるために、 適当に空色マスを決めてしまうのだった。
ということを踏まえて考え、次のようにして希望レベルの問題を選択することにした。
とりあえず、レベルは、仮に１から１３まであることとしよう。
1. まず、希望難易度(下限値、上限値、希望値)を指定する。
2. 問題の生成をやってみる。
3. 希望した難易度の問題が無ければ、再び2.へ戻る。
4. 希望した難易度の中から一番適当と思われるものを問題として選ぶ。
だいたいこれで良いのだが、詳細なレベルを判定しようとすると時間がかかるので、 実際のシステムでは、レベル評価を次のように２段階にした。
1. 非常に単純だけれど高速に評価できる方法。
2. 人間的に解いて、時間がかかるけれど、人間の感覚に近い評価をする方法。
1. と 2. の２つの方法では、評価が当然ずれることがあるが、 実際には１〜２段階程度しかずれない。 そのため、第１段階では全ユニーク解に対して、 下限値-α から 上限値+α までとして高速評価を適用し、大きく外れたものは 外してしまっている。αは、１または２で充分である。
第１段階を通過した場合にのみ、2.の丁寧な時間のかかる方法で評価し、 指定した難易度の問題ができたかどうか判定している。
要するに、複数のユニーク解を作って、その中から希望の難易度のものが できたかどうか調べることにしている。
自動生成の方法によっては、自動生成を行なった結果、ユニーク解が１つしか できない場合がかなり多い。 というか、そういう作り方の方が一般的ではないかと思う。