magic bitboard

例のswitch展開での指手生成もバグがとれて安定してきました。
floodgateにkuma2_testで投入しています。fv.bin使っている割に弱いです。
R2000あるかどうか。
最初から作り直していて、前回と違う個所は、

○指手生成一新。手情報もintにした。
○定跡選択をまともにした（頻度で選ぶようにした）
○静止探索でハッシュを使った
？指手を逐次生成にした
？インテルコンパイラにした

×まだ、差分評価していない（全バージョンは差分評価していた）、PGOなし。
です。○は多分よくなっている個所。？は不明。×は改善余地あり。
もうちょっと強くなっても欲しいけど弱いです。
プロファイル調べても見るとSEEですごく時間がかかっているようでした。
ここの部分はbitboardのほうがよいかもしれない。
というわけで、とうとうbitboardを作ってみることにした。
Apery式で１４個のビットボード＋issei式magic bitboard[1]。
盤の配置順は左上から右下が慣れているので回転はさせていない。

magic number生成プログラム

以下に置きます。飛車だと14bitの完全ハッシュを作らないといけないのだけど、
やみくもにmagic numberを乱数で生成しても、衝突しまくってなかなかできない。
ここらへんんは[2][3]でも苦労しているようでした。
[3]のように乱数生成の際に、1のビットが少なくなるようにすれば
なんとかできた。それでも、55角の12bitテーブルは100万回以上の試行が必要だった。
以下、コード置きます。
http://navi.cs.kumamoto-u.ac.jp/~koutaki/shogi/gen_magic.zip

[1]http://www.graco.c.u-tokyo.ac.jp/~issei/GPW_Proposal%20and%20Implementation%20of%20Magic%20Bitboards%20in%20Shogi.pdf
[2]http://d.hatena.ne.jp/stonestonestone/20091110
[3]http://d.hatena.ne.jp/mclh46/20101123

指手生成速度 core i7 3.2GHz

指手生成祭の後手側で、ビットボード版は300万/秒、switch展開は340万/秒。
ビットボード版はボナンザを参考にした。
Aperyは400万/秒とのことだったので、実は、switch展開板は結構速いことが判明。
ビットボードを使わなくても指手生成は、それなりに速くできるのかな？
でも、SEEや王手生成はやっぱりビットボードを使った方が良さそうです。

↓は以前アップした、switch展開指手生成コードです。
navi.cs.kumamoto-u.ac.jp/~koutaki/gen_move.zip

追記：bitを少なめに乱数生成する方法

以下のようにしています。これで結構速くmagic numberが見つかるようになりました。

 // 1のビットを少なめに乱数生成
 uint64 random()
 {
 	uint64 v = 0, n = 1;
 	for(int i = 0;i < 64;i++){
 		if(rand()%1000<150)
 			v += n;
 		n = n << 1;
 	};
 	return v;
 };