ビット演算テクニックAdvent Calendar 2016 投稿です。
トランプゲームの大富豪におけるビット演算の利用について、
私がこれまでに行ってきたことを書いてみたいと思います。
なお全て64ビット内での話になるので、128ビットや256ビットの演算の知識は必要ありません。
コンピュータで大富豪？
大富豪は人間同士でも非常に楽しいゲームですが、
実はコンピュータ将棋やコンピュータ囲碁と同じようにコンピュータ大富豪の大会もあるのです！
UECda2016
今年の大会は2週間ほど前に終わってしまいましたが、いち大学の学園祭イベントと侮ることなかれ、
現在1位のプログラムはかなり強くなってきています。
不完全情報かつ運の要素が強いゲームなので、少ない試合数では強さを判断することが難しいですが、
大会では1000試合から10000試合のオーダーで試合が行われるので、強さの差があればはっきりと結果に出ます。
各年度の優勝プログラムは大会サイトからダウンロードできます。
人間との対戦環境は標準では無いですが、運営の人に頼むともらえるはずです。
今年のコードも間もなく公開されるそうです。（追記:こちらのページにて公開されました）
なんと今年は日本テレビ系「変ラボ」の5月19日放映分にて
人類代表の手越祐也さんと対決させていただきました。
この記事ではコンピュータ大貧民大会のルールには特化せず、より一般的な状況を想定して考えていきます。
カード集合の表現
トランプのカードは
・ジョーカーなしで52枚
・ジョーカーを含めても53 or 54枚
となり64ビット整数にて任意のカード集合を表現できます。
具体的には、トランプのそれぞれのカードの有り無しを各1ビットで表現します。
以下、面倒なのでジョーカーは無いことにしましょう。
このとき大富豪においては3が一番弱く2が一番強いので、
弱いカードを下側のビットに、強いカードを上側のビットに対応させる実装が直感的です。
| 3 | 4 | 5 | 6 | 7 | 8 | 9 | T | J | Q | K | A | 2 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| C | 0 | 4 | 8 | 12 | 16 | 20 | 24 | 28 | 32 | 36 | 40 | 44 | 48 |
| D | 1 | 5 | 9 | 13 | 17 | 21 | 25 | 29 | 33 | 37 | 41 | 45 | 49 |
| H | 2 | 6 | 10 | 14 | 18 | 22 | 26 | 30 | 34 | 38 | 42 | 46 | 50 |
| S | 3 | 7 | 11 | 15 | 19 | 23 | 27 | 31 | 35 | 39 | 43 | 47 | 51 |
カードの強さの表記は 3,4, ... ,A,2
カードのスートの表記を C（クラブ♣️）, D（ダイヤ♦️）, H（ハート❤️）, S（スペード♠️）
として、各カードに一意な整数を割り振りました。
スートの順序をどうするべきかはルールによると思います。
カード交換のときなどにスート間に優先順位があればその順に並べておくと便利ですし、
なければなんでもよいと思います。
以下、上の表に従って番号が割り振られていることを仮定します。
カードごとの一意な整数を IntCard型 と呼ぶことにしましょう。
さらに64ビット整数のうち下から IntCard 番目のビットだけが立っている形式を BitCards型 とします。
下から指定の位置のビットだけ立てるには1を指定の数分左シフトすれば良いです。
IntCard (♣️４) = 4
BitCards (♣️４) = 1ULL << IntCard (♣️４) = 0x0000000000000010
このBitCardsのビットを増やせばカード集合として表現できます。
ではカード集合に対する演算を1つずつ見ていきましょう。
カード集合に対する基本演算
加算
BitCards (♣️４, ❤️５, ♠️８, ♦️２) = BitCards (♣️４, ❤️５) | BitCards (♠️８, ♦️２)
加算は A | Bで計算できます。A, Bが排他的な場合には + でも同じ結果ですが、
- の両側に同じカードが入っている場合はおかしくなるので | が安全です。
減算
BitCards (♣️４, ❤️５) = BitCards (♣️４, ❤️５, ♠️８, ♦️２) & ~BitCards (♠️８, ♦️２)
減算は A & ~B で計算できます。AがBを包含している場合には - でも同じ結果です。
減算は包含関係のある場合に使うことが多いので私は併用しています。
共通部分
BitCards (♦️２) = BitCards (♣️４, ❤️５, ♦️２) & BitCards (♠️８, ♦️２)
共通部分は & で計算できます。
ここまでカード集合に対する基本的な演算がビット演算で簡単に行えることがわかりました。
配列形式のカード集合表現などに比べて人間のコーディングもCPU上の計算も低コストで行えます。
ただ毎回 IntCard 1つずつからカード集合を構成するのは面倒なので、
ここから代表的なカード集合の生成方法を見ていきます。
カード集合の生成
全てのカード
BitCards (ALL) = (1ULL << (IntCard (♠️２) + 1)) - 1ULL
1ビットだけが立った状態から1を引くと、それより下位のビットに全て1が立ちます。
それを利用して、IntCardが最大のカード（今回の説明では♠️２）より1つ上のビットだけ立てて、
そこから1を引くとそれ以下のカードが全てある状態を作れます。
次にランクやスートに着目してカード集合を生成しますが、
話を簡単にするためカードに書かれた番号と、
カードのRank（強さ）の対応を以下のように書き換えておきます。
| 番号 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | T | J | Q | K | A | 2 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Rank | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
さらにスートにも、表に従って番号（SuitIndexとする）を振ります。
| スート | C | D | H | S |
|---|---|---|---|---|
| SuitIndex | 0 | 1 | 2 | 3 |
このように番号を振ると
IntCard = Rank * 4 + SuitIndex
となり、ランクやスートからカードを構成できます。
また、1ビットのシフトでスートが1つ変わり、4ビットのシフトで1ランク変わることもわかります。
これを利用します。
1つのランクのカード全て
BitCards (ALL r) = 15ULL << (r * 4)
15ULLは BitCards (ALL 最下位ランク) のことなので、
それを r * 4 ビット左シフトすると BitCards (ALL r) が得られます。
また全てのカードの作成と同じようにして、あるランク r 未満のランクのカードを生成できます。
ランク r 未満のランクのカード
BitCards (lower than r) = (1ULL << (r * 4)) - 1ULL
ランク r 未満のカードをカード全体から引くことで、ランク r 以上のカード全体の集合も計算できます。
スートについては、大富豪のゲームの性質を考えると1つのスート（♣️ など）のカードだけでなく
任意のスート集合（♣️ ❤️ など）のカード全体の集合を生成できると便利そうです。
そこでまずスート集合について、これまでの流れを踏まえて以下のように定義します。
Suits ( ♣️ ) = 1U << SuitIndex( ♣️ )
Suits ( ♦️ ) = 1U << SuitIndex( ♦️ )
Suits ( ❤️ ) = 1U << SuitIndex( ❤️ )
Suits ( ♠️ ) = 1U << SuitIndex( ♠️ )
| スート | C | D | H | S |
|---|---|---|---|---|
| Suits | 1 | 2 | 4 | 8 |
これで各スートが1ビットで表現できたので、スート集合についてもカード集合と同様に集合演算を行えます。
例えば
Suits ( ♣️ ♦️ ♠️ ) = Suits ( ♣️ ) | Suits ( ♦️ ) | Suits ( ♠️ ) = 1 | 2 | 8 = 11
任意のスート集合が 0 ~ 15 の値で表現されました。
これを利用して、あるスート集合 s のカード集合を以下のように計算できます。
スート集合 s のカード
BitCards (ALL s) = 0x0001111111111111ULL * s
こんどは乗算が出てきました。
0x0001111111111111ULLは何でしょうか。
これはビットが最下位から4ビットずつの間隔で計13ビット立っているので、
スート番号が最小（今回の説明では ♣️ ）のスートのカード全体の集合を表す BitCards の値を意味しています。
この値にスート集合の値 s を掛けることで、各ランクごとの1のビットが s 倍されます。
0 <= s <= 15 なのでランク間の干渉はありません。
ゆえに、0x0001111111111111ULL * s を計算することで各ランクの 1 が s になるというわけです。
sを16進数表記とすれば、
BitCards (ALL s) = 0x0001111111111111ULL * s = 0x000sssssssssssss
s 中の各ビットはそれぞれのスートの位置に立っているので、
各ランク内でスート集合 s に対応するカードのビットが立っており、
全体としてはスート集合 s のカード全体の集合が計算できていることがわかります。
以上の基本的な演算を組み合わせればカード集合を自由自在に操ることが出来ます。
ビット集合の基本的演算
計算した結果のビット集合から様々な状態を取り出すための基本的な演算について、
2016年時点での一般的なCPUで想定される実装をまとめておきます。
普段からビット演算を行っている方にとって目新しい点は無いかもしれません。
ビット数を数える
役の数を数える時等に使います。
過去にはビット演算で算出する方法などもありましたが、素直にpopcnt命令を使うのが吉です。
（ただしランクごとの枚数を数える場合にはビット演算が役に立ちます。おそらく後編でまとめます）
最下位ビット位置を得る
bsf命令をCPUが用意してくれています。
最上位ビット位置を得る
bsr命令をCPUが用意してくれています。
最下位ビットを得る
a = c & -c
とすると a には c にて立っているビットの内最下位のビットだけが立ちます。
最下位ビットのみ消す
c &= (c - 1)
で立っているビットの内最下位のビットだけが消えます。
特に最下位のビット位置を得る操作と最下位のビットを消す操作は、
役のビット集合を生成した後に1つずつ取り出すときなど非常に役に立ちます。
例えば、シングル（1枚出し）の1枚ずつの下位からの抽出は以下になります。
while (c)
{
IntCard ic = bsf(c);
// ic に関する処理を行う
c &= c - 1;
}
一方で、立ったビットについて調べるときに、以下のようなコードを書くことも考えられます。
for (IntCard ic = IntCard(♣️３); ic <= IntCard(♠️２) ; ic++)
{
if ((1ULL << ic) & c)
{
// ic に関する処理を行う
}
}
（ここでは IntCard 最小が ♣️３ 、最大が ♠️２ であることを前提としています）
さてどちらが高速でしょうか。
特に大富豪においては，カード集合全体に対して一人の手札の枚数が少ないので
疎なビット集合を扱うことが多いです。
さらに役の生成を行った場合には立つビットの数はさらに少なくなりますので、
2016年現在の一般的なCPUでは前者が数倍以上速いと考えて良いと思います。
しかもコードの簡潔さも全く同程度です。
ここから大富豪に特化した演算を紹介します。
階段系演算
階段は大富豪において特徴的なルールです。
♣️ - 345 のように同じスートの連続した数字を役として場に出すことができます。
ルールによっては、異なるスート間で階段を構成してもよいこともあるようですが、
私がこれまでに同じスートのものしか扱ったことがないので、以下こちらのルールにおける実装の話を進めます。
大富豪の基本はシングル（1枚）やグループ（同じランクのカード複数）ですが、
同一のスートのみで階段を構成可能なルールにおいては、
階段周りの計算はグループ（ダブルやトリプルなど）の計算より簡単なことが多いので先に書きます。
唐突ですが、手札（カード集合 c とする）内に存在する2枚階段は以下のように計算できます。
2枚階段の生成
Seq<2>(c) = c & (c >> 4)
詳しく見てみましょう。
c が自分の持つカード集合のとき、c >> 4 は
自分が持つカード集合の全てのランクを1下げたものになります。
その両者の共通部分を取ったときに残るビットは何を表現しているでしょうか。
例えば自分の手札 c = { ♣️４, ❤️５, ❤️６, ♠️８ } としましょう。
このとき (c >> 4) = { ♣️３, ❤️４, ❤️５, ♠️７ } となります。
両者の共通部分を取ると
c & (c >> 4) = {❤️５}
となりました。
何故 ❤️５ だけ残ったのだろう、と考えると一目瞭然。
元の手札にランクが1つ上の ❤️６ があったからです。
つまりより一般に、c & (c >> 4) を計算することで
同じスートの連続したランクのうち下の方のビットだけが立つのです。
この立ったビットを取り出せば、2枚階段が生成できたことになります。簡単ですね。
ただし多くのルールで階段は3枚以上で役になるので、
関心があるのは3枚階段や4枚階段が計算できるかどうかですが、同じようにできます。
3枚階段の生成
Seq<3>(c) = c & (c >> 4) & (c >> 8)
4枚階段の生成
Seq<4>(c) = c & (c >> 4) & (c >> 8) & (c >> 12)
となります。
cが自分の手札のとき、c >> 8 はランクを2つ下げたもの、 c >> 12 はランクを3つ下げたものです。
3枚階段の場合の例を挙げて確かめてみましょう。
c = { ♣️４, ❤️５, ❤️６, ♠️７, ♠️８, ♠️９ }
のとき
c >> 4 = { ♣️３, ❤️４, ❤️５, ♠️６, ♠️７, ♠️８ }
c >> 8 = { ♣️(２), ❤️３, ❤️４, ♠️５, ♠️６, ♠️７ }
c & (c >> 4) & (c >> 8) = { ♠️７ }
元の手札に ♠️ - 789 の階段がありますが、正しく生成できました。
一点注意ですが、c >> 8 のときに ♣️(２) としたカードは、
今回の実装では３が64ビット整数の下4ビットなので、
♣️４ から8ビットの右シフトを行うと消えていることになります。
階段の生成判定などでは消えても「無い」という判定に何ら不都合はありませんが、
ビットシフトによってカードの枚数が減りうることは留意する必要があります。
（といっても私は全く気になったことはないので、それが問題になる計算はあまりないのかもしれません）
また、長い階段の計算を行う上で、計算手順を以下のように変更することもできます。
Seq<3>(c) = Seq<2> & (Seq<2> >> 4)
Seq<4>(c) = Seq<3> & (Seq<3> >> 4)
Seq<5>(c) = Seq<4> & (Seq<4> >> 4)
3枚階段が存在することの必要十分条件は、
同じランクの2枚階段と1つ上のランクの2枚階段がどちらもあること、というわけです。
以降の長い階段もこのように順次生成していくことができます。
また n 枚階段がなければ n + 1 枚階段がないことも明らかなので、
そこで生成を打ち切ることができます。
ジョーカーを考慮した階段系演算
ジョーカーがある場合の階段の生成について考えてみましょう。
ジョーカーがある場合には、階段のうちどれか1枚（または2枚）を
ジョーカーが代わりに務められるルールが一般的です。
ジョーカーを1枚使う階段の生成は以下のように行えます。
JSeq<3> = (c & (c >> 4)) | (c & (c >> 8)) | ((c >> 4) & (c >> 8))
JSeq<4> = (c & (c >> 4) & ( c >> 8 )) | (c & (c >> 4) & (c >> 12)) | (c & (c >> 8) & (c >> 12)) | ((c >> 4) & (c >> 8) & (c >> 12))
一気に煩雑になったような気もしますが、3枚階段の場合を丁寧に見ていきます。
c = { ♣️４, ❤️５, ❤️６, ♠️７, ♠️９ } | Joker
の場合を考えます。
ここではジョーカーの存在は64ビットの外に表現されており、
カード集合演算には何も影響を与えないとします（ので以下ジョーカーは略します）。
c >> 4 = { ♣️３, ❤️４, ❤️５, ♠️６, ♠️８ }
c >> 8 = { ❤️３, ❤️４, ♠️５, ♠️７ } （消えたビットの分は表記から消しました）
このとき
c & (c >> 4) = { ❤️５ }
c & (c >> 8) = { ♠️７ }
(c >> 4) & (c >> 8) = { ❤️４ }
となります。
ジョーカーがない場合の3枚階段の生成が
c & (c >> 4) & (c >> 8)
でしたが、こちらでは & でつないだそれぞれの項のうち1つが抜けたものを計算したことになります。
そして、この抜けた部分はジョーカーで補えるというのがジョーカーありの階段の生成です。
つまり、
c & (c >> 4) = { ❤️５ }
から、
c に対応する ❤️５
c >> 4に対応する ❤️６
c >> 8 に対応する ❤️７（←ここをジョーカーで置き換え！）
という ❤️ - 567 階段が生成できます。
同じように
c & (c >> 8) = { ♠️７ }
から ♠️８ をジョーカーで置き換えた ♠️ - 789 階段が、
(c >> 4) & (c >> 8) = { ❤️４ }
から ❤️４ をジョーカーで置き換えた ❤️ - 567 階段が生成できました。
このように、ジョーカーなしの場合の階段の生成式から
ジョーカーの枚数分だけ項を取り除いた式を計算することで、
結果のそれぞれが生成可能な階段のビットとなり、
しかもどの式で出てきたかによってジョーカーの位置もわかります。
また、もし手札が { ♠️７, ♠️８, ♠️９ } | Joker のときに3枚階段を生成するとして、
♠️ - 789 の階段がすでに出来ているのでジョーカー含みの階段は考えない、
といったようなことも戦術的にはありえるかと思います。
このような場合にもビット演算で対応できます。
2パターンの場合を考えました。
###ジョーカーを含まない階段と異なるランクの階段のみ生成する場合
♠️７と♠️８とジョーカーによって ♠️ - 789 は生成しない
（ジョーカーなしでも全く同じ階段が生成できるため）けれども
♠️ - 678 は生成する場合です。
このときは、
seq = c & (c >> 4) & (c >> 8) （ジョーカーなし階段）
jseq1 = c & (c >> 4) & ~seq
jseq2 = c & (c >> 8) & ~seq
jseq3 = (c >> 8) & (c >> 4) & ~seq
とすれば、seqで立っているビットはジョーカー含みの階段の方では消えるので、
全く同じ階段を生成せずに済みます。
ジョーカーなしで階段生成できるカードはジョーカー含みの階段生成には使わない場合
♠️ - 789 の階段がジョーカーなしで出来るので、
これらの札はジョーカー含みの階段を生成する際には考慮しない場合です。
seq = c & (c >> 4) & (c >> 8)
によって3枚階段を生成しましたが、実はこの結果から3枚階段に含まれるカード全体の集合を計算できます。
seqCards = seq | (seq << 4) | (seq << 8)
実際に計算してみましょう。
seq = { ❤️４, ♠️７ } （❤️ - 456と♠️ - 789を持っていることを示す）のとき
seq << 4 = { ❤️５, ♠️８ }
seq << 8 = { ❤️６, ♠️９ }
seq | (seq << 4) | (seq << 8) = { ❤️４, ❤️５, ❤️６, ♠️７, ♠️８, ♠️９ }
元々右シフトによって移動していたカードを左シフトで元に戻すことで、
階段を構成するカードのみの集合を得ることができました。
あとはこれを手札全体から引いて、
残ったカード集合に対してジョーカー含みの階段の生成を適用すれば完成です。
前編はここまで
長くなってきたので前編はここで終了し、後編ではまだ扱っていないグループ系の演算と、
さらに面白い「必勝判定も実はビット演算で一瞬でできる！」という内容を書きたいと思います。
ここまで読んでくださった方ありがとうございました。
ビット演算テクニックAdvent Calendar 2016次回の更新も楽しみです。