Deep Proof-Number Search and Aesthetics of Mating Problems

 本研究では主に証明数探索について2つの研究テーマを扱った．それぞれ，a）より効率的な証明数探索アルゴリズムの開発，b）証明数探索を活用した詰め将棋の評価である．証明数探索はゲームを解くことができる効率的な探索アルゴリズムである．たとえば三目並べでは，お互いのプレイヤがミスをしなければ結果は必ず引き分ける．この，必ず引き分けるという結果を証明することを『ゲームを解く』という．1994年にAllisによって証明数探索が提案されて以降，チェッカーや四目並べなどいくつかのゲームが解かれてきた．また，詰め将棋などのパズルにおいてはその解を素早く求めることも可能となった．最長詰め手数を誇る詰め将棋『ミクロコスモス（1525手詰め）』においては，証明数探索により初めてコンピュータが解を得ることに成功した．今日では証明数探索のさまざまな改良アルゴリズムが開発され，多くのゲームや問題を解くことが可能になっている．しかし，いくつかの課題は取り残されており，すべてのゲームを解くことはできていない．また，証明数探索にかかわる研究も近年不活発である．そこで，本研究テーマとしてa） b）の2つのように，取り残された課題への対処と，証明数探索の新たな利活用発見について取り組んだ．

 研究テーマa）では証明数探索を改良し，より効率良く解を得られるアルゴリズムの開発に挑戦した．証明数探索は非常に効率的な探索を行うことができるが，一部の問題においてシーソーエフェクトと呼ばれる現象が発生し，その効率が失われることが分かっている．本テーマではこの問題に取り組み，新たなアルゴリズム『Deep証明数探索』の開発を行った．この探索アルゴリズムの特徴は，オリジナルの証明数探索と異なる定義の探索指標を持っている点である．実際にシーソーエフェクトが発生しやすいゲームであるオセロやHexにおいてDeep証明数探索を用いたところ，オリジナルの証明数探索に比べ2倍程度効率的に探索することが可能となった．この結果から，探索指標の定義を変更するという視点から証明数探索の新たな改良方法を提案できたと考える．

 研究テーマb）では証明数探索の新たな利活用方法として，詰め将棋の評価に用いることへ取り組んだ．証明数探索を用いて詰め将棋を解く際には，効率的に解を得るため内部で証明数・反証数の2つの探索指標を用いている．本テーマではこの2つの値を記録し，詰め将棋コンテストでの評価ランキングと比較することで，順位の高い問題の評価の秘密について調査した．その結果，最大反証数とコンテストの順位に相関を発見した．反証数は詰め将棋において紛れの難易度を表すと考えられていることから，難しい紛れを持つ問題ほど評価されているという結論に至った．このように，証明数探索が問題を効率的に解くだけでなく，その探索指標を用いることで詰め将棋の評価などに利活用できるという可能性を示すことができた．

 

 

（2016年7月31日受付）