Unityによる大富豪の作り方 1 ～ビット演算(基礎)～

はじめに
ビット演算(基礎)

はじめに

Unityで大富豪を作ってみたのでそのAIの作り方を書いていきます。AIといっても機械学習とかではなく、ヒューリスティック(経験則的にある場合はAを実行、別の場合はBを実行するという感じで条件を設定し、正解を導ていく)なものです。初心者にも比較的わかりやすいと思います。また、Unityの機能を使っているのは主にUI部分なのでロジックの部分は他のゲームエンジンや言語でも使えるはずです。
最後まで作り上げることを目的としたので大富豪の仕様は

カードの枚数は52枚でジョーカーは無し。
特殊ルールは4枚の同じ数字の組(グループ)、または5枚以上の階段での革命のみ。
カード交換は無し。

と超シンプルなものにしました。

ビット演算(基礎)

まず、52枚のカードを64ビットで表現(BitCard型)します。詳しい説明は下記サイトを参考にしてください。後編の中盤あたりまで理解すれば大丈夫だと思います。 qiita.com

qiita.com

今回のAIに必要なビット演算をいくつか紹介します。

1の数を数える

public int CountBit(ulong bit)
{
    bit = (bit & 0x5555555555555555) + (bit >> 1 & 0x5555555555555555);
    bit = (bit & 0x3333333333333333) + (bit >> 2 & 0x3333333333333333);
    bit = (bit & 0x0f0f0f0f0f0f0f0f) + (bit >> 4 & 0x0f0f0f0f0f0f0f0f);
    bit = (bit & 0x00ff00ff00ff00ff) + (bit >> 8 & 0x00ff00ff00ff00ff);
    bit = (bit & 0x0000ffff0000ffff) + (bit >> 16 & 0x0000ffff0000ffff);
    bit = (bit & 0xffffffffffffffff) + (bit >> 32 & 0xffffffffffffffff);

    return (int)bit;
}

var n = 0x1110ul;
Debug.Log(CountBit(n));
// 3

一見複雑ですが、まず2桁ごとの1の数を数えて、次に4桁ごとに数え、さらに8桁ごと…と繰り返すだけです。詳しくは下記サイトを参考にしてください。

qiita.com

最も下位にある1だけを残した値を取得

//最も下位にある1だけを残して取得
protected ulong GetLeastSignificantBit(ulong bit)
{
    var comp = ~bit + 1;

    return bit & comp;
}

var n = 0x1110ul;
var b = GetLeastSignificantBit(n);
Debug.Log(b.ToString("x4"));
//0010

これは特に問題ないですね。2の補数とANDしてるだけです。

最も上位にある1だけを残した値を取得

//最も上位にある1だけを残して取得
protected ulong GetMostSignificantBit(ulong bit)
{
    var b = bit | (bit >> 1);

    b |= b >> 2;
    b |= b >> 4;
    b |= b >> 8;
    b |= b >> 16;
    b |= b >> 32;

    return b ^ (b >> 1);
}

var n = 0x1110ul;
var b = GetMosttSignificantBit(n);
Debug.Log(b.ToString("x4"));
//1000

これはちょっとわかりづらいですね。
例えば、00100101の最も上位の1だけの値 00100000 を取り出すとすると

00100101 とこれを右1ビットシフトしたもの
00010010 をORし
00110111 を得ます。

次に今得た値
00110111 とこれを右2ビットシフトしたもの
00001101 をORし
00111111 を得ます。

右シフトしてORを繰り返すことで、最上位の1より下位がすべて1の値を得ることができました。

あとはこのすべてが１になったもの
00111111 とこれを右に1ビットシフトしたもの
00011111 の排他的論理和をとれば
00100000 となり、最上位の1だけの値を取得できます。

最も下位(上位)にある1の桁を取得

public class Bit
{
    private readonly static ulong M = 0x03F566ED27179461;
    private readonly static int[] table;

    static Bit()
    {
        table = new int[64];
        var m = M;

        for (int i = 0; i < 64; i++)
        {
            table[m >> 58] = i;
            m <<= 1;
        }
    }

    //最も下位にある1の桁を取得
    public int BitScanForward(ulong bit)
    {
        if (bit == 0) return 64;

        var d = bit & GetLeastSignificantBit(bit);
        var i = (d * M) >> 58;

        return table[i];
    }

    //最も上位にある1の桁を取得
    public int BitScanReverse(ulong bit)
    {
        if (bit == 0) return -1;

        var d = bit & GetMostSignificantBit(bit);
        var i = (d * M) >> 58;

        return table[i];
    }
}

var n = 0b01011010ul;
var i = BitScanForward(n);
Debug.Log(i);
//1

var n = 0b01011010ul;
var i = BitScanReverse(n);
Debug.Log(i);
//6

これはさっぱりわかりませんね(笑)。詳しくは下記サイトを参考にしてください。

siokoshou.hatenadiary.org

n個のものの中からr個のものを選択してできるすべての組み合わせを取得

//n個のものの中からr個のものを選択してできるすべての組み合わせを取得
public List<int> GetConbinations(int n, int r)
{
    var bits = new string[n];

    for (var i = 0; i < n; i++)
    {
        if (n - r <= i) bits[i] = "1";
        else bits[i] = "0";
    }

    var combinations = new List<int>();
    int bit = Convert.ToInt32(String.Join("", bits), 2);

    if (n == r)
    {
        combinations.Add(bit);
        return combinations;
    }

    int low;
    int high;

    do
    {
        combinations.Add(bit);

        low = n;

        //最も下位にある1の桁を取得
        for (int i = 0; i < n; i++)
        {
            if ((bit & (1 << i)) > 0)
            {
                low = i;
                break;
            }
        }

        high = n;

        //lowより上位で、最も下位にある0の桁を取得
        for (int i = low + 1; i < n; i++)
        {
            if ((bit & (1 << i)) == 0)
            {
                high = i;
                bit |= (1 << high);
                break;
            }
        }

        if (high < n)
        {
            //highより下位のビットを0にする
            bit &= ~((1 << high) - 1);
            int cnt = high - low - 1;
            //最下位から cnt-1 ビット分をすべて1にする
            bit |= (1 << cnt) - 1;
        }
    } while (high < n);

    return combinations;
}

var conbs = bit.GetConbinations(5, 3);

conbs.ForEach(c =>
{
    Debug.Log(System.Convert.ToString(c, 2).PadLeft(5, '0'));
});
//00111
//01011
//01101
//01110
//10011
//10101
//10110
//11001
//11010
//11100

これもわかりづらいですね。イメージとしては

1つ上の桁が0になってる1を探す。
その0と1を交換する。
残りの1を最下位から並べる。

を繰り返すって感じです。実行結果を見ながら考えればわかると思います。