麻雀で確実に勝つ方法はあるのでしょうか？チェス、囲碁、麻雀、テキサスホールデム…どのゲームがより複雑でしょうか?

多くの子供たちは、チェス、囲碁、麻雀、ポーカーなどのボードゲームが好きです。対戦相手と戦っているとき、これらのゲームに勝つための戦略はあるのだろうか、と疑問に思ったことはありませんか。

ある日、洞窟で偶然チート本を見つけて、特定のチェスやカードゲームの必勝法を手に入れ、Deep Blue と AlphaGo がすべて屈服しなければならなくなったら、それは何と名誉なことでしょう。

今日はこの問題について議論しましょう。

ツェルメロの定理

まず、ゲームを完全情報ゲームと不完全情報ゲームの 2 つのタイプに分類する必要があります。ゲームのどの段階でも参加者全員が過去と現在のゲーム情報をすべて知ることができる場合、このタイプのゲームは完全情報ゲームと呼ばれます。それ以外の場合は、不完全情報ゲームと呼ばれます。

例えば、チェス、囲碁、ゴバンでは、誰もが相手の動きを見ることができ、完全情報ゲームです。しかし、これは軍事チェスには当てはまりません。四国軍事チェスでは、相手の軍隊の配置はわかりませんし、チェスの駒を裏返しても自分の駒がどこにあるかさえわかりません。ポーカーでは、相手がどんなカードを持っているか分かりません。麻雀では、相手の手札が何であるか分からないだけでなく、テーブルに残っているカードも分かりません。チェス、ポーカー、麻雀などのゲームは不完全情報ゲームと呼ばれます。

1913 年、数学者ツェルメロは、2 人のプレイヤーによる完全情報ゲームでは、最初のプレイヤーが勝つか、2 番目のプレイヤーが勝つか、または両方のプレイヤーが引き分けになるような戦略が必ず存在することを証明しました。これがツェルメロの定理です。

ツェルメロ

この定理をどのように証明するのでしょうか?実はとても簡単です。チェスを順番に動かすゲームでは、各ステップを実行する方法が限られており、これをゲームブランチと呼びます。ゲームの分岐は有限です。勝ち負けや引き分けには一定のルールがあるため、ゲームのステップ数は限られています。

非常に単純なゲームがあると仮定します。最初のプレイヤー A と 2 番目のプレイヤー B がそれぞれ決定を下します (上のレーンを選択するか、下のレーンを選択するか)。 2 つの決定の結果に基づいて、ゲームの結果は次のようになります。この表から、誰がゲームに勝つかわかりますか?

ゲームの戦略と結果

生徒の中には、A の方が勝つ可能性が高いと考える人もいるかもしれませんが、そうではありません。このチェスのゲームの結果は引き分けになるはずです (ただし、一方が本当に頭をうまく使わなかった場合は負けになります)。ゲームツリーを描いて説明することができます。

ゲームツリー

プレイヤー A がトップポジションを選択した場合、ゲームはプレイヤー B が決定を下す分岐、つまりサブゲームに入ります。このサブゲームでは、B が上のオプションを選択した場合、A が勝ちます。 B が下の選択肢を選択した場合、B が勝ちます。 B は自分にとって有利なオプションを選択しなければならないため、より低いオプションを選択する必要があります。このサブゲームの結果は固定されており、B が勝ちます。

A が最初に下の位置を選択した場合、ゲームは別のサブゲームに入り、B が決定を下します。 B がトップポジションを選択した場合、A が勝ちます。 B が下の位置を選択した場合、ゲームは引き分けで終了します。 B は自分にとって有利なポジションを選択しなければならないため、このサブゲームの結果は必ず引き分けになります。

もう一度 A について考えてみましょう。A が上へ移動してサブゲーム 1 に入ると、B は確実に勝ちます。 A が下に移動してサブゲーム 2 に入ると、ゲームは確実に引き分けになります。 A も自分にとって有利なものを選択しなければならないため、以下のものを選択します。最終戦は引き分けです。

ゲームが複雑になると、分岐が増えて長くなります。しかし、最後のサブゲームから始めて、レイヤーごとに逆方向に作業を進めていく限り、最適な戦略に基づいて、ゲームが引き分けで終わるか、最初のプレイヤーが勝つかを判断できるようになります。このような勝利や敗北は避けられない。

たとえば、五目並べでは、両者が交互に手を動かし、5 つの手をつなぐ方が勝ちます。人々は、主導権を握れば確実に勝てる方法があることを徐々に発見しました。ゲームを公平にするために、3-3 の禁じ手、4-4 の禁じ手、長期の禁じ手を設計しました。先に禁じられた動きをした人が負けます。

禁止された動きのない、Gobang の確実な勝利の 2 つのオープニング

囲碁と比べると、中国将棋や囲碁のルールははるかに複雑ですが、それでも完全な情報を持つ2人用のゲームです。最適なルーチンが何であるかはわかりませんが、そのような最適な戦略が存在するはずだと確信しています。双方がこの戦略を実行した場合、先に行動した方が勝つか、後から行動した方が勝つか、あるいはゲームは引き分けで終了します。

しかし、チェスや囲碁で勝つ方法を習得したという話を聞いたことがないのはなぜでしょうか?

三目並べ

最も単純なチェスゲームである三目並べを例に挙げてみましょう。

三目並べはとても簡単です。まず三目並べを描き、次に最初の手で十字を描き、2 番目の手で円を描き、9 つのグリッドを交互に描きます。 3 つのピースが水平、垂直、斜めに一直線につながった人が勝ちます。盤面がいっぱいでどちらの側も勝てない場合は引き分けとなります。たとえば、先手が勝つ三目並べゲームを次に示します。

三目並べのゲーム

このゲームのルールはシンプルですが、実際にはかなり多くのバリエーションがあるため、非常にプレイしやすいです。もっと正確に言えば、それはゲームの複雑さと呼ぶべきでしょう。

まず、ボード上で起こり得る状況がいくつあるかを示す、ゲームの状態の複雑さについて説明します。一般的に言えば、ゲームの状態の複雑さを正確に計算することはできず、多くの場合、正確に計算する必要はありません。上限または桁数を推定する必要があるだけです。

たとえば、三目並べでは、各マスには十字、丸、空白の 3 つの可能性があります。合計で 9 つのマス目があるので、起こり得る状況の最大数は 39 = 19683 を超えません。ルールに従わない状況は数多くあります。たとえば、フォークの数は円の数と同じか、1 つ多くなります。その他の状況はすべて規則に準拠しません。対称的な状況は、実際には 1 つの状況としてカウントされる必要があります。これらすべての不規則性と対称性を取り除くと、残る状態の数は 765 になります。これは、三目並べで見られる唯一の 765 の状況です。

同じ状況に異なるパスで到達できるため、状態の数はゲームの複雑さを測定する唯一の方法ではありません。ゲームプレイの可能性の総数を調べるには、ゲームツリーのサイズを計算する必要があります。

三目並べゲームツリーの一部

見てください: 対称性を削除して最初の十字を手で描く場合、実際にはそれを描く方法は、中央、辺の中点、および角の 3 つしかありません。これは 3 つの枝を持つツリーの最初のレベルです。

最初の手が真ん中に十字を描いて対称性が失われると、2 番目の手が描く円は角と辺の中点の 2 つの方法しかなくなります。最初の手が端または角に描く場合、2 番目の手は図に示す 5 つの方法で描きます。これはツリーの 2 番目のレベルで、12 個の枝があります。

その後、ゲームには多くの層があり、各層には多くの分岐があり、最終的に一方が勝つか、ゲームが引き分けで終了します。ゲームツリー内の異なるパスの数は、ゲームの可能なバリエーションの数を表します。

三目並べのゲームでは、ゲームツリーの複雑さを推定できます。最初のプレイヤーが最初に位置を選択し、9 つの可能性があります。 2 番目のプレイヤーには 8 つの可能性しか残っておらず、1 番目のプレイヤーには 7 つの可能性しか残っていません... 9 つのグリッドがすべて埋まるまで、ゲーム ツリーの複雑さは 9!=362880 を超えません。ルールに従わないものがたくさんあります。たとえば、一方がすでに勝っている場合は、それ以上プレイする必要はありません。重複と対称性も削除する必要があります。最終的なゲームツリーの複雑さは 26830 です。

三目並べにおける 26,830 通りの可能なパスをすべて調べた結果、両方のプレイヤーが最適な戦略を使用した場合、三目並べは必ず引き分けになることがわかりました。

先手を取るための最善の戦略

2手目のための最善の戦略

このようにゲームツリーが完全に描かれ、最適な戦略が見つかったゲームを解決されたゲームと呼びます。それにもかかわらず、ほとんどの場合、三目並べには勝者と敗者が存在します。これは、ゲームツリーをよく理解している人もいれば、そうでない人もいるためです。相手がミスをすると、ゲームツリーについて十分な情報を持っている人はすぐにこの抜け穴をつかみ、プレイ方法を知らない人を必ず失敗するゲームツリーの枝に陥らせることができます。これが達人と初心者の違いです。

行く

実際、チェスや囲碁は三目並べと根本的に違いはありませんが、三目並べよりもはるかに複雑です。

行く

Go を例に挙げてみましょう。囲碁では、チェスの駒は 19x19=361 のマス目に順番に配置されるため、各マスには黒、白、空白の 3 つの可能性があります。囲碁盤全体の状態数の上限は3361=1.7x10172です。いくつかの繰り返しと対称性を除くと、囲碁の状態複雑度は約 10171 のオーダーになります。

宇宙には原子が約 1080 個しかないことを知っておく必要があります。宇宙の 1 つの原子を使って囲碁の状況を表現したとしても、宇宙のすべての原子を使ったとしても、囲碁の状況をすべて表現することはできません。

囲碁のゲームツリーを描くのはさらに難しいです。囲碁では、空きスペースがあるときにも駒を進めてゲームを続けることができるため、必ずしも盤面が完全に埋まったときにゲームが終了するわけではありません。ただし、ゲームツリー内のレベルの合計数と各レベルのブランチの平均数を推定することはできます。統計と計算によると、囲碁のゲームでの平均移動数は 150 で、各移動の平均分岐数は 250 なので、囲碁のゲームツリー全体の複雑さは約 250150≈10360 になります。

理論的には、10,360 通りの状況をすべて検討すれば、最初のプレイヤーが勝つのか、2 番目のプレイヤーが勝つのか、それとも確実に引き分けになるのかがわかります。しかし、計算量が多すぎます。世界最速のコンピュータ「富岳」は、1秒間に最大10京回の浮動小数点演算を実行できます。 1 回の浮動小数点演算でパスを計算できる場合、囲碁ゲームで起こり得るすべての状況を計算するには 10342 秒かかります。宇宙の年齢はわずか138億年で、これはおよそ1017秒に相当します。

明らかに、囲碁には最適な戦略があるはずだということはわかっていますが、この最適な戦略を計算することはできません。

しかし、数学者は、あらゆる状況を検討することなく、勝つためのより良い方法を見つけることができる他の方法もいくつか発見しました。たとえば、ディープ・ブルーは1997年にチェスの世界チャンピオン、カスパロフを破り、アルファ碁は2016年に無敵になりましたが、どちらも人工知能の手法を採用しています。

人工知能が人間に勝利した経緯

囲碁以外にも、以下の表に示すように、他のボードゲームの複雑さも推定されています。三目並べのケースは非常に少ないので、マスターするのは簡単です。二人の名人が対戦すると、結果は引き分けとなる。 Gobang にはさらに多くの状況がありますが、プレイし続けることで、ルーチンを発見してマスターできるようになります。禁止された動きがない場合、先攻が勝ちます。チェス、中国将棋、囲碁と同様に、複雑さはさらに高くなります。

軍事チェス

先ほど説明したいくつかの種類のチェスは複雑さのレベルが異なりますが、すべて明確なチェスであり、ゲームの両当事者が現在の状況を完全に認識していることを意味します。この種のチェスには最適な解があります。最適な解決策に近い人ほど、チェスのスキルが高くなります。偶然でもない限り、チェスのスキルが低い人がチェスのスキルが高い人に勝つことは決してできません。たとえば、AlphaGo と囲碁をプレイしても、絶対に勝てません。

しかし、プレイヤーがすべての駒の状態を知らないチェスゲームもあります。時には、運が良ければ、チェスのスキルが低い人がチェスのスキルが高い人に勝つこともあり、ゲームに多くの楽しみが加わります。この種のダークチェスは不完全情報ゲームです。

たとえば、軍隊チェスを覚えていますか?

軍事チェス

各サイドには 25 個のチェスの駒があります。指揮官は陸軍指揮官を捕獲でき、陸軍指揮官は師団指揮官を捕獲でき、エンジニアは地雷を掘ることができます。地雷を掘り、軍旗を掲げた者が勝者となる。軍事チェスの遊び方はたくさんありますが、その 1 つは、ゲーム開始前に、敵に見られないように秘密裏に軍隊を配置し、25 個の駒を 25 個の位置に配置する必要があるというものです。 2 つの駒が出会ったとき、審判がどちらがどちらを捕獲するかを決定します。つまり、どちらの側も相手の駒が何であるかを知りません。子どもの頃は特に軍事チェスをするのが好きでした。運が良ければ、私の指揮官が敵の指揮官を食べたり、敵の指揮官が私の地雷を踏んだりして、とても幸せでした。

軍事チェスの複雑さをどのように説明すればよいでしょうか?情報セットの概念が必要です。

情報セットのサイズは、すべての未知の情報の可能な数を表します。たとえば、張三と対戦しているとき、張三が軍隊を配置する方法を 10 種類しか知らないことはわかっていますが、どれを選んだのかはわかりません。この時点で情報セットのサイズは 10 です。

情報セットの数は、既知のすべての情報の可能な数を表します。たとえば、オープニングフォーメーションを 5 つしか知らない場合、情報セットの数は 5 になります。

考えてみてください。私と張三が対戦するとき、起こり得る状況はいくつありますか？ 50種類くらいあるんじゃないですか？情報セットのサイズと情報セットの数を掛け合わせるだけです。実際、2 人で対戦する場合、各側に 25 個の駒があり、それぞれ独自の 25 個の軍事ステーションに配置されます。ゲーム開始時の軍将棋情報セットのサイズと数はともに25です。 =1.5x1025 種（重複する種は無視）。

軍事チェス盤

ここで、情報セットのサイズと情報セットの数という、一次元的な状況から二次元的な状況に変わりました。情報セットのサイズは未知の可能性の集合を表し、情報セットの数は既知の状態の総数を表します。不完全情報ゲームには 2 つの複雑さの次元があります。

麻雀

私たちの国民的スポーツである麻雀を見てみましょう。

麻雀

麻雀は隠れたチェスゲームでもあります。カードは34種類、各4枚ずつ、合計136枚。ゲームの開始時に、各パーティは 13 枚のカードを引きます。各ラウンドで、プレイヤーはカードを 1 枚引いてから、別のカードをプレイします。最後に14〜16枚のカードが残っていて、誰も勝っていない場合は、ゲームは終了します。私たちは自分の手札のカードは知っていますが、他の人の手札のカードや、自分や他の人たちが引けるカードは知りません。そのため、これは不完全情報ゲーム、つまりダークチェスゲームです。

情報セットの数とサイズを計算してみましょう。

第1ラウンド

情報セット数：麻雀牌は全部で136枚あります。重複を無視して、13 個のタイルで開始します。タイルを入手する方法はいくつかあります。

情報セットサイズ: 手札の 13 枚に加えて、カードは 123 枚あります。他の 3 人のプレイヤーはそれぞれ 13 枚のカードを持っているので、未知数の可能性のある数は次のようになります。

第2ラウンド

情報セットの数: 最初のラウンドでは、4 人のプレイヤーがそれぞれ 1 枚のタイルをプレイしました。麻雀牌は34種類あるので、牌の遊び方は344通りあります。この時点でまだ手札は13枚あり、対処する方法はあります。さて、私が直面する可能性のある状況は次の通りです。

情報セットのサイズ: 手札の 13 枚と前のラウンドでプレイした 4 枚のカードに加えて、残っているカードは 119 枚です。 3 人のプレイヤーはそれぞれ 13 枚のカードを持っています。可能な数字は複数あります。

…

麻雀は残り牌が 14 〜 16 枚になると終了するため、プレイできるラウンド数は最大で約 17 回です。この方法に従って、この 17 ラウンドの情報セットの数とサイズを次の表に示します。

麻雀の各ラウンドにおける情報セットの数とサイズ

図を使ってわかりやすく説明しましょう。

ゲームが進むにつれて、情報セットの数がどんどん大きくなり、つまり観察できる可能性のある状況の数が増えることがわかります。情報セットのサイズはどんどん小さくなり、それはつまり、自分が知らない状況が発生する可能性がどんどん小さくなることを意味します。

また、麻雀では情報セットの総数は約 10115 であり、これが麻雀をプレイするときに見ることができる状態の総数の上限であることも計算できます。それぞれの状況において、情報セットの平均サイズは約 1049 で、これは、私たちには知られていない、他の人の手札にあるカードの可能な組み合わせです。情報セットの総数に平均情報セットサイズを掛けると、麻雀の状態の複雑さを推定でき、それは約 10^165 になります。

Microsoft Research Asia はかつて、いくつかのボードゲームの状態の複雑さを比較したことがあります。このグラフでは、縦軸は情報セットの大きさ、つまり不確実性を表しています。横軸は情報セット数、つまりオープン部分の変化を表します。

Microsoft Research Asiaが作成したチェスとカードの複雑さのチャートを参照してください。

三目並べ、国際チェッカー、中国将棋、チェス、囲碁では、不確実性がまったくないため、情報セットのサイズは 1 であり、情報セットの数という 1 つの次元のみがあることがわかります。先ほど述べたように、これらのチェスゲームにはそれぞれ最適な戦略があります。

麻雀、ブリッジ、テキサスホールデムでは、配られるカードに多くのバリエーションがあることに加え、同じ状況であっても、他の人には多くの可能性のあるカードがあります。これらは 2 次元の不完全情報ゲームです。比較すると、麻雀の情報セットサイズはブリッジやテキサスホールデムよりもはるかに大きく、これは麻雀の方が不確実性が大きく、麻雀では運がより重要であることを意味します。

ゲームに 2 つの次元があり、不確実性がある限り、一般的に勝利戦略は存在しません。当然ですが、私のカードが十分に良い限り、あなたのレベルがどれだけ高くても、麻雀で私に負ける可能性が高くなります。麻雀などの不完全情報ゲームの問題の計算におけるコンピュータの進歩は、チェスや囲碁に比べて大幅に遅れています。

麻雀には多くの変化と不確実性があり、そのため普通のプレイヤーが名人に勝つことも可能です。時折起こるサプライズが多くの人を夢中にさせます。麻雀をするときは流れに身を任せなければなりません。カードのスキルがどれだけ優れていても、ゲームの展開をコントロールできない場合があります。たとえば、麻雀をしていて、すべてのハンドで勝ちたい場合、おそらく一晩中負けてしまうでしょう。

麻雀ってこういうものですよね、人生も同じではないでしょうか？

終わり