はえええ - sakurapyon’s blog

合法手が生成できるだけの版が出来たので、指し手生成祭り局面を試したら1M回/秒ぐらい出るようだ。

駒打ち展開してないから駒打ちが50%ぐらい喰ってるし、実行時間をあまり考えずに素直に書いてるから、いじれば倍ぐらいになる……といいなあ? その前に王手回避とかMVV/LVAの代用を考えないといかんけど。

templateを使って先後は展開
bitboardは素直に32bit*3,それぞれ27bitずつ使う
- unionとかしてません
飛の横利きはoccupied bitboardを適当にシフトして使う
飛香の縦利きは7x9のrotated bitboardを使う
角の斜め利きは7x7のrotated bitboardを使う
- rotated bitboardが7x9,7x7で済むことを発見した人に感謝!
Magic bitboard は魅力的だけどメモリ喰うのが気になるのと難しそうだからやめておく(メモリの1バイトは血の一滴)

↓こんな感じに書いている。下準備の配列を作るのが恐ろしく面倒(特に飛び利き)だけど、そこを乗り越えると書くのは楽だなあ。C++のオーバーロードを使ってbitboard　の &,|,^,-,<<,>>,~ を定義したらソースもすっきり。

//
// 馬は取る手だけ(成れないし)
//
template        <Player p>
Move *Board::hGenTacticalMoveHorse(Move *m)
{
        BitBoard        b=((p==Black)?bb_piece[Horse_b]:bb_piece[Horse_w]);                     // 自馬の位置
        int     from;
        while((from=b.BitScanClear())!=-1){
                BitBoard        attack=  bb_attack_left[from][(occupied_left>>index_slide_left[from])&0x7f]     // 左上・右下の利き
                                        |bb_attack_right[from][(occupied_right>>index_slide_right[from])&0x7f]  // 左下・右上の利き
                                        |bb_king_attack[from];                                                  // 周囲
                BitBoard to_bb=attack&((p==Black)?bb_piece[Occupied_w]:bb_piece[Occupied_b]);
                int     to;
                while((to=to_bb.BitScanClear())!=-1){
                        *m++ = Move(p,from,to,Horse,board[to],0,MOVE_TACTICAL);
                }
        }
        return  m;
}

利き計算用のbitboardって、空だったり同じ内容のものがわんさかあるんだよね。間接アクセスにしてメモリ減らしたくなるけど、実行時間考えるとどうなんだろ。飛車の横利きのテーブルも位置を見て↓こんな風に条件分岐してるけど、配列アクセスにした方が速いのかな?　L1/L2 cacheの大きさ考えると悩ましいですな。

int     slided=(((from<27)?occupied.bb[0]:
                ((from<54)?occupied.bb[1]:
                           occupied.bb[2]))>>index_slide_rank[from])&0x7f;

追記：↑はこう↓書くべきであった。条件分岐2回と除算(from/27)と配列アクセスとどっちが速いか?
(さらに追記： (from>=27)+(from>=54)なんて書くと条件分岐はなくなるけど、命令数は増える)*1
(さらに追記：配列アクセスに掛け算がいるのと、元の配列はレジスタにありそう?だから最初の版が良かったりして^_^;)

int     slided=((occupied.bb[(from<27)?0:((from<54)?1:2)])>>index_slide_rank[from])&0x7f;

Thanks:

*1:http://www.slideshare.net/herumi/cmovmaxps