C#でつくる素数大富豪、完成品はこんな感じです。
既存の素数大富豪のアプリをみてみると2人対戦（人間VSコンピュータ）の場合、カードを全部配るのではなく、7～13枚になっています。ルールでは最初のカードの枚数は素数であることが望ましいとしています。
では仮に13枚のカードが配られた場合、それをうまく組み合わせれば素数になるかもしれない場合があるのですが、それはどのような場合なのでしょうか？
枚数毎の最大素数大富豪素数を求める – Qiitaをみてみると13枚のカードで作ることができる最大の素数は13131313131312121110111211です。この数は前回の素数判定法では調べることはできません。引数がlong型で表せる数を超えているからです。ではどうするか？ 素数でして出せるカードの枚数を制限するしかなさそうです。だいたいこういう領域でコンピュータに本気を出されたら人間には勝ち目はありません。
比較的小さな数で割りきれることがわかった場合、すぐに素数でないという結果が返ってきますが、素数であるという結果は3以上の奇数でこれ以上やっても意味が無いと見なされる数まで繰り返されるので時間がかかります。実際に素数を渡してみて素数であるという結果が返されるのは13桁くらいまでです（13131313131113が素数であるという結果はすぐに返される）。それ以上だとちょっと厳しいです。
そこで勝手ながら当サイトで作成する素数大富豪では素数として出すことができるカードの枚数は7枚までに限定することにします。
次にコンピュータが次に出すカードを選ぶアルゴリズムですが、手持ちのカードの組み合わせで最小のものを選ぶことにします。また合成数だしもできるようにするには素因数分解も必要です。そこで素因数分解のアルゴリズムを考えます。
N枚出しをする状況で手持ちのカードの組み合わせは何があるか？
その中で素数になるものはあるか？
素数が見つからない場合は合成数出しをできないか考えてみる
このように考えます。実際にゲームに勝つという観点ではダメダメなアルゴリズムですがご容赦ください。
N枚出しをする状況で手持ちのカードの組み合わせは何があるか？
初期のカードの枚数は13枚でコンピュータはミスをしないものとします。実際の素数大富豪ではあえて素数ではないものを出してカードを獲得するという駆け引きもあるそうなのですが、いまは考えないことにします。
出せるカードの組み合わせがどれだけ存在するかは順列を考えればよいことになります。最初のカードは13枚なので最大7枚出せると仮定すると全部で、13×12×11×10×9×8×7 = 8,648,640とおりになります。
ではそのような順列を生成するクラスを作成してみましょう。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
public class Permutation { public IEnumerable<T[]> GetPermutations<T>(IEnumerable<T> items, int length) { return _GetPermutations<T>(new List<T>(), items.ToList(), length); } private IEnumerable<T[]> _GetPermutations<T>(IEnumerable<T> perm, IEnumerable<T> items, int length) { if (items.Count() == 0 || perm.Count() == length) { yield return perm.ToArray(); } else { foreach (var item in items) { var result = _GetPermutations<T>( perm.Concat(new T[] { item }), items.Where(x => x.Equals(item) == false), length); foreach (var xs in result) yield return xs.ToArray(); } } } } |
これで以下のようなコードを書いて実行してみると確かに動作していることがわかります。
|
1 2 3 4 5 6 7 8 9 10 11 |
private void DoProcessing() { int[] cards = { 1, 2, 3, 4, 5, 6 }; Permutation permutation = new Permutation(); var arrayList = permutation.GetPermutations(cards, 3).ToList(); foreach (int[] array in arrayList) { Console.WriteLine(String.Join(", ", array)); } } |
問題はカードの数を増やしたときです。これだと結構な時間がかかります。ゲームにはなりません。
|
1 2 3 4 5 6 7 8 9 10 11 |
private void DoProcessing() { int[] cards = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 }; Permutation permutation = new Permutation(); var arrayList = permutation.GetPermutations(cards, 7).ToList(); foreach (int[] array in arrayList) { Console.WriteLine(String.Join(", ", array)); } } |
そこでコンピュータが出せるカードは4枚までに制限します。
コンピュータが持っているカードで出せるカードを調べるために必要な時間は？
そして試しにカードを適当に配って（この方法では同じ数字のカードが5枚以上配られる可能性があるが・・・）1～4枚の組み合わせで素数がどれくらい存在するか、合成数の場合、素因数分解可能かどうかを調べるためにどれくらい時間がかかるか調べてみましたが、ほぼ一瞬で処理は終わりました。
実行するたびに結果は変わりますが、素数は1500～2000，素因数分解可能な合成数は500～1500くらい存在することがわかります。ただし素因数がカードのなかに含まれるかどうかのチェックはいい加減な方法でやっているのでもう少し時間がかかるかもしれません。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
private void DoProcessing() { Random random = new Random(); // カードを13枚、適当に配る random.Next(13); List<int> cards = new List<int>(); for (int i = 0; i < 13; i++) { cards.Add(random.Next(13) + 1); } List<long> primeNumbers = new List<long>(); List<long> notPrimeNumbers = new List<long>(); List<long> possiblePrimeFactorizationNumbers = new List<long>(); Permutation permutation = new Permutation(); // カードを1～4枚出す場合、素数と合成数出しが可能な数を大雑把に数える for (int i = 1; i <= 4; i++) { // 手持ちのカードからカードを1～4枚取り出す List<int[]> arrayList = permutation.GetPermutations(cards, i).ToList(); // その数は素数か合成数か？ foreach (int[] vs in arrayList) { long num = GetNumber(vs); if (IsPrimeNumber(num)) primeNumbers.Add(num); else notPrimeNumbers.Add(num); } // 合成数の場合、手持ちのカードでつくられる素数で素因数分解可能か？ foreach (long notPrimeNumber in notPrimeNumbers) { long notPrimeNumber1 = notPrimeNumber; // 手持ちのカードでつくられる素数で割り切ることができるなら商を求める // これを繰り返して最終的に商が1になれば素因数分解可能？（この方法では厳密にはチェックできないが・・・） foreach (long primeNumber in primeNumbers) { if (notPrimeNumber1 % primeNumber == 0) notPrimeNumber1 /= primeNumber; } if(notPrimeNumber1 == 1) { // 素因数分解可能 // ただし本当にカードのなかに素因数がすべて存在するかは別途調べる必要がある possiblePrimeFactorizationNumbers.Add(notPrimeNumber); } } } } |
