Unityによる大富豪の作り方 6 ~完成~
完成
完成したものがこちら
ソースコードはこちら
まとめ
- とりあえず動くものを完成させようと思い、ジョーカーや8切りや9リバースなどの特殊ルール、カード交換などを実装できませんでした。人に遊んでもらうレベルにするには必要でしょうから時間があれば取り入れてみたいです。
- グラフィックも改善したいなと思いました。カードを扇状に配置したり、カードを出すアニメーションとか。あと、各プレイヤーの画像とかもいれてみたいです。
- 今回BitCard型(ulong)で手札を管理しましたが、役の取得や評価の計算で1ビットずつ取り出してループさせる……なんてことが多かった気がします。せっかくビットで管理しているのだから並列処理できればなと思いました。
- 案の定あまり賢いAIはできませんでした笑)。
Unityによる大富豪の作り方 5 ~場に出す役の選択~
場に出す役の選択
選択候補の選出
場に出してもよさそうな役の候補を選出します。候補がない場合パスします。場に出す役の決定
候補に挙がった役の中から、出した後の手札評価値が最も低くなる(同値の場合、役ランクが低い)役を出します。
選択候補の選出
親のとき
nullsuke.com で書いた方法で役を取得。単純に優先評価値が最も高い役を選択候補とします。優先評価値が同じ場合はランクの弱い役を選択候補とします。
子のとき
場の役が階段の場合
対象を出した後の手札があがれそうであるかまたは、出した後の手札評価値 < 出す前の手札評価値 + 1であるものを選択候補とします。
場の役がグループの場合
すべての合法役について以下の条件を順に判定していきます。一度候補の可否が決定されたらそれ以降の判定はしません。
- 場を流せそうな役でかつ、上がれそうな手札の場合
選択候補とする。 - 以下のいずれかの条件を満たした場合、選択候補とする。
- 場を流せそうな役でかつ、手札にある役が4未満
- 場を流せそうな役でかつ、出した後の手札にも場を流せそうな役がある
- 出した後の手札にある役が1でかつ、その役評価値が50以下の場合
選択候補としない。 - 出した後の手札が上がれそうな手札の場合
選択候補とする。 - 1やK(革命時は4や5)の単体やグループでありかつ、出した後の手札にある役が4以上でかつ、出した後の手札評価値が0より大きい場合
選択候補としない。 - 出した後の手札評価値 < 出す前の手札評価値 である場合
選択候補とする。
例1
場が♠️7 ♦️7
でどのカードも使われておらず、誰も上がっていなく
手札が♠️3 ♦️10 ♣️10 ♠️2 ♦️2の場合
合法役は[ ♦️10 ♣️10 ] [ ♠️2 ♦️2 ]
となる。
[ ♦️10 ♣️10 ]
は上記条件の4に該当するので候補となる。
[ ♠️2 ♦️2 ]
は上記条件の2に該当するので候補となる。
[ ♦️10 ♣️10 ]
を出した後の手札[ ♠️3 ♠️2 ♦️2 ]
の手札評価値は0
[ ♠️2 ♦️2 ]
を出した後の手札[ ♠️3 ♦️10 ♣️10 ]
の手札評価値は3
よって[ ♦️10 ♣️10 ]
が選択されます。
例2
場が♠️7
でどのカードも使われておらず、誰も上がっていなく
手札が♠️8 ♦️1
の場合
合法役は[ ♠️8] [ ♦️1 ]
となる。
[ ♠️8 ]
は上記条件の4に該当するので候補となる。
[ ♦️1 ]
は上記条件の3に該当するので候補とならない。
よって[ ♠️8 ]
が選択されます。
例3
場が♠️7
でどのカードも使われておらず、誰も上がっていなく
手札が♠️3 ♦️4 ♣️8 ♦️1 ❤️2
の場合
合法役は[ ♣️8] [ ♦️1 ] [ ❤️1 ]
となる。
[ ♠️8 ]
は上記条件の6に該当するので候補となる。
[ ♦️1 ]
は上記条件の5に該当するので候補とならない。
[ ❤️2 ]
はどの条件にも該当しないので候補とならない。
よって[ ♠️8 ]
が選択されます。
実装
public class PlayerLogic { private static BitUtility bit; private static ulong[] bitPlayerCards; //親のときに役を選択 private ulong SelectBitHandOnDealer(int id, GameData gameData) { var bitPlayerCard = bitPlayerCards[id]; var playerCard = new PlayerCard(bitPlayerCard, gameData); var hands = playerCard.Hands; var ordered = hands.OrderByDescending(h => h.Priority).ThenBy(h => h.Rank) .ToList<Hand>(); return ordered[0].BitHand; } //子のときに役を選択 private ulong SelectBitHandOnNoneDealer(int id, GameData gameData) { var bitPlayerCard = bitPlayerCards[id]; var playerCard = new PlayerCard(bitPlayerCard, gameData); var legalHands = playerCard.GetLegalHands(gameData); if (bit.IsSequence(gameData.BitFieldCard)) { legalHands.ForEach(h => { var next = playerCard.CreateNextPlayerCard(h.BitHand, gameData); if (next.CanEndGame || playerCard.Score <= next.Score + 1) { h.Selected = true; } }); } else { for (int i = 0; i < legalHands.Count; i++) { var h = legalHands[i]; var next = playerCard.CreateNextPlayerCard(h.BitHand, gameData); if (h.CanEndTurn && playerCard.CanEndGame) { h.Selected = true; } else if (h.CanEndTurn) { if (playerCard.Hands.Count < 4 || next.Hands.Exists(h2 => h2.CanEndTurn)) { h.Selected = true; } } else if (next.Hands.Count == 1 && next.Hands[0].Score <= 50) { continue; } else if (next.CanEndGame) { h.Selected = true; } else if (IsPrettyHigh(h.BitHand, gameData.IsRevolutionalizing) && next.Hands.Count >= 4 && next.Score > 0) { continue; } else if (next.Score <= playerCard.Score) { h.Selected = true; } } } var selected = legalHands.Where(h => h.Selected).ToList<Hand>(); if (selected.Count == 0) return 0; var min = Mathf.Infinity; int m = 0; //選択候補の中から、出した後の手札評価値が最も低い役を選択 for (int i = 0; i < selected.Count; i++) { var next = playerCard.CreateNextPlayerCard(selected[i].BitHand, gameData); if (next.Score <= min) { if (next.Score == min) { if (selected[i].Rank < selected[m].Rank) m = i; } else { m = i; } min = next.Score; } } return selected[m].BitHand; } //Kや1(革命時は4や5)の単体やグループかどうか判定する private bool IsPrettyHigh(ulong bitHand, bool isRevolutionalizing) { var qpCard = bit.ToQPCard(bitHand); if (!isRevolutionalizing) { return (qpCard & 0x0000110000000000ul) > 0; } else { return (qpCard & 0x0000000000000110ul) > 0; } } }
Unityによる大富豪の作り方 4 ~役、手札の評価~
評価値の計算
場にどのカードを出すか決定する為に必要な3つの評価値 - 役評価値、手札評価値、優先評価値 - の計算について説明します。 主に以下のサイトを参考にしました。
コンピュータ大貧民におけるヒューリスティック戦略の実装と効果
役評価値
役自体の強さを表します。役が単体かグループか階段なのかで計算方法が異なります。
単体
対象のカードよりランクが高く、相手が保持している可能性のあるカードのランクの総数をnとしたき役評価値は 100 - n × 30となります。
例
対象が[ ♠️Q ]
ですでに♠️K ♠️1 ♦️1 ♣️1 ♠️2 ♦️2 ♣️2 ❤️2
が使われている場合、役評価値は100 - 2 × 30 = 40 となります。
グループ
- そのグループと同じ枚数で、対象よりランクが高く、相手が保持している可能性のあるカード(H)を抽出します。
- Hに含まれる各ランク(Ri)ごとに以下の計算をします。
- Si = Riの総数 - 計算対象の枚数 - プレイ中の人数 + プレイヤー数
- Siの値によってNiの値を決定します。
- Si <= 0 なら Ni = 4
- Si = 1 なら Ni =9
- Si = 2 なら Ni =15
- Si >= 3 なら Ni =24
- 役評価値は 100 - Niの総和 となります。
対象が
[ ♠️J ♦️J ♣️J ]
ですでに♠️K ♠️1 ♦️1 ♣️1 ♠️2 ♦️2 ♣️2 ❤️2
が使われておりプレイ人数4人で誰も上がっていない場合Jより高く、相手が保持している可能性のあるカード(H)はQ、K。
Q、KそれぞれのNiの値Nq、Nkは
Sq = 4 - 3 - 4 + 4 = 1 より Nq = 9
Sk = 3 - 3 - 4 + 4 = 0 より Nk = 4
これより、役評価値は 100 - 9 + 4 = 87 となります。階段
対象のカードよりランクが高く、相手が保持している可能性のある階段の総数をnとしたき、役評価値は 100 - n × (プレイヤー数 + 1 - プレイ中の人数) となります。
例
対象が[ ♠️9 ♠️10 ♠️J ]
ですでに♦️Q ♣️Q ♣️K ❤️Q ❤️K ❤️1
が使われておりプレイ人数4人で誰も上がっていない場合
相手が保持している可能性のある対象より高ランクの階段は[ ♠️Q ♠️K ♠️1 ] [♠️K ♠️1 ♠️2 ] [ ♦️K ♦️1 ♦️2 ]
の3種類なので
役評価値は 100 - 3 × (4 + 1 - 4) = 97 となります。
手札評価値
手札にどれだけ弱いカードが残っているかを表します。弱い役が多いほど値が大きくなります。役評価値より各役に点数(S)を付けます。
- 役評価値が 1以上30以下の場合 S = 2
- 役評価値が 31以上60以下の場合 S = 1
- 役評価値が 61以上90以下の場足 S = 0
- 役評価値が 91以上かつ対象の役よりランクが高いカードを相手が保持している可能性がある場合 S = -1
- 役評価値が 91以上かつ対象の役よりランクが高いカードを相手が保持している可能性がない場合 S = 対象の役の枚数 × -1
手札評価値は、Sの総和となります。
例
手札が♠️3 ♦️9 ♦️10 ♦️J ♦️2 ♣️2
でどのカードも使われていなく、プレイ人数4人で誰も上がっていない場合
[ ♠️3 ]
の役評価値は1なので S = 2
[ ♦️9 ♦️10 ♦️J ]
の役評価値は94で、相手が高ランクの役を保持している可能性があるので S = -1
[ ♦️2 ♣️2 ]
の役評価値は100で、相手が高ランクの役を保持している可能性がないので S = -2
手札評価値は 2 - 1 - 2 = -1 となります。
優先評価値
親のときに場に出す優先順位を表します。革命できる役を持っているかどうかで計算方法が異なります。
革命できない場合
まず、各役が「場を流せそうな役」なのか、手札が「あがれそうな手札」なのかを計算します。
- 場を流せそうな役
- 役評価値が86以上の役。
- あがれそうな手札
- 手札内の役の数 - 場を流せそうな役の数 が1以下の手札。
あがれそうな手札の場合、場を流せない役の優先評価値を低くし、場を流せる役を優先的に場に出し続け上がりきるようにします(ずっと俺のターン!)。
あがれそうにない手札の場合、役ランク(役を構成するカード内で最も高いランク)が低く、手札内に同一枚数のものが多いほど高くします。
- 場を流せそうな役の優先評価値は 110 - 役評価値 となります。
- 場を流せなそうな役の優先評価値は
- 上がれそうな手札の場合は 2 となります。
- そうでない場合は 40 + (13 - 役ランク) × 2 + 手札内の同じ枚数の役の数 × 4 となります。
例1
手札が❤️3 ❤️4 ❤️5 ♦️6 ♣️7 ♠️7 ♠️8 ♦️8 ♣️8 ♦️J ♣️J ❤️2
でどのカードも使われていなく、プレイ人数4人で誰も上がっていない場合
[ ❤️3 ❤️4 ❤️5 ]
の役評価値は86
[ ♦️6 ]
の役評価値は1
[ ♣️7 ♠️7 ]
の役評価値は12
[ ♠️8 ♦️8 ♣️8 ]
の役評価値は51
[ ♦️J ♣️J ]
の役評価値は46
[ ❤️2 ]
の役評価値は100
手札内の役が6つ、場を流せそうな役が2つなのであがれそうな手札ではありません。よって、
[ ❤️3 ❤️4 ❤️5 ]
の優先評価値は 110 - 86 = 24
[ ♦️6 ]
の優先評価値は 40 + (13 - 3) × 2 + 2 × 4 = 68
[ ♣️7 ♠️7 ]
の優先評価値は 40 + (13 - 4) × 2 + 2 × 4 = 66
[ ♠️8 ♦️8 ♣️8 ]
の優先評価値は 40 + (13 - 5) × 2 + 1 × 4 = 60
[ ♦️J ♣️J ]
の優先評価値は 40 + (13 - 8) × 2 + 2 × 4 = 58
[ ❤️2 ]
の優先評価値は 110 - 100 = 10
となります。
例2
手札が❤️3 ❤️4 ❤️5 ♠️6 ♠️7 ♠️8 ♣️9
でどのカードも使われていなく、プレイ人数4人で誰も上がっていない場合
[ ❤️3 ❤️4 ❤️5 ]
の役評価値は74
[ ♠️6 ♠️7 ♠️8 ]
の役評価値は81
[ ♣️9 ]
の役評価値は1
場を流せる役はないので上がれそうな手札ではありません。よって、
[ ❤️3 ❤️4 ❤️5 ]
の優先評価値は 40 + (13 - 2) × 2 + 2 × 4 = 68
[ ♠️6 ♠️7 ♠️8 ]
の優先評価値は 40 + (13 - 5) × 2 + 2 × 4 = 64
[ ♣️9 ]
の優先評価値は 40 + (13 - 6) × 2 + 1 × 4 = 58
となります。
例3
手札が♠️3 ♠️4 ♠️5 ♦️8 ♦️9 ♦️10 ♣️2
でどのカードも使われていなく、プレイ人数4人で誰も上がっていない場合
[ ♠️3 ♠️4 ♠️5 ]
の役評価値は74
[ ♦️8 ♦️9 ♦️10 ]
の役評価値は89
[ ♣️2 ]
の役評価値は100
手札内の役が3つ、場を流せそうな役が2つなのであがれそうな手札です。よって、
[ ♠️3 ♠️4 ♠️5 ]
の優先評価値は2
[ ♦️8 ♦️9 ♦️10 ]
の優先評価値は110 - 89 = 21
[ ♣️2 ]
の優先評価値は110 - 100 = 10
革命できる場合
- 2枚以下のカードで構成される役の役評価値が90以下 かつ
- 出した後の手札評価値 < 出す前の手札評価値
の場合
- 革命の役の優先評価値を90
- 階段以外で場を流せそうな役の優先評価値を91
- 残りは革命できない場合と同様
とします。上記条件を満たさない場合は革命役の優先評価値を1とし革命しないようにします。
実装
public class Hand { private static readonly ulong MAll = 0x000fffffffffffff; private static BitUtility bit; private readonly ulong bitHand; private readonly int sameQuantity; private readonly int rank; //場を流せる役かどうか public bool CanEndTurn { get => Score >= 86; } public int Rank { get => rank; } //役の構成枚数 public int Quantity { get => bit.CountBit(bitHand); } //役評価値 public float Score { get; private set; } //優先評価値 public float Priority { get; set; } public int EnemyHigherRankQuantity { get; private set; } public Hand(ulong bitHand, ulong playerCard, GameData gameData, int same = 0) { this.bitHand = bitHand; bit = BitUtility.Instance; //役のランクを求める。革命時は逆になる rank = gameData.IsRevolutionalizing ? 12 - (int)(bit.BitScanForward(bitHand) / 4) : (int)(bit.BitScanReverse(bitHand) / 4); //場に出ていないカードを取得 var enemyCard = ~(playerCard | gameData.BitUsedCard) & MAll; //場に出ていないカードの中で、役より強いカードを取得 var enemyHigherCard = bit.GetHigherBitCard(enemyCard, bitHand, gameData.IsRevolutionalizing); EnemyHigherRankQuantity = CountRank(enemyHigherCard); //手札内にある同じ枚数の役の数 sameQuantity = same; Score = EvaluateHand(enemyHigherCard, gameData); } //役評価値を計算 public float EvaluateHand(ulong higher, GameData gameData) { float score = 0f; if (Quantity == 1) { score = EvaluateSingleHand(); } else if (bit.IsSequence(bitHand, Quantity)) { score = EvaluateSequenceHand(higher, Quantity, gameData); } else if (bit.IsGroup(bitHand, Quantity)) { score = EvaluateGroupHand(higher, Quantity, gameData); } return Mathf.Max(score, 1); } //優先評価値を求める public void SetPriority(bool canEndGame) { if (canEndGame) { if (!CanEndTurn) { Priority = 2; return; } } if (CanEndTurn) { Priority = 110 - Score; } else { Priority = 40 + (13 - Rank) * 2 + sameQuantity * 4; } } //単体のカードの強さ評価値を計算 private float EvaluateSingleHand() { return 100 - EnemyHigherRankQuantity * 30; } //階段の強さ評価値を計算 private float EvaluateSequenceHand(ulong higher, int cnt, GameData gameData) { var seqs = bit.GetSequenceList(higher, cnt); return 100 - seqs.Count * (gameData.PlayerNumber + 1 - gameData.PlayingNumber); } //グループの強さの評価値を計算 private float EvaluateGroupHand(ulong higher, int cnt, GameData gameData) { int score = 0; var cnts = CountOverQuantityEveryRank(higher, cnt); for (int i = 0; i < cnts.Length; i++) { if (cnts[i] == 0) continue; var s = cnts[i] - cnt - gameData.PlayingNumber + gameData.PlayerNumber; int n; if (s <= 0) n = 4; else if (s == 1) n = 9; else if (s == 2) n = 15; else n = 24; score += n; } return 100 - score; } private int CountRank(ulong bitCard) { var qpCard = bit.ToQPCard(bitCard); return bit.CountBit(qpCard); } //指定の枚数以上あるランク内で、何枚カードがあるか数える private int[] CountOverQuantityEveryRank(ulong higher, int cnt) { int n = cnt - 1; var noless = 16 - (1ul << n); var cntMask = BitUtility.M0001 * noless; var qpOver = bit.ToQPCard(higher) & cntMask; var cnts = new int[13]; for (int i = 0; i < 13; i++) { var c = (qpOver >> i * 4) & 15ul; if (c == 0) cnts[i] = 0; else cnts[i] = (int)Math.Log((int)c, 2) + 1; } return cnts; } }
public class PlayerCard { //手札内のすべての役 private List<Hand> hands; //あがれる手札かどうか public bool CanEndGame { get { int cnt = hands.Count; int end = hands.Count(h => h.CanEndTurn); return cnt == 0 || cnt - end <= 1; } } //手札評価値を取得 public float Score { get { float score = 0f; hands.ForEach(h => { if (h.Score >= 1 && h.Score <= 30) { score += 2; } else if (h.Score >= 31 && h.Score <= 60) { score += 1; } else if (h.Score >= 91 && h.EnemyHigherRankQuantity > 0) { score += -1; } else if (h.Score >= 91 && h.EnemyHigherRankQuantity == 0) { score += -h.Quantity; } }); return score; } } } //優先評価値を計算 private void SetPriority(GameData gameData) { var canEnd = CanEndGame; //革命役を取得 var rev = hands.Find(h => h.CanRevolutionalize); if (rev != null) { SetPriorityOnRevolution(rev, canEnd, gameData); } else { hands.ForEach(h => h.SetPriority(canEnd)); } } //革命できる場合の優先評価値を計算 private void SetPriorityOnRevolution(Hand rev, bool canEnd, GameData gameData) { var next = CreateNextPlayerCard(rev.BitHand, gameData); if (hands.Exists(h => h.Quantity <= 2 && h.Score > 90) || Score < next.Score) { rev.Priority = 1; foreach (var h in hands.Where(h => !h.CanRevolutionalize)) { h.SetPriority(canEnd); } } else { rev.Priority = 90; foreach (var h in hands.Where(h => !h.CanRevolutionalize)) { if (!bit.IsSequence(h.BitHand) && h.CanEndTurn) { h.Priority = 91; } else { h.SetPriority(canEnd); } } } }
Unityによる大富豪の作り方 3 ~役の取得~
役の取得
自分が親か子なのかで取得方法は異なります。
親のとき
概要
- 手札が4枚より多いときは一番強いカード(2、革命時は3)を除いた手札から、そうでないときは手札のすべてから階段を取得します。 ただし、階段を構成しているすべてのカードが2枚以上である場合は階段として取得しません。
- 階段を除いた手札で同一ランクが2枚以上あればそれらをグループとします。
- 階段にもグループにも使われなかったカードは単体とします。
例1
手札が♠️3 ♠️4 ♠️5 ♦️5 ♦️10 ♣️10 ❤️10 ♠️K ♦️K ♠️1 ♠️2
の場合
役は[ ♠️3 ♠️4 ♠️5 ] [ ♦️10 ♣️10 ❤️10 ] [ ♠️K ♦️K ] [♦️5] [♠️1] [♠️2]
となります。
例2
手札が♠️3 ♦️3 ♠️4 ♦️4 ♠️5 ♦️5 ♣️5
の場合
役は[♠️3 ♦️3][ ♠️4 ♦️4] [♠️5 ♦️5 ♣️5]
となります。
実装
//役を取得する private static BitUtility bit = BitUtility.Instance; private List<ulong> GetBitHands(bool isRevolutionalizing) { var bitHands = new List<ulong>(); var single = GetSingle(bitPlayerCard); var noStrongest = bitPlayerCard; var other = bitPlayerCard; int cnt = bit.CountBit(bitPlayerCard); //手札が4枚以下のとき階段役が存在すれば、階段役のみか、階段役+単数役であり、上がりきる可能性が高いので //最強ランクも階段に含める if (cnt > 4) { if (isRevolutionalizing) { noStrongest = bitPlayerCard & 0x000ffffffffffff0ul; } else { noStrongest = bitPlayerCard & 0x0000fffffffffffful; } } bit.GetSequenceList(noStrongest).ForEach(s => { if ((s & single) > 0) { bitHands.Add(s); other ^= s; } }); bit.GetGroupList(other).ForEach(g => { bitHands.Add(g); other ^= g; }); //BitCard型のカードの集合(other)から1枚ずつ取り出し、BitCard型のリストに変換 var list = bit.ToBitList(other); bitHands.AddRange(list); return bitHands; } //単数役を取得 private ulong GetSingle(ulong bitCard) { var qpSingle = bit.ToQPCard(bitCard) & BitUtility.M0001; return bit.ToBitCard(qpSingle, bitCard); }
//枚数位置型をBitCard型に変換 public ulong ToBitCard(ulong qpCard, ulong bitCard) { var result = 0ul; while (qpCard != 0) { int i = BitScanForward(qpCard); int r = i / 4; result |= bitCard & (15ul << (r * 4)); qpCard &= qpCard - 1; } return result; } //ulongから1ビットずつ取り出してリストに変換 public List<ulong> ToBitList(ulong bit) { var list = new List<ulong>(); while (bit != 0) { var b = GetMostSignificantBit(bit); list.Add(b); bit ^= b; } return list; }
子のとき
概要
場に出せる役(合法役)をすべて取得します。 特に単体やグループの場合、考えうるすべての組み合わせの役を取得します。
例1
場が♠️3 ♠️4 ♠️5
で
手札が♠️6 ♠️7 ♠️8 ♠️9 ♦️9 ♦️10 ♦️J
の場合
合法役は[ ♠️6 ♠️7 ♠️8 ] [ ♠️7 ♠️8 ♠️9 ] [ ♦️9 ♦️10 ♦️J ]
となります。
例2
場が♠️3 ♦️3
で
手札が♠️4 ♦️4 ♣️4 ♠️5 ♠️6
の場合
合法役は[ ♠️4 ♦️4 ] [ ♠️4 ♣️4 ] [ ♦️4 ♣️4 ]
となります。
例2の場合、合法役は3通りあるが♠️4
残すと手札に[ ♠️4 ♠️5 ♠️6 ]
が残り有利となるので[ ♦️4 ♣️4 ]
を場に出すのが最善となります。
このように場に出した後の手札のことを考える必要があるので、単体やグループ役を出す場合は、考えうるすべての組み合わせの役を取得する必要があります。
実装
//合法役を取得する private static BitUtility bit = BitUtility.Instance; private List<ulong> GetBitLegalHands(int cnt, ulong bitFieldCard, bool isRevolutionalizing) { List<ulong> bitHands; var higher = bit.GetHigherBitCard(bitPlayerCard, bitFieldCard, isRevolutionalizing); if (bit.IsSequence(bitFieldCard, cnt)) { bitHands = bit.GetSequenceList(higher, cnt); } else { bitHands = new List<ulong>(); var grps = bit.GetGroupList(higher, cnt); grps.ForEach(h => { //場にある枚数と役を構成する枚数が同じなら組み合わせを考える必要はない if (bit.CountBit(h) == cnt) { bitHands.Add(h); } else { var newGrps = GetConbinations(h, cnt); bitHands.AddRange(newGrps); } }); } return bitHands; } //n枚で構成されるグループ役からr枚取り出してできる役をすべて取得 private List<ulong> GetConbinations(ulong bitHand, int r) { int n = bit.CountBit(bitHand); //BitCard型のカードの集合(bitHand)から1枚ずつ取り出し、BitCard型のリストに変換 var bitList = bit.ToBitList(bitHand); //n枚で構成されるグループ役からr枚取り出してできるすべての組み合わせを取得。 //組み合わせはビットで表現されている。 var cnbs = bit.GetConbination(n, r); var newBitHand = 0ul; List<ulong> bitHands = new List<ulong>(); for (int i = 0; i < cnbs.Count; i++) { for (int j = 0; j < n; j++) { //ビットが立っていたら、対応するカードを役として使う if ((cnb[i] & (1 << j)) > 0) { newBitHand |= bitList[j]; } } bitHands.Add(newBitHand); newBitHand = 0; } return bitHands; }
Unityによる大富豪の作り方 2 ~ビット演算(応用)~
ビット演算(応用)
前回は基本的なビット演算の紹介でしたが、今回はそれらを使って具体的に階段やグループの判定・作成方法を説明します。
階段かグループか判定する
public readonly static ulong M0001 = 0x1111111111111111; private readonly static ulong M0011 = 0x3333333333333333; private readonly static ulong M0100 = 0x4444444444444444; private readonly static ulong M0101 = 0x5555555555555555; private readonly static ulong M1000 = 0x8888888888888888; //階段かどうか判定する。 public bool IsSequence(ulong bitCard, int cnt) { if (bitCard == 0 || cnt < 3) return false; var head = bitCard; for (int i = 0; i < cnt - 1; i++) { head &= head >> 4; } return CountBit(head) == 1; } //グループかどうか判定する public bool IsGroup(ulong bitCard, int cnt) { if (cnt > 4) return false; var n = (1ul << cnt - 1) * M0001; var qpCard = ToQPCard(bitCard); return (qpCard & n) > 0; } //枚数位置型(QuantityPosition)に変換 public ulong ToQPCard(ulong bitCard) { //2ビットごとの1の数を2進数で表現 var a = ((bitCard & M0101) + ((bitCard >> 1) & M0101)); //4枚あるランク var n4 = a & (a << 2) & M1000; //3枚あるランク var n3 = (a << 2) & (a >> 1) & M0100; n3 |= a & (a << 1) & M0100; //4ビットごとの1の数を2進数で表現(4は除く) var n12 = ((a & M0011) + ((a >> 2) & M0011)) & M0011; if (n3 != 0) { n4 |= n3; //3枚である場合を除く。 n4 |= n12 & ~(n3 >> 1 | n3 >> 2); } else { n4 |= n12; } return n4; }
枚数位置型への変換はわかりづらいので少し解説します。
var a = ((bitCard & M0101) + ((bitCard >> 1) & M0101));
aはbitCardを2ビットごとの1の数を2進数で表現しています。
例えば、bitCardが
1111 1011 0101 1100 0100 のとき、aは
1010 0110 0101 1000 0100 となります。
次に、このaを2ビットごとに足すと4ビットごとの1の数となります(この辺りは1の数を数えるCountBitと同じです)。
そして、4ビットごとの1の数とは各ランクごとのカードの枚数を表しています。
例えば、aが1010 0110 0101 1000 0100のとき、カードの枚数は4枚、3枚、2枚、2枚、1枚となります。
var n4 = a & (a << 2) & M1000;
あるランクが1010であるとき、そのランクのカードが4枚あるということなので4ビット目を1とします。
var n3 = (a << 2) & (a >> 1) & M0100; n3 |= a & (a << 1) & M0100;
あるランクが1001または0110であるとき、そのランクのカードが3枚あるということなので3ビット目を1とします。
var n12 = ((a & M0011) + ((a >> 2) & M0011)) & M0011;
4ビットごとの1の数を2進数で表現し、M0011をANDすることで4を除いています。つまりn12はそのランクの枚数(0~3)を2進数で表しています。
if (n3 != 0) { n4 |= n3; n4 |= n12 & ~(n3 >> 1 | n3 >> 2); } else { n4 |= n12; }
1、2枚の場合はn12から3枚の場合を除いたものを使うことで表現します。
階段を取得
長さが最大になる組み合わせですべての階段を取得
//長さが最大になる組み合わせですべての階段をList<ulong>で取得 public List<ulong> GetSequenceList(ulong bitCard) { var sequences = new List<ulong>(); ulong seq; do { seq = GetLongestSequence(bitCard); if (seq != 0) { sequences.Add(seq); bitCard ^= seq; } } while (seq != 0); return sequences; } //一番長い階段を取得 private ulong GetLongestSequence(ulong bitCard) { var head = bitCard; var max = 0ul; int i = 1; while (head != 0) { if (i >= 3) max = head; head &= bitCard >> (i * 4); i++; } if (max == 0) return 0; else { var b = GetLeastSignificantBit(max); return CreateSequence(b, i - 1); } } //階段を生成 private ulong CreateSequence(ulong head, int cnt = 3) { var seq = head; for (int i = 1; i < cnt; i++) { head <<= 4; seq |= head; } return seq; }
手札から最も長い階段を取得し、そのカードを除いた手札から再度、最大の長さの階段を取得する、ということを繰り返しています。すべての階段(BitCard型)をList<ulong>で取得します。自分が親で、枚数制限がない場合に使います。
例えば手札が♠️4 ♠️5 ♠️6 ♦️6 ♠️7 ♦️7 ♦️8 ♠️9 ♠️10
の場合
[ ♠️4 ♠️5 ♠️6 ♠️7 ] [ ♦️6 ♦️7 ♦️8 ]
を取得します。
指定した枚数の階段をすべて取得
//指定した枚数の階段をすべてList<ulong>で取得 public List<ulong> GetSequenceList(ulong bitCard, int cnt) { var sequences = new List<ulong>(); var head = bitCard; for (int i = 1; i < cnt; i++) { head &= bitCard >> (i * 4); } while (head != 0) { var b = GetLeastSignificantBit(head); sequences.Add(CreateSequence(b, cnt)); head ^= b; } return sequences; }
指定した枚数より多い階段が存在した場合、その枚数で組み合わせ可能な階段をすべて取得します。すべての階段(BitCard型)をList<ulong>で取得します。自分が子で、出せる枚数に制限がある場合に使います。
例えば手札が♠️4 ♠️5 ♠️6 ♠️7 ♠️8
で場の枚数が3の場合
[ ♠️4 ♠️5 ♠️6 ] [ ♠️5 ♠️6 ♠️7 ] [ ♠️6 ♠️7 ♠️8 ]
を取得します。
グループを取得
指定した枚数以上のグループをすべて取得
//指定した枚数以上のグループをすべてList<ulong>で取得 public List<ulong> GetGroupList(ulong bitCard, int cnt) { var groups = new List<ulong>(); var qpGroup = GetGroupByQPCard(bitCard, cnt); ToBitList(qpGroup).ForEach(q=> { groups.Add(ToBitCard(q, bitCard)); }); } //指定した枚数以上のグループを全て枚数位置型で取得 private ulong GetGroupByQPCard(ulong bitCard, int cnt) { var qpCard = ToQPCard(bitCard); int n = cnt - 1; var noless = 16 - (1ul << n); var cntMask = M0001 * noless; return qpCard & cntMask; } //枚数位置型をBitCard型に変換 public ulong ToBitCard(ulong qpCard, ulong bitCard) { var result = 0ul; while (qpCard != 0) { int i = BitScanForward(qpCard); int r = i / 4; result |= bitCard & (15ul << (r * 4)); qpCard &= qpCard - 1; } return result; } //ビットが1の値をそれぞれ分けてList<ulong>で取得 public List<ulong> ToBitList(ulong bit) { var list = new List<ulong>(); while (bit != 0) { var b = GetMostSignificantBit(bit); list.Add(b); bit ^= b; } return list; }
すべてのグループ(BitCard型)をList<ulong>で取得します。自分が子で、出せる枚数に制限がある場合に使います。
例えば手札が♠️3 ♠️5 ♦️5 ♠️6 ♦️6 ♣️6 ♠️8 ♦️8 ♣️8 ❤️8
で場の枚数が3の場合
[ ♠️6 ♦️6 ♣️6 ] [ ♠️8 ♦️8 ♣️8 ❤️8 ]
を取得します。
すべてのグループを取得
//すべてのグループをList<ulong>で取得 public List<ulong> GetGroupList(ulong bitCard) { return GetGroupList(bitCard, 2); }
すべてのグループ(BitCard型)をList<ulong>で取得します。自分が親で、枚数制限がない場合に使います。
例えば手札が♠️3 ♠️5 ♦️5 ♠️6 ♦️6 ♣️6 ♠️8 ♦️8 ♣️8 ❤️8
の場合
[ ♠️5 ♦️5 ] [ ♠️6 ♦️6 ♣️6 ] [ ♠️8 ♦️8 ♣️8 ❤️8 ]
を取得します。
その他
基準よりランクの高いカードを取得
//基準よりランクの高いカードを取得 private readonly static ulong M1111 = 0xffffffffffffffff; public ulong GetHigherBitCard(ulong bitCard, ulong basisCard, bool isRevolutionzlizing) { if (!isRevolutionzlizing) { int n = BitScanReverse(basisCard); int r = n < 0 ? 0 : n / 4 + 1; var noless = M1111 - ((1ul << r * 4) - 1ul); return bitCard & noless; } else { int n = BitScanForward(basisCard); int r = n < 0 ? 0 : n / 4; var nomore = (1ul << r * 4) - 1ul; return bitCard & nomore; } }
基準のカードよりランクが高い(革命時は低い)カードを取得します。場に出せるカードを抽出するときや、相手が自分より強いカードをどれだけ持っているか計算するときに使います。
Unityによる大富豪の作り方 1 ~ビット演算(基礎)~
はじめに
Unityで大富豪を作ってみたのでそのAIの作り方を書いていきます。AIといっても機械学習とかではなく、ヒューリスティック(経験則的にある場合はAを実行、別の場合はBを実行するという感じで条件を設定し、正解を導ていく)なものです。初心者にも比較的わかりやすいと思います。また、Unityの機能を使っているのは主にUI部分なのでロジックの部分は他のゲームエンジンや言語でも使えるはずです。 最後まで作り上げることを目的としたので大富豪の仕様は
- カードの枚数は52枚でジョーカーは無し。
- 特殊ルールは4枚の同じ数字の組(グループ)、または5枚以上の階段での革命のみ。
- カード交換は無し。
と超シンプルなものにしました。
ビット演算(基礎)
まず、52枚のカードを64ビットで表現(BitCard型)します。詳しい説明は下記サイトを参考にしてください。後編の中盤あたりまで理解すれば大丈夫だと思います。 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桁ごと…と繰り返すだけです。詳しくは下記サイトを参考にしてください。
最も下位にある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の値を得ることができました。
あとはこのすべてが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
これはさっぱりわかりませんね(笑)。詳しくは下記サイトを参考にしてください。
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を最下位から並べる。
を繰り返すって感じです。実行結果を見ながら考えればわかると思います。
Unityでリバーシを作ってみた 8
完成
完成したものがこちら
ソースコードはこちら
まとめ
AIの強さについては私自身が弱いので何とも言えない(Lv1にすら勝てない)。
速度については、下記の状態からの処理時間がそれぞれ
- Lv1(3手読み):24(ms)
- Lv2(5手読み):172(ms)
- Lv3(7手読み):3076(ms)
であった。遅い!特にLv3は遅すぎる。 合法手の取得や石の反転の処理速度を上げたり、置換表の導入すれば改善するのだろうか?合法手の取得や反転の高速化については下記サイトに解説があるのだがいまいち理解ができない(盤の回転ってどうやってるの?) primenumber.hatenadiary.jp
いろいろと研究されているのでネットで調べると情報は大量にでてくる。しかし、技術も時間も足りないので今回はこのレベルで妥協することにした(どうせ機械学習とやらには勝てないのでしょう?)