8タイル問題の解決過程とそのシミュレーション

8タイル問題の解決過程とそのシミュレーション

著者 弓野 憲一, 曽根 伸

雑誌名 静岡大学教育学部研究報告. 自然科学篇

巻 42

ページ 17‑35

発行年 1992‑03‑24

出版者 静岡大学教育学部

URL http://doi.org/10.14945/00008347

静岡大学教育学部研究報告 (自然科学)第^42号 (1992.3)17〜 ³⁵

8タ イル問題の解決過程 と そのシ ミュ レーシ ョン

Solving Process for 8‐ Tile Problelm and lts Si]mulation by Computer

弓 野 憲 一 ・ 曽 根   伸* Kenlchi YuMINO and Shin SoNE

(平成3年10月 11日受理)

3X3のマスのなかにおかれた1〜 8の数字か らなる 8タ イルを、一時に一つずつ動かして、

日標 と同 じ配置にする問題を 8タ イル問題 という。本研究の前半では、 7人の大学生にこの間 題 を繰 り返 し解かせ、その問題解決過程を吟味 した。 ここで与えた問題の最良解決の手数は 24手 であるが、24手 で解いた人は一人 もいなかった。7人の内4名が最終的に26手_で解決で

きるようになった。25試 行繰 り返 しても、ずっと50手の近傍に留 まる被験者が二人いた。 一 人の被験者は、最初か ら45手の近傍であったが、 数回繰 り返 して も、手数 は減 らなかった。

この最後の一人を除 くと、6人の被験者の問題解決に要する手の数は、上下の振幅は見せつつ も、試行の関数 として、次第に減少 していった。問題を解決するに当 り、全ての被験者は問題 を下位 目標に分割 して解決 した。その下位 目標は、まず 1を 左の最上段 に動かすことか ら始 ま るが、全ての被験者がす ぐに123を連続 して最上段 に動かす 目標に変化 させた。そ してそれ が達成 されると一人を除 き、左の中、下段 にそれぞれ4、 7を 置 く目標 を設定 した。一人だけ は、左下段 ―左中段 ―中央にそれぞれ4、 5、 6を 置 く目標 を設定 した。

コンピューターを使って 8タ イル問題を解 くために、 5種類のモデルを準備 した。第 1の モ デルは、 1手先の局面の得 られた関数値 により次の手を選択するモデル (Fl―^モデル)であ る。関数値は、 タイルを移動 させた後の局面におけるタイルの位置 と目標状態のタイルの位置 の距離である。第2のモデルは、2手先の局面の得 られた関数値 により次の手 を選択するモデ ル (F2‑モデル)。 第3のモデルはFl―モデルに局面の記憶機能をつけ、 同 じ局面で同 じ 手を選択 しないようにしたモデル (FlM―モデル)。 第4のモデルはF2‑モデルに局面の 記憶機能をつけたモデル (F2M―モデル)である。 これ ら2つのモデルは、人間が以前に通 過 した局面に達 した際、ある程度 までその局面 を記憶 していて、以前 とは違 う手 を選択すると いう推理過程をモデル化 したものである。記憶で きる局面数は可変 となっている。第5の_モデ ルは人間に 8タ イル問題 を解か して得 られたプロ トコルおよび手の選択系列 をもとに作成 した モデル (H― モデル)である。Fl、 F2モデルでは、この問題を解決できなかった。FlM―

モデルでは、12手 記憶 させた時に86手_で解け、F2M―モデルでは、12手 記憶 させた時 に86 手で解け、最後のH―モデルでは、58手 で解 いた。 しか し人間の ような学習が無いために、

これより少ない手では、問題を解決で きなかった。

17

約 要

*静_{岡大学研 究科 院生}

18 弓 野 憲 一 。 曽 根   伸

1  は じめに

人間が行う各種の問題解決の中には、新たな解決方法や解決手続きを必要とする、創造的問 題解決もあれば、既製の手続 きを順序よく適用することによって、解決に到るルーチン的な問 題解決もある。8タイル問題は後者の典型的なものである。Newell&Simon(1972)よ _ると、

このような課題の解決過程には、問題空間内のある解決段階から、次の段階へすすむためのオ ペレータの選択があるという。すなわち8タ イル問題でいうと、次の目標段階へ移行するため に有効な手の選択があるのである。

さて、このある段階から次の段階にすすむためのオペレータは、どのような基準で選ばれる のであろうか。これまでに行なわれた研究によると、人は最終日標に少しでも近似した形にな るように、オペレータを動かすという。このようにして動かされたオペレータによって、問題 状況が変化 して、ある場合には、最終日標により近づ くことになる。 しかし、そのようなオペ レータの移動が、最終日標への道を遠 くしてしまうことも当然ある。最終日標の形とは、異なっ た形に一旦変化させておき、そこから再度、最終日標へ向かってオペレータを動かすことも時

として必要になる。

その ようなわけで、人間の問題解決においては、最終 日標につながったどのような中間目標 を設定するか ということが、解決への鍵 となると思われる。 この小論では、 8タ イル問題を繰 り返 し解いた大学生が、 どのようにして効率的な解決へ到達するようになるかの過程 を吟味す る。

2。 研 究 方 法 1.被験者

大学生7名 (女子2名、男子5名)、 年齢 は、21〜 23歳であ った。

2.装置

課題 の提示 な らびに反応の記録 には、NECの PC9801‑LVを 用 い た。 被験 者 の操 作入力 には、4個の カー ソルキー を用いた。被験者の発語思考 を分析す るためのプロ トコルの 記録 には、 テープ レコー ダを用 いた。

3.課題 の提示

課題 は^Fig。 1の 下図の ように提示 され、被験者 は右側の画面の タイルを動か して、 左 の画面 の最終 日標 に到達す ることを求め られた。

B□■  ■2日 4■B→4□日

32□  ^■B□

初期状態 目標状態

Fig. 1 実験 に用 いた 8タ イル・パ ズルの問題

8タ イル問題の解決過程 とそのシミュレーション

4.手続 き

被験者へは、これから8タイルからなるパズルを解 くこと、テレビ画面中央の「初期状態」

のタイルを上下左右に動かして左側の「目標状態」にすること、 4つ のカーソルキーを用いて タイルを動かすこと、初期状態から目標状態に素早 く移れるようになるまで何回か試行を行な うことを教示した。一試行は、初期状態からはじめて目標状態に達するまでである。被験者が キーボー ドを押 してその操作が可能な場合には、それを知らせるクリック音を出し、画面上の タイルを描 き変え、前回の操作から今回の操作までの反応潜時を1/100秒単位で計測 して記 録 した。また試行中は発語思考をさせ、テープレコーダーで録音 した。一試行が終わる毎に、

内省報告を求めた。このような試行を繰 り返し行い、連続 して3試行、同じ操作系列で日標状 態に達した時点で、実験を終了した。

5.発語思考を促すためのプロ トコル例

発語試行がどのようなものかを説明するために、以下のような例を示した。①^lをまん中に もってきたいので、 ・・と動かす。②空白を5の 上まで移動 したいので・^0と動かす。③困り ました、 3のとなりに8がきてしまいました。④ もうす ぐできそうです。⑤よくわからないが、

とりあえず 4を 左に移動すると良いような気がします。⑥2を動かして様子を見てみます。⑦ この手はよくないのでもどします。

3  結果

7人の被験者の解決までに要 した手数 (操作系列数)と合計時間が、Fig.2a〜 8aに示 され ている。また被験者のプロ トコルと解 き方のパ ター ンより、被験者がい くつかの下位 目標 を設 定 して問題 を解決 しているのがわかった。その下位 目標は、 まず 1を 左の最上段 に動かすこと か らは じまるが、全ての被験者がす ぐに123を連続 して最上段 に動かす 目標 (これを段階¹

目標 とよぶことにする)に変化 させた。そ してそれが達成 されると一人を除 き、左の中、下段 にそれぞれ^4、 7を 置 く目標 を設定 した。一人だけは、左下段 ―左 中段 ―中央 にそれぞれ^4、

5、 6を 置 く目標 を設定 した。これ らを段階 2日 標 とよぶ。各試行において、それぞれの下位 目標 を達成するまでに要 した手の数が、Fig.2b〜8bに_{載せ られている。}

4  考 察

結果にういて考察する前に、今回の問題解決課題に用いた、^8タイル問題がいかなる性質を もっているかを考察しよう。^8タイル問題は、①問題空間は有限であり、必ず解決が可能であ る。②解決への過程は、タイルが移動可能な^1から4の選択肢の中から、有効な一つの手を選 ぶ操作から成っている。③解決までの手の選択の系列は、複数ある。④発見的 (創造的)な解 決法が見つかれば、それ以後の試行は再生的な問題解決となるような問題である。

ここで、課題 の特性 としての複雑 さについて検討 しよう。今 回の課題では、解決 に到 る経路 は無数 にある。その系列の中で最良の選択 を した場合 には、24手で解決 に到 る。そ して この24 手 は唯一 であ る。それぞれの有効 な手 を選ぶ場面 は、 1から4の選択肢 よ り成 って い るの で 、 各場面 で可能 な手の数の積が、問題空 間 を構 成す る異 なる系列 の数 とな る。 この24手で解 決 に到 るまでの系列の数 は、851944通 りある。 この中の一つ の系列のみが、問題 を解 決す る手 の系列 とい うことになる。 この数 は、一度動か した手 をその まま元 に もどす ことを許 さない場 19

20 弓 野 憲 一 ・ 曽 根  伸

合 であ る。 これ を許せ ば、操作系列の数は先の値 をはるかに上 回る。それゆえ、 もし被験者が 完全 にラ ンダムに手 を選択 して、24手で解決 に到 る確率 は、851944分の1(0.00017%)と

い う非常 に低 い確率 になる。事実、BASICで 、 この8タイル問題 を解決す るプログラムを 組んで、丸1日走 らせてみたが、とうとう解決できず じまいであった。つ ぎに、26、 28、 30、32 手での解決の系列を計算すると、それぞれ^15、58、171、497通りある。 また、問題空間を構成 する系列の数は、それぞれ2547639、 7659282、 22944962、 68900039通 りあ るこ とになる。

したがってランダムなタイルの移動では、32手 で解決で きる確率 は0.00108%と _{い う非常 に} 低い値にな り、ほとんど解決不可能なことがわかる。被験者のプロ トコルと、以上の考察より、

被験者はただやみ くもにタイルを動か していたのではな く、何等かの方略を用いて、 この課題 を解決 していたことが結論 される。

つ ぎに各被験者の問題解決過程を見ていこう。^Fig。2aの被験者Aは、 1試行 日は解決 に約 100手を要 しているが、2試行 日以降は、50試行 を割っている。 また解決に要 した時間パ ター ンは、手の数のパ ターンとほぼ同 じである。 さらにFig.2bの下位 目標を達成するまでのパター ンも、全体 を解決するに要 した手のパ ターンとほぼ同 じである。したがってこの被験者は、たっ た一試行で課題を解決するために有効な、解決方略を発見 したのであろう。その方略は少な く とも、段階 1お よび段階2の下位 目標 を含んだ方略であろう。 ただ、最後 まで50手_{の近傍 に} あることか ら、最良の解決 とはかな り離れている。

Fig.3aの 被験者Bは、第一試行は約300手を要 している。 しか し、その手はす ぐに減少 し、

5試_{行 日には、約}50手の近傍に落ち着いている。 さらにFig.3bの下位 目標の達成で も、安定 したパ ター ンを示 している。 しか しこの被験者 もAと 同 じように、最良の解決か らは遠いとこ ろで終っている。

Fig.4aの 被験者Cは、最初か ら50手 を割った素晴 らしい解決を示 している。 しか し、 7試

行を経て も、それ以上の解決手数の改善は見 られない。だた し、解決に要 した時間は、試行 と ともに次第に少な くなっているので、この課題解決がかな り機械的になったことがうかがえる。

Fig.5aの 被験者Dは、5試行 日までは、解決が安定 していない。 この原因が何であるか を 推測するために^Fig。5bを見ると、段階 1の 下位 目標の達成に要する手の数に格れがあ り、段 階2のそれには格れがほとんどない。 したがって、5試行 日までは段階1目標 を達成するため のタイルの動か し方が不十分であったといえる。ただ し、最後の3試行は26手 で解 いている。

Fig.6aの 被験者Eは、最初に約50手 で解決 しているが、^2、 3、 4試行では多 くの手 を要 している。 また^5、 6試行 日で50手を割る解決を見せるが、 また手数は上昇 し、 やつ と10試 行 日で元の水準にもどっている。最後の上昇がなぜ起 きたかをFig.6bよ り推察す る と、 7試

行 日では、段階 2目 標t8、 9試行では、段階^1、 段階 2日 標の達成に多 くの手を要 したこと が うかがえる。

Fig。7aの被験者Fは、^2、 3試_{行 日は}1試行 日より、幾分多 くの手 を要 しているが、 その 後順調に手を減 らし、最後の3試_行では、26手で解 いている。 この被験者 に特徴的なのは、

解決に要する時間が、4試行 日以降急速に短 くなっていることである。おそ らく、機械的な解 決がで きるようになったのであろう。Fig.8aの 被験者Gは、^2、 3および^12、 13で 短い手の 解決を見せているが、最後の3試行を除 くそれ以外の試行では、比較的多 くの手を要 している。

この原因が何であるかは、このデータのみか らは、推察不可能である。

8タイル問題の解決過程とそのシミュレーション

(■)準 lld 晋

OS

(碓)LH」判催e(■)準 lld W

︵ く榊 餐経

︶ 翠 黙Ｃ 覇尽

ⅨＯ

﹁せ 氣回 Ｌ稲 Ｃｐ 悩 艶 部興 回 肛 書噸  Ｏ Ｎ ．Ｅ

回 ︵

︶

  轟

Ｌ

卜      り     ｎ

輝 ぼ瞑

゛ Ｃ ︶罰

釜 饉

１ ０ ９ １１

輝 尽瞑 Ｃ ︶罰

︻ 盤 饉 ９ １１ １ ●

︵ く 榊饉 経 ︶ざ 黙 Ｃ 肛 士維 ぐ 却 氣 尽 帳 Ю

↓ 里覇 回 Ｌ 稲   Ｎ ．Ｅ

守稲

n

劇〇

〇

∞

ト

ロO V

覇n:ト

寸稲

n

ω 珊曇

ＮＮ

Ｂ

□□ ２ ２□

□階 田 四口 段 日□

□ １ ２□

□ 階 田□

□ 段

Ｊ 蝙 熙

︱

・ 岨 蒲   書

︵傘

︶肛 士 維 ぐ

︵畔

︶轟   一尽   係

1011 1213141516171819202122232425

試 行 数 (回)

―

段階^1までの系列数

―

段階 2ま での系列数

9 10111213141516171819202122232425 試 行 数 (回)

3

Fig。3a 試行日数 に よる系列数 と合計時 間の変化^(被験者B) Fig。3b 各中間 目標段階までの試行回数による系列数の変化(被験者B)

∞ヽへやコ醐０準藩鰤曲館中０ヾ″いて︱でШヾ

︵昨︶輝 尽 帳

︵傘

︶匡 世 紀 ぐ

︵十

︶轟   尽   廉

一

系 列 数

―

合 計 時 間^l

3 試  行

4   5

数 (回)

3 試 行

5  6

数 (回)

Ｎω

一

段階1までの系列数

―

o段^{階2までの系列数}

Fig。4a 試行回数に よる系列数 と合計時間の変化(被験者C) Fig。4b 各中間 目標段階 までの試行回数による系列数の変化^(被験者C)

Ｎヽ

畔 傘 轟 肛尽幕

Ⅸぐ

4567

試  行 ^数 (回)

劇 蝙 疇

︱

・ 雌 前   書

︵昨

︶氣   尽   瞑

34567891011

試 行 ^数 (回⁾

鮮 鮮

●

―

段階1まで の系列数

―

段階 2ま での系列数

Fig.5a 試行回数 に よる系列数 と合計 時 間の変化(被験 者D) Fig.5b 各 中間 目標段階 までの試行回数 に よる系列数の変化 (被験 者D)

25︵ 国 榊饉 経 ︶ざ 黙 Ｃ 無 尽

Ⅸ Ю

回 Ｌ 二 轟

︶ 価 編 Ｃ

聖 部 騨 回 肛 ■ 巾

回 ︵

経 ︶

  Ｌ   稲

０

∞ 卜 り ｎ

8タイル問題の解決過程とそのシミュレーション

(碓)Lu」判催号 (■)準 lld 晋

． ¨¨ ００

﹄ ｎｒ    Ｎ一      一 一

︵

継 ︶ギ 国 神経

黙 Ｃ肛

却 轟尽 士 維ぐ

帳 Ю

回 Ｌ稲 ↓ 里轟

．  Φ

こ ¨

︵ 回 ︶覇   中 ゛  稲

∞ 卜 Ｏ ｎ

輝 薫帳

︶ 罰Ｎ Ｃ

盤

１ 郎 ９１

１ ё

轟 尽瞑 Ｃ

︶ 悩︻

塞 謎 ９１ １

● １

ぐ ９１ 士 維

１ １ ё

一

係９ 尽  

１ １ １ ●

ＮＯ

劇 岬 疇

︱

・ 嘔 前   書 Ｏｎ

︵傘

︶肛 士 維 ぐ

︵＋

︶轟   尽   帳

︵中︶輝 尽 Ⅸ

●

―

段階1までの系列数

―

段階 2ま での系列数

Fig.7a 試行回数 に よる系列 数 と合計時間の変化 (被験 者F) Fig。7b 各中間目標段階 までの試行回数による系列数の変化(被験者F)

27︵ ｏ榊 餐経

︶ ギ 黙Ｃ 轟尽

ⅨЮ

轟回 局 二

Ｌ稲

価 艶 Ｃｐ

部興 回肛 書巾

∞ ︒Ｅ  ０

ｏ 榊餐 ︵

継 ︶ギ 黙 Ｃ 肛 士維 ぐ 掏 轟 尽

﹁ 二轟 Ⅸ Ｏ

 ∞ 回 ｔ稲

¨ ．

Ｅ

︵ 回 ︶覇   Ｌ  稲

︶ ｙ

睡 騨 ^園

準 碓 士

8タイル問題の解決過程とそのシミュレーション

ｏｒ  ｎ ｒ  寸ｒ  ｎ ｃ  劇゛

□ ︶轟 ︵

  Ｌ

Ｑ    〇 一 

∞

稲目日日墨目目日饉

目□□‐ロロロ迎■□□褻

輝 ぼ瞑 Ｃ

︶ 悩Ｎ 盤

１ 軽 ９１

１ ё

Ｃ 輝 蘇瞑

︶ 価︻

盤

１ 部 ９１

１

●

28 弓 野 憲 一 。 曽 根   伸

被験者の内で最短系列で 目標に到達 した者はいなかった。最短系列 よ り2手_多い26手で 日 標状態に達 した者は、7名_中4名いた。この4名の内、3名までが同 じ操作系列である。この ことは、15通 りある26手 の解決系列の内の同一系列を3人が辿ったことを意味す る。 この よ うな結果になったのは、今回の被験者の全員が段階^1の目標として、 123を最上列に並べる

日標 をつ くり、 さらに段 階2の目標 として、 ひだ りの二段 目に^4、 三段 日に7を置 く目標 を⁷ 人中6人の被験者が採 ったことと密接 に関係 していると思 える。

ここで、被験者Dをとりあげ、操作系列のデータと発語思考のデータか ら、問題解決の過程 を議論 してみよう。Dの最終的な方略をプロ トコルより拾ってみると、「123をつ なげなが ら上の段 に並べ、つ ぎに47を_{つなげなが ら}1の_{下にくっつけ、最後に}568のタイルを動か せばで きる」 というものである。このような全体的な方略「最初に123、 次に 47、 最後に

568」 は、Fig.5a,5bからもわかるように、 6試行 日でほぼ 自分の もの とした ようである。

しか し、 123のつなが りが、最上列以外にあっても、それ らは最終的には最上列に動かすこ とがで きる、あるいは47のつなが りについても同 じような意味があるということに気づぃた のは、 9試行 日以降であろう。このことは、操作系列のデータ、プロ トコルおよび内省報告の デー タか ら推測 される。

被験者AからGの解決過程か ら推論 されることは、^8タイル問題のような少数のオペレーター の移動か らなる問題においては、「当初の非常に大 きな問題空間を下位 目標 を設 けることな ど で縮小 していき、より先の見通 しがで きることで問題解決が進んでい く」 と言えるであろう。

5  シ ミュ レー シ ョンによ る考 察

1.モデルの目的

今回の実験により、被験者の 8タ イル問題の解決方略の推論はできた。 しか し、今回の実験 に用い られた課題は1題だけであるし、問題解決の過程の議論についても推測の域 を出ていな いように思われる。そこで、今回の実験で得 られたことを、推測ではな く仮説 として成立でき るように裏付けをしなければならない。

そのためには、 8タ イル問題の解決過程のモデルをつ くって、 このモデルが どれだけ人間の 8タ イル問題の解決過程 を表わしているのかを評価 しなければならないだろう。 ここでは、そ れをプログラム言語で作成 し、 コンピュータ上でシミュレーションを行なうことにする。

ここで、シミュレーションが有用であると思われる理由を挙げておこう。本研究 を例 に とる。

最初、実際に被験者を用いて実験 を行なう。この実験 とその考察によって、人間の 8タ イル間 題の解決過程を推測 し、 自然言語により1つのモデルがで きる。この時点でのモデルは、外か ら観察できることだけをもとにして人間の内部過程を説明 している。モデル作成者の主観が入 り込む余地が非常に大 きい。そこで、このモデルが どれだけ実際の人間の問題解決過程 を説明 しているか ということを客観的に評価することが重要になって くる。 1つ の方法 として、モデ ルをソフ トウェア形態に表わし直 して評価することがある。すなわち、コンピュータによるシ ミュレーションである。モデルをソフ トウェア形態で表わすことの利点を挙げる。 自然言語で 表わされたモデルは自然言語 に含 まれる曖味 さがそのままモデルの曖昧さとなる。これと比べ るとソフ トウェア形態のモデル、つ まリコンピュータ言語のモデルは曖昧 さの入る余地がない。

また自然言語で表現 されたモデルは、モデルの予測を厳密に決定することが困難である。 コン ピュー タ言語のモデルは、コンピュータでプログラムを実行することにより、特定の状況にお

8タ イル問題の解決過程 とそのシミュレーション

けるモデルの動 きを厳密に決定で きるという利点がある。異なる条件での行なっていない実験 の結果を予測することもできる。今回の例では、 まずモデルをコンピュータ言語で記述 し、被 験者に与えた問題 と同 じ8タ イル問題 をこのモデルに解かせてみる。モデルの動作過程や結果 を人間の ものと比較 してモデルを評価することになる。このように、モデルに主観が入 りやす い場合、そのモデルの評価は曖味 さを排除で きるシミュレーションが適 していると考えられる。

2.モデルの作成

最初 にどの個人を表わ したモデルをつ くるかが問題になる。モデルが、特定の個人を表現 し ているのか、あるいは一般化 されたまたは理想化 された個人を表現 しているかである。今回の 実験の被験者は、それぞれその問題解決方略が違 う。 しか し、それぞれの問題解決方略の中に は多 くの共通点 もあった。この点を考慮 して、ある程度一般化 された個人のモデルをめざした。

今回用意 したモデルは全部で5種類ある。第1のモデルは1手先の局面の得 られた関数値に より次の手を選択するモデル (Fl―モデル)である。関数値は、 タイルを移動 させた後の局 面 におけるタイルの位置 と目標状態のタイルの位置の距離である。 このモデルは、人間が 8タ イル問題を解 くとき先読みをし、その結果が よいと思われたとき実際にタイルを動かすのでは ないか という推測 をモデル化 したものである。第2のモデルは2手先の局面の得 られた関数値 により次の手を選択するモデル (F2‑モデル)である。Fl―モデルが1手先 を読んで タイ ルを動か しているのに対 して、人間は読みが1手先だけではないという推測により、2手先 ま で読むようにしたモデルである。第3のモデルはFl―モデルに局面の記憶機能をつけ、以前 と同 じ局面になるような手をなるべ く選択 しないようにしたモデル (FlM―^モデル)である。

第4のモデルはF2‑モデルに局面の記憶機能をつけたモデル (F2M―^モデル)であ る。 こ れ ら2つのモデルは、人間が以前に通過 した局面に達 した際、ある程度 までその局面を記憶 し ていて、以前 とは違 う手 を選択するという推測 をモデル化 したものである。記憶できる局面数 は可変 となっている。第5のモデルは人間に 8タ イル問題を解か して得 られたプロ トコルおよ び手の選択系列 をもとに作成 したモデル (H― モデル)である。いずれのモデルもC言語で記 述 されている。

各モデルの手の選択方法は、次の ようになっている。

①Fl―モデルおよびF2‑モデルの評価関数による選択

評価値=(移動する前のタイルの位置 とその タイルが本来あるべ き位置 との距離)― (移動 した後のタイルの位置 とそのタイルが本来あるべ き位置 との距離)

Fl―モデルでは、これを次の1手についてのみ算出し最高値の手を選択する。F2‑モデ ルでは、 1手先の関数値はその1手か ら選択可能な2手目の評価関数の最大値 をその手の評価 値 としている。

②FlM―モデルお よびF2M― モデルの評価関数による選択

評価値=(F10F2‑モ デルの評価値)― (過去a回の内で移動後のタイルの状態になっ た回数)X(重み)

ここで「重み」は、可変 となってお り、 aも 可変 となっている。今回「重み」は、Fl・ F 2‑モデルの評価値の とり得る最高値 を超える値 とした。 また過去何局面を記憶するのか とい うaの値は、無限ループの 1周 よりも大 きくな くては無限ループを解消で きない。

29

30 弓 野 憲 一 ・ 曽 根  ^伸

③H―モデルの手の選択

H―モデルは、問題をい くつかの下位 目標にわけている。 まず最 も上のレベルでの下位 目標 は、上の列に123を並べる、 1の下に47を並べる、568の位置を揃える、となっている^o このそれぞれの下位 目標の下にも下位 目標がある。例えば、上の列に123を並べるとい う下 位 目標の下には、 1を左隅に置 く、 2を 1の_{隣に置 く、}2の_隣に3を入れる、がある。そ して 最 も下の レベルでは、例えば右 に移動するという目標の下で、右に空白を移動 して くるという ような下位 目標 も存在する。 このようにして、大 きな目標 を小 さな目標に分解 していき、その 結果が次の1手を決定 している。

3。モデルの動作過程

モデルを動作 させるにあたっては、人間に解かせた 8タ イル問題をつかった。この問題の最 短系列数は24手 、人間のおこなった最短系列数は26手 であった。 この問題 を使い、各 々のモ デルを動作 させた。 まずFl―モデル、F2‑モデルでは無限ループにな り問題を解決するこ とがで きなかった。 これはこの2つのモデルが、同 じ局面になったときいつで も必ず同 じ手を 選択するか らである。次に局面の記憶機能をつけた、FlM― モデル、F2M―モデルにおい ては問題を解決することができた。系列数は過去12の局面を記憶 した とき、FlM―モデル で、86手、F2M― モデルで86手であった。一方、H― モデルは、問題 を解決す ることはで きたが、系列数は58手 で人間の最短系列の約2倍となった。 しか し、他のモデル との比較 に おいては、 より人間の操作系列に近づいていると言えよう。

4.モデルの検討

関数値 によるモデル (Fl―モデル、F2‑モデル)は、今回の問題を解決することがで き なかった。 タイルを移動 させた後の状態を評価 して、なるべ く高い評価の手を選択するという ことを人間は少なか らず行なっていると予想 されるが、この関数型のモデルだけでは人間の問 題解決過程は説明できない。評価値の算出方法を改良すれば問題解決能力をあげることがで き るだろうが無限ループに入って しまうというこのモデルの欠点は残ることになる。この欠点を 取 り除 くためにFlM―モデル、F2M―モデルでは、過去い くつかの局面を記憶 して、以前

と同 じ局面 となるような手をなるべ く選択 しないようにした。 これ らのモデルでは今回の問題 は解決で きたが、他の問題では解決で きない もの もあった。記憶する局面の数を増やすことに よって解 くことので きる問題数を増やすことはで きる。 しか し、記憶する局面数を増やせば増 やすほど解決の過程は局面の樹の探索に近づいてい く。人間の場合にこの方略を当てはめてみ ると、処理する情報の量か らいってある程度以上は不可能だといわざるをえない。最後に人間 の問題解決過程をもとに作成 したH―モデルであるが、このモデルの解決過程は当然のことな が らかな り人間の解決過程に近づいたといえるだろう。 しか し、人間に見 られるような,3つ

の タイルを 1つ のまとまりと見なす,とい うような機能は記述 されていなかったとい うことも あって、人間と全 く同 じ系列で解決するということはで きなかった。 また、 このモデルは、 日 標状態が 1つ に限定 されていて、その 目標状態の問題 しか解決で きない。 このモデルにはまだ

まだ改良の余地が数多 く残 されている。

8タ イル問題の解決過程 とそのシミュレーション       31

5.H―モデルのプロ トコルの出力例 (今回の実験に用いた問題を与えた)

では、始めます^.

すべて揃っているか?揃ってはいない^. では,12347と 定位置にあるか ?な い^. それでは,123は定位置にあるか?それ もない^.

1は_{定位置 にあるか}?それ もない。          ^′

では,はじめに1から定位置に移動することにする^. 1を (左上隅)に移動 したい^.

1が ,

(右上 隅)から (左上 隅)に^{動 くため には,左左 とやれば よい.} 1は ,左左 と動かな くてはいけない^.

左へ と動 くために,空自が空いてい るか とい えば,空いていない^. (上真 中)を空 けたい^.

空 白が

(右下隅)から (上真 中)に^{動 くため には,上}左 上 とやれば よい^. 空 白を上左 上 と移動す るのな ら,タ^{イルは反対 に},下右下 と動かせ ば よい^. けっ き ょく,下右 下 とや って空 きをつ くって,最後 に左へ と動かす^.

左へ と動 くために,空自が空いてい るか とい えば,空いていない^. (左上隅)を空 けたい^.

空 白が

(右上隅)から (左上 隅)に動 くため には,下左左 上 とやれ ば よい^. 空 白を下左左 上 と移動す るのな ら,タイルは反対 に,上右右下 と動 かせ ば よい^. けっ き ょく,上右右下 とや って空 きをつ くって,最後 に左へ と動 かす^.

2は_{定位置 にあ るか?な}い.

それで は,2を定位置 に移動す るこ とにす る^. 2を (上真 中)に^{移動 したい.}

2が,

(下真 中)から (上真 中)に動 くため には,上上 とやれ ば よい^. 2は_,上」Lと動かな くてはいけない^.

上へ と動 くために,空自が空いているか といえば,空いていない^. (真真中)を空けたい^.

空自が

(上真中)から (真真中)に動 くためには,下とやればよい^. 空白を下 と移動するのなら,タ イルは反対に,上と動かせばよい^. けっきょく,上とやって空 きをつ くって,最後に上へ と動かす^.

上へ と動 くために,空白が空いているか といえば,空いていない^. (上真中)を空けたい^.

1空_白が

(下真中)から (上真中)に動 くためには,右上上左 とやればよい^.

32 弓 野 憲 一 。曽 根  伸

空 白を右上上左 と移動す るのな ら,タ イルは反対 に,左下下右 と動かせ ば よい。

けっ きょく,左下下右 とや って空 きをつ くって,最後 に上へ と動かす^. 1の下 は,3以外 の数字か?3以外 の数字 だ^.

12を_{右 にず らす}.

そのため には、2の右側 を空 けな くてはな らない^. (右上隅)を空 けたい.

空 白が

(真真 中)から (右上 隅)に動 くため には,右上 とやればよい^. 空 白を右上 と移動す るのな ら,タ イルは反対 に,左下 と動かせ ば よい.

で,左下 そ して,2,1とず らす。

つ ま り,右右上 と,動かす^. 3は 2の下 にあるか?な^い.

それでは,2の下 に3を移動 して くることにす る^. 3を (右中段)に移動 したい^.

3が,

(下真 中)から (右中段)に動 くためには,右上 とやれば よい.

3は ,右上 と動かな くてはいけない^.

右へ と動 くため に,空白が空いてい るか とい えば,空いていない.

(右下隅)を空 けたい.

空 白が

(左中段)から (右下隅)に動 くため には,右右 下 とやれば よい。

空 白を右右下 と移動す るのな ら,タ イルは反対 に,左左上 と動かせ ば よい。

けっ きょく,左左 上 とや って空 きをつ くって,最後 に右へ と動 かす。

上へ と動 くために,空白が空 いてい るか とい えば,空いていない.

(右中段)を空 けたい.

空 自が

(下真 中)から (右中段)に動 くためには,上右 とやれ ば よい.

空 白を上右 と移動す るのな ら,タ イルは反対 に,下左 と動かせ ば よい^. けつ き よく,下左 とや って空 きをつ くって,最後 に上へ と動かす^.

では,123の つ なが りを左 にひとつず らす ことにす る。

ず らすためには,左上すみを空けな くてはならない^. (左上隅)を空けたい^.

空白が

(右下隅)から (左上隅)に動 くためには,左左上上 とやればよい.

空白を左左上上 と移動するのなら,タ イルは反対に,右右下下 と動かせばよい^. で,右右下下^.

それか ら,123をず らす。

つ まり,左左上 と,動かす。

では,1の下に4が_{来ているか?.}

来てない^.

8タ イル問題の解決過程 とそのシミュレーション

だか ら,1の下 まで4を_{移動す る}.

4を (左中段)に移動 したい^.

4が,

(右下隅)から (左中段)に動 くため には,左左 上 とやれば よい。

4は ,左左 上 と動か な くてはいけない^.

左 へ と動 くために,空白が空いてい るか とい えば,空いていない^. (下真 中)を空 けたい^.

空 白が

(右中段)か^{ら (下}真 中)に動 くため には,左左 下右 とやれば よい。

空 白を左左下右 と移動す るのな ら,タイルは反対 に,右右上左 と動 かせ ば よい^. けっ き よく,右右上左 とや って空 きをつ くって,最後 に左へ と動 かす^.

左へ と動 くために,空自が空いてい るか とい えば,空いていない.

(左下隅)を空 けたい。

空 白が

(右下隅)から (左下 隅)に動 くため には,上左左 下 とやれ ば よい^. 空 白を上左左下 と移動す るのな ら,タイルは反対 に,下右右上 と動 かせ ば よい^. け っ きょく,下右右上 とや って空 きをつ くって,最後 に左 へ と動かす^.

上へ と動 くために,空白が空いてい るか とい えば,空いていない.

(左中段)を空 けたい^. 空 自が

(下真 中)から (左中段)に動 くため には,上左 とやれ ば よい。

空 白を上左 と移動す るのな ら,タ イルは反対 に,下右 と動 かせ ば よい^. けっ き ょく,下右 とや って空 きをつ くって,最後 に上へ と動 かす^.

4の_{右 隣は}7以外 の数字が あ るか?

7以_{外 の数字 だ。}

つ ぎに,4を下 にず らしたいか ら^. 4の_{下 を空 ける}.

もう空いてる。で^.

こうしておいてか ら,4をず らす^. つまり,下左 と,動かす^.

4の_{右 に}7があるか ?あ る。

次に,47のつなが りを1の下につけます^. そのためには,4の上 を空けねばならない^.

(左中段)を空けたい1

空自が

(真真中)から (左中段)に動 くためには,左とやればよい.

空白を左 と移動するのなら,タイルは反対に,右と動かせばよい^. で,右^.

そ うしたら47のつなが りを 1の 下につける。

つ まり,上左 と・動かす^.