雨の降る午後、台所のテーブルでおばあちゃんとトランプをしています。遊んでいるのは、おばあちゃん流のCamiciaです。
最初は、いつもどおりの和やかな勝負に見えます。カードをバシッと置き、テーブルをはさんで笑い合い、ときどきNonnaが勝ち誇ったようにほほえみます。でも、ゲームが長引くにつれて、不思議なことが起こります。同じカードが何度も巡ってくるのです。カードを何枚出しても、終わりは見えてきません。
だんだん気になってきます。 このゲームは、いったい終わるのでしょうか? それとも、永遠に遊び続けられるのでしょうか?
後になって、好奇心からインターネットで調べてみると、驚いたことに、あのとき起きたことはただの不運ではなかったとわかります。あなたとおばあちゃんは、もしかすると、ありうるかぎり最も長い並びのひとつに偶然出会っていたのかもしれません! そのとたん、すっかり引き込まれてしまいます。何気ない遊びだったものが、ひとつの探究に変わります。こんなゲームは、実際どこまで長く続くのでしょうか? 台所のテーブルで遊んだものより、もっと長い並びを見つけられるでしょうか? もしかしたら、世界記録を塗り替えられるほど長いものさえ?
こうして、1組のトランプとアルゴリズムを工夫する知恵だけを武器に、その謎を調べてみることにします...
この演習では、古典的なカードゲームCamiciaによく似たゲームをシミュレートします。プログラムは2人のプレイヤーの山札の初期状態を受け取り、ゲームが終わるまで(あるいは永遠に終わらないことを検出するまで)シミュレートします。
終了する試合の小さな例です。
| ラウンド | プレイヤーA | プレイヤーB | 山 | 支払う枚数 |
|---|---|---|---|---|
| 1 | 2 A 7 8 Q 10 | 3 4 5 6 K 9 J | - | |
| 1 | A 7 8 Q 10 | 3 4 5 6 K 9 J | 2 | - |
| 1 | A 7 8 Q 10 | 4 5 6 K 9 J | 2 3 | - |
| 1 | 7 8 Q 10 | 4 5 6 K 9 J | 2 3 A | プレイヤーB:4 |
| 1 | 7 8 Q 10 | 5 6 K 9 J | 2 3 A 4 | プレイヤーB:3 |
| 1 | 7 8 Q 10 | 6 K 9 J | 2 3 A 4 5 | プレイヤーB:2 |
| 1 | 7 8 Q 10 | K 9 J | 2 3 A 4 5 6 | プレイヤーB:1 |
| 1 | 7 8 Q 10 | 9 J | 2 3 A 4 5 6 K | プレイヤーA:3 |
| 1 | 8 Q 10 | 9 J | 2 3 A 4 5 6 K 7 | プレイヤーA:2 |
| 1 | Q 10 | 9 J | 2 3 A 4 5 6 K 7 8 | プレイヤーA:1 |
| 1 | 10 | 9 J | 2 3 A 4 5 6 K 7 8 Q | プレイヤーB:2 |
| 1 | 10 | J | 2 3 A 4 5 6 K 7 8 Q 9 | プレイヤーB:1 |
| 1 | 10 | - | 2 3 A 4 5 6 K 7 8 Q 9 J | プレイヤーA:1 |
| 1 | - | - | 2 3 A 4 5 6 K 7 8 Q 9 J 10 | - |
| 2 | - | 2 3 A 4 5 6 K 7 8 Q 9 J 10 | - | - |
status: "finished", cards: 13, tricks: 1
ループする試合の小さな例です。
| ラウンド | プレイヤーA | プレイヤーB | 山 | 支払う枚数 |
|---|---|---|---|---|
| 1 | J 2 3 | 4 J 5 | - | - |
| 1 | 2 3 | 4 J 5 | J | プレイヤーB:1 |
| 1 | 2 3 | J 5 | J 4 | - |
| 2 | 2 3 J 4 | J 5 | - | - |
| 2 | 3 J 4 | J 5 | 2 | - |
| 2 | 3 J 4 | 5 | 2 J | プレイヤーA:1 |
| 2 | J 4 | 5 | 2 J 3 | - |
| 3 | J 4 | 5 2 J 3 | - | - |
| 3 | J 4 | 2 J 3 | 5 | - |
| 3 | 4 | 2 J 3 | 5 J | プレイヤーB:1 |
| 3 | 4 | J 3 | 5 J 2 | - |
| 4 | 4 5 J 2 | J 3 | - | - |
ラウンド4の開始時点は、ラウンド2の開始時点と同じです。思い出してください。数字カードの値は関係ありません。
status: "loop", cards: 8, tricks: 3
"finished" または "loop"
もっと刺激的な挑戦に取り組みたい人へ。終わりのある最長のゲームの新記録探しは、まだ続いています。 653,534,134,886,878,245,000(およそ6.5×10²⁰)通りの可能性があり、まだすべてを計算し終えていません!
from_quoteの長所と短所Card.from_quote関数は、文字列をCardにパースします。これにより、次のようなコードを書くことができます。
card : Card
card = "Q"
このコードは、コンパイル時に暗黙的にCard.from_quote("Q")を呼び出します。この方法(または後述する他の方法)でコンパイル時にコードを実行すると、実行時にパースやデータの検証を行う必要がないため、プログラムを高速化できる可能性があります。さらに、不正なデータ(たとえば誤った形式の日付など)は実行時ではなくコンパイル時に拒否されるので、アプリがより堅牢になります。最後に、コードが読みやすくなるという利点もあります。たとえば、この演習のテストの一つを見てみましょう。
result = simulate_game({
player_a: ["2", "A"],
player_b: ["3", "4", "5", "6", "K"],
})
しかし、このコードを読んだ人は、simulate_game関数が2つのList(Str)を含むレコードを受け取ると勘違いするかもしれません。実際には、2つのList(Card)を含むレコードです。これは混乱やエラーの原因になりえます。そのため、少し長くなりますがより明示的な"Q".Cardという書き方を好むかもしれません。これもコンパイル時にfrom_quoteを呼び出します。
自分のプログラムでは、代わりにfrom_strを使うほうがよいかもしれません。
Card := { ... }.{
from_str : Str -> Try(Card, [InvalidCard])
from_str = |card_str| ...
}
次のように、コンパイル時にfrom_str(または他の任意の純粋関数)を呼び出すこともできます。
Ok(card) = Card.from_str("Q")
注:この定義をトップレベルに置くと、コンパイル時に実行されます(関数が純粋で、入力がコンパイル時にわかっているためです)。関数の中では、実行時にfrom_strを使うことができます。
matchと[]、[card, .. as rest]を使って、空のデッキと、次のカードや残りのカードを区別します。
{ ..state, pile: new_pile }のようなレコード更新を使うと、可変状態を使わずにゲームの状態遷移を明示的に保てます。
これまでに見たゲームの状態を追跡するときは、Setのキーとしてタプルや配列を保存できます。