13 0 0 0 df-pnアルゴリズムの詰将棋を解くプログラムへの応用
- 著者
- 長井 歩 今井 浩
- 出版者
- 一般社団法人情報処理学会
- 雑誌
- 情報処理学会論文誌 (ISSN:18827764)
- 巻号頁・発行日
- vol.43, no.6, pp.1769-1777, 2002-06-15
- 参考文献数
- 18
- 被引用文献数
- 9
詰将棋を解くプログラムの研究はこの10年の間に大きく進歩した.その原動力となったのは,証明数や反証数という概念の導入である.詰将棋に適用すると,直感的にいうと,証明数は玉の逃げ方の総数を,反証数は攻め方の王手の総数を表す.前者は攻め方にとって,後者は玉方にとって非常に重要な値である.証明数・反証数を対等に扱った,最もナイーブなアルゴリズムは,Allisによるpn-searchという最良優先探索法である.我々は近年,df-pnアルゴリズムという,pn-searchと同等の振舞いをする深さ優先探索法を提案している.この論文では,df-pnアルゴリズムを用いて詰将棋を解く強力なプログラムを作成し,その過程で導入した様々な技法を提案する.これらの技法をdf-pnの上に実装することにより,我々のプログラムでは300手以上の詰将棋のすべてを解くことに初めて成功した.しかもそれは,シングルプロセッサのワークステーションで解くなど,解答能力と解答時間の両面で優れた結果を出すことができた.During this decade, a study of programs to solve Tsume-Shogi problemshas greatly advanced. This is due to the development ofthe concept of a proof number and a disproof number.Allis' pn-search is the most naive best-first algorithm that usesboth proof numbers and disproof numbers on equal terms.We already developed a df-pn algorithm which is a depth-firstalgorithm that behaves the same as pn-search.In this paper, we applied df-pn algorithm to a program solvingTsume-Shogi problems. Moreover, we propose some techniqueswhich we imported during implementing the program.As a result, by these techniques implemented on df-pn,our program solved all the Tsume-Shogi problems,for the first time, that require over 300 plies to reach to the checkmate.
12 0 0 0 OA 難解な必至問題を解くアルゴリズムとその実装
- 著者
- 長井 歩
- 雑誌
- ゲームプログラミングワークショップ2011論文集
- 巻号頁・発行日
- vol.2011, no.6, pp.1-8, 2011-10-28
将棋の終盤戦をパズル化した問題として,詰将棋以外に必至問題がある.その違いは,攻め側の手として王手以外に詰めろも許される点にある.詰将棋では攻め側の指せる手は王手のみであるのに対し,必至問題では王手と詰めろで相手の玉を受けなしに追い込む.攻め側の手が増える分,必至問題に強いアルゴリズムは,実際の将棋の終盤戦で役立つ機会は詰将棋に比べ格段に多くなる.しかし問題としての難易度は,一般に詰将棋よりも必至問題の方が難しい.詰将棋を高速に解くアルゴリズムは近年著しく進歩したが,必至問題を高速に解くアルゴリズムは未開拓である.本研究では,難解な必至問題を高速に解くアルゴリズムとしてdf-pn+ を応用し実装した.実験の結果,難解な必至問題集として有名な『来条克由必至名作集』全81 問のうち79 問を解くことに成功した.また,余必至探索にて3つの早必至を含む27 の余必至を発見できた.
7 0 0 0 OA df-pnアルゴリズムの詰将棋を解くプログラムへの応用
- 著者
- 長井 歩 今井 浩
- 雑誌
- 情報処理学会論文誌 (ISSN:18827764)
- 巻号頁・発行日
- vol.43, no.6, pp.1769-1777, 2002-06-15
詰将棋を解くプログラムの研究はこの10年の間に大きく進歩した.その原動力となったのは,証明数や反証数という概念の導入である.詰将棋に適用すると,直感的にいうと,証明数は玉の逃げ方の総数を,反証数は攻め方の王手の総数を表す.前者は攻め方にとって,後者は玉方にとって非常に重要な値である.証明数・反証数を対等に扱った,最もナイーブなアルゴリズムは,Allisによるpn-searchという最良優先探索法である.我々は近年,df-pnアルゴリズムという,pn-searchと同等の振舞いをする深さ優先探索法を提案している.この論文では,df-pnアルゴリズムを用いて詰将棋を解く強力なプログラムを作成し,その過程で導入した様々な技法を提案する.これらの技法をdf-pnの上に実装することにより,我々のプログラムでは300手以上の詰将棋のすべてを解くことに初めて成功した.しかもそれは,シングルプロセッサのワークステーションで解くなど,解答能力と解答時間の両面で優れた結果を出すことができた.
5 0 0 0 OA 詰将棋における変別チェックと余詰探索を同時に行える新しいアルゴリズムの提案
- 著者
- 長井 歩 今井 浩
- 雑誌
- ゲームプログラミングワークショップ2001論文集
- 巻号頁・発行日
- vol.2001, no.14, pp.9-16, 2001-10-26
詰将棋の用語に,余詰と変化別詰(変別)がある.詰将棋において,作者の作意手順中では,詰ますための攻め方の王手は原則として唯一でなくてはならない.作意以外の王手でも詰ますことが出来るなら,その手順を余詰と呼ぶ.詰将棋において,余詰の発見は重要である.余詰を発見するための探索を余詰探索という.また,余詰は作意手順中にあってはならないが,作意手順以外の枝葉の部分にはあっても良い.そのせいで,詰将棋の手順として,作意手順の途中から玉方の受けの違う手順を答えてしまうことがある.このような手順は変別と呼ばれ,間違いではないが不満が残る.そのため,普通に詰むことを調べた後,変別を除去するような処理をしなくてはならない.これを変別チェックと言う.既存のアルゴリズムとして,脊尾によるアルゴリズムがあるが,余詰探索と変別チェックを別々に行う上に,原理的に発見不可能な余詰の存在を否定できないなどの欠点がある.この論文では,余詰の定義に立ち返って,余詰探索を変別チェックを同時に行える,ナイーブなアルゴリズムを提案する.その結果,証明数探索に対する既存の余詰探索アルゴリズムでは原理的に発見できなかった類いの余詰も見つけるなどの成果を得た.
3 0 0 0 OA 将棋の必至問題および最終盤を解くアルゴリズムの研究
- 著者
- 長井 歩
- 出版者
- 一般社団法人情報処理学会
- 雑誌
- 情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)
- 巻号頁・発行日
- vol.2007, no.119, pp.73-80, 2007-11-30
多種多様なアルゴリズムのひしめくクラスタリング・アルゴリズムの中でも,近年注目されているものにNormalized Cutsがある.Norma』ized Cuts の最大の特徴は,固有値分解を行うなど行列計算を多用する点にある.基本的には,Normalized Cuts は分割クラスタ数を固定した上で,独自の評価基準のもとでクラスタ分割を得るという手法である.クラスタ数を固定するため,クラスタ数を変えることに対する柔軟性には乏しい.また Normalized Cuts は行列計算を行う際に粗行列化することによって計算量をO(n1.5) に減らしてるが,粗行列化できない場合にはO(n2.5) にまで増大してしまう.(nはデータ数である.)本論文で提案する階層型アルゴリズムは Normalized Cuts のこれらの問題点を解消できるいったん実行してしまえば,様々なクラスタ数の解を得ることが容易である.また,計算量は常にO(n2)である.アルゴリズムの基本的な骨格は古典的な階層型手法に似ている.しかし Normalized Cuts の評価基準を用いているために,両者の長所を併せ持つ.すなわち,Normalized Cuts のように任意の形状のクラスタを得られ,かつWard法のように樹形図を得ることができる.The characteristic mark of Normalized Cuts is that it relies on a linear algebraic approach including spectral decomposition. Basically, it obtains a partition by fixing the number K; of clusters. Therefore, it is not so easy to obtain partitions of various k, besides re-calculating. Moreover, when we cannot use sparse matrix, computational complexity jumps up to O(n2.5). We propose an hierarchical algorithm which can resolve these problems. It is easy to obtain partitions of various k after running the program. Its computational complexity is O(n2).