前回、positionクラスについて解説しましたが、position.cppのほうにSEE(Static Exchange Evaluation)の実装があります。

SEEは、局面を評価するときに、駒の取り合いが終わっている静かな局面で評価するために考えられた手法で、ある地点での駒の取り合いを指し手生成などをせずに調べます。

続きを読む →

今回は盤面構造体であるpositionクラスについて解説します。このpositionクラス、本当によく出来ていて、将棋ソフトに応用する場合でも、よくよく考えていくとこれと同じ構造に辿り着くと思います。

そういう意味では、将棋ソフトを作る場合でも独自に実装するより先に、このpositionクラスのソースコードを読んだほうがいいと思います。

続きを読む →

今回はスレッド周りです。

探索を並列化するために並列数だけスレッドの生成が必要です。あと思考時間を監視して、時間になったときに思考を打ち切る判定をするためのスレッドも必要です。

GitHubのC++11用のコードだとスレッド生成はstd::threadを使って実装されています。なお、ここで紹介しているのはC++11用のブランチです。

続きを読む →

今回はmove pickerと言って、指し手を段階的に生成して、生成した指し手のなかから1つ一番よさげな指し手を取り出す部分(いわゆる指し手オーダリング)について見ていきます。

killerが2本あったり、なるべくソートが要らないように工夫してあったり、なかなか興味深いです。

続きを読む →

今回は指し手をUCIの指し手文字列に変換する部分を見ていきます。将棋ではUCIではなくUSIプロトコルとなっています。以下、UCIと書いてある部分はUSIと読み換えて理解してください。

UCIプロトコルでは、思考を開始する局面は、普通、startpos(平手の初期局面)からの指し手を示す文字列が送られてきます。と言うことは、常識的には、UCI表記での指し手文字列を思考エンジンが内部で使っている指し手構造体に変換する必要があります。ところが、Stockfishにはこの変換をダイレクトに行なう関数は存在しません。さて、どうやっているのでしょうか。

続きを読む →

今回は思考時間制御部(time manager)です。現局面での次の1手に使うべき時間を計算します。

maximum search time = 今回の指し手で使える最大思考時間。fail high/fail lowした場合など、この最大時間までは使うものとします。(残りの手数に応じて時間をある程度残しておかないといけないので、この値は残り持ち時間のすべてではありません。)

optimum search time = 今回の指し手で使える平常時の目安時間。

unstable PV Extra Time = 反復深化のiterationを深くしていくときにPV(最善応手列)が変化したときは評価値が不安定な局面だということで与えられる追加の思考時間。

続きを読む →

今回はStockfishのbitcount.hです。これは、2進数的に見て1になっているbitの数を数えるというものです。いわゆるpopcountですね。SSE4.1以降であればx86/x64ではpopcnt命令が使えますので簡単なのですが、そうではない環境ではビット演算のテクニックを用いて求めることになります。

続きを読む →

Stockfishのbitboardは、チェスなので盤面が8×8 = 64升であり、64bit変数に収まります。(将棋の場合、81升なので128bit変数もしくは、64bit変数が2つ必要になります。)

あと、magic bitboardと言う仕組みが使われています。これは斜めに利く駒の利きのbitboardに対して掛け算を使って連続するビットに移動させるテクニックです。→ Magic Bitboard – Chess Programming Wiki

Haswell以降であればBMIを使うべきでしょう。→ BMI使ってますか？

続きを読む →

今回は擬似乱数生成器です。世間では「乱数と言えばMT(Mersenne twister : メルセンヌツイスター)乱数だろ」と思われているかも知れませんが、MT乱数は生成に結構コストがかかるので、ベストなソリューションとは言えません。かと言って、組み込み系の乱数は乱数の精度が今ひとつですのでそういう部分で偏りが出るのは困ります。(定跡選択で乱数を使うので、乱数に偏りがあると連続自己対戦の勝率に偏りが生じかねない)

Stockfishで採用されているのはRKISSという乱数で、この乱数の実装を見るためだけにでも、Stockfishのソースコードを読む価値はあると私は思います。

続きを読む →

今回はStockfishのtypes.hの解説です。このファイルはBonanza6で言うとshogi.hに相当するもので、チェスで使う基本的な構造体の定義が一式書かれています。このファイルの内容を頭においてからソースコードを読み進めれば細部まで理解しやすいでしょう。

続きを読む →