A New Algorithm to Remove Henbetu and to Find Yodume of Tsume-Shogi

IPSJ

Bibliographic Information

Other Title
  • 詰将棋における変別チェックと余詰探索を同時に行える新しいアルゴリズムの提案

Description

詰将棋の用語に，余詰と変化別詰（変別）がある．詰将棋において，作者の作意手順中では，詰ますための攻め方の王手は原則として唯一でなくてはならない．作意以外の王手でも詰ますことが出来るなら，その手順を余詰と呼ぶ．詰将棋において，余詰の発見は重要である．余詰を発見するための探索を余詰探索という．また，余詰は作意手順中にあってはならないが，作意手順以外の枝葉の部分にはあっても良い．そのせいで，詰将棋の手順として，作意手順の途中から玉方の受けの違う手順を答えてしまうことがある．このような手順は変別と呼ばれ，間違いではないが不満が残る．そのため，普通に詰むことを調べた後，変別を除去するような処理をしなくてはならない．これを変別チェックと言う．既存のアルゴリズムとして，脊尾によるアルゴリズムがあるが，余詰探索と変別チェックを別々に行う上に，原理的に発見不可能な余詰の存在を否定できないなどの欠点がある．この論文では，余詰の定義に立ち返って，余詰探索を変別チェックを同時に行える，ナイーブなアルゴリズムを提案する．その結果，証明数探索に対する既存の余詰探索アルゴリズムでは原理的に発見できなかった類いの余詰も見つけるなどの成果を得た．

There are Yodume and Henbetu in the terms of Tsume-Shogi. As with Tsume-Shogi, attacker's check must be the only move to mate the defender's king. If there is any other move, it is called Yodume, which makes the problem incomplete. It is significant to find Yodume on Tsume-Shogi problems. While there must be no Yodume in the intentional sequence, it is allowed to have a Yodume in the sequence except the intentional sequence. Due to this rule, an answerer may reply a winning sequence whose defensive move is different from the intentional sequence. This sequence is called Henbetu, which is not wrong, but not perfect. It is better to remove Henbetu. For such purpose, Seo's algorithm is known, but the algorithm to find Yodume and the algorithm to remove Henbetu at the same time. As a result, our program can find a Yodume that are impossible to find by already known algorithm to find Yodume used with Proof-Number Search.

Journal

Details 詳細情報について

Report a problem

Back to top