図解

前回のエントリーで説明した書き方では大変分かりにくいので、図で示す。
Aのような配置のとき、128bitレジスタではBに示しているように白と黒をそれぞれ上位と下位64bitにして別々にした形で持っている。
この配置のうち、一番上の一行を16bit整数にする場合を取り上げる。
もちろん一番簡単な方法は0byte目と8byte目を取り出して連結することだが、それでは縦の列を計算する場合別の方法をとらなければならない。また、黒白反転は値を入れ替えればよいものの、左右対称のコードをつくる場合簡単にはいかない。(spu_reverseというような関数があればよかったのだが）
そこで汎用性があり、それほど性能的なペナルティもなさそうな方法として、Cに示した以下のような方法を採用した。

1. spu_shuffleで、一番上の行を下位8bitに、上位8bitが0の16bit整数8つからなるベクトルを生成する（これは黒のみだが、白でも同様）
2. spu_rlを用いて第0要素の0bit目、第1要素の2bit目…に順に対象となるマスが来るようにローテートし、spu_andで必要としないマスをマスクする
3. 白を1bitだけローテートして、spu_orで論理和をとる
4. spu_orxで一つの32bit整数にまとめる
5. 32bit整数の上位16bitと下位16bitの論理和をとり、16bit整数を生成する(D)

この方法のよいところは、前回挙げたコードと、spu_shuffle, spu_rl用の二つの定数を与えるだけで、8つのマスで表現されるパターンならば全て同じクロック数で計算できることだ。このとき条件分岐、ループ、メモリアクセス、加減算を行わない。SPUのアーキテクチャではローテートがもっと早かったらとか、shortにも対応していたらとか、spu_orxがshortやlong longにも対応していたらとかいう気持ちもあるが、まあそれほどボトルネックにはなるまいという程度の性能は出ている。
実際の適用ではパターンの計算よりもパターンの評価のためのメモリアクセスの方が足を引っ張るのでここであまり力を入れても仕方がないのだが、SPUのアーキテクチャの理解という意味ではなかなか面白かった。

二分検索

このようにしてパターンの評価値を得た後、使用しなければ意味がないのだが、その評価値の検索で無駄な処理をしてしまっては意味がない。
広大なメモリがあればO(1)でデータを得られるようテーブルをメモリ上に持っておけばよいが、それは無理なのでO(log(N))で検索できる二分検索を用いた。

二分検索の場合、SPUでの使用でためらわれるのは一度の比較ごとに条件分岐を挟むことにある。できるだけ条件分岐をしたくないSPUでのコーディングを考えれば、あまり好ましいアルゴリズムではない。
しかしもしテーブルのサイズが一定であれば、ループの最大数は一定であり、ループアンローリングで条件分岐を排除する事ができる。またどうせ常に見つかる回数だけループするならば、一度に複数の検索をやってしまってもよい。

そこで使用するテーブルのサイズが512より大きく、1024以下である場合として、以下の関数で検索を行うようにした。

inline vector unsigned int binary_search_4( vector unsigned int code, unsigned int data_start, unsigned int data_end, unsigned int* data ) {

    vector unsigned int start = spu_splats( data_start );

    vector unsigned int end = spu_splats( data_end );

    static const vector unsigned int mask_code = (vector unsigned int){ 0xffff, 0xffff, 0xffff, 0xffff };

    static const vector unsigned int not_found = (vector unsigned int){0,0,0,0};

    vector unsigned int target = spu_and( code, mask_code );

    vector unsigned int probe = zerovector;// = spu_splats( (unsigned short)0 );

    vector unsigned int center;

    for ( int i = 0; i < 10; i++ ) {

        // 4つの値について比較対象の位置を設定

        center = spu_rlmask( spu_add( start, end ), -1 );

        // それぞれの場所の値を代入

        for ( int j = 0; j < 4; j++ ) {

            probe = spu_insert( data[ spu_extract( center, j ) ], probe, j );

        }

        // 最上位ビットは白黒反転のフラグなのでクリア

        probe = spu_and( probe, mask_code );

        // 目的とする値より大きいか小さいかを判定

        vector unsigned int sel2 = spu_cmpgt( (vector unsigned int)probe, (vector unsigned int)target );

        // 条件分岐を使わず、検索位置の更新

        start = spu_sel( center, start, sel2 );

        end = spu_sel( end, center, sel2 );

    }

    // 真の値をみつけたかどうか確かめ、違ったら0を返す

    center = spu_rlmask( spu_add( start, end ), -1 );

    for ( int j = 0; j < 4; j++ ) {

        probe = spu_insert( data[ spu_extract( center, j ) ], probe, j );

    }

    probe = spu_and( probe, mask_code );

    vector unsigned int pos = spu_sel( not_found, center, spu_cmpeq( (vector unsigned int)probe, (vector unsigned int)target ) );

    return pos;

}

最後の念押しの判定が無駄なのでどうにかしたいのだが、とりあえず条件分岐の排除と４スロットの同時検索はできたのでこれでよしとしている。

パターンの抽出ルーチン

しばらく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マスでつくられる別のパターンで結果と関係するものがないかを試している。これは本気でやれば終わりのない試行錯誤になるので、しばらくアルゴリズム的な進歩を導入しづらい状況になっている。

FFOベンチマーク２

細かい改良を施しつつ、ゆっくりと更新しているのだが、現在のプログラムでのFFO endgameベンチマークは以下の通り。

それほど探索性能は悪い訳ではないのだが、枝狩りの性能が悪いので結果として非常に時間がかかっている。
現在はαβカットとmove orderingだけをしており、move orderingについてはまだやることが残っているのでいくらか時間がかかる。
問題点は探索樹のサイズが大きくなるとちょうどそれに対応して時間がかかっていることにある。
アルゴリズム的にはnega-scoutを導入して早めに解の範囲を決定しておくことによって、簡単な問題であれば全探索では時間のかかる問題も速く終了するようになると思われる。
Nega-scoutを導入するためには探索関数を新たに導入すべきか、既存のものを使い回すべきか、どちらが性能とこれ以降の開発によいか考慮中。

またもや頓挫

余り時間がないので詳細は後にするとして、周辺配列と対角線について評価を行い、その評価値によって次手を並び替えして検索する方法を試みた。
方法としては以下の通り

1. 残り14, 15, 16手のランダムな配置を作成する
2. そのときの配置を記録
3. 完全読みを行い、勝敗を記録
4. 配置と勝敗についての分割表を作成し、オッズ比の99.9%信頼区間を計算
5. 14, 15, 16の全てで（勝つ方が多い場合）オッズ比の下限が１以上であるものを選択
6. 下限の平均値を計算し、その対数をとる

これによって、ある配置が出現したとき勝つ確率が何倍になるかを計算し、評価値とした。
この結果、着手可能手数と石の数も組み入れて計算した評価値と最終的な石の数は相関係数0.9で相関したのだが、パターン評価の際に二分検索でメモリを数回アクセスするため、検索するノードの数は減ったのだが時間は逆にかかるようになってしまった。

おそらくmove orderingでは思ったほど探索樹は小さくならないので、どこかで打ち切りが必要なのだろう。
またZebraのソースを読まなければならなさそうだ。

また、可能であればメモリアクセスなしで周辺配列のパターン評価をできないか考えてみたい。

パターン化

他の「まともな」オセロプログラムより終盤解析が遅い理由は，次の階層の最善手を探す並び替えがお粗末だからだ．
とりあえず４辺と対角線の配置に付いてはパターン化し，有利なものを選択するようにすることは最低限しておこうと思う．
８つの石の配置は3^8=6561あるが，この中で対象や，白黒反転のものを除くと1651通りになる．
このサイズであればSPUのメモリでも保持可能だ．
また，パターンのうち本当に勝敗に影響をもたらすものは全部ではない．
そのため勝敗に影響のあるものだけを選択することで更に効率化できるのではないかと考えている．

まとめると，パターン作成の戦略として

• 8つのマスの配置を考慮
• 勝敗に関係するものだけを選択
• パターンと勝敗の関係を抽出

とする．
パラメタを取得する場合，一定数までランダムに進めた配置を用い，そのときのパターンを列挙．勝敗は完全読みを使い，パターンとの相関を調べることで評価テーブルを作成することにする．

また，配置からパターンの生成では，

• メモリアクセスを伴わない
• ビット演算だけで計算

は必須である．

Try & Error

現在の探索では次の階層の配置の評価を行うときと，新しく配置可能な位置を求めるときとで同じ処理を二回している．
これは無駄なのでここを改善すれば速度が上がるだろうと期待していた．
しかしやってみると全く反対の結果になった．
なぜこのようになるかと言えば，計算の結果を配列に保持するため，メモリへのアクセスが発生してしまうからだ．
この結果はかなり暗澹となってしまった．
石の反転でZebraが私のプログラムよりもずっと高速なのは，全ての方向について条件分岐を使いまくり，無駄な部分は早々に打ち切るからなのだが，それをSPUでやると圧倒的に遅くなるので，固定数のループを回すようになった．
この無駄をなくすためにキャッシュを保持しようとすると，10*16=160byteの書き込みをすることになる．この書き込み／読み込みのためのウェイトが計算よりも遅いので，レジスタを使い回して済むならば２度同じ計算をした方がよいということになってしまう．
演算自体をビット演算のような軽いものにチューニングしていけばいくほどアーキテクチャからくるオーバーヘッドで頭打ちになり，つらい．