虱潰し探索による
詰将棋を解くプログラム
近畿大学理工学部情報学科 情報論理工学研究室
13-1-037-0179
玉置 康平
目次
・研究背景
・研究内容
・結果と考察
・今後の課題
・参考文献
研究背景
・詰将棋を解くプログラムの既知の情報
・長手数の詰将棋を解く
→
「脊尾詰」がミクロコスモスを 解く・早く詰将棋を解く
→プロが
35
分かけて解くという問題集 をT2
を 1 分で解いている。ミクロコスモス 橋本孝治氏作
研究背景
➲詰将棋に使用されている主な探索法
b:
分枝率n:
深さ–
→
余詰めがあるのではないか探索法 空間計算量 時間計算量
最優良探索
O(b n ) O(b n ) ( 最悪時 )
虱潰し深さ優先探索
O(n) O(b n )
深さ優先探索
➲先手側は局面から王手となる全ての手を
Stack
に収納➲後手側は局面から王手を回避する全ての手を
Stack
に収容研究内容
例題
研究内容
研究内容
研究内容
研究内容
結果と考察
➲例１：▲ 2 三龍
,△
同玉,▲3
三金➲例２：▲ 2 四龍上,△
同金,▲3
三 龍結果と考察
➲
考察➲探索木が大きすぎない問題は解けている
➲→千日手などがあると無限ループに陥ってしまう
➲
応用方法➲自作した詰将棋の問題の余詰めのチェックが出来る
➲実戦の棋譜で詰みがありそうな局面での詰みを調べる
今後の課題
➲
今後の課題➲探索木が大きくなると回答時間が現実的なものではなくなっ てしまう
➲ユーザインタフェースの改良
➲
改善案➲柿木のアルゴリズムの採用
➲
kif
ファイルへの対応参考文献
[1]
長井歩 ,今井浩. df-pn
アルゴリズムの詰将棋を解くプログラムへの応 用,
情報処理学会論文誌,Vol.43, No.6, pp.1769-1777, 2002,
http://id.nii.ac.jp/1001/00011597/ .
[2]
伊藤琢巳 ,野下浩平.
詰将棋を早く解く 2 つのプログラムとその評価,
情報処理学会論文誌,
Vol.35, No.8,pp.1531-1539, 1994 , http://id.nii.ac.jp/1001/00014156/ . [3]
伊藤琢巳 ,ハイフリット探索法を用いた詰将棋を解くプログラム ,情報処 理学会第48
回全国大会講演論文集 ( 人工知能及ひ認知科学
), pp.125-126, 1996http://id.nii.ac.jp/1001/00125421/
[4]
池泰弘,
コンヒュータ将棋の作り方 「うさひょん」「ねこにゃ」開発日記http://usapyon.cocolog-nifty.com/shogi/
[5]
日本将棋連盟, https://www.shogi.or.jp
ご清聴ありがとうございました
