携帯電話におけるオセロプログラム - 気になったネタリンク

BitBoardで実装しよう

色々実験しています。(オセロは商標なんで、本当はリバーシですね)
iアプリで505i程度でまともに動くものを作りましょう。
　
とりあえずこのサイト。
http://vivi.dyndns.org/W/257
BitBoardにおいて、対象の位置に石を置いた場合に反転する位置を示したMaskを取得するのが目的です。
ループを使うパターンと、ループを使わないbit演算パターンの2つが載っていますね。
これのループ使わない版を使ってみたのですが、どうもいまいちなのです。
　
試しにループ版でテストしてみたところ、計測上2倍は速い。はて…。
と考えてみたところ、わかりました。
オセロの場合、whileの探査打ち切りが早いのです。そんなに同じ色が連続することが多くない。
　
ループを使わないパターンですと、どんな盤面でも同じ時間で調査できるというメリットはありますが、美味しくないですね。

[プログラム]if文が思いのほか速い？

上のwhile探査ですが、ちょっとした気まぐれでwhileの前に1つif文をかませてみました。

if (となりに敵石がある)
{
    while(となりに敵石がある限り)
    {
        //  省略
    }
    if (となりに自石がある)
    {
        lRet = 敵石MASK;
    }
}

こっちのほうが速い。多分1つ目でダメになるパターンが多いからだと思うのですが…。
はて？
まぁ2〜3%程度の誤差なので、可読性を考慮してwhileだけのほうにしておきましょう。

longのシフト遅い

longのシフトが遅い！
そりゃJavaはlongを32bit2つでエミュレートしているわけですから、遅いのも当然といえば当然。
うーむ。
long型を見て、いくつbitが立っているか調べるルーチンです。
処理が遅い順に並べます。

lBits = (lBits & 0x5555555555555555L) + (lBits >> 1 & 0x5555555555555555L);
lBits = (lBits & 0x3333333333333333L) + (lBits >> 2 & 0x3333333333333333L);
lBits = (lBits & 0x0f0f0f0f0f0f0f0fL) + (lBits >> 4 & 0x0f0f0f0f0f0f0f0fL);
lBits = (lBits & 0x00ff00ff00ff00ffL) + (lBits >> 8 & 0x00ff00ff00ff00ffL);
lBits = (lBits & 0x0000ffff0000ffffL) + (lBits >> 16 & 0x0000ffff0000ffffL);
lBits = (lBits & 0x00000000ffffffffL) + (lBits >> 32 & 0x00000000ffffffffL);
return (int)lBits;

int n = 0;
while(0 != lBits)
{
	n++;
	lBits &= lBits - 1;
}
return n;

a = (int)(lBits & 0x00000000FFFFFFFFL);
b = (int)((lBits >>> 32) & 0x00000000FFFFFFFFL);

a = (a & 0x55555555) + (a >> 1 & 0x55555555);
a = (a & 0x33333333) + (a >> 2 & 0x33333333);
a = (a & 0x0f0f0f0f) + (a >> 4 & 0x0f0f0f0f);
a = (a & 0x00ff00ff) + (a >> 8 & 0x00ff00ff);
a = (a & 0x0000ffff) + (a >>16 & 0x0000ffff);
b = (b & 0x55555555) + (b >> 1 & 0x55555555);
b = (b & 0x33333333) + (b >> 2 & 0x33333333);
b = (b & 0x0f0f0f0f) + (b >> 4 & 0x0f0f0f0f);
b = (b & 0x00ff00ff) + (b >> 8 & 0x00ff00ff);
b = (b & 0x0000ffff) + (b >>16 & 0x0000ffff);
return a + b;

桁溢れとかが関係無い場合においては、longは一旦手動でintにばらして処理したほうが速いようです。