スポンサード リンク

T.Ishii's Software Library

HTML5 レトロ風ゲーム館

無料ブログはココログ

« コード変更を始めた | トップページ | 速くはならないので »

Flip処理の違いかなあ

昨日書いた様に、64Bit版MasterReversiの完全読み性能がEdaxの64Bit版に劣っているので変更を始めたのだが、Edax4.0.5の時点では似たような性能だったのが、Edax4.3で結構な差がついてしまった原因は何だろう? と、Edaxのソースを確認するとFlip処理が変わっていた。

作者的には、Edaxの処理ルーチンに今回エンジン対局をしている「Edax+Unified Book 2010」の作者であり、かつ、Booby Reversiの作者でもあるOkuhara氏がFlipルーチンを提供していた、というのは、Edaxのホームページを見て知っていたのだが、これは、32Bit版だけの話と思っていた。

しかし、64Bit版のソースを見てみても、FlipルーチンのAuthor名には、Edaxの元々の作者である所の「Richard Delorme」氏と共に「Toshihiko Okuhara」氏の名前があり、かつ、Okuhara氏の名前が無かった4.0.5のソースコードで使われていたアルゴリズムとは異なるアルゴリズムになっていた。

と、いう事で、Edax4.3で使われているFlip処理というのは、多分、Okuhara氏が提供したモノだと思われるのだが、かなり、トリッキーだ。

で、どんな風になっているのか、というと、元々のEdax4.0.5の処理ルーチンというのは、作者も良く使うテーブル参照方式になっていて、パターン上のデータを元に8ビットのデータを作成し、その8ビットデータを引数にしてテーブルデータを引っ張ってくる格好になっている。

もっとも、この方式にもトリッキーな所はあって、縦方向だとか斜め方向のパターンデータを配列用の8Bitデータにするために、トリッキーな掛け算を使っている。何処がトリッキーなのか、というと、64Bitx64Bitの演算を行い、桁あふれする事を上手く使って、残されるビット部分に欲しいデータが残る様な演算を行っている訳だ。

ただ、MasterReversi Ver1.4.0の開発時に書いたと思うのだが、テーブル参照方式というのは、メモリアクセスがネックになるので見た目上は綺麗でも速度が出ない事も多い。

このため、MasterReversi的には、Edax4.0.5のFlip方式を見た上で、既存方式は変えなかったのだが、多分、Okuhara氏が考案したと思われるEdax4.3のFlipルーチンでは、多くの場合、テーブル参照を回避している。

で、Edax4.3のFlip方式の何処がトリッキーなのか、というと、ビットボードにある石の連続性を足し算の桁あふれの状態を使って抽出している所だ。

例えば、黒石として00011100Bというパターンがあった時、00000010Bという位置に白石を置いた場合に、ひっくりかえる石に必要になる条件は何なのか、というと、まず、その隣の00000100Bは黒で無ければならず、それから連続している黒である事が必要条件になる。

問題は、その連続性をどうやって確認するか、になるのだが、Edax4.3では、足し算を使って、その桁上げを利用している訳だ。

00011100B+00000100B=00100000Bとなるので、黒が連続している場合、その位置は0で埋め尽くされる格好になる。そして、もし、隣に黒が無かった場合には、例えば、00011000B+00000100B = 00011100Bとなり、0にはならない。

で、もし、隣が黒だった場合、その黒の連続性が無くなる位置のビットが1になるのだが、この1の位置にあるのは、白でなければひっくり返す事は出来ない。しかし、現時点では、空白かもしれない。

なので、Edax4.3のFlipルーチンでは、そのデータと白とのAndをとって、もし、白だった場合には、1が残り、空白だった場合には、0になる様にしている。当然の事ながら、隣が黒ではなかった場合には、白の位置に1が立つ事は無いので、この場合は白とAndを取るとデータは0になる。

この段階で、もし黒をひっくり返せる場合には、上記の1が残っていて、そうではない場合には、All0になるのだが、Edax4.3のFlipルーチンでは、All0ではなく、ひっくり返せる石がある場合には、ひっくり返される石のビットパターンを得るために、今度は1を引き算する訳だ。

そうすると、00100000B-00000001B = 00011111Bになるのだが、着手位置は00000010Bなので、関係ないビットを消去するために、11111100BとAndすると、00011100Bになり、ひっくり返せる石が確定する。

上記で重要なのは、桁あふれするかどうか、という事なので、関係ないビット位置を1で埋めておけば、関心があるビット位置だけに注目できる、という事だ。

なので、縦方向でも横方向でも斜め方向でも同様のアルゴリズムで処理が行えるし、テーブル参照方式ではないので、メモリアクセスが性能を劣化させる事もない。

ただし、桁あふれを使っている関係で、着手位置と黒石の位置関係によっては、上手く使えない場合も多いので、Edax4.3では従来方式との併用の形になっている。

と、いう事で、Edax4.3のFlip方式はかなりトリッキーになっていて、多分、その分、性能向上していると思われるので、MasterReversi的にも、Flip処理の見直しは必要かもしれない。

= この記事に関連する公開中ソフト =

MasterReversi for Windows

MasterReversiForAndroid

(2014/06/12追加)

« コード変更を始めた | トップページ | 速くはならないので »

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/534482/59125140

この記事へのトラックバック一覧です: Flip処理の違いかなあ:

« コード変更を始めた | トップページ | 速くはならないので »

2017年4月
            1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30            

広告

プライバシーポリシー

  • 当サイトでは、第三者配信による広告(Google Adsense)サービスを利用しています。

    Google を含む第三者配信事業者は、Cookie を使用して、ユーザーのウェブサイトでの閲覧履歴に基づく広告を配信します。 Google 広告 Cookie を使用することにより、Google や Google のパートナーは当サイトや他のサイトへのアクセス情報に基づく広告をユーザーに表示できます。

    Cookieを無効にする設定およびAdsenseに関する詳細については、以下のリンクを参照下さい。

    広告 - ポリシーと規約 - Google