トイ・プロブレム

研究者どうしで手法を比べるための問題

トイ・プロブレム(toy problem)は、問題を解く手法の働きを示したり試したりするために用意された、単純化された問題です。スチュアート・ラッセル(Stuart J. Russell)とピーター・ノーヴィグ(Peter Norvig)の教科書『Artificial Intelligence: A Modern Approach』第2版は、探索による問題解決を扱う第3章で、問題をトイ・プロブレムと実世界の問題(real-world problem)の2種類に分けて説明しています。

トイ・プロブレムの特徴は、簡潔で厳密な記述を与えられることです。何が状態で、どんな操作ができ、どうなれば解けたことになるのかが、短い文で曖昧さなく決まります。記述が1通りに定まるので、別々の研究者が同じ問題に自分のアルゴリズムを当てて、性能を同じ条件で比べられます。名前の「トイ」はおもちゃという意味で、現実の問題にある込み入った事情を取り除いた小さな問題であることを表しています。

8パズル・8クイーン問題・掃除機の世界

教科書が挙げる代表的なトイ・プロブレムを3つ見ます。

8パズル(8-puzzle)は、3×3のマスに1から8の番号が付いたタイル8枚と空きマス1つを置き、空きマスの隣にあるタイルを滑らせて動かしながら、決められた並びにそろえるパズルです。

8クイーン問題(8-queens problem)は、どのクイーンもほかのクイーンを取れないように、チェス盤の上に8個のクイーンを並べる問題です。

掃除機の世界(vacuum world)は、ごみがあるかもしれない場所と、左右に動いたりごみを吸い取ったりする掃除機だけからなる、ごく小さな世界です。

3つとも、ありうる状態と取れるアクションが前もってすべて決まっており、目標の状態に着いたかどうかも迷わず判定できます。このため、同じ問題を幅優先探索や深さ優先探索のような別々の探索手法で解き、調べた状態の数や必要な時間とメモリを比べる題材になります。

実世界の問題とどこが違うか

実世界の問題は、解いた結果そのものに人が関心を持つ問題です。教科書は、目的地までの道順を探す経路探索、いくつもの都市を1回ずつ回って戻る最短の順路を探す巡回セールスマン問題、チップの上に部品と配線を並べるVLSI(超大規模集積回路)のレイアウトなどを例に挙げています。

両者の違いは、問題の記述のされ方に表れます。トイ・プロブレムには誰が読んでも同じ意味になる1つの記述がありますが、実世界の問題には合意された1つの記述が無いことが多く、何を状態とみなし、何を費用として数えるかを場面ごとに決める必要があります。

この違いから、トイ・プロブレムで分かるのは手法どうしの比較や手法の性質であり、その手法が実世界の問題でも役に立つことまでは保証されません。トイ・プロブレムでうまく動いた手法でも、記述の定まらない現実の問題にそのまま当てはめられるとは限りません。

G検定での位置づけ

G検定のシラバスでは、トイ・プロブレムは中項目2「人工知能分野で議論される問題」に属するキーワードの一つです。

第1次AIブームでは、探索と推論によって迷路やパズルのような問題を解く研究が進みました。こうした問題はルールが明確に書けるトイ・プロブレムにあたり、コンピュータで解くことができました。一方、現実の問題は記述そのものが定まらず、考えに入れるべき事柄も限られていません。トイ・プロブレムは解けても現実の問題は解けないという限界が見えてきたことは、第1次AIブームが下火になった要因の一つとされます。

ただし、トイ・プロブレムは過去の失敗を表すだけの語ではありません。上の教科書のように、探索手法の考え方を説明したり性能を比べたりする題材として、現在も使われています。歴史の文脈で出てきたときも、単純化された問題そのものの意味と結び付けて理解しておくと整理しやすくなります。