« 詰将棋メモ(2009年9月12日) | トップページ | 詰将棋メモ(2009年9月13日) »

コンピュータ詰将棋の課題

[2009年9月13日最終更新]
2009年9月11日に、「コンピュータ将棋・囲碁の最新動向」と題する講演会があり、コンピュータ将棋とコンピュータ囲碁が局面評価の自動学習やモンテカルロ法など、新しい手法をベースに改善を重ね、急速に強くなっている現状が解説された。詰将棋についてもこのようなドラスティックな展開の余地は残っていないのか。現状のコンピュータ詰将棋の課題について考えてみた。

関連情報: コンピュータ将棋2017  2016  将棋ソフト・コンピュータ将棋
  詰将棋ソフト・コンピュータ詰将棋 


1.コンピュータ詰将棋の歴史と動向

これまでの歴史を簡単に振り返ってみる。 (参考:コンピュータで詰将棋

1)1990年以前
1968年に詰将棋の解図プログラムが初めて登場した。大型計算機によるものだったが、短い詰将棋しか解けず、時間も人間が解くのと競争する企画があったほど遅かった。

2)1990年代
コンピュータ将棋協会が活動を始め、コンピュータ将棋選手権開始など、コンピュータ将棋研究が活発化した時代。詰将棋についても、各種の解答アルゴリズムが提案され、共謀数を利用した脊尾詰が最長手数(1525手)のミクロコスモスを解いた。またプログラムによる詰将棋の創作もいろいろ試みられ、30手ぐらいまでの詰将棋を生成することもできるようになるなど、大きな発展を遂げた。

3)2000年代前半
df-pnアルゴリズムが登場、さらに強力になりほとんどの詰将棋が解けるようになった。df-pn+や経路探索など、改善、強化する研究も進められた。

4)最近
上記のように発展してきたコンピュータ詰将棋だが、ここ数年はめだった展開は見られない。最近のコンピュータ詰将棋研究が低調なのは、df-pn探索が強力でほとんどの詰将棋が解けたため、もう詰将棋の研究は終わったという雰囲気になったからかもしれない(実際、将棋プログラムの詰ルーチンとしては、現在の能力でも十分である)。

2.コンピュータ詰将棋の課題

人間は詰将棋について、解答、創作、鑑賞、発表、蒐集、研究などいろいろな関わり方をしている。人口知能研究の題材として考えたとき興味深いのは、解答、創作、鑑賞であろうか。それぞれ、現状と課題を考えてみる。

3.詰将棋解答の課題

プログラムでほとんどの詰将棋を詰められるようになったが、正解を出すのは案外難しい。

課題A: 現在のプログラムでは詰められない難解作を解く
コンピュータ向け超難解詰将棋作品集にはプログラムで解くのが難しい詰将棋が集められている。裸玉などで変化紛れが膨大な作品や、数百手の長手数で、変化が多くそれも数百手かかるような作品が多い。この作品群が全て解けるか。
df-pnは詰将棋の知識なしに実装できる優れた方法だが、問題によっては手の選択が必ずしも効率的とは限らない。いろいろな手法を検討する必要があるかもしれない。
・詰将棋データベースから最適な評価項目、評価値を学習する
・異種の複数のアルゴリズムを組み合わせる
・問題の特性を分析し、それにあうアルゴリズムや知識ベースを使う
・類似局面の読みを大きく省略する手法
・FPGA化、並列化、大容量メモリなど、パワーで解決

課題B: 単に解くだけではなく、できるだけ正解する
どんな応手でも詰むことが証明できても、正しい応手を選択するのは別な問題である。原理的には全ての手を読まなければならないが、それは現実的でない。現在のプログラムの正解率はどのぐらいだろうか。例えば詰将棋パラダイスの解答競争では1年間全題正解者がいるが、このような解答名人に匹敵するプログラムが作れるか。

課題G: (実用的な時間で)完全検討 (2009年9月13日追加)
課題H: (実用的な時間で)不詰局面での不詰の証明 (2009年9月13日追加)
神無七郎さん「課題に「完全検討」(あるいは「不詰の証明」)を追加して欲しいと思います。「作意以外の攻方の着手で不詰となること」を完璧に、かつ実用的な時間で証明できるようになれば、「課題B」も自然に解決しますし。」
ということで追加。完全検討と不詰の証明は同値ではないと思うので二つに分けた(正解するには不詰の証明だけでなく複数の詰みがあるときに最短の詰を見つけることが必要)。課題Gが達成できれば課題Bは100%正解できるが・・・。課題Hについては2004年のGPWで岸本さんがGHI問題を解決し将棋無双の不詰14作のうち12作の不詰を証明したとの報告をしている。

4.詰将棋創作の課題

詰将棋の創作の研究は、まだ端緒についたばかりで、人間が感心するような詰将棋はほとんど作れない。

課題C: プログラムで長手数の詰将棋(例えば100手以上)を作る
これまでのプログラム創作の手法には、順算式(条件+ランダムな配置でたくさん生成して完全作を抽出)、逆算式(詰上りから1手ずつ戻す)などが試みられている(コンピュータによる詰将棋創作)。しかし、こういった手法では長手数の詰将棋は作れないため、何らかの新手法が必要になる。
・手順を与えて、それが成立する配置を求める手法
・繰り返しを含む趣向詰を生成する手法
・既存の詰将棋から繰り返し手順を抽出する手法

課題D: プログラムだけで煙詰を作る
詰将棋の鑑賞と関係してくるが、人間に感心される詰将棋を作るのは評価基準があいまいなため非常に難しい。その中で、煙詰(初形39枚配置で詰上りは3枚だけになる詰将棋)は分かりやすく、詰将棋をほとんど知らないひとでも感心してくれる可能性が大きい。煙詰の創作は人間はほとんどの人が逆算式で行っており、プログラムでも逆算式で創作することになるだろう。逆算は全部の手を生成するとすぐに爆発するため、できるだけ長く逆算が続く手を選択する手法が必要である。
全駒の煙詰の生成はグランドチャレンジだが、煙詰にはもっと枚数が少ない煙詰(小駒煙、歩なし煙など)もある(ネットで見る煙詰参照)ので、段階的に挑戦できる。最初のターゲットは金銀煙ぐらいだろうか(これは実は岡村さんによって全検されている)。

課題E: 詰将棋創作のアシストをするプログラム
詰将棋創作で一番時間がかかっていた完全作かの検討をプログラムでできるようになって、とても楽になったが、創作自体をアシストする機能はほとんど存在しない(人間とプログラムのコラボレーションは逆算式で試みられたことがある)。この分野が発展して、人間とプログラムの合作で看寿賞受賞、なんていう日はくるのだろうか。
・逆算でお勧め候補を提示
・骨格を人間が作り、序や収束はプログラムが付ける
・詰将棋データベースを知識ベース化し、創作のアドバイス

5.詰将棋鑑賞の課題

プログラムに人間が見ていい作品を創作させるには、人間がどんなふうに鑑賞しているのか分析することが重要になる。

課題F: 人間に近い評価を行えるプログラム
詰将棋に点数をつける試みはいろいろ行われているが、いずれも短編が中心で、人間が感動する構想や趣向など中長編を含む評価はほとんど手つかずの状態。人によって感性が異なり、また似た作品だと評価が下がるようなこともあって絶対的な評価をつけることは非常に難しい。ある程度人間に近い評価ができるようになれば、鑑賞に耐えうる詰将棋をプログラムで作ることができるようになる。詰将棋パラダイスでの出題は解答者がABCなど評価を付けることが多いので、これと比較することでどのくらい人間に近いか判断できるだろう。

6.詰将棋プログラムも研究しよう

思いつくままに課題をあげてきたが、もちろん、こっちの方が大事とか、ほかにもいろいろな課題があるだろう。将棋プログラムはいつ名人に勝つか、非常におもしろい段階にあるけれど、詰将棋もまだまだおもしろいよ、ということが伝われば幸いである。

|

« 詰将棋メモ(2009年9月12日) | トップページ | 詰将棋メモ(2009年9月13日) »

「コンピュータ詰将棋」カテゴリの記事

コメント

課題に「完全検討」(あるいは「不詰の証明」)を追加して欲しいと思います。
「作意以外の攻方の着手で不詰となること」を完璧に、かつ実用的な時間で証明できるようになれば、「課題B」も自然に解決しますし。

投稿: 神無七郎 | 2009.09.12 21:07

手順から盤面を生成するプログラムがあれば、いいですね。

投稿: こんさん | 2009.09.14 13:11

課題Cで書いた「手順を与えて、それが成立する配置を求める手法」ですね。人間とコンピュータのコラボレーションの有力な方法だと思います。

投稿: TETSU | 2009.09.14 19:58

コメントを書く



(ウェブ上には掲載しません)




トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/22735/46191253

この記事へのトラックバック一覧です: コンピュータ詰将棋の課題:

« 詰将棋メモ(2009年9月12日) | トップページ | 詰将棋メモ(2009年9月13日) »