前回のエントリーで説明した書き方では大変分かりにくいので、図で示す。 Aのような配置のとき、128bitレジスタではBに示しているように白と黒をそれぞれ上位と下位64bitにして別々にした形で持っている。 この配置のうち、一番上の一行を16bit整数にする場…

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

しばらくSPUと関係ない話ばかりだったので、コードを載せて少し話を進めたい。 Move orderingにおいて、盤面のパターンをどのように認識するかという問題について、私のプログラムでは16bitの整数に変換することで実行しているのだが、16bit全部のテーブルを…

細かい改良を施しつつ、ゆっくりと更新しているのだが、現在のプログラムでのFFO endgameベンチマークは以下の通り。 それほど探索性能は悪い訳ではないのだが、枝狩りの性能が悪いので結果として非常に時間がかかっている。 現在はαβカットとmove ordering…

余り時間がないので詳細は後にするとして、周辺配列と対角線について評価を行い、その評価値によって次手を並び替えして検索する方法を試みた。 方法としては以下の通り 残り14, 15, 16手のランダムな配置を作成する そのときの配置を記録 完全読みを行い、…

他の「まともな」オセロプログラムより終盤解析が遅い理由は，次の階層の最善手を探す並び替えがお粗末だからだ． とりあえず４辺と対角線の配置に付いてはパターン化し，有利なものを選択するようにすることは最低限しておこうと思う． ８つの石の配置は3^8…

現在の探索では次の階層の配置の評価を行うときと，新しく配置可能な位置を求めるときとで同じ処理を二回している． これは無駄なのでここを改善すれば速度が上がるだろうと期待していた． しかしやってみると全く反対の結果になった． なぜこのようになるか…

細かい機能の最適化をあきらめて、探索アルゴリズムを実装してhttp://www.radagast.se/othello/ffotest.html FFO endgame test suiteにある終盤解析を実際にやってみた。 最前手は正解を出力したが、そこまでの時間は以下の通りだった。 手の順位付けを最低…

このプログラムのアルゴリズムには標準的な手法のみを使用しているのだが、一つの配置を128bitの値一つで示すことで白番と黒番を64bitシフトで簡単に入れ替える事ができる。 そのためMaxノードとMinノードで関数を分ける必要はない。 ゲームが終了したかどう…

昨日条件分岐が問題ではないかと言ったが、実際は条件分岐を削ると特定の（軽い）パターンを繰り返すために速くなったように見えただけだった。 そして考えてみれば、5Mnpsというのは1ノードあたり640クロックの消費ということになる。 着手可能位置の検出が…

一生懸命最適化したつもりでまたベンチマークをとってみたが，やはり非常に遅い． 4-5Mnps程度の速度しかでない． この原因として思い当たるのが，探索関数の再帰呼び出しだ． 関数を再帰的に呼び出すと，そのとき使用していた変数をメモリに待避させなけれ…

以前SPUで乱数を使うためにメルセンヌツイスターを実装した． この時はただコードを書いただけで全く効率化していないものだったので，少し調べてみたらMMXを使用したSFMTというものがあるそうで，速いらしいとソースコードをダウンロードしてみた． しかし…

以前やったN-Queen問題では，コードのコンパクトさを期待してCで全て書いていた． しかし，現在は全てC++で書くようにしている． なぜかというと，単純に表記が自由だということもあるが，128-bit代入で警告を出さないことと，参照を用いた関数をインライン…

いろいろと基本的なところから細かいベンチマークをとりながら再構築をしてみたが、最初に思っていたよりもずっとLoad/Storeが遅い事に気がついた。 今回、駒の効きが八方向にあるので８要素の配列を使っていたのだが、コンパイラの最適化でレジスタに格納し…

ひっくり返す関数が悪い訳ではなかったようだ。 とにかく条件分岐のコストが高過ぎるのが原因らしい。 一生懸命最適化したつもりの関数も全く速くならなかったが、関数内の条件分岐を削っただけで５倍速くなった。 枝刈りはどうしても条件分岐を使わない訳に…

とりあえずαβカットを入れた1SPU版の探索プログラムまで作成してどの程度の効率か調べてみた。 しかし中間評価も手の善し悪しによる並べ替えも入れていないにも関わらずScrZebraの半分以下の探索性能だった。 これは一度全ての場所でおけるかどうかを調べ、…

反転の方法を考えていたが、今ひとつよいアイデアがないので前回の置ける位置の走査時に、すべての方向の結果の論理和をとるのではなく、8要素のベクトルに格納して利用することにした。 例えば上方向へひっくり返すには以下のようにした。 vector unsigned …

このコードがどれくらいの効率を持っているかだが、Zebraの日本語訳のサイトには「200-300クロック」と書いてあったように記憶している。 前回のコードを８方向分に膨らませ（全てのステップで直前のビット演算への依存が高いので、IPCを稼ぐために２方向分…

N-queen問題を解いてみる事で、SPUを128bitの論理回路として用いる事で、ある程度の速度のプログラムが書ける事は分かった。 次にどのような目標を立てるかということだが、以前から少し興味のあった話題として、オセロのプログラムを作成してみたい。 最初…