ホームページ目次2013-09-20(前)2014-09-13(次)

子供向けグラフィカル言語Scratchでナンプレの自動生成

2013年9月20日


この問題は、この夏、高等専門学校からのインターン生がナンプレの自動生成のプログラム作成を体験し、そのプログラムが自動生成した問題です。 使ったプログラムは、なんと、子供向けの言語、Scratchです。 MITのメディアラボが子供向けに、ソースコードをキーボードから打ち込んだりせず、マウスでつんつんする程度で作れるようにと開発した言語です。確かに、実際おもちゃのような言語で、できることはとても限られています。 そして、めちゃくちゃ遅いです。どのくらい遅いかというと、64ビットのコンピュータが普通になってきたのに、まるで昔の8ビットのコンピュータを使っている感じです。

次のページへ行ってみましょう。
http://scratch.mit.edu/projects/25661093/
この中にある旗をクリックすると、問題を自動生成し始めます。 現在、数字の個数は25個に固定になっています。でも、配置は、90度回転対称になっています。 こういう配置を自動的に決めて、問題を作り始めます。

旗を押すと、盤面の上のバーが進んでいきますが、右端まで到達しそうになっても、消えてしまって、左端からやり直しに なることがあります。これは、自動生成に失敗したことを示しているのでしょう。(私が作っていないので想像です。)

1問つくるのにかかる時間ですが、これは運と、コンピュータの性能に依存します。 まあ、数分程度でできます。幸運な場合には、1分以内で生成されます。

実際に自動生成された問題を解いてみてください。 難解な手筋を使わなくても解けます。 これは、自動生成から呼び出すナンプレソルバー(問題を解くプログラム)に組み込まれている手筋が、基本的なものだけになっているためです。 インターンシップ期間が短いこともあって、手筋は基本的なものだけになっています。

実行するだけでなく、プログラムを全部見ることができます。 プログラムといっても、次の図のように、とてもグラフィカルなプログラムです。

上の画面は、「問題改良」の部分のプログラム(スクリプト)の全体を示しています。 問題改良というのは、うまく行かなかったら調整するということをやっている部分で、 要するに人工知能(AI)の部分です。つまり、AIの本質的な部分は、おもちゃ言語で書いても短いのです。

これだけのプログラムですが、Scratchを学習するところから、ここまで作り上げるのに、 1週間、つまり5日間でした。予想より早かったのは、優秀だったということでしょう。

ぜひ、みなさんも、ナンプレの自動生成を作ってみましょう。 人工知能とかそんな難しいことではなく、最適化の基本的なことを実行するだけで大丈夫なのです。 最近は、大学に、知識工学科とか、その種の学科が増えているので、 ちらっとこういうのを演習などで行うのも良いのではないかと思います。

Scratchはものすごく遅いプログラムです。 この言語でナンプレの問題の自動生成を行うというのは、異常、いやキチガイ沙汰でしょう。 でも、できるんです。 ヒント数を減らしても、長い時間を待てば作成可能なのですが、もっと頑張るには、 C,C++とかJavaとかの言語を使った方が良いでしょう。 そのあたりの話は次回にしましょう。


ホームページ目次2013-09-20(前)2014-09-13(次)