パターンの抽出ルーチン

o-cell-o

しばらくSPUと関係ない話ばかりだったので、コードを載せて少し話を進めたい。
Move orderingにおいて、盤面のパターンをどのように認識するかという問題について、私のプログラムでは16bitの整数に変換することで実行しているのだが、16bit全部のテーブルを持っておくのは無駄の上にメモリの制約上不可能に近いので、同じ意味のパターンは一つにまとめるようにしている。
つまり、ある辺が
○●●●●●○●
である場合、
●○●●●●●○
●○○○○○●○
○●○○○○○●
も同じ評価になるはずであり、白黒反転させたものは評価値を負にしたものでよい。
ある配置から効率的に４つのパターンを生成し、その中で代表値を選ぶ作業をSPUなりに行うために、SPUの独自命令を活用した。

まず、以下の関数を用意する。



// 盤面の配置から16bitパターンを生成する

// 下位16bitと上位16bitは白黒反転させたパターンになる

unsigned int extract_pattern_1( vector unsigned int assembly, 

                                       vector unsigned char mixer, 

                                       vector signed short shift ) {

    static const vector unsigned int mask_d = (vector unsigned int){0x00010004, 0x00100040, 0x01000400, 0x10004000 };

    static const vector unsigned char mask_8 = (vector unsigned char){0,8,0,8,0,8,0,8,0,8,0,8,0,8,0,8};

    vector unsigned int mask_1, mask_2;

    // 使用する行をばらまく

    mask_1 = spu_shuffle( assembly, assembly, mixer );

    mask_2 = spu_shuffle( assembly, assembly, spu_or( mixer, mask_8 ) );

    // 対角線上に並べる

    mask_1 = (vector unsigned int)spu_rl( (vector unsigned short)mask_1, shift );

    mask_2 = (vector unsigned int)spu_rl( (vector unsigned short)mask_2, shift );

    // 必要としないビットをクリア

    mask_1 = spu_and( mask_1, mask_d );

    mask_2 = spu_and( mask_2, mask_d );

    // pat1は自分の石が下位ビットに、pat2は相手の石が下位ビットになる白黒反転パターン

    unsigned int pat1 = spu_extract( spu_orx( spu_or( mask_1, spu_rlqw( mask_2, 1 ) ) ), 0 );

    unsigned int pat2 = spu_extract( spu_orx( spu_or( spu_rlqw( mask_1, 1 ), mask_2 ) ), 0 );

    pat1 = ( pat1 | pat1 >> 16 ) & 0xffff;

    pat2 = ( pat2 | ( pat2 << 16 ) ) & 0xffff0000;

    return pat1 | pat2;

}
この関数はある配置について、符号化に用いるマスを8bitおきにばらまき、次に対角線上に並べた上で他を取り除いて、spu_orxでまとめ、16bit整数にした上で白黒反転させたものと組み合わせた32bit整数として返す。
例えば上一列に対して符号化を施す場合は以下の二つの関数を用いる。


const vector unsigned char mixer_top_row = (vector unsigned char){ 128,0,128,0,128,0,128,0,128,0,128,0,128,0,128,0};

    const vector signed short shifter_stepping = (vector signed short){0,1,2,3,4,5,6,7};

    const vector signed short shifter_stepping_rev = (vector signed short){-7,-4,-1,2,5,8,11,14};
unsigned int extract_pattern_top_0( vector unsigned int assembly ) {

    return extract_pattern_1( assembly, mixer_top_row, shifter_stepping );

}

unsigned int extract_pattern_top_1( vector unsigned int assembly ) {

    return extract_pattern_1( assembly, mixer_top_row, shifter_stepping_rev );

}

この関数は全ての場合に最適化されたものではないのだが、spu_shuffleに渡す値とspu_rlに渡す値によって、16bitのあらゆるパターンをメモリアクセスなし、条件分岐なし、更に加減算すらなしで生成することができる。
Zebraでは対象とするマスを3進数の整数として計算しているが、これは非効率だし、反転や回転が簡単にできない。

このようにして得た４つの16bit整数は、例えば4辺の場合4つのレジスタに入れられ、spu_selを使ってその中で最小のものだけが選ばれるようにしている。ただし白黒反転したものは、後で評価値を正負逆にするためのフラグとして最上位ビットを1にしている。（この部分の関数は長いので省略）

この結果分かった事は、4辺のパターンは確かに結果に強く影響を及ぼすのだが、対角線のパターンはほとんど意味をなさないということだ。（パターンの評価値と解の値の相関係数が0.1）
そのため、当初計算していた対角線は無視することにし、8マスでつくられる別のパターンで結果と関係するものがないかを試している。これは本気でやれば終わりのない試行錯誤になるので、しばらくアルゴリズム的な進歩を導入しづらい状況になっている。