以前、ポーカーの役を判定するためのアルゴリズムの作り方についての記事を公開しました。
ありがたいことにこちらの記事は公開当初から今に至るまで継続的に結構多くのアクセスがあるのですが（こんなことが気になる人が世の中には意外といるもんなんですね）、私個人としてはこれについてずっと思っていたことがありました。
これではまだ遅いんですよ。
まあ確かにペア系の役の判定はかなりスマートにできていると思います。競プロの初心者脱出～中級者ぐらいの問題として出てきたら、このレベルで問題ないと思います。
ですが現実問題このプログラムを使って大量のハンドの強さを一気に判定させようとすると、商用ソフトの速度には遥かに及ばないことに気付くでしょう。
そこで他の記事を書いたりWebコンテンツを製作したりしながら頭の片隅のさらに隅っこの方でずっと考えていたのですが、ビット演算を活用することでなんとなくこれならいけそうというものがまとまりました。
Contents
役の種類
ここは前回と同じです。
判定したい役は以下の9種類です。
- ストレートフラッシュ
- フォー・オブ・ア・カインド
- フルハウス
- フラッシュ
- ストレート
- スリー・オブ・ア・カインド
- ツーペア
- ワンペア
- ハイカード
ロイヤルフラッシュはAハイのストレートフラッシュと同等なので分けて判定はしません。
カードと役の情報の持たせ方
52枚のカードに0～51(あるいは1～52)の数値を割り振ってどうにかするのではなく、int32(-2,147,483,648～2,147,483,647)の範囲の中で適切な数値を割り振ることによって単純計算で判定ができるようにします。
同じ型である限り、1でも2,147,483,647もデータ量は一緒ですからね。
今回は以下のようにデータを持たせます。
shdcxxxxxx
1000101001 (=As)
0010010111 (=Td) etc.
shdc : 対応するスートの位置に1を立てる
xxxxxx: 23456789TJQKAに素数(2,3,5,7,11,13,17,19,23,29,31,37,41)を対応させ、2進数表記でデータを持つカードの数字を素数で表すというのが大きな工夫ポイントです。この理由はすぐにわかります。
役の判定方法
そもそも52枚から5枚を選ぶ組み合わせなんて高々\(_{52}\rm C_{5}=2598960\) 通りしかないので、うまいことやれば計算量はほぼ\(O(1)\)で済むはずです。
フラッシュ
public static bool IsFlush(int i0, int i1, int i2, int i3, int i4) {
return i0 & i1 & i2 & i3 & i4 & 0b1111000000 != 0;
}なんとたったの1行です。
スート以外の部分は関係が無いので0b1111000000でマスクしてあげて、5枚のカードを全てANDすると、違うスートが1枚でも入っていれば0になります。とりあえずこれで5倍速です（たぶん）。
ストレート
前回は結構苦労しましたが、今回は一発で決めます。
static HashSet<int> straight = new HashSet<int>();
public static void PreCalculation(){ //実行前に回しておく関数
int[] prime = new int[14]{41, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41};
for(int i=0; i<14-5; i++){
straight.Add(prime[i] * prime[i+1] * prime[i+2] * prime[i+3] * prime[i+4]);
}
}
public static bool IsStraight(int i0, int i1, int i2, int i3, int i4) {
return straight.Contains((i0 & 63) * (i1 & 63) * (i2 & 63) * (i3 & 63) * (i4 & 63));
// 63 = 0b111111
}予めPreCalculation()を回して、straightに値を格納してから実行してください。A~Kを全て素数で表しておけば、その積を見るだけで判定できるというわけです。HashSet<T>のContainsメソッドは\(O(1)\)で回せますが、ここをArrayなどで代替しようとすると計算量は\(O(N)\)になりますので注意してください。
ちなみに13番目の素数が41ですが、\(41^5=115856201<2^{31}\)なので、絶妙にint32で耐えています。
ペア系の役(フォー・オブ・ア・カインド、フルハウス、スリー・オブ・ア・カインド、ツーペア、ワンペア)
これも発想はストレートと同じです。
static HashSet<int> pairs = new HashSet<int>();
private static int CountSameRankLine(int i0, int i1, int i2, int i3, int i4) {
int count = 0;
int[] cards = { i0, i1, i2, i3, i4 };
for(int i = 0; i < 5; i++) {
for(int j = i; j < 5; j++) {
if ((cards[i] & 0b111111) == (cards[j] & 0b111111))
++count;
}
}
return count;
}
public static void PreCalculation2(){ //実行前に回しておく関数
int[] prime = new int[13]{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41};
for(int a=0; a<13; a++){
for(int b=a; b<13; b++){
for(int c=b; c<13; c++){
for(int d=c; d<13; d++){
for(int e=d; e<13; e++){
pairs.Add(prime[a] * prime[b] * prime[c] * prime[d] * prime[e],
CountSameRankLine(prime[a], prime[b], prime[c], prime[d], prime[e]));
}}}}}
}
public static bool IsQuads(int i0, int i1, int i2, int i3, int i4) {
return pairs[(i0 & 63) * (i1 & 63) * (i2 & 63) * (i3 & 63) * (i4 & 63)] == 6;
}
public static bool IsFullHouse(int i0, int i1, int i2, int i3, int i4) {
return pairs[(i0 & 63) * (i1 & 63) * (i2 & 63) * (i3 & 63) * (i4 & 63)] == 4;
}
public static bool IsTrips(int i0, int i1, int i2, int i3, int i4) {
return pairs[(i0 & 63) * (i1 & 63) * (i2 & 63) * (i3 & 63) * (i4 & 63)] == 3;
}
public static bool IsTwoPairs(int i0, int i1, int i2, int i3, int i4) {
return pairs[(i0 & 63) * (i1 & 63) * (i2 & 63) * (i3 & 63) * (i4 & 63)] == 2;
}
public static bool IsOnePair(int i0, int i1, int i2, int i3, int i4) {
return pairs[(i0 & 63) * (i1 & 63) * (i2 & 63) * (i3 & 63) * (i4 & 63)] == 1;
}事前に関数を一つ回しておくことで、計算量は\(O(1)\)にできます。コードが若干汚いですが、\(13^5=371293\)なのでこれくらいは我慢しましょう。
