コンピュータで詰将棋

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

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

１９９８年１０月５日、東公平　将棋雑話「電子計算機と将棋」

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

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

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

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

---

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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