なんか最近、コンピューター将棋界にはモンテカルロブームが到来しているらしいので、モンテカルロ型の探索についてつらつらと書いてみます。 まず、ランダムプレイヤーを実装するとします。ここで言うランダムプレイヤーとは、合法なすべての指し手を生成し…

is_move_validを見ていて思い出したのですが、以前も少し書いたようにCSA読み込み中で合法手かどうかをテストするためにすべての指し手を生成してそのなかの指し手に含まれるかをチェックしているのですが、あの部分、速度的な観点からは、この is_move_vali…

Bonanzaで実装されている主要なvalidatorは次の3つと言えるでしょう。 // valid.c int is_move_valid( tree_t * restrict __ptree__, unsigned int move, int turn ); int exam_tree( const tree_t * restrict ptree ); // debug.c int exam_bb( const tree_…

Bonanzaのコードに致命的なバグが少ないのは、探索木のvalidatorがあることが理由に挙げられると思います。ここで言うvalidatorとは、正当性(状態が正しいかどうか)をチェックする関数のことです。 探索木で言えば、 ・敵陣の1段目に成っていない歩・香が無…

さて、昨日の問題の答えですが、平岡さん(id:hiraoka64)から昨日のコメント欄に解答がありました。詳しくは昨日のコメント欄を見ていただきたく…。 また、他の駒(桂・角・飛)の王手生成についても同様です。さらに言えば昨日のケースではp[0]だけが問題であ…

で、その後は香車の移動先が敵陣かどうかを判定せずに、 香車の成りの手を生成しています。 FLAG_PROMOが成りを表しています。Bonanzaの王手生成(buoyance) http://d.hatena.ne.jp/hiraoka64/20110923/1316747966 そういや、私もそれBonanza 4.12のときに気…

Bonanza以前の評価関数は挟撃形ならば挟撃する側はプラス何点というような評価をしていたわけですが、Bonanzaで導入された3駒関係(KPP)は、それを内包していました。 これと同様に、4〜6駒関係は自動的に重要なさまざまな概念を内包しているということは言え…

Bonanzaの評価関数はプロ棋士の棋譜から学習させていて、入玉模様の棋譜は絶対数が少ないため、入玉模様の将棋は正しく学習できていないというのが定説であります。 しかし、単に教示データが少ないという理由だけであれば、手でドーピングするなり、制約条…

優秀なコンピューター将棋開発者には、自分が作っているコンピューター将棋が正しく評価できない懸案の局面というのがいくつも頭のなかにありまして、まあ、私はいま気になっているのは次の局面のみなのですが、そういう意味では私は「優秀なコンピューター…

integer→float変換を使うぐらいなら、乗算を使えばどうかというのは自然な流れでして、コツがわかったところで、完全ハッシュを使うことを考えます。 参考:http://d.hatena.ne.jp/siokoshou/20090704 まず1になっている最下位のビットを得るところは、普通、…

packed u16の下位8bitにbsr/bsfしたときの結果らしきものが代入できました。 では、これをpacked u16となして最小値を探せば良いのです。 最小値を探す命令は、_mm_minpos_epu16(PHMINPOSUW)を使います。 残念なことに最大値を探す命令(PHMAXPOSUW?)はありま…

この_mm_cvtepi32_ps命令によって、 bit127 : 符号 bit126から8bit : bit96〜bit126の1が立っていたbit位置…(a) bit95 : 符号 bit94から8bit : bit64〜bit125の1が立っていたbit位置…(b) bit63 : 符号 bit62から8bit : bit32〜bit62の1が立っていたbit位置…(…

さて、SSEでbsr/bsfを実現するためには、まず_mm_cvtepi32_ps(アセンブリ命令はCVTDQ2PS)という整数をfloatに変換する命令を使います。 というか、一昨日の記事のコメントで、すでにそのことは指摘されています ktanaka 2011/09/16 11:29 CVTDQ2PSを使う方法…

まず下準備としまして、Bitboard構造体にメンバーを追加します。 struct BB { union { u64 p[2]; __m128i m; // integer型とみなすとき __m128 mf; // float型とみなすとき }; }; float型というのを見て、もうピンと来たかも知れませんね。例のアレですね。 …

今回からはbsr/bsf命令をSSEでどうするのか？という問題について考えていきます。 というのも、SSEの命令だけで完結しないとむしろ(SSEを使わないときより)遅くなるからです。 SSE命令だけで完結することはすこぶる大事です。 ただ、コンピューター将棋の場…

長々と書いてきましたが、一番基本的なことを説明するのを忘れておりました。 SSEでは、xmmレジスタという128bitのレジスタを使います。これはMMXのときのmmレジスタ(64bit)が拡張されたものです。 MMX用のコードを書いたことのある人ならご存知だと思うので…

あと、SSEを使う場合と使わない場合とで、普通のプログラムですと、仮想関数にしたりして呼び分けると思うのですが、極限まで速度が要求されるコンピューター将棋の場合、どうするのが良いでしょうか？ 無理やり1つの実行ファイルにしようと思えばコーディン…

(問) andnotのときに使った_mm_set1_epi8という命令に対応するアセンブリ命令は何か？ (答え) 直接対応する命令はありません。どこかのメモリに0xffが16バイト格納されて、(普通は)それをいったんxmmレジスタに取り出すコードが生成されます。 複数回、_mm_s…

今日はSSE4の命令を紹介します。 // 交差部分(andしたのちに1のbit)があるなら1 # define Bitboard_Contract(b1,b2) ( ! _mm_testz_si128( (b1).m, (b2).m ) ) // 非0なら1 # define Bitboard_Test(b) ( ! _mm_testz_si128( (b).m, _mm_set1_epi8(0xff) ) ) …

今回はVisual C++2010で拡張命令を使う(/arch:SSE2)を指定してのコンパイルについてです。 Visual C++2010は拡張命令を使うように指定すれば*1、SSE2命令が使えるようなことを書いてあるのですが、コンパイラが普通のコード生成のときに積極的に使ってくれる…

さて、SSEの話も第三回目。 今回は、SSEの得意な処理と不得意な処理についてです。 もうお気づきかも知れませんが、SSEにはnot(bitwise not)すらないのです。 何故無いのでしょうか？ それは、notが単項演算だからです。SSEは、2つのデータに対して何か演算…

それではSSE命令の使い方を説明していきましょう。 SSE2命令だけを使うときは、emmintrin.hをincludeします。 SSE2/SSE4の命令を使うときは、smmintrin.hをincludeします。 つまり、以下のようになります。 #if defined(HAVE_SSE2) || defined(HAVE_SSE4) #i…

CSAの読み込み部の説明が終わったので、CSAの書き出し部の説明に入る前に、ちょっと息抜きにSSE命令の使い方を解説します。 まずBitboardを使っているとして、使えそうなSSEの命令はSSE2とSSE4の命令です。 どちらも128bit幅の演算が一命令で出来ますので、…

CSAファイルの読み込み部分の解説が終わったのでCSAファイルの書き出しについて解説していこうと思うのですが、その前に、in_CSA_headerの引数で渡しているflagの意味を書いておきます。これは書き出しのときも共通です。 enum { flag_time = b0001, // CSA…

実際にN手目の局面をCSAファイルから読み出すコードとして、csa.cのread_recordという関数が非常に参考になるのでソースを引用して、ソースに私が注釈を入れておきますので読んでみてください。 ここまでの内容を理解していれば、すんなり読めるはずです。 i…

CSA形式のデータは大雑把に言えば 1) 開始局面の図 2) そこからの指し手 から成るわけですが、この1)のことをBonanzaではCSA_headerと呼んでいます。このことを知っているとソースがずいぶん読みやすくなるはずです。 私は「header？ 対局者の名前とか対局日…

さて、今回は、csa.cのそれぞれの関数の意味を書いておきます。 今回の解説と併せてBonanzaのソースコードを読めば、CSA読み込みルーチンを自作ようという人の参考にもなるはずです。 static int str2piece( const char *str ); // CSAの駒を意味する文字列(…

CSA形式の読み込みルーチンについて解説する前に、Bonanzaの設計スタイルについて少し書いておきます。 Bonanzaは、Cで書かれています。C++ではありません。 C++ならば、CSA読み込み部分のプログラムを書くならばCSA用のclassを作って、そのメンバ変数として…

今回からBonanzaのCSA形式のデータ読み込み部を解説していきます。 CSA形式のデータをファイルから読み込むとき、それは単なる局面図とき限らず、指し手をともなっており、局面が変化していきます。 そこでCSA形式のデータを読み込むためには、 1) 初期局面…

昨日の記事で書き忘れましたが、昨日以降、このブログで単にBonanzaと表記するときは現時点で最新であるBonanza 6.0のことを指します。 とは言ってもBonanza 6.0も以前のソース(Bonanza 4.1.2あたり)からあまり大きな変更はないのですが。 今回は、Bonanzaの…