なのは 第21回世界コンピュータ将棋選手権アピール文書(仮)
                                                  2011年2月22日       川端一之
                                                  http://vivio.blog.shinobi.jp

■なのはとは？
熱血魔法バトルアクションアニメ「魔法少女リリカルなのは」シリーズの主人公高町な
のはを由来にし、さまざまな称号を冠する彼女のような強さを盤上で実現したいという
願いを込めている。

■野望
・選手権で活躍して、竜王と対局する。
  「キタ━━━━(゜∀゜)━━━━ッ!!」」と某巨大掲示板で大盛り上がりされるｗ
・AMD の CPU を搭載したマシンを使用して選手権で活躍することにより AMD を盛り上
  げ、Intel と AMD とを適度に均衡させてコンピュータ市場を活性化させる。
・コンピュータ将棋に萌えを導入する。
・「コンピュータ将棋の進歩」に寄稿。
・詰将棋に特化したソフトを公開し、デファクトスタンダードになる。

■開発目標
・将棋図巧 100番「寿」を TACOS 以上の速度で解く。
・実戦詰将棋問題の95%を2秒以内に解く。

■全体構成
・Bitboardでなく、駒番号による盤面データを採用している。
・定跡ルーチン＋詰ルーチン＋思考ルーチン
  (1) 定跡DBを検索し、手が見つかれば採用する。
  (2) 次に、詰探索を行い、詰みが見つかれば採用する。
  (3) 最後に、思考ルーチンにて、先読みを行い、評価値が最大になる手を選択する。

■定跡ルーチン
・実戦数および勝率を元に着手を選択する。
  勝率はいいが、決定的な手が発見されたため指されなくなった手などの補正は行って
  いない。
  定跡DBは合流を考慮して、tree構造でなく局面をキーにした構造にしている。

■詰ルーチン
なのはの詰ルーチンは証明数と反証数を使用した WPNS を基本にし、
・優越関係
・最小距離法
・証明駒、反証駒
・新規節点で固定深さの探索を併用[新規]
・局面を更新しない1手詰めルーチン(高速1手詰)[新規]
を実装している。実戦では必要ないだろうとの判断で探索中のハッシュのクリアは行っ
ていない。また、なるべく歩角飛の不成を読まないようにして、かつ打ち歩詰めが絡む
局面で詰みを発見できるように以下のようにしている。
(1) 王手生成では歩角飛の不成も含めて全ての王手を生成する。
(2) 証明数・反証数の計算のときに、打ち歩詰めが絡まないときは歩角飛の不成を無視する。
(3) 証明数・反証数の計算のときに、打ち歩詰めが絡むときは歩角飛の不成も含めて計算する。

■思考ルーチン
・探索処理
  αβで全幅探索＋静止探索を基本に、Null Move Pruning、LMR、Futility Pruning に
  より効率化を図っている。
  マルチスレッド化はできていないため単スレッドによる探索。
・静止探索では駒を取る手＋歩を成る手＋飛を敵陣に動かして成る手を生成。
・評価関数
  第20回では Bonanza を使用して学習し直した fv.bin を使用していたが、本選手権で
  学習し直した fv.bin を使用した場合もライブラリ使用したことになるとルール変更
  になったため、本家 Bonanza Ver.4.1.3 の fv.bin を使用。
  駒割＋位置(KKP＋KP＋KPP)により算出している。

■参考文献
・小谷善行、他:「コンピュータ将棋」, サイエンス社, 1990.
・松原仁 編著:「コンピュータ将棋の進歩」, 共立出版, 1996.
・松原仁 編著:「コンピュータ将棋の進歩2」, 共立出版, 1998.
・松原仁 編著:「コンピュータ将棋の進歩3」, 共立出版, 2000.
・松原仁 編著:「アマ四段を超えるコンピュータ将棋の進歩4」, 共立出版, 2003.
・松原仁 編著:「アマトップクラスに迫るコンピュータ将棋の進歩5」, 共立出版, 2005.
・池泰弘:「コンピュータ将棋のアルゴリズム」, 工学社, 2005.
・金子知適, 田中哲朗, 山口和紀, 川合慧:「新規節点で固定深さの探索を併用するdf-pn アルゴリズム」, 第10回ゲーム・プログラミングワークショップ, pp.1-8, 2005.
・脊尾昌宏:「詰将棋を解くアルゴリズムにおける優越関係の効率的な利用について」, 第5回ゲーム・プログラミングワークショップ, pp. 129-136, 1999.
・保木邦仁:「局面評価の学習を目指した探索結果の最適制御」 http://www.geocities.jp/bonanza_shogi/gpw2006.pdf 
・岸本章宏:「IS 将棋の詰将棋解答プログラムについて」, http://www.is.titech.ac.jp/~kishi/pdf_file/csa.pdf, 2004.
・橋本剛, 上田徹, 橋本隼一:「オセロ求解へ向けた取り組み」, http://www.lab2.kuis.kyoto-u.ac.jp/~itohiro/Games/Game080307.html

■参考web
・小宮日記: http://d.hatena.ne.jp/mkomiya/
・State of the Digital Shogics [最先端計数将棋学]: http://ameblo.jp/professionalhearts/
・ながとダイアリー: http://d.hatena.ne.jp/mclh46/
・毎日がEveryday: http://d.hatena.ne.jp/issei_y/
・Bonanzaソース完全解析ブログ: http://d.hatena.ne.jp/LS3600/
・aki.の日記: http://d.hatena.ne.jp/ak11/
・FPGA で将棋プログラムを作ってみるブログ: http://blog.livedoor.jp/yss_fpga/

■参考ソース
・れさぴょん(v3)
・Fruit 2.1
・Bonanza Version 4.1.3
・Ponanza WCSC20版
・代理将棋通信プログラム「木偶の坊」 Version 0.79