著者

是川 空 小谷 善行

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.53, no.6, pp.1617-1624, 2012-06-15

---

本研究ではパズルの思考過程のモデル化の研究として,四川省と呼ばれる麻雀牌を利用したパズルの難易度推定を行う.これは四川省パズルの問題に対して,計算機によって算出された状態空間が持つ特徴量と,人間が実際に問題を解いているときの正答率や解答時間などの難易度に関わる項目との間にどのような相関があるかを測るものである.四川省パズルの持つ状態空間は解状態への経路を持つ状態と持たない状態の2つに分割することができる.解状態への経路を持つ局面をsolvable局面,持たない局面をunsolvable局面と定義し,問題から局面構造の特徴として平均可能手数,solvable局面とunsolvable局面の割合,平均unsolvable遷移パス割合,unsolvable局面空間の最長経路の4種類の特徴量を抽出した.それに対し人間のパズルを解く思考過程を得る方法として,Web上に四川省プログラムを設置しデータを収集した.収集されたデータから各問題に対する解答時間と正答率に対する難易度指標値を算出した.問題から得られた特徴と収集したデータから算出した難易度指標値の間の相関を測るため,回帰分析によって特徴から難易度指標値を推定する予測式を得た.この結果より平均解答時間を推定するには平均可能手数が大きく寄与していることが分かった.一方で正答率は平均可能手数に加え状態空間構造の特徴を回帰式に導入することで相関が向上した.

著者

是川 空 五十嵐 力 但馬 康宏 小谷 善行

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告. GI, [ゲーム情報学] (ISSN:09196072)

巻号頁・発行日

vol.17, pp.65-72, 2007-03-05

参考文献数

2

---

はめ込みパズルの一種であるHeptamond問題は膨大な分岐数と解局面を持つことで知られている.この問題について未知数である全解数の推定を行った.探索を高速化する手法として,複数の分岐の可能性から最少の分岐数を選択して探索を行うアルゴリズムを用いた.各探索深さにおける選択された最少の分岐数の平均が,その探索深さの局面数の変化率に値することに着目し,各深さにおける平均最少分岐数を得るための実験を行った.一つ目の実験は探索を一定確率で打ち切るシミュレーション実験,もう一つは探索深さに閾値を設けた全探索を行った.この実験によって,平均最少分岐数の推定を行い, Heptamond問題の各深さにおける総局面数を求め,全解数がおよそ10^<11>であると推定した.

著者

是川 空 五十嵐 力 柴原 一友 但馬 康宏 小谷 善行

雑誌

ゲームプログラミングワークショップ2007論文集

巻号頁・発行日

vol.2007, no.12, pp.99-106, 2007-11-09

---

パズルは探索問題としての見地からその性質が考えられてきた.しかし数独やカックロなどのペンシルパズルでは,探索経路が一本道であり、探索問題として考えるのは意味がない.効率的な解法のためには数字を入れる図中の箇所を選ぶ順序が重要である. 本研究ではこの点に着目して新しい概念を提起し,理論化する.ペンシルパズルにおいて一般的に存在している,制約による解答の順序構造を問題の「解き筋」として定義した.解き筋を問題から抽出することで,問題の難易度や良し悪しの判定をするために使用する.効率的に解き筋を抽出するために,解き筋の中でも重複した部分を取り除いた有用な解き筋のみを得るアルゴリズムを設計する.ラテン方陣問題による実験を行い,その解き筋を得た.得られた解き筋から問題の特徴を考察する.

著者

秋山 晴彦 是川 空 小谷 善行

雑誌

第52回プログラミング・シンポジウム予稿集

巻号頁・発行日

vol.2011, pp.111-118, 2011-01-07