推理パズル問題における難易度判定に関する研究

2018年度 卒 業 論 文

推理パズル問題における

難易度判定に関する研究

2018年度 卒 業 論 文 概 要 論文題目

推理パズル問題における

難易度判定に関する研究

メディア学部 氏 指導 学籍番号 : M0115195 名 鈴木 健太 教員 渡辺 大地 准教授 キーワード 推理パズル、ペンシルパズル、難易度判定、解法、スコア ペンシルパズルとは、数独やイラストロジックなどの紙とペンを用いるパズルを 指す。その中でも、本研究ではペンシルパズル「推理パズル」に着目した。主に書籍 に掲載され、初心者向けの簡単なものや熟練者向けの難しいものなど、難易度は様々 である。解き手が自分の目的や、望む難易度に合った問題を選ぶため、出題者は難易 度を正しく設定する必要がある。しかし、人間の手で問題の難易度を設定する場合、 設定する人の主観が含まれてしまう点や、問題の制作者以外の人を用意する必要が ある場合もあるなど、手間が掛かる作業である。そこで、本研究では推理パズルを解 き、難易度判定を行うシステムを提案する。本研究の目的は、推理パズルの解き手の 考え方を重視した難易度判定手法を提案し、既存の手動で難易度判定している問題 を、システムによって同様の判定結果になるように自動判定することである。 本研究では、推理パズルの難易度判定を行う際に、解き手の考え方や解き方を重 視した難易度判定手法を提案する。本手法は、推理パズルにおける解き手の考え方 や解き方を抽出し定式化した。この定式化したものを解法と呼び、解法にそれぞれ コストを定めた。その後、問題中にどの解法が含まれているかを考慮し、スコアと して難易度を判定する。解法のコストの付け方は、解法を適用する手間を基にした。 提案手法の有用性を検証するため、既存の問題に対して難易度判定を行い、その問題 の掲載難易度との比較実験を行った。実験の結果、提案手法で得たスコアは一意に 難易度を定めるとは言えないが、大まかな難易度の判定は行えることが分かった。

目 次

第1章 はじめに 1 1.1 研究背景と目的 . . . 1 1.2 論文構成 . . . 3 第2章 ペンシルパズル「推理パズル」 4 2.1 推理パズルの概要 . . . 4 2.2 推理パズルの基本形 . . . 4 2.3 推理パズルのルール . . . 6 第3章 推理パズルにおける解法抽出及び解法の種類 8 3.1 解法抽出の概要 . . . 8 3.2 セルの表記方法 . . . 9 3.3 解法抽出の流れ . . . 10 3.4 ヒントと解法の種類 . . . 13 3.4.1 特定のセルの真偽を確定するヒント . . . 13 3.4.2 2つのセルの範囲を比較して真偽を確定するヒント . . . 15 3.4.3 真セルを確定する解法 . . . 16 3.4.4 偽セルを確定する解法 . . . 17 3.4.5 真セルまたは偽セルを確定する解法 . . . 18

5.2 検証結果 . . . 30 5.3 考察 . . . 31

第6章 まとめ 33

謝辞 35

第

₁

章

はじめに

1.1

研究背景と目的

ペンシルパズルとは、数独やイラストロジックなどの紙とペンを用いるパズルを指す。主に書 籍に掲載され、初心者向けの簡単なものや熟練者向けの難しいものなど、問題の難易度は様々で あり、解き手が自分の目的や、望む難易度に合った問題を選ぶ。そのため、出題者は難易度を正 しく設定する必要がある。しかし、人間の手で問題の難易度を設定する場合、設定する人の主観 が含まれてしまう点や、問題の制作者以外の人を用意する必要がある場合もあるなど、手間や時 間が掛かる作業である。また、出題者が望む難易度となる問題制作を行う場合も、同様に手間や 時間が掛かる作業である。このことから、ペンシルパズルの難易度判定手法や、問題の自動生成 手法の研究が多く存在する。 松原ら や土出ら は、解き手が数独を解く際の考え方をそれぞれ解法とした難易度判定手

[5][6][7]や、ブーリアングレブナ基底を用いた手法[8]、思考過程などを測定できる皮膚電気活動 を用いた手法[9]などがある。様々な難易度判定手法が研究されているため、小場ら[10]は、数独 の難易度設定について、難易度判定者間で生じる誤差を減らすシステムの提案をしている。しか し、これらの手法はペンシルパズルの中でも数独に特化しているものであり、他のペンシルパズ ルで全く同じ手法を用いることはできない。そのため、鹿島ら[11]は、ペンシルパズルの1つで ある美術館のルールに合った解法を求めることで難易度判定を行っており、金井ら[12]は、イラ ストロジックのルールに合った解法を求め、難易度判定を行っている。また、是川ら[13]は、ペ ンシルパズルの解法の指標をラテン式方陣問題を基に示している。 問題の自動生成に関する研究としては、モンテカルロ木探索を改良したシステムを用いた数独 の少数ヒント問題の生成手法[14]や、解法の中でも高度なものが必要になる数独の問題の生成手 法[15]、スリザーリンクを制約充足問題として定式化した生成手法[16]などがある。 本研究では、数多くあるペンシルパズルの中でも推理パズルに着目し、推理パズルを解き、難 易度判定を行うシステムを提案する。本研究の目的は、推理パズルの解き手の考え方を重視した 難易度判定手法を提案し、既存の手動で難易度判定している問題を、システムによって同様の判 定結果になるように自動判定することである。本研究の手法は、推理パズルにおける解き手の考 え方を抽出し、「解法」としてアルゴリズム化した。この解法は、推理パズルを解くために複数存 在するため、それぞれの解法に解き手の考え方や手間から点数を設定する。次に、問題を解き終 えるまでの解法の適用パターンを全て検索し、問題中にどの解法がどれだけ含まれているのかを 抽出する。その後、抽出した解法の点数を総和することで、その問題の難易度を判定する。これ により、推理パズルの難易度を判定することができる。また、研究対象の推理パズルの問題を既 存の難易度ごとにグループ化し、提案手法によって得た判定結果がグループ全体で差があるのか、 各グループ間で差があるのかを検証し、差があるのであれば、判定結果が既存の難易度に近いこ とを示す。検証した結果、大まかな難易度判定は行えるが、難易度を一意に定めることはできな

いことが分かった。

1.2

論文構成

論文構成本論文は全6章で構成する。2章で推理パズルの概要やルールなどを述べ、推理パズ ルがどのようなものであるかを説明する。その後、3章及び4章では解き手の考え方を重視した 本研究の提案手法を述べ、5章で検証の方法とその結果を考察する。最後に6章で本研究のまと めを述べる。

第

₂

章

ペンシルパズル「推理パズル」

本章では、本研究で扱う推理パズルとはどのようなものなのかを述べ、そのルールや基本とな る形について詳細を述べる。

2.1

推理パズルの概要

推理パズルとは、文章で示された状況などから論理的に思考し、矛盾のないただ一つの正解を 見つけ出すパズルである。問題の形式も様々で、ヒントとなる文章などに嘘の情報が混在してい る場合や、情報を整理するために用いる表(以下「マトリックス」)が問題中にある場合もある。 本研究では、嘘の情報が無く、マトリックスが問題中にある推理パズルを対象とする。

2.2

推理パズルの基本形

推理パズルは、文章とマトリックスで構成するペンシルパズルである。また、マトリックスは 大項目、小項目、セルで構成し、大項目と大項目に属する小項目を列と行に分けて羅列し、「列と して羅列した小項目」と「行として羅列した小項目」が交わる箇所にセルを生成する。ただし、列 と行の大項目が同じ場合、セルは生成しない。推理パズルの問題例を図2.1に示す。

図2.1 推理パズルの問題例

マトリックスの使用方法として、まず、異なる大項目に属した二つの小項目から命題を定義す る。この命題の真偽を該当するセルに埋めていく。セルの状態は命題の真偽によって変化し、「命

題の真偽が確定していないセル」(以下空セル)、「命題が真であるセル」(以下真セル)、「命題が偽

めることを目的として、パズルを解く。

2.3

推理パズルのルール

本節では、推理パズルのクリア条件と、セルを埋めるためのルールについて述べる。 まず、クリア条件について述べる。推理パズルのクリア条件は、ヒントとなる文章や、すでに 埋まっている命題の真偽を利用して、空セルが1つもない状態であり、かつ全ての命題において 矛盾がないことである。推理パズルの例題をクリアしたものを図2.3に示す。 図2.3 推理パズルのクリア条件 次に、セルを埋めるためのルールについて述べる。推理パズルのセルを埋めるためのルールは、 各小項目が必ず全て1対1に対応することである。例えば、「月曜日は赤い服が売れたが、40着 は売れなかった。」というヒントがあった場合、命題「月曜日に売れた色は赤」は真であり、月曜 日には赤以外の色は売れておらず、赤の色は月曜日以外には売れていない。また、命題「月曜日 に売れた数は40着」が偽であることから、命題「40着売れた色は赤」も偽である。このセルを埋 めるためのルールを図2.4に示す。

図2.4 セルを埋めるためのルール

第

₃

章

推理パズルにおける解法抽出及び解法

の種類

3.1

解法抽出の概要

本節では、推理パズルにおける人間の解き方や考え方を基にした解法の概要を述べる。 解法の抽出には、株式会社ニコリから出版された、まるまる推理パズル[17]に掲載されている 問題を用いた。また、その問題でしか適用できない制約を追加するヒント(以下制約追加ヒント) を含んだ問題は、研究対象から除外した。 解法を抽出するにあたり、初めにヒントの情報の分類を行う。その後、解法を1つずつ定式化 し、解法抽出プログラムに組み込み、問題を解く。この時、解けない問題があった場合は、別の 解法を組み込む必要があり、新たに定式化した解法を解法抽出プログラムに組み込む。この方法 により、制約追加ヒントの情報が存在する場合を除いた全ての解法を導き、それらの解法を全て 実装した解法抽出プログラムを作ることができる。

3.2

セルの表記方法

本節では、セルの表記方法について述べる。まず、マトリックスにおいて、大項目の種類の数を M、大項目1つに属する小項目の数をI とすると、M は3以上、Iは1以上である。マトリック スにおいて、左側に表記する大項目を上から順にL1, L2,· · · , LM−1 とし、任意の左側の大項目 をLa とおく。マトリックスにおいて、上側に表記する大項目を左から順にT1, T2,· · · , TM−1 と し、任意の上側の大項目をTb とおく。Laに属する小項目を上から順にl1, l2,· · · , lI とし、Laに 属する任意の小項目をlc とおく。Tb に属する小項目を左から順にt1, t2,· · · , tI とし、Tb に属す る任意の小項目をtdとおく。これにより本研究では、ある特定のセルを[La, lc, Tb, td] と表記し、 各要素をセルの成分と呼称する。この時、a + b≤ M を常に満たす。例として、[L1, l3, T2, t4]と 表記した時、左側の大項目の内、上から1番目の大項目を指し、その大項目に属する小項目の内、 上から3番目の小項目を指す。また、上側の大項目の内、左から2番目の大項目を指し、その大 項目に属する小項目の内、左から4番目の小項目を指す。 次に、セルの集合の表記について述べる。セルの成分の内、lc またはtd のどちらかの成分を 省略した場合、残りの成分を保持するセルの集合として表す。例として、lc を省略した場合、 [La, Tb, td]と表す。また、lc, td の両成分を省略し、セルの成分が大項目のみの[La, Tb]として表 す集合を「大セル」と呼称する。本研究において、大項目の成分であるLa, Tbは必ず記載する成 分とする。この表記法の例を図3.1に示す。

図3.1 セルの表記方法の例

3.3

解法抽出の流れ

本手法では、推理パズルの解法の種類を抽出することを目的とした、解法抽出プログラムを作 成する。この解法抽出プログラムで問題を解くことにより、すでに定式化し組み込んだ解法のみ を用いている問題であれば解くことができる。この時、解けない問題があった場合は、別の解法 を組み込む必要があり、新たに定式化した解法を解法抽出プログラムに組み込む。この方法によ り、制約追加ヒントの情報が存在する場合を除いた全ての解法を導き、それらの解法を全て実装 した解法抽出プログラムを作ることができる。 まず、解法抽出プログラムを使用して問題を解くにあたり、基本となる解法を組み込む。この 解法は、ルールによってセルに埋める命題の真偽が決まる解法である。この解法の例として、真 セルがあるとき、その真セルを含んだセルの行と列の空セルが偽セルに確定するといった解法が ある。 次に、ヒントを適用した状態のマトリックスを作成する。推理パズルのヒントの文章で表す命 題の真偽情報を基に、該当するセルに真偽情報を加えることで行う。この真偽情報を追加する例

を図3.2に示す。 図3.2 セルの成分に真偽情報を追加 最後に、基本となる解法を入力した解法抽出プログラムによって問題を解く流れを述べる。解 法抽出プログラムは、組み込んだ解法を使えるセルを探し、解法が使える場合は解法を使用する。 この時、「解法の使用」とはその解法によってマトリックスの状態を一度だけ更新することであり、 あるマトリックスの状態で同じ解法が複数使用できる場合、それら全てを使用することを「解法 の適用」とする。この適用した解法によって、空セルは真セルまたは偽セルに変化する。その解 法が使えるセルが無くなった場合、次の解法を使えるセルを探すといったように解法の検索を行 う。検索の最後の解法が使えるセルが無くなった場合、最初の解法に戻り、再度検索を行う。こ の解法抽出の流れを図3.3に示す。

図3.3 解法抽出の流れ どの解法を用いても、新たに真セルや偽セルとなる空セルが存在しなくなった場合、検索を終 了する。この時、空セルが存在しなければ問題が組み込んだ解法のみで解けることになり、空セ ルが存在したら、新たに解法を追加する。この解法追加の流れを図3.4に示す。 図3.4 解法追加の流れ これを繰り返すことにより、推理パズルの解法を抽出することができる。以上が解法抽出プロ グラムの詳細である。

解法抽出プログラムを用いて解法を抽出する過程で、ヒントは4種類、解法は5種類に分類す ることで制約追加ヒントを含まない問題を全て解くことができた。したがって、基本的な推理パ ズルを解く上ではヒントの4種類と、解法の5種類で十分対応可能であり、本研究ではこのヒン トと解法を基に、難易度判定を行うこととする。次節では、各ヒントと解法の名前及び、詳細に ついて述べる。

3.4

ヒントと解法の種類

本研究で抽出した4種類のヒントは、次の2種類に分類する。 • 特定のセルの真偽を確定するヒント • 2つのセルの範囲を比較して真偽を確定するヒント 5種類の解法は、次の3種類に分類する。 • 真セルを確定する解法 • 偽セルを確定する解法 • 真セルまたは偽セルのいずれかが確定する解法 次項では、ヒントと解法の詳細を分類ごとに説明する。

3.4.1

特定のセルの真偽を確定するヒント

それぞれに分類したヒントの詳細を次に述べる。 まず、指定確定ヒントの詳細を述べる。指定確定ヒントは、小項目2つlc, td と、その2つで作 られる命題の真偽を指定してるヒントを指し、[La, lc, Tb, td]のセルの真偽情報が、指定されてい る命題の真偽に確定する。このヒントの適用例を図3.5に示す。      図3.5 指定確定ヒントの適用例   次に、補集合確定ヒントの詳細を述べる。補集合確定ヒントは、[La, Tb, td]または [La, lc, Tb] のセルの集合を示し、このセルの集合の中で、真となり得るセルを複数示しているヒントを指す。 この時、真にならない命題が補集合として示され、該当するセルを偽セルに確定する。このヒン トの適用例を図3.6に示す。

図3.6 補集合確定ヒントの適用例

3.4.2

2

つのセルの範囲を比較して真偽を確定するヒント

2つのセルの範囲を比較して真偽を確定するヒントは、小項目2つを数値情報によって比較し ているものを指し、次の2種類に分類する。 • 相互決定比較ヒント • 単純比較ヒント それぞれに分類したヒントの詳細を次に述べる。 まず、相互決定比較ヒントは、ある小項目2つに大小関係があり、その小項目同士の差または

図3.7 相互決定比較ヒントの適用例 次に、単純比較ヒントは、ある小項目2つの大小関係のみを示しているヒントを指す。この時、 [La, Tb, td]または[La, lc, Tb]のどちらかの成分表記をするセルの集合を2つ示し、それぞれのセ ルの集合に含まれるセルは、1対複数の関係で真偽が対応する。このヒントの適用例を図3.8に 示す。 図3.8 単純比較ヒントの適用例

3.4.3

真セルを確定する解法

真セルを確定する解法は、空セルを真セルに確定するものを指す。これを「残り1つは真」と

残り1つは真は、[La, Tb, td]または[La, lc, Tb] で示すセルの集合に含まれるセルのうち、1つ が空セルでその他のセルが全て偽セルの時に使用できる。この時、その空セルは真セルに確定す る。この解法の使用例を図3.9に示す。 図3.9 残り1つは真の使用例

3.4.4

偽セルを確定する解法

この解法は、空セルを偽セルに確定するものを指し、次の2種類に分類する。 • 残り全ては偽 • 単純比較ヒントの更新 まず、残り全ては偽は、空セルが真セルに確定したときに使用できる。この時、真セルに確定

図3.10 残り全ては偽の使用例 次に、単純比較ヒントの更新は、単純比較ヒントが示す2つのセルの集合のうち、必ず真セル にならない空セルが存在するときに使用できる。この時、その空セルが偽セルに確定する。この 解法の使用例を図3.11に示す。 図3.11 単純比較ヒントの更新の使用例

3.4.5

真セルまたは偽セルを確定する解法

この解法は、空セルを真セルか偽セルに確定するものを指し、次の 種類に分類する。

• 三段論法型真偽反映 • 相互決定比較ヒントの更新 まず、三段論法型真偽反映は、ある真セルの成分を[La, lc, Tb, td]とし、その真セルとは異なる2 つのセルが真偽情報を持つセルと空セルの場合、真偽情報を持つセルの真偽情報を空セルに反映 する。この時、基準となる真セル、真偽情報を反映するセル、真偽情報が反映されるセルは全て 異なる大セルに含まれる。また、[La, Tb]の位置により、三段論法型真偽反映を次の3種類に分類 する。 • 真偽反映(右、下) • 真偽反映(左、下) • 真偽反映(上、右) 真偽反映(右、下)は、[La, Tb]の位置より右側に異なる大セルが存在する時、すなわちb < M−1 の時に使用できる。この時、[La, lc, Te, tg]と[Lf, lg, Tb, td]の2つのセルの内、一方のセルのみ 真偽情報を持つ場合、その真偽情報をもう一方の空セルに反映する。e, f, gは b + 1≤ e ≤ M − 1, f = M − e + 1, 1 ≤ g ≤ I である。この解法の使用例を図3.12に示す。

図3.12 真偽反映(右、下)の使用例 真偽反映(左、下)は、[La, Tb]の位置より左側に異なる大セルが存在する時、すなわちb > 1の 時に使用できる。この時、[La, lc, Ti, tk]と[Lj, ld, Ti, tk]の2つのセルの内、一方のセルのみ真偽 情報を持つ場合、その真偽情報をもう一方の空セルに反映する。i, j, kは 1≤ i ≤ b, j = M − b + 1, 1 ≤ k ≤ I である。この解法の使用例を図3.13に示す。 図3.13 真偽反映(左、下)の使用例 真偽反映(上、右)は、[La, Tb]の位置より上側に異なる大セルが存在する時、すなわちa > 1

報を持つ場合、その真偽情報をもう一方の空セルに反映する。p, q, rは 1≤ p ≤ a, q = M − a + 1, 1 ≤ r ≤ I である。この解法の使用例を図3.14に示す。 図3.14 真偽反映(上、右)の使用例 次に、相互決定比較ヒントの更新は、相互決定比較ヒントにより示されている2つのセルの集 合のうち、必ず真セルにならない空セルが存在する時に使用できる。この時、その空セルが偽セ ルに確定する。また、示されている2つのセルの集合に真セルがあり、その真セルに対応するセ ルが空セルの時にも使用できる。この場合、その空セルが真セルに確定する。この解法の使用例 を図3.15に示す。

第

₄

章

提案手法

本章では、4種類のヒントと5種類の解法を用いた難易度判定手法について述べる。本研究で は、ヒントと解法それぞれにコストを数値化して設定する。問題を解く際、どの解法をどの順で適 用するのかを全て抽出し、コストの数値を総和する。その後、適用した解法の全てのコストの合 計と解法の適用パターン数と特定のセルの真偽を確定するヒントで確定するセル数を用いて、そ の問題のスコアを算出することで、問題の難易度を判定する。

4.1

コストの概要

特定のセルの真偽を確定するヒントのコストは、問題の難易度を下げる役割があるため、この ヒントによって命題の真偽が確定した数を負の数値として定める。また、2つのセルの範囲を比較 して真偽を確定するヒントは、解法のコストとして計算する。解法のコストは、その解法を適用

4.2

コストの計算方法

本節では、各解法のコストの計算方法を述べる。 まず、残り1つは真のコストの計算方法について述べる。この解法を使用する際に参照するセ ル数は1つである。問題を解き終えた際のこの解法のコストの合計Aは、問題を解き終えるまで のこの解法の使用回数V を用いて、式(4.1)で求める。 A = V (4.1) このコストの計算例を図4.1に示す。 図4.1 残り1つは真の計算例 次に、残り全ては偽のコストの計算方法について述べる。この解法を使用する際に参照するセ ル数は1つである。問題を解き終えた際のこの解法のコストの合計Bは、問題を解き終えるまで のこの解法の使用回数W を用いて、式(4.2)で求める。 B = W (4.2) このコストの計算例を図4.2に示す。

図4.2 残り全ては偽の計算例 次に、三段論法型真偽反映のコストの計算方法について述べる。この解法を適用する際に参照 するセル数は、解法の適用時に基準となり得る真セルの数Dx、大項目1つに属する小項目の数I を用いて、2DxI である。問題を解き終えた際のこの解法のコストの合計 Cは、問題を解き終え るまでのこの解法の適用回数X、解法の適用時に基準となり得る真セルの数D、大項目1つに属 する小項目の数Iを用いて、式(4.3)で求める。 C = 2I X ∑ x=1 Dx (4.3) このコストの計算例を図4.3に示す。

に参照するセル数は、大項目1つに属する小項目の数I を用いて、2I である。問題を解き終えた 際のこの解法のコストの合計Eは、大項目1つに属する小項目の数I、問題を解き終えるまでの この解法の適用回数Y を用いて、式(4.4)で求める。 E = 2IY (4.4) このコストの計算例を図4.4に示す。 図4.4 相互決定比較ヒントの更新の計算例 最後に単純比較ヒントの更新のコストの計算方法について述べる。この解法を適用する際に参 照するセル数は、大項目1つに属する小項目の数I を用いて、2I である。問題を解き終えた際の この解法のコストの合計F は、大項目1つに属する小項目の数I、問題を解き終えるまでのこの 解法の適用回数Z を用いて、式(4.5)で求める。 F = 2IZ (4.5) このコストの計算例を図4.5に示す。

図4.5 単純比較ヒントの更新の計算例 以上の各解法のコストの計算方法により、問題を解き終えた際の全ての解法の合計のコストGk は、式(4.6)で求めることができる。 Gk = A + B + C + E + F (4.6) 次節でスコアによる難易度判定の詳細を述べる。

4.3

スコアによる難易度設定

スコアによる難易度判定行うために、コストを用いたスコアの計算を行う必要がある。問題を 解く際、同じ問題であっても解法の適用順によってコストが異なる場合がある。そこで本研究で は、問題を解く際の解法の適用順(以下解法の適用パターン)を全て検出することでスコアを求め る。解法の適用パターンの全検出の流れを次に述べる。まず、ヒントを適用した状態のマトリッ

の解法まで解法の適用ができなかった場合、マトリックスの状態を最後に適用した解法の適用前 に戻す。その後、その適用していた解法は適用せず、次の解法が適用できるか判断する。最後に 適用した解法が無くなるまで繰り返すことで、全ての解法の適用パターンが求めることができる。 この解法の適用パターンの全検出する流れを図4.6に示す。 図4.6 解法の適用パターンの全検出 これにより、解法の全適用パターンを求めることができる。スコアS は、解法の適用パターン 数N、1つの解法の適用パターンにおける解法の合計のコストGk、特定のセルの真偽を確定する ヒントで確定するセル数H を用いて、式(4.7)で求めることができ、S の値が大きいほど問題の 難易度は高いと判定することができる。 S = ( 1 N N ∑ k=1 Gk ) − H (4.7)

第

₅

章

検証と考察

本章では、先の章で定まったスコアによる難易度判定結果が妥当であるか検証した。本検証の 目的は、本手法による難易度設定が、既存の難易度設定に近いのかを検証することである。

5.1

検証方法

スコアを求めた問題を既存の難易度ごとにグループ化し、グループ全体でスコアに差があるの か、各グループ間でスコアに差があるのかを検証した。初めにバートレット検定を用いて各グ ループの分散が等しいか検定し、その後、クラスカル・ウォリス検定を用いて、グループ全体で スコアに差があるのか検証した。次に、本研究で得られたサンプルサイズが小さいため、サンプ ルサイズが小さい場合であっても正しいp値を求めることができるマン・ホイットニーのU検定 [18]を用いて各グループ間でスコアに差があるか検証した。検証対象となる問題は3章で解法の

表5.2 掲載難易度が2の問題 スコア 152.6 176.0 184.0 265.9 表5.3 掲載難易度が3の問題 スコア 306.1 237.1 246.3 246.3 359.0 201.5 284.0 202.6 245.4 表5.4 掲載難易度が4の問題 スコア 204.4 198.8 299.2 270.7 224.8 564.4 表5.5 掲載難易度が5の問題 スコア 964.2 656.3

5.2

検証結果

まず、帰無仮説を「全てのグループに対して母分散が等しい」としたバートレット検定を行っ た。その結果、p値は0.03064となり、有意水準5％で帰無仮説は棄却された。次に、バートレッ ト検定により「いずれかの母分散が異なる」ことが示されたため、帰無仮説を「グループ全体の スコアに差はない」としてクラスカル・ウォリス検定を行った。その結果、p値は0.006275とな り、有意水準1％で帰無仮説は棄却された。また、帰無仮説を「2つのグループのスコアに差はな い」としてマン・ホイットニーのU検定を各グループの組み合わせ、計10通りに対して行った。 その結果を表5.6に示す。

表5.6 マン・ホイットニーのU検定を行った結果 グループの組 p値 (1, 2) 0.05714 (1, 3) 0.009091 (1, 4) 0.02381 (1, 5) 0.2 (2, 3) 0.07552 (2, 4) 0.06667 (2, 5) 0.1333 (3, 4) 0.9546 (3, 5) 0.03636 (4, 5) 0.07143 表5.6の結果より、グループの組(1, 3)について有意水準1％で帰無仮説は棄却し、グループ の組(1, 4)、(3, 5)について有意水準5％で帰無仮説は棄却された。また、グループの組(1, 5)、 (2, 5)、(3, 4)について帰無仮説は棄却されないが、残りのグループの4組は有意傾向にあると言 える。

5.3

考察

クラスカル・ウォリス検定を行った結果、有意水準1％で帰無仮説「グループ全体でスコアに差 はない」が棄却され、グループ全体ではスコアに差があることが分かった。また、マン・ホイッ トニーのU 検定を用いて多群検定を行ったところ、グループの組のうち、3組で有意水準1％ま

第

₆

章

まとめ

本研究では、推理パズルにおける解法を抽出し、各解法にコストの計算方法を設定することで、 推理パズルの難易度を判定する手法を提案した。この手法による難易度判定結果となるスコアと 既存の難易度の比較を行い、スコアは既存の難易度を一意に定めるとは言えないことが分かった。 ただし、一部の難易度間ではスコアに差があることが分かったため、大まかにであれば難易度の 判定を行えると推察することができる。 推理パズルのヒントと解法の種類について、3章で概要を述べたが、本研究の対象外となって いる問題も多数あるため、他に未発見のヒントや解法が存在する場合や増える可能性がある。新 たな解法やヒントの定式化ができた場合、そのコストを計算し、難易度判定に組み込む必要があ る。また、本研究ではヒントの文章からヒントデータを作る過程を難易度判定に組み込んでいな い。これは、人間の読解力はそれぞれであるため、数値化するのは困難だと考えられる。ただし、

問題を自動生成することも可能であると推察することができる。

なお本研究は、芸術家学会NICOGRAPH2018における「推理パズル問題における難易度判定

謝辞

本論文の執筆にあたり、終始適切なご指導を頂きました渡辺先生をはじめとする指導教員の 方々に心より御礼申し上げます。また、日頃から研究のサポートをして頂いたゲームサイエンス プロジェクトの皆様に深く感謝いたします。

参考文献

[1] 松原康夫. 数独の推論規則と難易度に関する考察. 情報処理学会研究報告エンタテインメント

コンピューティング (EC), Vol. 2006, No. 134 (2006-EC-005), pp. 1–6, 2006.

[2] 土出智也, 真貝寿明. 数独パズルの難易度判定-解法ロジックを用いた数値化の提案-. 大阪工

業大学紀要 and 理工篇, Vol. 56, No. 1, pp. 1–18, 2011.

[3] 乾伸雄, 小谷善行. ナンプレの解法, 難易度の算出, 問題の作成. ゲームプログラミングワーク

ショップ 2002 論文集, Vol. 2002, No. 17, pp. 163–170, 2002.

[4] 夏見勇矢, 謝孟春, 森徹, 村田充利. 数独パズルにおける低難易度の細分化. 2014年度 情報処

理学会関西支部 支部大会 講演論文集, Vol. 2014, , 2014.

[5] Simonis and Helmut. Sudoku as a constraint problem. In CP Workshop on modeling

and reformulating Constraint Satisfaction Problems, Vol. 12, pp. 13–27. Citeseer, 2005.

[6] 馬野洋平, 酒井正彦, 西田直樹, 坂部俊樹, 草刈圭一朗. 対話型埋込みによる数独問題の設計

ツール. 電子情報通信学会技術研究報告. SS, ソフトウェアサイエンス, Vol. 107, No. 392,

pp. 73–78, 2007.

[7] I. Lynce and J. Ouaknine. Sudoku as a SAT problem. In Proceedings of the 9th

Sympo-sium on Artificial Intelligence and Mathematics, 2006.

リアングレブナ基底による並列計算(数式処理とその周辺分野の研究). 数理解析研究所講究 録, Vol. 2015, No. 1955, pp. 124–133, 2015.

[9] 棟方渚, 志水雅俊, 松原仁. 皮膚電気活動を用いた数独問題の難易度評価. 情報処理学会研究

報告エンタテインメントコンピューティング(EC), Vol. 2012, No. 6, pp. 1–4, 2012.

[10] 小場隆行, 中所武司. 数独の難易度判定アプリケーションの提案と評価. 情報処理学会研究報

告ゲーム情報学(GI), Vol. 2011, No. 8, pp. 1–6, 2011.

[11] 鹿島勇紀. ペンシルパズル「美術館」における難易度判定に関する研究. 学部卒業論文, 東京

工科大学メディア学部ゲームサイエンスプロジェクト, 2010.

[12] 金井誠, 伊藤毅志. ヒューリスティックス解法に基づくイラストロジックの難易度判定関数.

情報処理学会研究報告ゲーム情報学 (GI), Vol. 2017, No. 8, pp. 1–7, 2017.

[13] 是川空,五十嵐力, 柴原一友,但馬康宏, 小谷善行. ペンシルパズルにおける 「解き筋」 の概念 の提案. ゲームプログラミングワークショップ2007 論文集, Vol. 2007, No. 12, pp. 99–106, 2007. [14] 那須律政, 松崎公紀. モンテカルロ木探索による数独少数ヒント盤面の生成. 第54回プログ ラミングシンポジウム予稿集, Vol. 2013, pp. 173–180, 2013. [15] 座間翔, 篠埜功. 初期配置が指定された場合における高難易度数独問題の自動生成手法の提案

および実装. 情報処理学会研究報告ゲーム情報学(GI), Vol. 2017, No. 7, pp. 1–12, 2017.

の解答システム. 情報処理学会第66回全国大会講演論文集, Vol. 2004, No. 1, pp. 219–220, 2004.

[20] 鈴木健太, 阿部雅樹, 渡辺大地. 推理パズル問題における難易度判定に関する研究. 芸術科学