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

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

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

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


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.詰将棋プログラムも研究しよう

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

| | コメント (3) | トラックバック (0)

コンピュータによる詰将棋創作

[2006年12月2日最終更新]
コンピュータ(将棋ソフト)による詰将棋解答は研究が進み、現在では人間を凌ぐ解答能力を持つに至っている。一方、コンピュータによる詰将棋の創作は、かなり前から試みられていて、市販の将棋ソフトでも詰将棋創作機能を搭載したものも出てきているが、いまだに人間をびっくりさせるような作品を生み出せていない。コンピュータ創作の詰将棋が看寿賞を受賞するのはいつの日になるのだろうか。

関連情報: コンピュータ将棋2012  2011  将棋ソフト・コンピュータ将棋
  コンピュータで詰将棋  コンピュータ詰将棋の課題


ソフトは詰将棋を作れるか
2006年12月1日、おおた葉一郎のしょーと・しょーと・えっせいで、ソフトは詰将棋を作れるか
「・・・ 詰将棋の駒の配置や詰めに至る手筋に対して、人間が感じる感情を数値的に捉えていないことになる。それでは優れた詰将棋をつくることはできない。そのため、この詰将棋を点数で評価しようということを企てている人たちがいるようだ。例えば、ソフトはまず、ランダムに10題作成して、それらを採点して、もっとも点数の高い作品を完成作とする、とかいうのだろう。一方、私は「徒労だろう」と思うと同時に、そういうことを真剣にやろうとする人たちの神経を疑うしかない。 ・・・ さらに、その詰将棋に点数をつけようという考え方の、採点基準なるものが重要になるのだが、ちょっと聞いたところでは、
1.大駒(飛車、角)の使用が評価が高い。
2.5五の地点(盤の中央)に近いところで詰む方が難しいので評価が高い。
3.詰め上り図で、王様に接する駒が少ない方がいい。
というような条件が付けられているようだ。そのためのみの作品を作ってみたのが、前々週の出題。 ・・・」

詰将棋評価プログラム
2006年7月6日、おもちゃ箱掲示板で、門脇芳雄さん
「7月8日(土)午後3時からのコンピュータ将棋協会(CSA)の例会で、「コンピュータによる詰将棋の評価」(自作プログラム)について発表します。関心のある方は御来聴ください。来聴は自由です。 会場=早稲田大学(本部)キャンパス1号館3階303教室」

金銀煙
2006年2月27日、おもちゃ箱掲示板で、橋本孝治さん
「昨日の詰工房で話題になった金銀煙の例です。
例)23銀 34銀 41金 43銀 / 12金 21玉 31金 32銀 33金 / なし
「金銀桂」の煙や「金銀桂歩」の煙は、これより遥かに難しそうなのであまり考えていません。
乞う挑戦者!」
2006年2月27日、TETSU
「煙詰のコンピュータ創作が話題になったとき、全駒は大変だからまずは小駒煙から・・・
香も省いて「金銀桂歩煙」では・・・いや香がないと3枚は不可能では・・・
「金銀煙」なら簡単にできそう・・・と盛り上がりました。 ・・・」

TETSU: 人間が高度な詰将棋を創作する過程を考えると、解答とは異質の知識ベースやアルゴリズムが存在することが推察できる。この分野はあまり研究されてなく、コンピュータで看寿賞クラスの作品を創作するには、超えなければならないハードルは多い。まずは、人間と協調して高度な作品を創作する創作支援システムでノウハウを蓄積するところから始めるのがよいかもしれない。コンピュータ単独での創作では、現在の時点で短期的に可能性がありそうなのは、煙詰である。といっても、これもグランドチャレンジであり、5年ぐらいかかると予想。最初は金銀煙や七色煙あたりで、逆算の基礎的理論を構築したい。

逆算法に基く詰め将棋の列挙
2005年9月12日、組合せゲーム・パズル ミニプロジェクト 2005年度 第1回ミニ研究集会
 ・逆算法に基づく詰め将棋の列挙 [発表資料(ppt)]
  堀山貴史、中塚裕之、岩間一雄(京都大学       情報学研究科)
「・・・逆算法により詰め手数の少ないものから順に詰将棋を列挙することで、詰将棋解答プログラムを用いることなく、与えられた条件下で可能な詰将棋を高速に列挙することができる。」

コンピュータは詰将棋を作れるか
2005年11月11日、勝手に将棋トピックスで、コンピュータは詰将棋を作れるか
「・・・この話題は2段階にわけて考えるのがいいと思います。
  1. コンピュータに(ルールにのっとった)完全な詰将棋を作らせるにはどうするのか。
  2. コンピュータに人間の鑑賞に堪えうる詰将棋を作らせるにはどうするのか。
前者に関しては、ランダムに配置した詰将棋の中から完全性をチェックして抽出するという方法で、すでに商品化されたものもあります。後者については人間がどのような判断基準で詰将棋の良し悪しを決めているかをある程度数値的に判断することはまだ課題が多く、初形一色図式などの条件を人間が指定して検索するというようなアプローチなどがあるようです。」

コンピュータによる詰将棋創作の歴史

2005年11月9日、TETSU
詰将棋創作関連のトピックスをまとめてみた。詰将棋関連全般についてはコンピュータで詰将棋を参照されたい(情報処理学会関連の論文は電子図書館の移行により、以前のURLではアクセスできなくなっているので注意)。

  1. 解答プログラムの進歩
    初めて詰将棋を解くプログラムが書かれたのは1967年、日立の越智さん。大型計算機のプログラムだったが、短編しか解けず、解くスピードは人間といい勝負だった。
    これからしばらくは停滞し、再び取り組みが始まったのは1980年代に入ってから。田中さん、柿木さん、森田さんなど、アルゴリズムは手数による反復深化だったが、柿木さんの無駄合検出などでだんだん実用になっていく。
    1990年代に入ると、野下先生のハッシュの活用で飛躍的に高速化、更に伊藤さんの最良優先探索、河野さんの類似局面の利用、脊尾さんの共謀数による多重反復深化と研究が進み、超長編も解けるようになった。この流れはdf-pnに進化し、2000年には長井さんのプログラムが300手以上の全ての超長編詰将棋を解くまでに至った。

  2. 感性評価
    1993年頃から小山さん、河野さんの詰将棋の感性評価の研究。詰将棋の創作では、人間から好感、高い評価を得ることが目標になるので、人間は何を基準に評価しているのかの研究は重要。ただ、評価には個人差も大きく、短編と長編ではまた違う。初めて発表されたとき高い評価でも同じような作品が次に出ると類似作で低評価になるなど、難しい面が多く、人間に近い実用的な評価アルゴリズムを得るにはまだ課題が多い。

  3. 詰将棋問題生成アルゴリズム (電通大 川上)
    解答プログラムが進歩し、超長編詰将棋も解けるようになったことで、研究者の関心は詰将棋の創作に移っていった。
    1995年3月のCSA例会で、電通大の野下先生より報告。
    「卒業研究でコンピュータによる詰将棋の創作を行った。ランダムに駒を配置し、完全作を探索した。不要駒の除去を工夫した。2題の完全作を得た」
    2題とも7手詰で、妙手もほとんどないが、余詰はない。

  4. 逆算法による詰め将棋問題の生成 (電総研・松原、東工大・広瀬)
    1996年3月のCSA例会で松原先生より紹介。
    ・詰め上がり局面を人間が作ってから、逆算して問題を作成する。
    ・問題を選ぶ評価には松原、小山氏らが考案した項目を使用。

  5. 順算法による詰め将棋問題の作成 (電通大・野下、石崎、渥美)
    同じく1996年3月のCSA例会で野下先生より紹介。
    ・駒の配置に制限を設けてからランダムに問題を作る方法。
    ・問題を選ぶ評価基準として、野下氏の詰め将棋プログラムT2が解くために探索したノード数の多いものを選んだ。

  6. 人間の詰将棋創作法
    上記の例会で、加藤より人間が詰将棋を創作するときの方法を説明
    ・順算法(正算法):初形曲詰、実戦型などに向く
    ・逆算法:あぶり出し曲詰、煙詰などに向く
    ・手順法:中心となる詰手順を先に作り、それを成立させる配置を作る。趣向詰、構想作、手筋問題に向く

  7. 詰め将棋問題の自動生成について (電通大・野下)
    1996年9月GPWで発表。5の研究の展開。駒を置く範囲、駒数、先手後手の確率など、生成条件を指定して詰将棋を自動生成する。生成した15手から19手の詰将棋12題を紹介。単にランダムに生成するだけではなく、いったん生成した問題を少し変更して改良する方式で、長い手数の問題を生成する効率をアップしている。
    ちなみに、このTsume-Shogi Makerで生成した詰将棋の作品集が作成されている。これはおそらく唯一のコンピュータ創作詰将棋作品集だろう。

  8. 逆算法による詰め将棋の自動創作 (東工大・広瀬、NTT・伊藤、電総研・松原)
    同じく1996年9月GPWで発表。4の研究の展開。単純に逆算すると探索空間が爆発的に大きくなるが、不詰・余詰の検査でかなり削減でき、評価を考慮することで更に削減できる。例えば、短編では評価を落とす可能性が高い駒取りを生成しないなど。9手までの詰将棋百数十題を創作。あぶり出し曲詰も創作した。

  9. 裸玉詰め将棋問題の体系的評価 (NTT・小山)
    1997年10月のGPWで発表。1八玉の裸玉を体系的に評価、新たな完全作を発見した。当時のプログラムの解答能力の限界と、無理に詰・不詰を結論付けてしまったため、現在ではいくつか誤りも見つかっている。「コンピュータ将棋の進歩5」で岡村さんによる最近の裸玉研究が解説されている。

  10. 詰将棋の3×3金銀図式の数え上げ (電通大・野下、飯田)
    同じく1997年10月のGPWで発表。全検して完全作567題(7手以上)を生成した。15手と17手の17題と、19手以上で軽微な余詰のある7題を紹介。

  11. 逆算法での詰将棋創作
    1998年1月、3月のCSA例会で松原先生より紹介。
    ・村瀬さんと逆算による創作の研究を行っている。23桂24桂33桂34桂/11玉の詰め上がりとなる17手詰が17題あった。
    ・長手数を狙っている。
    純四桂詰の(飛角香を使わないで)16手逆算、と金図式の(歩ととのみで)14手逆算の図を紹介。

  12. 逆算式創作支援システムについて
    1999年3月のCSA例会で、山田剛さんより紹介。
    ・詰将棋創作支援システム。
    ・逆算と検討を自動的に行い、出力された候補から人が選択する。
    ・検討には証明数と反証数による反復深化法を利用。
    ・1手逆算すると、数十~200局面出現するが、検討は10分以内に終わる。
    ・29手の作品ができた。
    6月の第1回ゲーム情報学研究会で発表されている。

ソフトが作品を創作する時代
2005年11月7日~、2ちゃんねるの【詰将棋】これが神局だ!!! その2で、コンピュータによる詰将棋創作の話題
「指し将棋の世界では、コンピュータソフトの進化が注目を集めていますが、詰将棋の世界でソフトが作品を創作する時代は将来やってくるのでしょうか? 現在でも作図家が自作の完全検討にソフトの力を借りることはあると思いますが、創作の助手ではなく、主役の座に就くことができるか、興味深いところです。以前、ゲームセンターで詰将棋をランダムに生成、出題するゲームがありましたが、飾り駒あり、妙手なし、余詰、不詰ありで、とても「作品」と呼べるレベルではありませんでした。  」
「完全に人間の手を離れて、という段階に行くかはさておき、ほとんどをPCの力に頼っての作図であればすでにそれに近いことをしている人は多いかと。底の知れた作品になりますけどね。」
「10年ほど前に自動創作の作品が詰パラのヤン詰で3題出題され、どれも割と好評だった。
↓はそのうちの一題。 ・・・」

| | コメント (0) | トラックバック (0)

将棋ソフトでの詰将棋解答

[2006年1月28日最終更新]
詰将棋パラダイス2005年8月号の読書サロンに、小川悦勇さんがソフトの解答能力が高くなってきて詰将棋が崩壊するのでは、と問題提起している。近代将棋9月号の力だめし詰将棋7月号出題の解説を見ると、1番の金子義隆さんの作品は柿木将棋が誤解する作品だったようで、その月の全題正解者がわずか3名というのは、かなりの人がソフト解答をしていることを推測させる。果たして詰将棋はソフトに制覇されて終焉のときを迎えるのか。みなさんはどう思われますか。

関連情報: コンピュータ将棋2012  2011  将棋ソフト・コンピュータ将棋


変同駒余らず
2006年1月27日、詰将棋天旗雑記のページ
「「変同あれこれ」の続編を書こうとして、変同についていろいろ考えている時に「変同駒余らず」の実例を見ました。近将3月号の「力だめし詰将棋 1月号 出題 解答解説」によりますと、1番IMさん作25手詰の8手目から変化同手数駒余らずがあり、2番KTさん作25手詰の10手目から変化同手数駒余らずがある ものです。 ・・・」

TETSU: 近代将棋2006年1月号の力だめし詰将棋で、2題に同手数駒余らずの変化があり、両方とも投稿原稿に書かれていなかったとのこと。変化同手数はルール上は問題ないが、同手数変化は作意と同格なので、それを含めて作品として評価される。したがって、作家は同手数変化は作意と同様に気を使って創作するものだ。今回 の2題はいずれも合駒の変化が同手数になるもので、解答者なら必ず読まされる手順。この順を作者も選題した編集部も見落としたとすると、出題側がチェック をコンピュータに丸投げしている構図が見えてくる。コンピュータは便利だが道具であって、神様ではない。何をしてくれ、何はしてくれないかを理解して、使 いこなすことが重要だ。とはいえ、便利になるのは良いことなので、将棋ソフトには余詰チェックと同様に変化同手数、変化長手数のチェック機能の搭載を期待したい。

昨今の詰将棋事情
2005年11月5日、詰将棋パラダイス掲示板で、北の勇者さん
「・・・ 昔、読者サロンで貴重なご意見を言われておられる方がいました。確か、「コン君の○○秒で解けました」は止めましょう、詰将棋を解いてくれる「人」は神様です。コンピュータで解かれると作家もやる気も失い、また、プログラムを変えれば作図も可能となるでしょう、のようなご意見だったと思います。私も、何作か詰将棋を作っておりますが、正直なところ投稿しようという気にはなりません。また、昔では、考えられないような傑作もコンピュータを使って出来上がっていますが、どんな訳か感動をおぼえません(作家の方に申し訳ないですね。作品を否定している訳ではございません) 毎月、詰パラの到着を楽しみにしておりましたが、毎月「コンピュータ」という文字を見なかった月はありませんでした。こんな気持ちで購入しても致し方ないので退会させていただきました。 ・・・」
東の愚者さん、西の愚者さん、管理人さんよりコメントあり、詰将棋パラダイス掲示板で参照されたい。

TETSU: コンピュータの進歩で、詰将棋の楽しみ方が変わって来つつある。これまでより楽しめるようになった人がいる一方で、これまでの楽しみが阻害される人もいる。コンピュータが更に進歩したとき、詰将棋は発展するのか、終焉のときを迎えるのか。

「コン君の実力」
2005年10月3日、同じく詰パラ10月号、読者サロンの今川健一さんの文章。8月出題作品に7名のコン君から回答あり、出題作には早詰があったのだが、この早詰を最初に答えたソフトはいなかった。なぜだろうという話。またソフト解答している人にひとこと。

 ・・・ 最後にコン君を使って解答している人への、ご注意。
 コン君に解いてもらって詰将棋鑑賞、これも一つの趣味です。
 文明の利器を使って、詰将棋益々発展、このように私は思いたいです。
 コン君は時々、いや、しばしば、誤答します。コン君はいつも正確とは限りません。コン君の解答を盤上に並べて鑑賞、そして、もう一度調べましょう。 ・・・

TETSU: 詰将棋ソフトの解図方式は、大きく2つに分けられる。
一つは手数の少ない順に全ての手を読んで行く方式(柿木だと短手数用)
一つは詰みそうな手(受方は詰まなそうな手)から順に読んで行く方式(柿木だと長手数用)
前者だと、早詰があれば、必ず先に検出する。しかし全部の手を読むので長手数の作品は時間的にほとんど解けない。
後者は、詰方の手は全部は読まないので、早詰を見逃したり、変化別詰を答えることがある。その代わり長手数でも短時間に解けることが多い。正解を見つけるため、変化別詰のチェックや余詰検討の機能が用意されていることが多い。
8月の問題は49手と長いので、コン君は後者で解いていると思われる。そのため早詰より作意が先に見つけられ、余詰検討で早詰が見つかったのだろう。
なお、森田進二さんより、更に早く解けた、との連絡があったので紹介しておく。
Pentium4 2.4BGHz 脊尾参2 V2.10 レベル25(660MB) 変別浅く : 21秒
Pentium4 2.4BGHz 柿木617 1672MB 長手数用 変別17手 : 6分31秒
脊尾参のバージョンが私のより新しいので速くなっているのかもしれない。 

3つの疑問
2005年10月3日、TETSU
詰将棋パラダイス10月号が到着。読者サロンの川崎弘さんの「3つの疑問」を読む。6月号やさしい大学のCOOOさんの作品、9月 号の解説によると、39手目「59香に58角合以下無理矢理51手で詰めた解答が数通ありました ・・・ 角合自体が無駄合と判定できます。・・・」とあり、川崎さんは 1.柿木6/7は58角合を答える 2.大学レベルの人はすぐ無駄合と分かる ことから、この数通の解答は「解図ソフトを使った解答ではないのか?」という疑いを生じさせる、という。これはおそらく、その通りだろうし、58角合をしないソフト(柿木8など)もあるので実際のソフト解答はもっと多いことが推測される。やはり、もう、解答競争は解答選手権や詰-1グランプリのように集まってしなければ成り立たなくなっているのだろう。

「ソフト解答」の影響
2005年8月8日、勝手に将棋トピックスで、「ソフト解答」の影響 (トラックバック)
  ・詰将棋メモ: 将棋ソフトでの詰将棋解答
「雑誌で出題される詰将棋の解答を送る際に、将棋ソフトでカンニングをする人が増えているのではないかという指摘。たしかに、ソフトが変化を間違えるような詰将棋で誤解が増える現象がときどき見受けられます。(将棋ソフトは詰みを見つけるのは得意ですが、様々な受け方のうちで最善の手順を確実に選ぶことはまだまだ難しい状況です。)
将棋ソフトの発展は詰将棋創作に大きく貢献してきましたが、他方で詰将棋の解答競争が成り立たなくなる可能性が現実のものとなりつつあります。しかし、だからといって詰将棋を解くことの価値が下がるわけではありません。これからは、詰将棋を解くことそのものよりも、解いた後どう感じたかを重視するようになってくるのかもしれませんね。」

頑固一徹な老人では有りません
2005年8月8日、ボケ老人ーAさんよりコメント
「決して頑固一徹な老人では有りません、”老いては子に従え”詰棋界も変わってきています。TETSUさんの言われるとうり、これからも”将棋ソフト”は上を上を目指していくでしょう。其の流れをいかに詰棋界にむすびつけるか?それがこれからの問題でしょう。
 B-老人え、将棋盤の使用とコン君の使用時間は、今のところ 6:4位です」

ボケ老人Bの独り言
2005年8月8日、今川健一さんよりコメント
「間もなく70才になる、ボケかけた老人の独り言。
 浮気性の私は、この年齢になるまでに、種々の趣味(道楽)に填りました。その中で、一番長続きしているのが、詰将棋。「旧パラ」、「風ぐるま」から現在まで、付かず、離れず、飽きもせず、本当に長いお付き合いです。
 詰パラ8月号に小川さんとの対話が記載され、多少は詰棋人の話題になったようですね。その記事の中で、付録のアンケートを提案したのは、私です。8日現在で5名の方から、ご回答を頂いていますが、皆さんのコン君は、極めて優秀、高性能、そして、たぶん高価です。ちなみに、私のコン君はFUJITSUのFMV DESKPOWR CVⅢ33Lで、息子のお古。新しい高性能のコン君は、年金生活では、手が出ない。使用ソフトは、最近メール友達から頂戴した柿木将棋Ⅷ。この古い機種では、小川さんの「ヘ」は解けない。(私は短気、20分以上は待てない。時間をかけても、解けないかも。20分以内と書いた理由です。)
 私が柿木将棋を使用するのは、詰将棋を解かせるよりは、その機能の一つ「詰将棋データベース」を使うため。暇に任せて詰将棋を解き、私製のデータベースを作っています。データ入力の時には、柿木将棋の手を借りる。ときおりは、柿木君と意見が合わない。「?」です。
 近将の金子作も、メール友達の小川さんと誤答が多いのではと会話していたら、予想通りの結果でした。8月でいえば、短大の土屋作も将棋世界の妻木作も、私のコン君は間違える。アンケートご回答のコン君にもこの件の調査をお願いしたら、その答もいろいろで、興味津々。
 「風と共に去りぬ」、「戦争と平和」を読破した人は、この作品を映画で観た人より、はるかに少ないと思います。それでも、作品の良さ、素晴らしさは、伝わったでしょう。某大学で女子大生が、「風と共に去りぬ」の感想を求められ、”ビビアン・リーと クラーク・ゲイブルのキスシーンが素晴らしかった。” 、こんな笑話もありますね。
 ソフトに解かせて解答、鑑賞。人それぞれ、それも趣味。こんなことに、目くじらを立ててはダメ。ソフトのお陰で解答者、鑑賞者増加。詰将棋界、益々発展。そう思う昨今です。
 最後に質問です。最近、あなたは、将棋盤駒使用時間とコン君使用の時間と、どちらが多いですか? 私は半々くらいかな。」

TETSU: 私は将棋盤駒は使ってないので0:10ですね。ちなみに付録アンケートは脊尾参レベル25(672MB)で44秒(athlon64 3500+)でした。

作意手順を見つけ出すのは難しい
2005年8月8日、高橋@謎電さんよりコメント
「おじゃまします。
>金子義隆さんの作品は柿木将棋が誤解する作品だったようで
純粋に作意手順を見つけ出す為のアルゴリズムを作るのは、極めて難しいですね。市販・フリーに限らず、作意を正しく見つけ出せるものは、現時点では存在しませんし、将来も「決定版」といえるプログラムは、計算機が時の名人に勝つ日が来てすら現れていないと思います。
例えば、玉方に同一手数で詰められる応じ方が複数あって、作意の応手なら当然余詰なし、それ以外は余詰がある、というような問題は(確率的に)誤答を(今のプログラムは)起こしやすいですよ。
また、それ以外でも駒余りがない方が当然作意ですが、駒余りになる応じ方を解としたりするのは未だに時々ある話で、このあたりの完全な対処はプログラムを作る側にとって簡単ではないわけです。場合によっては解図時間を非常に多く必要としますので。ですので、
>B-間もなく、詰将棋解答はコン君の一人舞台になるでしょう。
その日は簡単には来ないと見てます。例えばあぶりだしだと、絵図的な認識も必要になるので、(不可能とは言いませんが)極めて解決が難しいでしょう。
>ソフトの解答能力が高くなってきて詰将棋が崩壊するのでは、と問題提起している。
対策という言い方も変ですが、計算機を使っても作意解が得難い問題、つまりは人間でなければ正しい解手順を得にくい詰物を作る、というのがこれからの課題になるかもしれません。人間の盲点だけでなく、「計算機(手順組立アルゴリズム)の盲点を突く」というのも詰将棋作家の方にとっては新しいテーマになり得るのではないでしょうか。」

ソフトは詰棋界にプラスかマイナスか
2005年8月7日、TETSU
私は学生のころ詰将棋を創作してたが、就職して忙しくなってしばらく離れていた。それが復活できたのは、検討に使えるレベルのソフトが登場したおかげである。ソフトがなければ、最近の創作もおもちゃ箱もなかったわけで、私個人にははっきりプラスだったといえる。
私は棋力が低いので、詰パラだと幼稚園ぐらいまでしか解かない。それ以上は3か月後に解説が発表されるのを待つしかなかったわけだが、ソフトがでてきてからは解答も変化紛れもソフトで調べられるようになり、解説を読む前に自分で鑑賞できるようになった。これも大きなプラス。このあたりの事情は多くの人に共通だと思うので、詰棋界としてもプラス要因と考えてよいだろう。
一方マイナス面は、解答競争の崩壊であろう。誰でもソフトで簡単に全題正解できるのだから、解答競争は成り立たない。今後は解いたことそのものではなく、鑑賞に比重が移っていくことになるだろう。表彰も、今月の優秀短評、半期短評賞、最優秀鑑賞者、という形に変わっていく。これは案外プラスの面もあるかもしれない。
いずれにしてもソフトの進歩は止まらないので、プラスになるように詰棋界が変わるしかないと思うのである。

おもちゃ箱では
2005年8月7日、TETSU
おもちゃ箱では、解答よりは鑑賞を主な目的に詰将棋を出題しています。
解答にソフトを使うのはかまいませんが、できるだけ鑑賞して感想(短評)を記述していただくようお願いします。
ただ、解くこと自体、大きな楽しみですし、ある程度解いてみないと鑑賞しにくい問題もありますから、まずは自力で解いてみることをお勧めします。

金子義隆氏作・解説より
近代将棋2005年9月号力だめし詰将棋、7月号出題の解説(柳田明さん)
「・・・ 柿木将棋で解くと2手目25銀合と10手目24角合が入れ替わった答えが出てくる。更に検索すると25銀合には23銀成で余詰と出るが、これはその答えが変化手順だと自ら証明しているだけ。作者は便箋3枚に詳細な変化紛れ記入しておられる。機械を使っても読み負けては恥ずかしいというものでしょう。 ・・・」

ボケ老人の会話
詰将棋パラダイス2005年8月号読者サロンで、小川悦勇さん

 A-小川悦勇 B-今川健一
A-おもちゃ箱の「超難解詰将棋」を見ましたか? コンピュータによる詰将棋の解答です。凄いことですね。詰将棋の崩壊は、案外「ソフト」の解答力から来るかもしれません。作家は自作を考えてもらうことに、喜びを感じます。それがボタン1つで終わりでは創作意欲は湧いてきません。コンピュータを否定するわけではありませんが、考える楽しさを大切にしたいものです。
B-間もなく、詰将棋解答はコン君の一人舞台になるでしょう。ただ、創作に関しては、まだ大丈夫。コン君は写真は撮せても芸術的な絵は描けないでしょう。そしてコン君は解答者にはなれても鑑賞者にはなれません。HP等を見ていると、多数の詰将棋創作者は創作過程で、コン君に検討をお願いしています。創り手が使用して、解答者が使用するのはダメとは、おかしな話です。・・・
 (中略)
A-解答者や鑑賞者がいなくなるのでしょうか? 作家は? 危ない、危ない。
C-(天の声)そんなに詰棋界の将来を悲観することは有りません。たとえ解答は抜きにしても、山田修司氏や柳田明氏の様な、優れた鑑賞者や解説陣が数多く、残るでしょう。詰棋界は不滅を信じましょう。

| | コメント (3) | トラックバック (1)

コンピュータ向け超難解詰将棋作品集

[2010年1月9日最終更新]

脊尾詰でミクロコスモスが解け、長井詰でほとんどの長編が解けてしまってから、詰将棋プログラムの研究は新たな展開がほとんどない。そこで、コンピュータに挑戦!ということで、コンピュータ向けのベンチマークとして超難解詰将棋作品集を作ってみようと思いついた。10作ぐらい揃えたいので超難解作をご存知の方はコメントやトラックバック、またはおもちゃ箱掲示板で教えてください。また、これらの作品がコンピュータで解けた場合は、プログラム、環境(CPUやメモリ設定)、時間をレポートしていただければ、随時掲載したいと思います。

  作品集はこちら(現在13作品) ===> コンピュータ向け超難解詰将棋作品集

関連情報: コンピュータ将棋2012  2011  将棋ソフト・コンピュータ将棋
  コンピュータで詰将棋  コンピュータ詰将棋の課題  コンピュータによる詰将棋創作
  超長編作品のプログラムによる解図と検討  裸玉の検証


おめでとうございます!(o^-^o)
2010年1月8日、岡部文洋さんよりコメント
「特に「明日香」については個人的に過去何度も挑戦し、無念な思いをした経験があり、現存中最難問か...と感じていました。それにしても探索数800億越えとはすごいですね。なにがこの問題をこれほど難解にしたのか興味のあるところです。」

大きな展開ですね
2010年1月8日、岡村孝雄さんよりコメント
「大きな展開ですね。解の厳密性は別として、全て詰ますことができたというのは素晴らしいと思います。新バージョンでも確認中とのこと、同一のマシンとプログラムで問題集の全13題を解いたデータが初めて揃いそうですので、ぜひ見たいですね。」

ここにある問題集をすべて解きました
2010年1月6日、岸本章宏さんよりコメント
「明けましておめでとうございます。最近、詰将棋のプログラムを作っており、ここにある問題集をすべて解きましたので、ご連絡いたします。いくつかの問題に関する数値は、下の方にあります。ただし、詰みであることの保証はできるのですが、ハッシュのGCがかなり起こりますので、無駄合い等の手順は正しく返すことはできません。難しかった問題は、明日香と驚愕の荒野で、かなりの日数がかかりました。また、300手以上の長手数もほとんど試したのですが、これらもすべて解けていると思います。アトランティスも解けました。まだ、試していないものとしては、「2009年8月2日 広沢「古時計」「古時計II」の橋本修正案追加」と書かれている修正図です(修正なしのものは確認済みであり、不詰をきちんと返しました)。旧バージョンですべての難問は解いているのですが、年末頃に改良したバージョンでも現在解けるかどうか確認中です。このため、申し訳ありませんが、数値は古いバージョンと新しいバージョンの二つが混ざっています。また、複数のマシン環境で実験したので、マシン環境も混ざっています。なお、このバージョンは、東大将棋無双IIには取り込まれていません。今回開発した手法は、何人かの方にはすでに説明しているのですが、論文などでそのうちに発表する予定です。 ・・・」

TETSU: すべて解けたとはすばらしい。どのような手法で改善されたのか、発表が待たれます。それにしても「驚愕の曠野」が335925秒、約4日間とは、やはり超弩級の作品ですね。

No.13(29手詰)も解けました
2009年9月23日、かずの心の贅肉で、超難解詰将棋作品集
コンピュータ向け超難解詰将棋作品集No.13(29手詰)も解けました。
動作環境はAthlon64X2 4600+(2.4GHz)/RAM:2GB/WindowsXP(32bit)。
詰将棋用メモリ設定を768MB。
実行時間: 35366.6秒: 探索節点数: 2872680807
9時間49分27秒 詰手数は79手(手順(kif))。 ・・・」

木星の旅・三重鋸が詰んだ!
2009年9月22日、かずの心の贅肉で、木星の旅が詰んだ!
「詰ませたのはもちろん(?)新・東大将棋 無双II!
動作環境はAthlon64X2 4600+(2.4GHz)/RAM:2GB/WindowsXP(32bit)。
詰将棋用メモリ設定を1024MB。
実行時間: 21839.0秒: 探索節点数: 2211318923
ってことで、6時間3分59秒で22億局面探索です。詰手数は449手手順(kif)。詰み上がりを見ると駒が余っていますね…。 ・・・ No.12も解けました。
実行時間: 14863.3秒: 探索節点数: 1666221961
ってことで4時間7分43秒 16億6622万局面探索、335手まで手順(kif)。これも詰み上がりを見ると駒が余っています…。 ・・・」

Re: 新桃花源: 続報
2007年1月15日、コンピュータ将棋や囲碁の掲示板で、山田 剛@対局サーバ担当さん
「・・・ 期待どおり、岡部さんに解いていただけました。 ・・・ 岡部さんには、CSA例会でも成果発表していただきました。ありがとうございました。 ・・・」
2007年1月15日、山下さん
「東大6で24時間ぐらい走らせたのですがだめでした。岡部さんのプログラムはミクロコスモスを900秒ぐらいで解いてしまうそうですが それが9時間かかった、とのことですから、かなり(コンピュータ的には?)難解な問題なんでしょうね。」

「新桃花源」がコンピュータで解かれたらしい
2007年1月13日、囲碁・将棋ソフト開発日誌で、世界で2番目に長い詰め将棋「新桃花源」がコンピュータで解かれたらしい
詰将棋メモ: コンピュータ向け超難解詰将棋作品集によると、少し前に紹介した「新桃花源」をコンピュータが解いたそうだ。解答したソフトの製作者は岡部文洋さんという方で、過去にGPWで詰め将棋関連の発表をされていたらしい。そのレポートの中でも、9時間33分という消費時間が作品の複雑さを物語っている気がする。 ・・・」

「新桃花源」 解図レポート
2007年1月6日、岡部文洋さん
 岡部文洋です。ご無沙汰しております。超難解作品集で「新桃花源」のプログラム解図募集を拝見しましたのでレポートいたします。
 9月初旬、ネットの書き込み等を見て「新桃花源」の発表を知りました。早速「詰めパラ8月号」を取り寄せ、一晩パソコンを走らせたことがあります。その際は約9億局面探索したのですが解けず、途中でPC電源を切りました
 近日 山田剛さんからのネット上での要請を知り、結論を出すべくGPW当時のソース(BNS:ハッシュ700万)で再度解図を試みました。マシン環境は CPU Core2DuoE6600、メモリ1GBです。
 結果は1229手詰め、消費時間9時間33分、探索局面数15億8543万でした。これまで解けた問題のなかではもっとも探索量の多いものとなりました。
 以下はプログラム出力ログの最後の部分です。参考まで (尚、使用プログラムは無駄な合い駒を贅沢に使いきって詰めてしまうこともあり必ずしも作意手順にはなりません。)

---------------------------------------------------------------------------
削除前 7340033 残存 3469226 証明 452148 削除閾値 10 探索局面数 1582822796
hash_clear abn = 26 obn = 173 sh = 2135
削除前 7340033 残存 3469756 証明 452301 削除閾値 10 探索局面数 1585124418
詰みです 1229手詰め
所持 3926651 探索局面数 1585429706
消費時間 = 34355.781000sec
手数: 0
手番:先手
先手玉 9 9  後手玉 4 8
後手:0 0 0 0 0 0 0
+---------------------------+
|v歩 ・ ・^圭 ・ ・ ・v金 ・|
|^歩 ・ ・^飛 ・ ・ ・vと^歩|
|v金 ・ ・ ・^馬v桂v歩^歩 ・|
|v香^歩^歩 ・vと ・ ・ ・v歩|
|^杏v桂v桂^銀 ・ ・^杏^銀vと|
|^金^と ・v香^馬v歩^と ・vと|
| ・ ・ ・v歩v歩 ・^歩 ・v金|
| ・ ・ ・ ・ ・ ・ ・ ・ ・|
| ・ ・ ・ ・v王^銀^飛 ・v銀|
+---------------------------+
先手:0 0 0 0 0 0 0
1   ▲4八銀 (49) 0 32767 1228
INPUT?

Re: 新桃花源: 続報
2006年12月24日、コンピュータ将棋や囲碁の掲示板で、山田 剛@対局サーバ担当さん
「・・・ 載りました。 http://toybox.tea-nifty.com/memo/2006/07/post_9839.html これがコンピュータで解けた、との報告をお待ちしたいと思います。たとえば、GPW2005にて岡部文洋さんが発表されたBNSであれば、解けるのではないかと思います。 ・・・」

添川公司さん「新桃花源」
2006年12月23日、TETSU
詰パラ2006年8月号で出題された史上第2位の長手数作品(1205手)、添川公司さんの「新桃花源」、12月号で解答が発表されたので、超難解詰将棋作品集に追加した。私も出題前に検討を依頼されたのだが、柿木将棋VIII、脊尾参など市販ソフトでは解けず苦労した。本作品についての情報は添川公司さん「新桃花源」を参照されたい。

チャンピオン戦37手
2006年4月10日、State of the Digital Shogics [最先端計数将棋学]で、詰将棋解答選手権 (3)
日本チェス・プロブレム協会 の詰将棋解答選手権が06/03/21に行われた。第3回 の問題セットが公開されたので、毎度のことながら謎電でチャレンジしてみることにした。今回の問題セットは、チャンピオン戦(10局)、一般戦(6局)、初級戦(10局)と階級が3つになったようだ。一般戦と初級戦は計算機将棋的に簡単過ぎるので、チャンピオン戦の10局 のみ解図してみた。 ・・・」
2006年4月19日、小宮日記で、詰め将棋の改良
「・・・ 謎電が約70秒かけて解いた日本チェスプロブレム協会のチャンピオン戦のひとつの37手詰めの問題が解けません。 ・・・」
2006年4月19日、State of the Digital Shogics [最先端計数将棋学]で、ネタが転がってた
「・・・ 小宮日記 (06/04/19)
>謎電あたりの高速なソフトだと、PN-DNをやってるんでしょうねえ。
謎電の詰探索アルゴリズムは現状、古典的な「深さに基づく反復深化」でしかない。しかも王手全幅・応手全幅。当然ながらAND-OR探索なので応手については、ある手が詰まない限り別の手を読まない。 ・・・
> 「成って詰まないなら、成らない手も詰まないので指さない」とか柿木さんのアルゴリズムもある
初耳だが、柿木師匠そんなこと言ってましたっけ!? ・・・」
2006年4月19日、小宮日記で上記にレス
「・・・ すみません。かなり間違って書いてました。 「成って王手をかけ、それが取られて詰まないとき、不成りの手を読まない(取られれば同じ)」 でした(サイエンス社「コンピュータ将棋」P93)」
2006年5月1日、小宮日記で、解けなかった37手詰めが解けた!(^-^)/
「・・・ 探索数自体9億です(^^;;;;;; 謎電は1億2千万(127,707,259)ですから、約8倍も無駄な計算をしていることになります。 ・・・」
2006年5月1日、State of the Digital Shogics [最先端計数将棋学]で、ネタが転がってた(3)  小宮日記(06/05/01) > 解けなかった37手詰めが解けた!(^-^)/
  > #激指2に高速モードで解かせたら、あっというまに解いた orz
「 このあたりにコメントし出すとキリがなくなるのだが少々。謎電の詰・必至解図・終盤解析は、可能な限り読み落としなし、また攻方最短(受方最長)で妥当な手順解を出すことをコンセプトにしている。 ・・・ 柿木将棋の解図能力は、速度ではなく出力解の妥当性の高さに大きな意味があると思う。 ・・・」

ネタが転がってた(2)
2006年4月19日、State of the Digital Shogics [最先端計数将棋学]で、ネタが転がってた(2)
(2005年8月6日の岩田俊二さんのコメント 「・・・ コンピュータは全検をしているのでか? 場合の数でいえば,全検は不可能と思えるのですが・・・。全検でなければ,ソフトの隙を狙う手がありそうな気がします。」 について)
「・・・ 置換表が効きやすく、実質的な探索幅が狭い詰物は計算機にとって難解な部類に入らない。計算機の隙を突くには、手数が長いというだけでなく「玉方がどう応じても王手の候補が沢山ある」ことで短時間では解けなくし、玉方作意手の外に多くの余詰手順を含ませておくことで作意解を得られ難いようにすることが方法の一つとして考えられる。その上で完全作を目指すとなれば、作り手側も相当苦労するのではないかと思われる。謎電の作者としては、是非、そのような作品を作って頂きたいと願うところである(嫌味ではなくマジで)。 ・・・」

詰むことを証明できるまでの探索局面数
2005年8月19日、岡村孝雄さんよりコメント
「3八裸玉の探索局面数「7億」という数字、「1億と3手読む」という将棋界の名セリフをふと思い出しますね。さて、万が一にも不詰があってはなりませんし、その責任を持つのはコンピュータではなくあくまでも作者ということで、投稿前の検討の際には変化手順を盤にも並べて全て確認してきました。棋譜ファイルに転記した手数から推定すると、3八裸玉で5桁(数万手)、「驚愕の曠野」改良図では6桁(それぞれ、余詰検討で並べた局面は別勘定)と思われますが、今後のアルゴリズムの進歩で「詰むことを証明できるまでの探索局面数」がどこまで減るのかという興味も湧くところです。」
探索局面数を減らすには、探索途中局面での詰む確率の評価関数がキーになりそう。データベース10万局の詰将棋を分析して、統計的に評価関数を作れないだろうか。

Re.岩田 俊二 作
2005年8月6日、高橋恭嗣さんよりコメント
「37手詰め解かせていただきました。遠角では以前あった手筋ですが、これを馬鋸にしたのは初めてではないのですか? ちょっともったいないような発表の仕方ですね。もう、詰めパラなどには投稿できないのでしょうか? ちなみに私のコンピュータ(P4・3.2Gh、1Gb、柿木5)は、14秒でした。」
手順も出してないし、「発表」として掲載したものではないので、詰パラへの投稿は問題なし。
2005年8月6日、岩田俊二さんよりコメント
「髙橋さんへ 新手筋でも,序も捌きもない作品は,詰パラでは酷評を受けます。この作品の詰め上がりの残骸を見ると,とても投稿できません。これをヒントに,誰かが良い作品を創ってほしいです。」

コンピュータは,人間の創造性を超えることはできない
2005年8月5日、岩田俊二さんよりコメント
「3月末に退職後,20数年ぶりに積みっぱなしの詰パラを読んだら,人間がコンピュータに押され気味とのこと。そんなことはないはずと,自作(未発表)を解かせたら,東大将棋も激指もギブアップ。コンピュータは,人間の創造性を超えることはできないと思う。・・・たぶん。図を表示する知識がないので、誰か助けて!
駒の配置
 攻方:1九桂 2五飛 2七歩 3六龍 4七馬 4八桂 4九歩 5八歩 6九香
 王方:1六金 1八香 2八王 3九角 5九と
 持駒:なし
手数:37手詰」
柿木将棋VIIIに解かせたら4秒、脊尾参だと0秒で37手解。人間向きにはおもしろい狙いだが、最近のコンピュータは楽々クリア。
2005年8月6日、岩田俊二さんよりコメント
「何日もかかって作った作品が,4秒と0秒で解かれてしまいました。コンピュータがこんなに進化しているとは,知りませんでした。ところで,コンピュータ は全検をしているのでか? 場合の数でいえば,全検は不可能と思えるのですが・・・。全検でなければ,ソフトの隙を狙う手がありそうな気がします。」

有吉澄男氏の「チップイン」
2005年6月5日、TETSU
岡村さん、岡部さんの報告があったので、私もちょっとやってみた。
・解図報告-3 2005年6月5日 TETSU 脊尾参Ver.2.4
 Athlon64 3500+/Level 25(RAM 消費は約 670MB)
 解答時間 5分16秒 121手 変化別詰解
ちなみに、柿木将棋8(652MB+3MB)では10時間かけても解けなかった。

難解作品集へ挑戦中
2005年5月26日、岡部文洋さんより
「難解作品集に楽しく挑戦させていただいてます。近況ですがその後2題解図できました。
【環境】 CPU Athlon64 +3400  メモリ 1GB
  プログラム 自作  ハッシュ 盤面数350万
7、岡村孝雄さん「3八裸玉」
探索局面数 716137130  解図時間 13717.344秒  手数 77手詰め(変化長別)
8、有吉澄男さん「チップイン」
探索局面数 661388853  解図時間 15017.5秒  手数 237手詰め(変化長別)
相変わらず玉方の無駄合いに対し、取った持ち駒を使い切って贅沢に詰める手順を手数にカウントしてしまいますが玉方に作為の着手を選択させて局面を進めれば作為詰めが再現されるようです。他の6題については歯が立たない状況がつづいてます。」

有吉澄男氏の「チップイン」
2005年5月22日、岡村孝雄さんより
「有吉澄男氏の「チップイン」、難解な煙詰ということで、コンピュータによる解図をテストしたことがあります。 『脊尾四』Level44(Ver.1.5、2001年10月14日、RAM 消費は約 1.2GB)で
44分51秒、詰むこと自体は確認しておりました。ただし変化別詰チェックを省いているため、最初に出てきた解は151手。この作品は、むしろ粗解の中にある別詰を探索させながら正解(作意手順、もしくは100手目15玉の同手数変化)へと精錬させていく過程が大変で、「余詰検索」と「変化別詰の検証」のコマンドを何度も繰り返す必要がありました(『脊尾四』は、最終的には変同順を2手長1駒余りの別詰で解きましたが)。その意味で、コンピュータにとっても難解な作品だと思っています。 ちなみに「44分51秒」という数字については、 CPU に Pentium3 1GHz(えらい旧型ですが)を使っておりましたので、最新の機械を使えば1/3 以内の時間で詰めることができるのではないかと推測しております。」
岡村さん、ご報告ありがとうございます。解図時間だけでなく、作意(or変化同手数)解か変別解かの情報も重要ですね。

超難解詰将棋作品集
2005年5月21日、State of the Digital Shogics [最先端計数将棋学]で、超難解詰将棋作品集 「コンピュータ向け超難解詰将棋作品集というタイトルのページが、詰将棋メモの中に最近新設されたので、ここで紹介する。詰探索アルゴリズムに自信のあるプログラマの方、必読。これは決して挑発でも嫌味でもない純粋に学究的興味の現れで、このような提起をしてくださる詰将棋作家の方がいらっしゃるというのは、非常にありがたいことだと私は思っている。実際、これは私も知りたいと思っていた。特に、それ程手数が長くない割に解図コストが極めて高い詰物に興味があり、次の2問について現在分析中。 ・・・
裸玉(5一玉・角金4銀2歩9、詰パラ2004年4月号)『驚愕の曠野』改良図
裸玉(3八玉・金4銀4桂香歩3、詰パラ2003年11月号)
なお、頭から解こうとすると、謎電ではどちらも実用時間内で解けない。 」

コンピュータが解けない詰将棋
2005年5月21日、勝手に将棋トピックスで、コンピュータが解けない詰将棋

「将棋ソフトはほとんどの詰将棋を短時間で解けるということはご存じだと思います。しかし、現実的な時間で[解けない詰将棋が]わずかながら存在します。上記ページではそんな詰将棋を募集しています。大変興味深いと思うので、ご存じの方がいらしたらTETSUさんにお知らせ下さるとありがたいです。」

メガロポリスと明日香
2005年5月21日、 岡部文洋さんよりコメント
「おもちゃ箱長編完全作(310手以上)全題解図を目指してプログラムを自作調整中です。現時点、上記完全作で解けていない問題は以下の5題のみになりました。
 1、木星の旅 2、メガロポリス(修正図) 3、赤兎馬 4、明日香 5、メタ新世界
上記問題は9億局面探索しても全くだめです。超難解作品に載っていないメガロポリス修正図と明日香について解図報告が無いのであればエントリー希望です。
 メガロポリス修正図 61手目99角に対する変化がコンピュータにも超難解。メタ新世界と通じるものがある。
 明日香 なぜか解けない。
リストの中で解けている問題は以下です。
【マシン環境】 
 CPU Athlon+3400  メモリ 1GB  プログラム 自作  ハッシュ 盤面数700万
馬詰恒司・摩利支天 「FAIRWAY」(修正図) 夢銀河 2000年3月
 探索局面数 82491905  回答時間 1977.391秒  
田島秀男 「乱」 詰パラ1999年10月
 探索局面数 288553645  回答時間 6957.594秒」
岡部さん、ご報告ありがとうございます。「FAIRWAY」と「乱」が解けるというのは優秀なプログラムですね。メガロポリスと明日香、追加しました。
2005年5月22日、補足コメント
「fairway,乱の解図手数についてですがfairway687手、乱461手でした。無駄合いした駒を使い切って長手順でつめてしまう等の問題もあり、作為手数に至っていない点補足します。」

有吉澄男氏の「チップイン」
2005年5月21日、橋本孝治さんよりコメント
「有吉澄男氏の「チップイン」(パラ2004年3月)はどうでしょう? 少なくとも私のパソコンでは解けませんでした。人間にとっても超難解ですし…。」
橋本さん、ありがとうございます。第8番として追加しました。

コンピュータ向け超難解詰将棋作品集
2005年5月21日、おもちゃ箱掲示板で、岡村孝雄さん。
「投稿者が私ということで、ご想像通り裸玉になります(苦笑) 『驚愕の曠野』改良図59手よりもさらに短手数の作品を挙げると、拙作「38玉・金4銀4桂香歩3」35手詰(詰将棋パラダイス2003年11月号)が、数年前の私の調査では解けていませんでした。発表図から「47銀、同玉」の2手を進めた「47玉・金4銀3桂香歩3」は33手詰ですが、実はこれでも……。 現在主流となっているアルゴリズムにとってかなりシビアな例題かとは思っていますが、最新のハードウェア、ソフトウェアで果たして解けるようになっているのか、あるいはどのぐらいの時間まで短縮されているのか、興味のあるところです。 http://www.ne.jp/asahi/tetsu/toybox/kenkyu/38-00441103a.htm 」
岡村さん、ありがとうございます。第7番として追加しました。


コンピュータ向け超難解詰将棋作品集
2005年5月21日、まずは、思いつくものを挙げてみる。棋譜ファイルは柿木将棋のkif形式。

  1. 岡村孝雄 「驚愕の曠野」(改良図) 詰パラ2004年4月
    kinen003a棋譜ファイル(59手)
    史上初、完全玉座裸玉 (おもちゃ箱

    わずか59手ながら、難解さは超弩級。最初4手進めた局面で出題されたが、このままの図で出題されたら、正解者はおそらくいなかったのではないか。

    ・解図報告-1 2010年1月6日 岸本章宏さん 自作プログラム(旧バージョン)
     動作環境: Intel(R) Core(TM)2 Extreme CPU Q6850  @ 3.00GHz ハッシュ2GB
     探索節点数: 45890747353 手数: 69 実行時間: 335925秒

  2. 高橋恭嗣 「木星の旅」 詰パラ2004年4月
    cho030a棋譜ファイル(411手)
    詰め将棋 上級その1 (1)命名 「木星の旅」 (高橋農園

    複雑な馬ノコで、並べても意味を理解するのが難しい。詰将棋専門誌「詰将棋パラダイス」で正解者ゼロ。

    ・解図報告-1 2009年9月22日 かずさん 新・東大将棋 無双II
     Athlon64X2 4600+(2.4GHz)/:2GB
     詰将棋用メモリ設定:1024MB
     探索節点数 2211318923 実行時間: 21839.0秒(6時間3分59秒)
     449手 無駄合+迂回+変化別詰解

  3. 馬詰恒司・摩利支天 「FAIRWAY」(修正図) 夢銀河 2000年3月
    cho014棋譜ファイル(611手)
    長手数作品 「FAIRWAY」 (おもちゃ箱

    前半の微妙な変化紛れが収束まで行かないと作意と区別つかないので、コンピュータには難問。原作は看寿賞を受賞したが不詰であった。

    ・解図報告-1 2005年5月21日 岡部文洋さん 自作プログラム
     Athlon+3400/1GB/ハッシュ 盤面数700万
     探索局面数 82491905  解答時間 1977.391秒(32分57秒)
     687手 変化別詰解

  4. 山本昭一 「メタ新世界」 詰パラ1982年7月
    cho002棋譜ファイル(941手)
    長手数作品 「メタ新世界」 (おもちゃ箱

    ミクロコスモス登場まで長手数記録作品だった。と金で取る順番の非限定が多数あることの処理がコンピュータにとって難関。

    ・解図報告-1:「コンピュータ将棋の進歩4」で長井歩さんのプログラムにより解けたとの報告あり

    ・解図報告-2 2010年1月6日 岸本章宏さん 自作プログラム(新バージョン)
     動作環境: Intel(R) Xeon(R) CPU L5410  @ 2.33GHz ハッシュ2GB
     探索節点数: 6299167751 手数: 947 実行時間: 40364 秒

  5. 山崎隆 「赤兎馬」 詰パラ1979年7月
    cho020棋譜ファイル(525手)
    長手数作品 「赤兎馬」 (おもちゃ箱

    人間が見てもややこしい、とても複雑な馬ノコ。

    ・解図報告-1:「コンピュータ将棋の進歩4」で長井歩さんのプログラムにより解けたとの報告あり

    ・解図報告-2 2010年1月6日 岸本章宏さん 自作プログラム(新バージョン)
     動作環境: Intel(R) Xeon(R) CPU L5410  @ 2.33GHz ハッシュ2GB
     探索節点数: 1427457068 手数: 527 実行時間: 9667 秒

  6. 田島秀男 「乱」 詰パラ1999年10月
    cho024棋譜ファイル(451手)
    長手数作品 「乱」 (おもちゃ箱

    これまでの詰将棋の常識を覆す飛追いベースの複雑な連取り趣向。最初からどの変化も複雑で、読み筋を絞れない。本局も詰将棋専門誌「詰将棋パラダイス」で正解者ゼロ。

    ・解図報告-1 2005年5月21日 岡部文洋さん 自作プログラム
     Athlon+3400/1GB/ハッシュ 盤面数700万
     探索局面数 288553645  解答時間 6957.594秒(1時間55分58秒)
     461手 変化別詰解

  7. 岡村孝雄 裸玉 詰パラ2003年11月 [2005年5月21日追加]
    38a棋譜ファイル(35手)
    裸玉(3八玉・金4銀4桂香歩3) (手順) (おもちゃ箱

    岡村孝雄さん 「本作は一面においては、証明数・反証数と探索の深化手法という、現代の詰将棋思考の根幹をなす部分への問題提起でもありましたので ・・・」

    ・解図報告-1 2005年5月26日 岡部文洋さん 自作プログラム
     Athlon+3400/1GB/ハッシュ 盤面数350万
     探索局面数 716137130  解答時間 13717.344秒(3時間48分37秒)
     77手 変化別詰解

  8. 有吉澄男 「チップイン」 詰パラ2004年3月 [2005年5月21日追加]
    Nankai008棋譜ファイル(111手)
    超難解詰将棋作品集 No.8 「チップイン」 (おもちゃ箱

    橋本孝治さん 「・・・ 少なくとも私のパソコンでは解けませんでした。人間にとっても超難解ですし…。」

    ・解図報告-1 2005年5月22日 岡村孝雄さん 脊尾四Ver.1.5
     Pentium3 1GHz/Level44(RAM 消費は約 1.2GB)
     解答時間 44分51秒 151手 変化別詰解
    ・解図報告-2 2005年5月26日 岡部文洋さん 自作プログラム
     Athlon+3400/1GB/ハッシュ 盤面数350万
     探索局面数 661388853  解答時間 15017.5秒(4時間10分18秒)
     237手 変化別詰解
    ・解図報告-3 2005年6月5日 TETSU 脊尾参Ver.2.4
     Athlon64 3500+/Level 25(RAM 消費は約 670MB)
     解答時間 5分16秒 121手 変化別詰解

  9. 山本昭一 「メガロポリス」修正図 怒濤 2003年12月 [2005年5月21日追加]
    Cho021棋譜ファイル(515手)
    長手数作品 「メガロポリス」 (おもちゃ箱

    岡部文洋さん 「61手目99角に対する変化がコンピュータにも超難解。メタ新世界と通じるものがある。」

    ・解図報告-1 2010年1月6日 岸本章宏さん 自作プログラム(新バージョン)
     動作環境: Intel(R) Xeon(R) CPU L5410  @ 2.33GHz ハッシュ2GB
     探索節点数: 4647889662 手数: 559 実行時間: 43620秒

  10. 添川公司 「明日香」 近代将棋2002年12月 [2005年5月21日追加]
    Cho009a棋譜ファイル(703手)
    長手数作品 「明日香」 (おもちゃ箱

    岡部文洋さん 「なぜか解けない。」
    1サイクルごとに1筋の往復が入る馬ノコ。人間だと1サイクル分かればあとの読みを省略できるのだが・・・

    ・解図報告-1 2010年1月6日 岸本章宏さん 自作プログラム(旧バージョン)
     動作環境: Intel(R) Core(TM)2 Extreme CPU Q6850  @ 3.00GHz ハッシュ2GB
     探索節点数: 83990970117 手数: 1097 実行時間: 571413秒

  11. 添川公司 「新桃花源」 詰パラ2006年8月 [2006年12月23日追加]
    Cho001a棋譜ファイル(1205手)
    長手数作品 「新桃花源」 (おもちゃ箱
    添川公司さん「新桃花源」 (詰将棋メモ

    「桃花源」の一手馬ノコを合駒とその消去を入れて複雑化した2分の1手馬ノコ。市販の将棋ソフトでは解けない。

    ・解図報告-1 2007年1月6日 岡部文洋さん 自作プログラム
     Core2DuoE6600/1GB/ハッシュ700万
     探索局面数 15億8543万  解答時間 9時間33分
     1229手 変化別詰解

  12. 田島秀男 詰パラ2006年12月 [2007年6月17日追加]
    Nankai012棋譜ファイル(289手)
    超難解詰将棋作品集 No.12 (おもちゃ箱
    田島秀男さん、驚異の三重ノコ (詰将棋メモ

    コンピュータに苦手の鋸引き趣向を三重に組み合わせた超難解作。詰パラ出題時の正解者は福村努さんただ一人。

    ・解図報告-1 2009年9月22日 かずさん 新・東大将棋 無双II
     Athlon64X2 4600+(2.4GHz)/:2GB
     詰将棋用メモリ設定:1024MB
     探索節点数 1666221961 実行時間: 14863.3秒:(4時間7分43秒)
     335手 迂回+変化別詰解

  13. 谷口均 詰パラ2008年12月 [2008年12月29日追加]
    Nankai013棋譜ファイル(29手)
    超難解詰将棋作品集 No.13 (おもちゃ箱
    平成20年度看寿賞 (詰将棋メモ

    解答選手権向けに創作されたがコンピュータ検討できず出題されなかった超難解作。29手という手数にも関わらず、詰パラでの出題時、正解者は僅か3名。
    作者「私の限度を超え、解答者の限度を超え?、更に超えようとした作です。・・・」
    はたしてコンピュータの限度も超えたのか。

    ・解図報告-1 2009年9月23日 かずさん 新・東大将棋 無双II
     Athlon64X2 4600+(2.4GHz)/:2GB 詰将棋用メモリ設定:768MB
     探索節点数 2872680807 実行時間: 35366.6秒(9時間49分27秒)
     79手 変化別詰解

| | コメント (16) | トラックバック (0)

GPW

[2004年12月14日最終更新]
2004年11月12日から14日、第9回 ゲームプログラミングワークショップ2004 (GPW-04)が開催されている(プログラム:PDF)。詰将棋関連の発表を紹介する。私の興味と理解で書いているので、不正確な部分もあるかもしれない。

関連情報: コンピュータ将棋2012  2011  将棋ソフト・コンピュータ将棋
 


大槻さんがGPW杯の自戦記を書かれています。
12月14日、コンピュータ将棋や囲碁の掲示板で山下さん 「しかしトップページがどこかと似てますね・・・うーむ。私のページもCSAのページのコピーなのですけど。    http://home.q00.itscom.net/otsuki/
11月29日、大槻将棋で、GPW杯2004自戦記

GPW杯の結果
11月19日、コンピュータ将棋や囲碁の掲示板で、山下さん

    11/12-14のGPWで行われたGPW杯の結果です。
    下に写真も置きました。
   +---------------+----+----+----+----+----+----+----+----+
    |対局者名    |柿|TA|奈|SP|GP|ゆ|HI|大|う|棚|勝敗|順位|
    +---------------+----+----+----+----+----+----+----+----+
    | 1.柿木将棋  |\|×|○|○|○|○|○|○|○|×| 7-2| 3|
    | 2.TACOS    |○|\|○|×|○|○|○|○|○|×| 7-2| 2|
    | 3.奈良将棋  |×|×|\|×|○|○|○|○|○|×| 5-4| 6|
    | 4.SPEAR    |×|○|○|\|○|○|○|×|○|×| 6-3| 4|
    | 5.GPS将棋   |×|×|×|×|\|×|○|×|○|×| 2-7| 8|
    | 6.ゆうちゃん |×|×|×|×|○|\|○|×|○|×| 3-6| 7|
    | 7.HIT将棋   |×|×|×|×|×|×|\|×|×|×| 0-9| 10|
    | 8.大槻将棋  |×|×|×|○|○|○|○|\|○|×| 5-4| 5|
    | 9.うさぴょん |×|×|×|×|×|×|○|×|\|×| 1-8| 9|
    |10.棚瀬(人間)|○|○|○|○|○|○|○|○|○|\| 9-0|優勝|
    +---------------+----+----+----+----+----+----+----+----+

    http://www.yss-aya.com/photo/20041114gpw/index01.html

ソフトに勝つ開発者
11月16日、勝手に将棋トピックスで、ソフトに勝つ開発者 「日々の記録11月15日付 11月12日に紹介したゲームプログラミングワークショップ2004の中でコンピュータ将棋の大会「GPW杯」が開催され、そこに人間として特別参加した棚瀬寧氏(東大将棋開発者)が全勝優勝を果たしたそうです。IS将棋(東大将棋)や激指は参加していませんでしたが、9つのソフトに全て勝つというのはなかなかできないことではないでしょうか。」

棚瀬さん全勝優勝
11月15日、日々の記録 「昨日までの3日間、毎年恒例箱根で行われるGPWに参加してきた。去年に続いて非常に楽しくかつためにもなったのだが(去年もGPS将棋の金子と話したことなどかなり実際プログラムに組み込んだ)、なんと言っても今回自分にとって印象深いのはGPW杯。将来の選手権でのLAN化の実験として去年も行われていて、その時はIS将棋で一応全勝優勝を遂げているのだが、最近ソースをごちゃごちゃいじっていてなんとなく面倒な感じがしたので今回は参加しない方針でパソコンも一番速いノートは持っていかなかった。ところが会場でなんとなく私自身が人間プレーヤーとして特別参加することに決定。相手は柿木将棋、TACOS、奈良将棋、大槻将棋、SPEAR、GPS将棋、うさぴょん、まったりゆうちゃん、HIT将棋。条件は私も含めて25分切れ負け。サーバーが時間を管理しているので、時間切れの判定は容赦なく下される。私は去年LANを組み込んだIS将棋のインターフェースを介して対局という形。で、結果はというと、私が乏しい棋力とコンピュータ将棋の弱点を知りぬいた勝負術(≒にわか穴熊党へ転向)を総動員して9-0の完全優勝!とあいなりました。 ・・・」

GPW杯2004
11月14日、本日でワークショップは終了。みなさん、お疲れ様でした。12、13の両日夜行われたコンピュータ将棋大会「GPW杯2004」は、参加者を偶数にするために参加した棚瀬さん(人間)が優勝。コンピュータもまだまだがんばらねば。

6-3 SVMによる将棋の詰みの予測とその応用
11月14日、東大の横山大作さん。
SVM(Support Vector Machine)を用いて将棋の詰み有無の予測の学習を行い、探索時間を最大6割程度削減できた。
将棋の終盤に対する研究だが、詰将棋に適用したらどうなるだろうか。データベース10万局で平均20手ぐらいとすると詰む局面が200万局面、紛れは詰まないのが原則だから、ここから詰まない局面が1000万局面以上生成できるだろう。この学習から制度の高い分類ができれば、詰将棋プログラムの探索アルゴリズムとして使える可能性があるかも。誰かやってみませんか。

ゲームプログラミングワークショップ2004
11月12日、勝手に将棋トピックスゲームプログラミングワークショップ2004。 「12日から14日まで箱根にてゲームプログラミングの研究者が集まってワークショップを行っているそうです。プログラムから将棋に関係ありそうな発表を列挙してみます。 ・・・」

DI将棋
11月12日、GPW、夜のイベントとしてコンピュータ将棋大会が行われている。その横で飯田先生に「やってみませんか」と誘われて、DI将棋に挑戦。飯田先生は研究室でのDI将棋のチャンピョンとのことで、あっさりひねられた。衝立将棋に似ているが、ちょっと感覚が違う。ネットで公開されたら流行しそう。

第9回 ゲームプログラミングワークショップ2004 (GPW-04)
11月12日、All by myselfで、第9回 ゲームプログラミングワークショップ2004 (GPW-04) 「詰将棋メモに取り上げられているのを見て、面白そうだったので暫く眺めていました。こういう分野の研究をしてみたいような、したくないような…。」
将来の有望研究者の誕生か。

1-3 詰将棋におけるdf-pn+探索のための、
    展開後の証明数と反証数を予測する評価関数

11月12日、東大の金子知適さん。
df-pn探索に評価関数を組み合わせたdf-pn+探索が提案されている。これを詰将棋に適用し、評価関数を作成した。これにより探索ノード数は半分ぐらいに減少できたが、現段階では評価のコストで時間の短縮にはいたっていない。
今後、評価関数の効率化などで、より強力な詰将棋解答プログラムが実現することを期待したい。

1-2 一手詰み判定関数の実装および終盤探索への応用
11月12日、静岡大の佐野晶彦さん。
詰み探索は終盤では重要だが、手間がかかるので全ノードでやるのは難しい。結果として一手詰みを見逃すことがあった。先読みしない高速な一手詰み判定関数を作り、全ノードで実行することで、終番用問題の解答率があがった。
コストと効果の点で、終盤、詰み探索自体に効果が出せるか、検討が必要そう。

1-1 不詰を正しく証明するアルゴリズム
11月12日、最初の発表。岸本章宏さん。
長井のプログラムは詰む問題はほとんど解くが、不詰の問題を「不詰」と判定するのは難しい。阻害している原因の一つにGHI(Graph History Interaction)問題があり、これを新たな手法で解決した、という発表。図巧、無双、続詰むや詰まざるやに含まれる不詰の14作品のうち、12作品の不詰を証明できた(長井プログラムでは0作品)。
不詰の問題はめったにないが、詰将棋の余詰検討に応用すれば、「余詰なし」と結論がきちんと出ることになるので、その意義は大きいと思われる。

| | コメント (0) | トラックバック (0)

コンピュータで詰将棋

[2006年11月5日最終更新] 情報処理学会関連の論文を立ち読みページへのリンクに変更。

2004年5月28日、コンピュータ将棋や囲碁の掲示板で、高橋さんが昔のコラムを紹介。

1998年10月5日、東公平 将棋雑話「電子計算機と将棋」

1968年に初めてコンピュータで詰将棋を解いたときの話。高橋さんによると、このとき日立の1台10億円の大型計算機で36秒かかった詰将棋を現在の謎的電棋で解かせたら約0.005秒で、「1968年から36年経って約7000倍速くなった」。

現在では1525手のミクロコスモスも解けるようになった「コンピュータで詰将棋」の研究の軌跡をWeb上の論文などからまとめてみた。なお、コンピュータ将棋全般についてはコンピュータ将棋協会コンピュータ将棋関係の文献リストを参照されたい。最近では、情報処理学会ゲーム情報学研究会で、関連する研究が発表されることが多い。

注)情報処理学会関連の論文は立ち読みページ(最初の1ページ)にリンク。全文は、電子図書館でユーザ登録して検索して利用されたい(論文により無料・有料あり)。

関連情報: コンピュータ将棋2012  2011  将棋ソフト・コンピュータ将棋
  コンピュータによる詰将棋創作  将棋ソフトでの詰将棋解答
  コンピュータ詰将棋の課題  コンピュータ向け超難解詰将棋作品集


1968年
 ・日立製作所日立研究所の越智利夫博士が、初めて詰将棋を解くプログラム。
  数学セミナー1968年6月 計算機が解く詰将棋
   越智利夫/亀井達弥/徳増真司/内ヶ崎儀一郎
  前述の東公平さんのコラム「電子計算機と将棋」を参照。

1992年
 ・計算機による詰め将棋評価システムの試作 ==> IPSJ電子図書館
   松原仁、半田剣一、元吉文男

1993年
 ・詰将棋の感性評価 ==> IPSJ電子図書館
   小山謙二、河野泰人 
 ・詰将棋問題のデータベースと評価 ==> IPSJ電子図書館
   小山謙二、河野泰人 

1994年
 ・詰将棋を速く解く2つのプログラムとその評価 ==> IPSJ電子図書館
   伊藤琢巳、野下浩平
 ・ゲーム木の並列探索のための分散的実行管理機構 ==> IPSJ電子図書館
   中山泰一、赤澤忠文、野下浩平
 ・名作詰将棋における感性の定量的評価 ==> IPSJ電子図書館
   小山謙二、河野泰人
 ・C^*アルゴリズムによるAND/OR木の探索および詰将棋プログラムへの応用 ==> IPSJ電子図書館
   脊尾昌宏
 ・第1回ゲーム プログラミング ワークショップ
  ・名作詰将棋における好感度の因子分析      
    小山謙二、河野泰人
  ・分散的並列計算による詰将棋の解法
    野下浩平、中山泰一、松本真一、赤澤忠文

1995年
 ・詰将棋を解くプログラムの進歩
   伊藤琢巳、河野泰人、脊尾昌宏、野下浩平
 ・詰将棋におけるゲーム木の並列探索とその評価 ==> IPSJ電子図書館
   笠田洋和、山田雅之、松波功一、世木博久、伊藤英則
 ・非常に手数の長い詰将棋問題を解くアルゴリズムについて ==> IPSJ電子図書館
   伊藤琢巳、河野泰人、野下浩平
 ・第2回ゲーム プログラミング ワークショップ
  ・詰将棋を解くプログラム
    伊藤琢巳
  ・共謀数を応用した詰め将棋プログラムについて
    脊尾昌宏
  ・詰み判定評価関数とPN探索の融合
    田中盛一、飯田弘之、小谷善行

1996年
 ・詰将棋における戦略の獲得方法に関する研究  成果概要
   伊藤英則
 ・コンピュータによる逆算法を用いた詰め将棋の作成の試み ==> IPSJ電子図書館
   広瀬正幸、伊藤琢巳、松原仁
 ・詰将棋におけるプロセッサ稼働率を考慮したゲーム木並列探索 ==> IPSJ電子図書館
   立松靖朗、山田雅之、世木博久、伊藤英則
 ・第3回ゲーム プログラミング ワークショップ
  ・詰め将棋問題の自動生成について
    野下浩平
  ・逆算法による詰め将棋の自動創作
    広瀬正幸、伊藤琢巳、松原仁
  ・詰み判定評価関数を用いた先読み
    田中盛一、小谷善行
  ・Using pattern recognition and selective deeping to solve Tume Shogi
    Reijer Grimbergen (Electrotechnical Laboratory)
  ・将棋の必至アルゴリズム  
    飯田弘之、安部文也

1997年
 ・詰め将棋探索のためのヒューリスティック関数の帰納
   中野智文、犬塚信博、世木博久、伊藤英則
 ・第4回ゲーム プログラミング ワークショップ
  ・裸玉詰め将棋問題の体系的評価
    小山謙二
  ・詰将棋の3×3金銀図式の数え上げ
    野下浩平、飯田崇仁
  ・ミクロコスモスを解くまで  
    脊尾昌宏

1998年
 ・パソコンで詰将棋 ==> IPSJ電子図書館
   脊尾昌宏
 ・帰納論理プログラミングを用いた詰将棋ヒューリスティックの帰納
   中野智文、犬塚信博、伊藤英則
 ・帰納論理プログラミングを用いた詰め将棋のルール獲得
   中野智文、犬塚信博、世木博久、伊藤英則

1999年
 ・逆算型詰め将棋作成支援システム ==> IPSJ電子図書館
   山田剛、松原仁
 ・第5回ゲーム プログラミング ワークショップ
  ・詰将棋を解くアルゴリズムにおける優越関係の効率的な利用について
    脊尾昌宏
  ・詰将棋における評価関数の自動獲得に向けて -評価関数中の論理式の効率的評価方法-
    金子知適、山口和紀、川合慧
  ・Solving problems with uncertainty: a case study using Tsuitate-Tsume-Shogi
    Makoto Sakuta、Hiriyuki Iida
  ・ニューラルネットワークを用いた詰将棋評価実験
    春日利文、鈴木豪、小谷善行

2000年
 ・問題解決における不確定性パラダイムの提案と適用 ==> IPSJ電子図書館
   作田誠、飯田弘之
 ・詰将棋プロジェクト
   成田智也、他
 ・体系的検索による裸玉詰将棋問題の創作 ==> IPSJ電子図書館
   小山謙二
 ・df-pnアルゴリズムの詰将棋解答プログラムへの応用 ==> IPSJ電子図書館
   長井歩、今井浩
 ・反復深化探索に基く協力詰将棋の解法 ==> IPSJ電子図書館
   星由雄、野下浩平、柳井啓司

2001年
 ・盤面の評価を考慮した正算法による詰将棋の自動創作
   増野友彦
 ・将棋を解くプログラムにおける効率的なハッシュの利用法について ==> IPSJ電子図書館
   長井歩、今井浩
 ・第6回 ゲーム・プログラミング ワークショップ
  ・完全に解を保証する必死探索について
    橋本剛、作田誠、飯田弘之
  ・詰将棋における変別チェックと余詰探索を同時に行える新しいアルゴリズムの提案
    長井歩、今井浩  

2002年
 ・df-pnアルゴリズムの詰将棋を解くプログラムへの応用 ==> IPSJ電子図書館
   長井歩、今井浩
 ・不確定性を持つ問題を解くためのAND/OR木探索 - 衝立詰将棋を題材として ==> IPSJ電子図書館
   作田誠、飯田弘之
 ・反復深化探索に基づく協力詰将棋の解法 全文 ==> IPSJ電子図書館
   星由雄、野下浩平、柳井啓司
 ・ゲームの解手順の一般化とある詰将棋の数え上げ ==> IPSJ電子図書館
   野下浩平、飯田崇仁

2003年
 ・ゲーム情報学:2.ゲーム情報学研究の事例2.2詰将棋 ==> IPSJ電子図書館
   長井歩
 ・第8回 ゲーム・プログラミングワークショップ2003
  ・FPGAを用いた詰将棋専用ハードウェアプラットフォームの開発
    堀洋平 、斎藤尚徳、丸山勉
 ・詰将棋専用ハードウェアの作成 ==> IPSJ電子図書館
   堀洋平、斎藤尚徳、丸山勉

2004年
 ・効率的な詰将棋探索のための評価関数 ==> IPSJ電子図書館
   金子知適、田中哲朗、山口和紀、川合慧
 ・第11回 ゲーム情報学研究会
  ・効率的な詰将棋探索のための評価関数
    金子知適、田中哲朗、山口和紀、川合慧
 ・第9回ゲームプログラミングワークショップ2004
  (詰将棋メモのGPW参照)
  ・不詰を正しく証明するアルゴリズム
    岸本章宏
  ・一手詰み判定関数の実装および終盤探索への応用
    佐野晶彦、橋本剛、長嶋淳、飯田弘之
  ・詰将棋におけるdf-pn+探索のための、展開後の証明数と反証数を予測する評価関数
    金子知適、田中哲朗、山口和紀、川合慧

2005年
 ・ 「詰将棋プログラムにおける証明数の2重カウント対策の一手法」
   柿木義一
 ・df-pn(+)で詰将棋
  (駒得少年の冒険 shogi programing journal
 ・組合せゲーム・パズル ミニプロジェクト 2005年度 第1回ミニ研究集会
  ・逆算法に基づく詰め将棋の列挙 [発表資料(ppt)]
   堀山貴史、中塚裕之、岩間一雄
 ・第10回ゲームプログラミングワークショップ2005
  ・新規節点で固定深さの探索を併用するdf-pnアルゴリズム
    金子知適、田中哲朗、山口和紀、川合慧
  ・経路分枝数を用いた詰め将棋解図について
    岡部文洋

こうした研究の成果は、柿木将棋など市販の将棋ソフトにも実装され、今では詰将棋、特に難解な長編の創作(検討)ではコンピュータは必須になっている。
また、単行本では共立出版の「コンピュータ将棋の進歩」シリーズなどに上記のいくつかの研究が収録されている。

| | コメント (0) | トラックバック (0)