QBFソルバを用いた詰将棋に対する即詰みの有無判定

• Item type: Symposium(1)
• 公開日: 2017-11-03
• タイトル: QBFソルバを用いた詰将棋に対する即詰みの有無判定
• タイトル / 言語: en
• タイトル: Determining Forced Mate Possibility in Shogi using a QBF Solver
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 詰将棋
• キーワード / 主題Scheme: Other
• キーワード / 主題: QBF
• キーワード / 主題Scheme: Other
• キーワード / 主題: 詰みの有無
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: 東北大学大学院情報科学研究科
• 著者所属: 東北大学大学院情報科学研究科
• 著者所属: 東北大学大学院情報科学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Sciences, Tohoku University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Sciences, Tohoku University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Sciences, Tohoku University
• 著者名: 石脇, 滉己; 吉仲, 亮; 篠原, 歩
• 著者名(英): Koki, Ishiwaki; Ryo, Yoshinaka; Ayumi, Shinohara
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本研究の目標は，与えられた将棋の局面が入力された手数以内に詰むかどうかの問題をTrue Quantified Boolean Formula (TQBF)問題に帰着して，QBFソルバを用いることで即詰みの有無判定を行う手法を確立することである．TQBF問題とは，与えられたQuantified Boolean Formula (QBF)が充足可能であるかを判定する問題である．この問題は，PSPACE完全問題として知られており，理論的には高速に解くことは非常に困難である．これに対して，このTQBF問題を実用的に高速に解くためにQBFソルバが開発されてきた．本稿では，持ち駒のない局面をQBFに帰着する方法を提案し，簡単な局面に対しては即詰みの有無判定を正しく行えることを確認した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The goal of this research is to establish a method to solve the problem to decide whether there is a forced mate within inputted number of moves on a given shogi position by reducing it to the true quantified boolean formula (TQBF) problem and then using a QBF solver. The TQBF problem is to determine whether a given quantified boolean formula (QBF) can be satisfied. This problem is known as PSPACE complete, so it is very difficult to solve fast in theory. In order to solve the TQBF problem fast in practice, various QBF solvers have been developed. In this paper, we propose a method to reduce positions without pieces in hand to QBF and verified that a QBF solver can determine the forced mate possibility of simple position.
• 書誌情報: ゲームプログラミングワークショップ2017論文集; 巻 2017, p. 152-157, 発行日 2017-11-03
• 出版者 / 言語: ja
• 出版者: 情報処理学会