原口和也 高橋隆一 丸岡章 石巻専修大学 理工学部 情報電子工学科

Presentation on theme: "原口和也 高橋隆一 丸岡章 石巻専修大学 理工学部 情報電子工学科"— Presentation transcript:

1 原口和也 高橋隆一 丸岡章 石巻専修大学 理工学部 情報電子工学科
計算ブロックパズルの問題例生成 9 8 1 4 3 6 原口和也 高橋隆一 丸岡章 石巻専修大学 理工学部 情報電子工学科

2 計算ブロックパズルとは？ セル ブロック 合計値 1 3 4 2
6 9 1 3 4 2 下の条件を満たすように 1 から n の整数を セルに埋めよ (i) ラテン方陣条件 (ii) 部分和条件 3 8 3 1 2 4 4 2 4 1 3 9 1 4 2 3 1 n  n のセルから成る盤面

3 発表内容 唯一解を持つ中で最も「難しい」問題例の生成 (WAAC08で発表済) パターンの獲得に関する実験

4 生成の方針 +  L P 解となるラテン方陣 L を決定 n  nセル集合の分割 P を決定 L を唯一の解として持ち、
6 9 1 3 4 2 3 8 +  4 9 1 L P L を唯一の解として持ち、 最も「難しい」問題例? ラテン方陣 L は given  分割 P が問題例に対応

5 準備  解集合 唯一解 分割上の半順序 分割 P（に対応する問題例）において 解となるラテン方陣の集合を SOL(P)
明らかに for P, LSOL(P) 解集合 分割 P（に対応する問題例）において 解となるラテン方陣の集合を SOL(P) 唯一解 SOL(P) = {L} ならば、Pは唯一解分割という 分割上の半順序  Q P

6 40 分割の Hasse 図 P  唯一解分割でない 1 3 4 2 3 1 2 4 2 4 1 3 唯一解分割 P 4 2 3 1

7 40 明らかに、 P  Q ならば SOL(P)  SOL(Q) P  極大な唯一解分割 1 3 2 4 唯一解分割 P

8 極大な唯一解分割 の求め方     P  P 隣接する 2ブロックを選択 すべて試したら終了 唯一解分割の判定 YESならば採用
1 へ戻る     4 2 3 1 1 3 4 2 3 1 2 4 2 4 1 3 P 4 2 3 1

9 [宮本, ”強育パズル vol.3,” Discover, 2004] との比較
人が作った問題例との比較 [宮本, ”強育パズル vol.3,” Discover, 2004] との比較 難しすぎることも しばしば試行錯誤を要する 簡単 論理的に解くことができる

10 極大な唯一解分割による 面白いパズルの例 20 55

11 発表内容 (cont.) 唯一解を持つ中で最も「難しい」問題例の生成 (WAAC08で発表済) パターンの獲得に関する実験

12 パターンとは パズルのルールから論理的に導かれる セルを埋めるためのテクニック 多大な試行錯誤（探索木）を必要とせず
パターンの適用で解ける問題例が 一般に「面白い」とされる プレイヤーはパターンをどう獲得するのか 自明なパターンからそうでないものまで5つに分類 被験者にパズルを解いてもらい パターンが獲得される様子を観察

13 パターン (P1) 単一のセルから成るブロック 7 6 4 3 6 4 3 2 3 2 5

14 パターン (P2) ブロックの残り１セル 7 6 4 3 6 4 3 2 1 3 2 5 3

15 パターン (P3) 行 or 列の残り１セル 7 6 4 3 6 4 3 2 4 1 3 2 5 3

16 パターン (P4) 行 or 列内のブロックの合計値および 確定した値から導出 7 6 4 3 6 4 3 2 4 1 3 2 5 3 1

17 パターン (P5) 同じ値がn1個のセルで確定 7 6 4 1 3 1 6 4 3 2 4 1 3 2 5 3 1

18 データ収集 データ収集のシステム 使用する問題例 収集されたデータ 学内イントラネット上に構築 被験者はブラウザを通じてパズルを解く
類似の問題例に対する傾向を観察したい 一辺のセル数を n=4, ブロックの最大サイズを 2 に限定 収集されたデータ 2週間、約6000件（63名の被験者） 1件のデータは1被験者が1問題例を解いた記録 データの項目 被験者ID, 問題例番号, 開始時刻, 各セルを埋めた時刻, ...

19 7 6 4 3 6 4 3 2 5 セルを埋めた順序を 追跡可能 (P1)から(P5)のうち 適用可能かつ 最小indexのパターンを
適用したものとみなす 適用可能なパターンが なければ(P6) i.e., その他 パターンの適用に 要した時間を推定 01:25 01:20 01:50 01:40 3 01:15 01:10 01:45 01:35 6 4 (P6) 3 (P1) 2 (P1) 00:45 00:35 00:10 00:05 [00:25] [00:05] [00:05] (P2) 5 00:50 00:40 01:55 02:00 [00:10] ゲーム開始から 埋められるまでに要した時間

20 （パターンの適用に要した時間：秒） （解いた問題例の数）

21 （パターンの適用に要した時間：秒） （解いた問題例の数）

22 実験のまとめ 何人かの被験者について パターンを獲得する過程が観察された 計算時間から問題例の難しさを 評価するのは容易ではない
被験者によって習熟度が異なる 「習熟した」とみなす基準?

23 今後の課題 人が解いて「面白い」問題例の生成 プレイヤーがパターンをどう適用するかを 考慮に入れて Hasse 図 を上れないか
パターンにはどのようなものがあるのか 実験方法の検討