大富豪AIにおけるビット演算の利用 後編

ビット演算テクニックAdvent Calendar 2016 投稿です。

トランプゲームの大富豪におけるビット演算の利用について、前編に引き続き書いていきます。
大富豪AIにおけるビット演算の利用 前編
前編と同じ仮定を置いているので、前編の前半部分を先にご覧いただければ幸いです。

4ビットごとの情報の並列計算

前編にて、カード集合を64ビット整数1つで表現しました。
その長所として、集合演算の簡単さや階段系演算の簡略化がありましたが、
同一ランク内での処理も1度の演算でパラレルに行うことが可能です。
より一般的に言えば、64ビット内の各4ビットに同じ処理を一度で掛けられるということです。
8ビット以上ではベクトル演算によって並列計算することも有りえますが、
現状では4ビットごとの演算は1つの整数として計算することになります。

では大富豪にも使えそうな代表的な演算を順に見ていきます。
以下4ビットごとのビットマッピングを多用するので、
略記（繰り返しの一部のみの二進数表記）を用います。

0000 = 0x0000000000000000  0001 = 0x1111111111111111 
0010 = 0x2222222222222222  0011 = 0x3333333333333333
0100 = 0x4444444444444444  0101 = 0x5555555555555555
0110 = 0x6666666666666666  0111 = 0x7777777777777777
1000 = 0x8888888888888888  1001 = 0x9999999999999999
1010 = 0xaaaaaaaaaaaaaaaa  1011 = 0xbbbbbbbbbbbbbbbb
1100 = 0xcccccccccccccccc  1101 = 0xdddddddddddddddd
1110 = 0xeeeeeeeeeeeeeeee  1111 = 0xffffffffffffffff

4ビットごとのビット数を数える

ビット数を数えるアルゴリズムを途中段階まで使うことで、各4ビットごとのビット数が求まります。
なお、本記事ではコードはC++とし、64ビット整数をuint64_t型で扱います。

uint64_t count(uint64_t c) {
    c = (c & 0101) + ((c >> 1) & 0101);
    return (c & 0011) + ((c >> 2) & 0011);
}

こうして求めた数値の各4ビットごとには4ビットの中のビット数（0 ~ 4）が入るので、
4ビットごとの配列のように利用できます。
以下この出力を枚数型と呼びます（各ランクの札の枚数を表すため）。

4ビットごとのビット数の位置にビットを立てる

ビット数を上のように計算できましたが、ビット数が絡んだアルゴリズムにおいてまだ使いにくい場合があります。
大富豪においては以下のような状況があるでしょう。

「各ランク内に2枚あるランクだけを抽出したい」

こういった場合に、枚数型では不十分です。各ランクを見れば2枚どうかは確認できますが、
全体から2枚のところだけ取り出すのは少し手間がかかります。

そのため以下の型（枚数位置型と呼ぶことにします）を持っておくと便利です。

「4ビットごとのn番目のブロックのビット数が0ならばビットを立てず、
k (1 <= k <= 4)ビットならば4n + k - 1番目のビットを立てる」

トランプの手札を使ってビット配置を具体的に見ていきましょう。
以下、「1」とある場所にビットが立っていて、それ以外の場所には立っていないとします。

カード集合 { ♣️３, ❤️４, ♣️５、❤️５, ♠️５ ♦️６, ♣️ J, ❤️ J, ♠️２ }

BitCards型（素のカード集合）

	3	4	5	6	7	8	9	T	J	Q	K	A	2
C	1		1						1
D				1
H		1	1						1
S			1										1

枚数位置型

	3	4	5	6	7	8	9	T	J	Q	K	A	2
1	1	1		1									1
2									1
3			1
4

このように各ランク高々1ビットで枚数を表現できます。

ビット配置は前編で示した、最下位ビットから1ランク4ビットのシンプルなマッピングを用いているとします。
このとき以下のように特定の枚数のランクのビットだけ取り出すことができます。

特定のビット数のブロックの抽出

uint64_t pick2ByPqr(uint64_t pqr) {
    return pqr & 0010;
}

枚数ごとにビット位置を定めたことで、「2枚」 を表すビットだけを簡単に取り出せました。
同様に、「3枚以上」や「1枚 or 4枚」 のような取り出し方もできます。

枚数位置型の生成は以下のように行えます。
ただもっと高速な生成方法がありそうなので、わかる方がいればご教示いただきたいです。

→本記事を最初に公開してから約7年、ビット演算を大富豪AIに適用してから9年でより高速な方法が見つかりました！！！！！！！！！

（新）枚数位置型の生成（枚数型から）

uint64_t locate(uint64_t qr) {
    return qr + (qr & 0100) + (qr & (qr >> 1));
}

（新）枚数位置型の生成（ビット集合から）

新しい方法では一度枚数型を経由し、上記の変換を適用します。

uint64_t countToLocate(uint64_t c) {
    uint64_t qr = count(c); // 枚数型に変換
    return locate(qr);
}

以下が2016年から記載していた古い方法も残します。
こちらは命令数が多く、ほとんどのコンピュータで新しい方法の方が速いはずです。
（ただし、加減算を使わずビット演算のみのため、加減算が遅い環境ではこういった方法もありえます）

（旧）枚数位置型の生成（枚数型から）

uint64_t locate(uint64_t qr) {
    uint64_t iqr = ~qr;
    uint64_t qr_l1 = (qr << 1);
    return (0001 & qr & (iqr >> 1)) | (0010 & qr & (iqr << 1)) 
           | ((qr & qr_l1) << 1) | (qr_l1 & 1000);
}

（旧）枚数位置型の生成（ビット集合から）

uint64_t countToLocate(uint64_t c) {
    uint64_t a = (c & 0101) + ((c >> 1) & 0101);
    uint64_t r = a & (a << 2) & 1000;         // 4ビットあったところを4に配置
    uint64_t r3 = (a << 2) & (a >> 1) & 0100; // 3ビットあったところを3に配置
    r3 |= a & (a << 1) & 0100;

    // 残りは足すだけ ただし3, 4ビットがすでにあったところにはビットを置かない
    uint64_t r12 = (((a & 0011) + ((a >> 2) & 0011))) & 0011;
    if (r3) {
            r |= r3;
            r |= r12 & ~((r3 >> 1) | (r3 >> 2));
    } else {
            r |= r12;
    }
    return r;
}

ビット集合からの特定のビット数のブロックの抽出

枚数位置型を計算すれば0以外の任意のビット数（の集合）のブロックを抽出することが可能ですが、
特定のビット数の部分だけ抽出できれば良い場合に、枚数位置型を計算するコストが勿体無い場合もあります。

実際に特定の枚数のブロックを抽出する操作を挙げていきます。
こちらの演算についても、より高速な処理を教えていただければ嬉しいです。

ビット集合から4ビットのブロック抽出

uint64_t pickUp4(uint64_t c) {
    c = c & (c >> 1);
    return c & (c >> 2) & 0001;
}

ビット集合から3ビットのブロック抽出

uint64_t pickUp3(uint64_t c) {
    uint64_t a = c & (c >> 1);
    uint64_t b = c ^ (c >> 1);
    return ((a & (b >> 2)) | ((a >> 2) & b)) & 0001;
}

1ビットと0ビットの部分の抽出は、それぞれpickUp3()とpickUp4()にnotを取ったものを投げれば良いです。

2ビットの場合はどうやるんでしょう。枚数型を経由すれば以下のようにできますが。

枚数型から2ビットのブロック抽出

uint64_t pickUp2ByQr(uint64_t qr) {
    return (qr >> 1) & ~qr & 0001;
}

ビット集合からの特定のビット数集合のブロックの抽出

抽出したいビット数が集合として与えられる場合についても代表的なものを載せます。

1ビット以上のブロック抽出

uint64_t pickUp1234(uint64_t c) {
    uint64_t a = c | (c >> 1);
    return (a | (a >> 2)) & 0001;
}

枚数型から奇数枚数のブロック抽出

uint64_t pickUp13(uint64_t qr) {
    return qr & 0001;
}

大富豪における4ビットごと情報の差分更新

大富豪において枚数型や枚数位置型を利用することの利点として、
大富豪の役を構成するカード集合に対してこれらの型の差分計算が簡単であることがあります。

ここではプレーヤーの手札から大富豪における役が出された場合の枚数型と枚数位置型の差分更新を、
グループ系（シングル含む）の役、階段系の役のそれぞれに対して見ていきます。

枚数型の差分更新

グループ系

uint64_t nextQr(uint64_t qr, GroupMeld m) {
    return qr - (m.qty() << (m.rank() * 4));
}

階段系

uint64_t nextQr(uint64_t qr, SequenceMeld m) {
    diff = ((1ULL << (m.qty() * 4)) - 1ULL) << (m.rank() * 4) & 0001;
    return qr - diff;
}

枚数位置型の差分更新

役の表現は適当なクラスを置いています。
rank()で役の札のランク（強さ）、qty()で枚数が得られるものとします。

グループ系

uint64_t nextPqr(uint64_t pqr, GoulpMeld m) {
    uint64_t mask = 15ULL << (m.rank() * 4);
    return (pqr & ~mask) | (((pqr & mask) >> m.qty()) & mask);
}

階段系

uint64_t nextPqr(uint64_t pqr, SequenceMeld m) {
    uint64_t mask = ((1ULL << (m.qty() * 4)) - 1ULL) << (m.rank() * 4);
    return (pqr & ~mask) | ((pqr >> 1) & mask & 0111);
}

大富豪における役は、同じランクのカードのみで構成されたり
同じスートの連続したランクのみで構成されたりするためこのように部分的に情報更新ができます。

一方で、カード交換等の任意のカードの組み合わせが増減される処理においては
全体を計算しなおすのが良いと考えられます。
（ただし枚数が1枚であることが分かっていれば、1枚分更新した方が速いでしょう）

グループ系演算

ここまで一般的な4ビットごとの演算を見てきました。
これらを組み合わせることでグループ系の演算が行えます。

階段系演算と異なり、グループ系演算は場役の枚数やスートしばりの有無によって
異なる演算を行うことが高速である場合も多いと思われます。
そういった場合を全て網羅するのは大変なので、ここでは基本的なパターンの紹介に留めます。

スートしばり無しの場合

まず場役（n枚とする）と同じ枚数だけ持っているランクの役だけを出す場合を考えます。

スートしばり（提出可能なスートの限定）が無い場合は、
枚数位置型が差分更新されている場合には枚数位置型のnビットの部分を抽出し、
枚数位置型が無い場合にはビット集合からnビットの部分を抽出する先ほどのアルゴリズムが使えます。

次に場役より多い枚数持っているランクについては、それぞれの枚数で抽出して

Melds groupByPqr(uint64_t pqr, int n) { // nは場役の枚数
    uint64_t a = pqr & 1000;
    while (a) {
        4枚ある場合に全てを生成
    }
    uint64_t b = pqr & 0100;
    while (b) {
        3枚ある場合に全てを生成
    }
    ... n まで生成
}

とするのが高速なように思いますが、例えば探索目的なら生成速度より良さそうな（or 良くなさそうな）順に
並んでいることが重要なので用途に合わせた処理を行うべきでしょう。

スートしばりありの場合

スートしばりがある場合の役の生成です。
ここでのスートしばりのルールは、場の役と全く同じスート集合の役しか出せないというルールを考えます。
このときスートしばりがあっても出せるランクを以下のように抽出できます。

uint64_t groupInSuitLock(uint64_t c, Meld boardMeld) {
    unsigned s = boardMeld.suits();
    return pickUp4(c | (0001 * (15 - s)));
}

場役のスートsによって限定するのではなく
場役以外のスート15 - sを補充するところがポイントです。

前者では、限定した後場役と同じ枚数が残っていることを判定することになるので
場役の枚数によって違う処理が続くことになりますが、
このように補充によって書けば１つのランクの全ビット存在判定により
場役のサイズに関わらず同じコードが動きます。

無支配型

グループ系の演算に使えそうなものが沢山ありましたが、
大富豪におけるビット演算で非常に面白いのが最後に紹介する無支配型です。

無支配型 定義

以下のように定義される型です。

64ビット整数であり、枚数位置型の全てのビットに対して、
未満のランク、以下の枚数の全てのビットが立った形式

枚数位置型の説明の例として挙げたカード集合に対して計算してみます。

カード集合 { ♣️３, ❤️４, ♣️５、❤️５, ♠️５ ♦️６, ♣️ J, ❤️ J, ♠️２ }

のとき枚数位置型（再掲）

	3	4	5	6	7	8	9	T	J	Q	K	A	2
1	1	1		1									1
2									1
3			1
4

無支配型

	3	4	5	6	7	8	9	T	J	Q	K	A	2
1	1	1	1	1	1	1	1	1	1	1	1	1
2	1	1	1	1	1	1	1	1
3	1	1
4

定義通りに計算するとこのような階段状のビット列になります。
使用方法はとりあえず置いておいて、この型の計算方法については以下のように行えます。

uint64_t noDominance(uint64_t pqr) {
    uint64_t nd = 0;
    pqr >>= 4;
    while (pqr) { // 無支配ゾーンがまだ広いはず
        int index = bsr(pqr); // ランク上の方から順に
        nd |= ndMask(index); // このゾーンに対して返せることが確定
        pqr &= ~nd; // もう関係なくなった部分は外す
    }
    return nd;
}

ここで、ndMask()関数は枚数位置型のビットに対して、
引数のインデックスのランク以下で枚数以下の全てのビットのマスクを返す関数とします。

テーブル参照が高速だとは思いますが、毎回ビット演算で計算する場合は以下のようにできます。

uint64_t ndMask(int i) {
    return (((1ULL << (i + 1)) - 1ULL) & 0001) * ((1 << ((i & 3) + 1)) - 1);
}

掛け算の左側の項でランク以下の0b0001の繰り返しを計算、
右側の項で枚数以下の集合を計算することで目的のマスクを得ています。
他の計算手順もあるでしょう。

さて、無支配型を計算する関数ですが、枚数位置型の各ビットでループするので、
一見カード集合に含まれるランクの種類数のオーダーでの計算量が掛かるように見えますが、
実際にはこの計算のループは最大4回しか回らず、より少ない回数で終了することが多いです。

実際に計算手順を見てみると、

1回目のループ後
nd　（無支配型の計算途中）

	3	4	5	6	7	8	9	T	J	Q	K	A	2
1	1	1	1	1	1	1	1	1	1	1	1	1
2
3
4

pqr (枚数位置型、ループ開始前にランク1つ分下にシフトされていることに注意)

	3	4	5	6	7	8	9	T	J	Q	K	A	2
1
2								1
3		1
4

pqr &= ~nd によって、pqrの1ビットの部分が全て消えてしまったわけですが、
これらのビットが仮に消えなかったとしても今後の計算には影響を与えません。
1枚以下で、各ビット以下のランクのビットはすでに埋められてしまったためです。

この例の場合にはループ回数は3回となります。
上のランクに枚数が最も多いものがあったり、
各ランクに1枚ずつしか含まれない場合には1回で終了します。

枚数位置型 - 無支配型 支配性判定

無支配型の基本的な使い方としてグループ系の役の支配性（確実に場を流せるかどうか）
の判定が挙げられます。

以下自分の提出役がグループ系であり、
スートしばり等の特殊効果による支配性の変化が無い場合を考えます。

事前に「自分以外の手札のカード集合の無支配型」、
つまりまだ提出されていない残りカード集合から自分のカード集合を引いたものの
無支配型が計算されているとします。

このとき自分の提出役により他全員を支配できることは以下のように判定できます。

bool dominate(uint64_t movePqr, uint64_t oppNd) {
    // meldPqr: 自分の役の枚数位置型
    // oppNd: 自分以外の手札のカード集合の無支配型
    return !(movePqr & oppNd);
}

さてここで無支配型は一体どういった性質を持つかが問題になりますが、
無支配型で立っている全てのビットに対して以下の性質があります。

「ビットをグループ型の役の枚数位置型と解釈した際に、
カード集合のより上のランクに、それ以上の枚数があるランクがある」

上のランクにより多い枚数があるものがあるということは、
そのランクのグループを出しても返される可能性があることです。

逆に、無支配型でビットが立っていない位置のグループについては、
返される心配はありません。

以上より、役の枚数位置型と相手無支配型の&をとることで、
場を支配できるかどうかが判定できるということになります。

ただし、相手の手札の最大枚数が2枚のときに3枚グループが支配的である、という類の判定は
このままではできないので、別途枚数を比較するなり無支配型を限定したりする必要があります。

枚数位置型 - 無支配型 空場必勝判定

最後に、無支配型のさらに有効な利用として必勝判定法を紹介します。
多人数ゲームである大富豪の必勝条件はルールによって様々ありますが、
ここでは最も単純な、
「空の場からグループ系の役を出し続けて、他の誰も出せずに勝つ」
いわゆる完全勝利の場合を考えます。

bool perfectWin(uint64_t myPqr, uint64_t oppNd){ 
    // myPqr: 自分の手札の枚数位置型
    // oppNd: 自分以外の手札のカード集合の無支配型
    return !any2(myPqr & oppNd);
}

ただしany2()は2ビット以上が経っているかどうか判定する関数とします。
any2()の実装はビット数を数えるか、ビット演算によって以下のように行えます。

uint64_t any2(uint64_t c) {
    return c & (c - 1);
}

前編にて、c & (c - 1) で立っているビットのうち最も下のビットのみ消えることを紹介しました。
最下位のビットが消えてもまだ0でなければ2ビット以上が立っていたことになります。

では元のperfectWin()関数に戻ります。
先ほど役の支配性判定で述べたように、
枚数位置型 & 無支配型
で立つビットは「支配できていない」ことを示します。
つまり、ここで立ったビットの数が、グループとして提出した際に支配できない役の数を表しています。

ここで、完全勝利のための条件を考えてみると、

1. 最後の1つの役は支配できなくても良い
2. それ以前に出す役は全て支配できる必要がある

と表現できます。
ですので結局、完全勝利のためには 枚数位置型 & 無支配型が1ビット以下 であればよいことになります。

深さ優先探索を行えば指数時間、
上がり役を固定してそれ以外全て支配できるか調べるという処理でも多項式時間
かかる完全勝利の判定を定数時間で行うことが出来ました！

最後に

ここまでご覧いただきありがとうございました。
リアルな大富豪を扱う場合には、今回紹介したような演算をベースとしつつも
多くの分岐や特殊な状況の処理が必要になります。
例えば「革命」という役の強さが逆転するルールがある場合には、
通常オーダーの支配型と反転オーダーの無支配型をどちらも用意しておくことで対応できます。

また今回はビット演算による実装面の記事ということで、
強い大富豪の思考ルーチンをどう作るかについては触れませんでした。
そちらに興味がある方は是非コメントいただけると嬉しいです。

ぜひ楽しい大富豪ライフをお過ごしください！

こちらのブログにて
大富豪の思考アルゴリズムについての私の論文を紹介してくださった方がいます。
ありがとうございます！

ビット演算テクニックAdvent Calendar 2016
残り4日です！まだ空きがあるので是非！