棋譜からの学習について保木さんにメールで直接教えていただきました 保木さんのご厚意により、メールで質問して構わないということでしたので、私は厚かましくもメールで根掘り葉掘り質問させていただきました。保木さんに教えていただいた情報のうち、保木…

■ まえがき 今回から何回かにわけて差分指し手生成の具体的な手法について書いていきます。差分指し手生成をしても普通に生成するより遅くなっていては何の意味もなく、差分指し手生成によって普通に生成するより速くならなくてはなりません。つまり、どのよ…

昨日の記事で差分指し手生成に成功したと書いたが、差分指し手生成とは次の3つの段階にわけられる。1) MakeMoveで利きの更新を行ない、影響を受ける駒を確定させておく。 2) gen_XXXでは、そこでdirty flag(指し手のupdateを要する駒を示すフラグ)の立ってい…

■ Bonanzaで使われているinsertion sortとは何か？ Bonanzaで使われているsort(並べ替え)は、 1) insertion sort 2) shell sort 3) quick sort の3種類である。 3)はCのqsort関数を呼び出しているだけなので解説は不要だろう。また、3)は定跡データベースの…

なんかアクセス多いなと思ったら、昨日の記事をtwitterで言及してくれている人がいた。(→ http://twitter.com/cpp_akira/status/5997348630 ) 誰かと思ったら、Faith and Braveの中の人だった。この人は、C++標準化委員会の人だ。そう言えば7年ぐらい前は私…

■ 差分指し手生成とメモリコピーの高速化の基礎 差分指し手生成などをしようと思うと、それぞれの駒についての指し手をシリアル化(ここでは一次元の配列にまとめるの意味)する必要があります。 このとき、細切れになっているメモリを一箇所に集める必要があ…

■ double-sized bitboardの提案 将棋盤は81マスで、bitboardで表現する場合81bit必要です。これは64bitに収まらないので、盤面をbitboardで表現しようとすると64bit + 32bitもしくは64bit×2のようになるのが普通です。 上の組み合わせをメモリの無駄を承知で…

■ FPGAって本当に速いのですか？ 指し手生成祭りでは一応のところトップになった(→ http://vivio.blog.shinobi.jp/Entry/151/ )のですが、どうもこの結果に納得いかないのです。 あの局面なら私の普段使っているマシン(Core 2 Duo 2.8GHz)で4M回/secぐらい出…

■ Bonanzaの定跡データベースはどういう構造になっているのか？ 指し手生成について一通り解説が終わったので、その他の部分を順番に解説していく。 解説していくとは言うものの、私自身そんなに時間がとれるわけではないので、Bonanzaのソースにコメントを…

■ 将棋プログラムに何故coroutineが必要なのか Bonanzaの3手詰めルーチンや静止探索ではcoroutineが使われている。coroutineについて理解していないとこれらの処理はとても読みがたく、理解できない。 今回は、将棋プログラムに何故coroutineが必要なのかに…

■ Rotated Bitboardsは本当に高速なのか？ rotateをやろうと思うと、90度、45度x2で、３つのbitboardをmakeMoveで更新しないといけない unmakeMoveも同様。一つのbitboardは3個の32bitのint変数に演算を行うことになる。 これはけっこうばかにならないコスト…

■ Bonanzaの指し手生成ルーチン完全解読(7) 今回は、一通り利きに関するマクロや関数の紹介が終わったのでis_pinned_on_black_kingの実装を読んでみる。 ■ is_pinned_on_black_kingの実装 この実装は以下のようになっている。なお、ソース自体は私が少し手を…

stacksさんがコメントで書かれてましたが、 細かい話ですが、取り出す順序を問わないforeachであれば、 bsr(_BitScanReverse)を使って_c_ ^= 1 << _index_;で消すよりも、 bsf(_BitScanForward)を使って_c_ &= _c_ - 1;で消したほうが少しだけ速いはずです。…

■ Bonanzaの指し手生成ルーチン完全解読(6) 今回は指し手生成で使用している利き関係の残りのマクロについて解説する。 ■ AttackBishop , AttackHorse , AttackRook , AttackDragon extern bitboard abb_file_attacks[ nsquare ][ 128 ]; // 縦の利き extern…

■ Bonanzaの指し手生成ルーチン完全解読(5) 指し手生成のソースを解読するには利き関係のマクロの解読が必須ということがわかったところで、利き関係のマクロの解読を続けていこう。 ■ AttackFile , AttackRank 前回、香の利きを生成するマクロとして次のも…

■ Bonanzaの指し手生成ルーチン完全解読(4) 今回は指し手生成で使う利き関係のマクロや配列に関してその説明を書いておく。 なお、コメントは私が追加した。また無名列挙体の場合、私が名前を追加している。 ■ abb_X_XXX_attacks BoardPosにある駒の利きを表…

■ Bonanzaの指し手生成ルーチン完全解読(3) 今回は、指し手生成関係の関数の一覧を書いておく。 ■ 指し手生成関係の関数 Bonanzaの指し手生成関係の関数は以下のものがある。b_gen_XXXは、先手用。w_gen_XXXは後手用。第二引数にMove*を渡しているが、ここに…

■ Bonanzaの指し手生成ルーチン完全解読(2) 前回の時点で、gennocapとgencapで生成する指し手の種類については解説が終わっている。ここから指し手生成のコードを読まなければならないが、指し手関係のマクロに関して知っていないとソースが読みにくいので今…

■ Bonanzaの指し手表現は何故優れていると言えるのか 指し手生成祭り開催http://d.hatena.ne.jp/LS3600/20091110 指し手生成に関して、「私の将棋ライブラリ」で2.15M/sec、Bonanzaが1.1M/sec、misakiが私の方法を取り入れて300K/sec→600K/secになりました。…

■ 指し手生成祭り開催 指し手生成の早さ競争http://d.hatena.ne.jp/mkomiya/20091107/1257596065 小宮さん、mclh46さん、aki.さんのところで盛り上がっているようなので私も大人げなく私の将棋ライブラリで参加してみました。 Bonanza改造ソースを「私の将棋…

■ 2010年の世界コンピュータ将棋選手権の件 まだ予定だけで本当のところどうするかはわかりませんが、私はたぶん2010年の世界コンピュータ将棋選手権に出場すると思います。 何か某掲示板のほうでは私のことがいろいろ書かれているようですが、余計な勘ぐり…

■ Bonanzaの指し手生成ルーチン完全解読(1) Bonanzaの指し手生成ルーチンは、genXXX.cというファイルにあり、次の5つのファイルから構成される。 1) gennocap 2) gencap.c 3) gendrop 4) genchk.c 5) genevasn.c 名前からすると、 1) は駒を捕獲しない指し手…

■ Bonanzaが用いているbitboardの定数配列の意味【後編】 前回記事 : Bonanzaが用いているbitboardの定数配列の意味【前編】http://d.hatena.ne.jp/LS3600/20091102 の続き。 今回は、残りのbitboardの定数配列の意味を解説する。 これによりBonanzaのソース…

■ Bonanzaの指し手生成は40%以上の高速化ができる Bonanzaの評価関数はどのようなものか？【KKP編】http://d.hatena.ne.jp/LS3600/20090928 のほうで保木さんからコメントを頂戴した。 > 先頭でbitwise ORをとって空なら抜けるように Bonanza のソースファイ…

■ C++で書き直したBonanza もうすでにお気づきの人がいるかも知れないが、私は、Bonanzaのソースを全面的にC++で書き直している。 何故、本家BonanzaがC++ではなくCで書かれているのか、その理由は私にはよくわからない。移植性を気にされたのかも知れない。…

■ Bonanzaの手駒の優劣比較にはあまり知られていない技法が使われている 以前、Bonanzaの手駒のbit layoutについて書いたときに、駒のbit fieldをpaddingしておけば優劣比較が引き算一発で済みますよという話を書いた。 Bonanzaの手駒のbit layoutはどうなっ…

■ Bonanzaが用いているbitboardの定数配列の意味【前編】 Bonanzaではbitboardの定数配列をいくつか持っている。これらの初期化は、ファイルから値を読み込むのではなく、プログラムのなかで動的に初期化している。 初期化している場所はini.cのini_tablesで…