algorithm - 麻雀のシャンテン数の計算方法を教えてください。

Question

これは、ハンドの準備ができているかどうかの判断に関する以前の質問の補足です。

麻雀のルールの知識は優れていますが、この質問を理解するには、ポーカーまたは ROMME ベースのバックグラウンドでも十分です。

麻雀では 14 枚の牌 (牌はポーカーのカードのようなもの) が 4 セットとペアに配置されます。ストレート (「123」) は常に正確に 3 枚のタイルを使用します。同じ種類のセット (「111」) もちょうど 3 枚のタイルで構成されています。これにより、合計 3 * 4 + 2 = 14 タイルになります。

カンや十三の孤児など、ここでは関係のないさまざまな例外があります。色と値の範囲 (1 ～ 9) もアルゴリズムにとって重要ではありません。

ハンドは 13 枚のタイルで構成され、自分の番になるたびに新しいタイルを選択し、任意のタイルを破棄する必要があるため、13 枚のタイルにとどまります (新しく選択したタイルを使用して勝つことができる場合を除く)。

4 セットとペアを形成するように配置できるハンドが「準備完了」です。牌を 1 枚だけ交換する手札を「てんぱい」または「1 から準備ができている」といいます。他の手札には、天牌になるために何枚の牌を交換する必要があるかを表すシャンテン数があります。したがって、シャンテン数が 1 の手札では、1 枚の牌をテンパイにする必要があります (したがって、2 枚の牌を用意する必要があります)。シャンテン数が 5 の手札は、テンパイになるために 5 枚の牌が必要です。

手のシャンテン数を計算しようとしています。何時間もグーグルで検索し、このトピックに関する複数の記事や論文を読んだ後、これは未解決の問題のようです (ブルート フォース アプローチを除く)。私が見つけた最も近いアルゴリズムは偶然に頼っていました。つまり、100% の確率で正しいシャンテン数を検出できませんでした。

ルール

実際のルール (簡略化されたもの) について少し説明し、次に、このタスクに取り組む方法について考えます。麻雀では、「マン」「ピン」「ソウ」と呼ばれるカードゲームのような通常の 3 つの色 (エース、ハートなど) の 4 つの色があります。これらの色はそれぞれ 1 から 9 まであり、ストレートや同種のグループを形成するために使用できます。4番目の色は「名誉」と呼ばれ、同じ種類のグループにのみ使用できますが、ストレートには使用できません. 7つの栄誉は「E、S、W、N、R、G、B」と呼ばれます。

テンパイ ハンドの例を見てみましょう2p, 3p, 3p, 3p, 3p, 4p, 5m, 5m, 5m, W, W, W, E。次に を選択しEます。これは完全な麻雀ハンド (準備完了) で、2 ～ 4 ピンのストリート (ピンはストレートに使用できることを思い出してください)、3 ピンのトリプル、5 人のトリプル、W トリプル、E ペアで構成されています。

元の手札を に少し変更すると2p, 2p, 3p, 3p, 3p, 4p, 5m, 5m, 5m, W, W, W, E、1 シャンテンの手札になりました。つまり、天牌になるには追加のタイルが必要です。この場合、2p を 3p に交換すると、てんぱいに戻るので、3p と E を引いて勝ちです。

1p, 1p, 5p, 5p, 9p, 9p, E, E, E, S, S, W, W2シャンテンのハンドです。完成したトリプレットが1つとペアが5つあります。最後に 1 つのペアが必要なので、1p、5p、9p、S、または W のいずれかを選択したら、残りのペアの 1 つを破棄する必要があります。例: 1 ピンをピックし、W を破棄します。ハンドは現在 1 シャンテンにあり、次のようになります1p, 1p, 1p, 5p, 5p, 9p, 9p, E, E, E, S, S, W。次に、5p、9p、または S のいずれかを待ちます。5p を選択して残りの W を破棄すると仮定すると、次のようになります1p, 1p, 1p, 5p, 5p, 5p, 9p, 9p, E, E, E, S, S。このハンドはテンパイで、9 ピンまたは S でコンプリートできます。

このテキストがさらに長くなるのを避けるために、ウィキペディアでより多くの例を読んだり、Google でさまざまな検索結果の 1 つを使用したりできます。ただし、それらはすべてもう少し技術的なものなので、上記の説明で十分であることを願っています.

アルゴリズム

述べたように、ハンドのシャンテン数を計算したいと思います。私のアイデアは、タイルを色に応じて 4 つのグループに分割することでした。次に、すべての牌がそれぞれのグループ内のセットに分類され、栄誉グループのトリプレット、ペア、またはシングル タイル、または 3 つの通常グループのストライトになります。完成したセットは無視されます。ペアがカウントされ、最終的な数が減ります (最終的に 1 ペアが必要です)。この数に単一のタイルが追加されます。最後に、数字を 2 で割ります (天牌に近づく良い牌を選ぶたびに、別の不要な牌を取り除くことができるため)。

しかし、このアルゴリズムが正しいことを証明することはできませんし、近距離に多くの牌を含む難しいグループにストレートを組み込むことにも苦労しています。あらゆる種類のアイデアが高く評価されます。私は .NET で開発していますが、疑似コードや読み取り可能な言語も歓迎します。

Answer 1

この問題についてもう少し考えてみました。最終結果を確認するには、最後のセクションにスキップしてください。

最初のアイデア: ブルート フォース アプローチ

まず、力ずくのアプローチを書きました。1 分以内に 3 シャンテンを特定できましたが、あまり信頼性が高くありませんでした (場合によっては、あまりにも長い時間がかかり、3 シャンテンだけでも空間全体を列挙することは不可能です)。

ブルートフォースアプローチの改善

頭に浮かんだことの 1 つは、ブルート フォース アプローチにインテリジェンスを追加することでした。単純な方法は、残りの牌を追加し、それが麻雀を生成したかどうかを確認し、そうでない場合は、次の牌が見つかるまで再帰的に試行することです。約 30 の異なるタイルが残っていて、最大深度が 6 であると仮定すると (7+シャンテン ハンドが可能かどうかはわかりません[編集: 後で開発された式によると、可能な最大シャンテン数は (13-1 )*2/3 = 8] )、(13*30)^6 の可能性が得られ、これは大きい (10^15 の範囲)。

ただし、残りのタイルをすべて手札のすべての位置に置く必要はありません。すべての色はそれ自体で完全でなければならないため、タイルをそれぞれの色グループに追加し、グループがそれ自体で完全であるかどうかを書き留めることができます。全体でちょうど 1 ペアにするなどの詳細を追加するのは難しくありません。このように、最大​​で (13*9)^6 程度の可能性があります。つまり、10^12 程度以上の可能性があります。

より良い解決策: 既存の麻雀チェッカーの修正

次のアイデアは、以前に書いたコードを使用して麻雀をテストし、次の 2 つの方法で変更することでした。

• 無効な手が見つかったときに停止しないで、欠けているタイルを書き留めます
• タイルを使用する方法が複数ある場合は、それらすべてを試してみてください

これは最適なアイデアであり、いくつかのヒューリスティックを追加すると、最適なアルゴリズムになるはずです。しかし、実装するのは非常に難しいことがわかりました - それは間違いなく可能です。最初にソリューションを作成して維持するのが簡単な方がいいと思います。

ドメイン知識を活用した高度なアプローチ

より経験豊富なプレイヤーと話すと、使用できる法律がいくつかあるようです. たとえば、3 つのタイルのセットを分割する必要はありません。分割してもシャンテン数が減少することはありません。ただし、さまざまな方法で使用できます (たとえば、111 または 123 の組み合わせのいずれか)。

考えられるすべての 3 セットを列挙し、それぞれについて新しいシミュレーションを作成します。3セットを外します。結果の手ですべての 2 セットを作成し、それらを 3 セットに改善するすべてのタイルをシミュレートします。同時に、削除される 1 セットのいずれかをシミュレートします。3 セットと 2 セットがすべてなくなるまで、これを続けます。最後に 1 セット (つまり、1 つのタイル) を残す必要があります。

実装と最終的なアルゴリズムからの学習

上記のアルゴリズムを実装しました。理解を容易にするために、擬似コードで書き留めました。

Remove completed 3-sets
If removed, return (i.e. do not simulate NOT taking the 3-set later)

Remove 2-set by looping through discarding any other tile (this creates a number of branches in the simulation)
If removed, return (same as earlier)

Use the number of left-over single tiles to calculate the shanten number

ちなみに、これは私が自分で数を計算するときに取ったアプローチと非常によく似ており、明らかに大きすぎる数にはなりません。

これは、ほとんどすべてのケースで非常にうまく機能します。ただし、以前の仮定 (「既に完了した 3 セットを削除することは決して悪い考えではない」) が間違っている場合があることがわかりました。反例: 23566M 25667P 159S. 重要な部分は25667. 5673セットを削除すると、残りの6牌になり、5シャンテンにつながります. 56x単牌を2枚使って と を形成し67x、全体で4シャンテンにするのが良いでしょう。

修正するには、間違った最適化を削除する必要があり、次のコードにつながります。

Remove completed 3-sets
Remove 2-set by looping through discarding any other tile
Use the number of left-over single tiles to calculate the shanten number

これは常に最小のシャンテン数を正確に見つけると信じていますが、それを証明する方法がわかりません。所要時間は「妥当な」範囲内です (私のマシンでは最大 10 秒、通常は 0 秒)。

最後のポイントは、残ったシングル タイルの数からシャンテンを計算することです。まず第一に、数字がフォームにあることは明らかです3*n+1(14 枚のタイルから始めて、常に 3 枚のタイルを差し引いたため)。

タイルが 1 つ残っている場合は、既にシャンテンです (最後のペアを待っているだけです)。4 枚のタイルが残っているので、そのうちの 2 枚を捨てて 3 セットを形成し、再び 1 枚のタイルを残す必要があります。これにより、さらに 2 つの廃棄が発生します。タイルが 7 枚の場合、2 かける 2 の破棄があり、4 が追加されます。

これにより、簡単な式が得られshanten_added = (number_of_singles - 1) * (2/3)ます。

説明されているアルゴリズムはうまく機能し、すべてのテストに合格したので、正しいと思います。おっしゃるとおり、証明はできませんが。

アルゴリズムは最も可能性の高いタイルの組み合わせを最初に削除するため、最適化が組み込まれています。簡単なチェックを追加すると、if (current_depth > best_shanten) then return;シャンテン数が多い場合でも非常にうまく機能します。

Answer 2

私の最善の推測は、A* にインスパイアされたアプローチです。シャンテン数を決して過大評価しないヒューリスティックを見つけ、それを使用して、十分に迅速に準備完了状態に入ることが可能な領域でのみブルート フォース ツリーを検索する必要があります。

Answer 3

少し考えて、まふとは少し違う処方にたどり着きました。まず、ハンド (非常にひどいハンド) を考えてみましょう。

1s 4s 6s 1m 5m 8m 9m 9m 7p 8p 西 東 北

mafu のアルゴリズムを使用することで、できることはペア (9m,9m) をキャストすることだけです。その後、11のシングルが残ります。ここで、まふの式を適用すると、(11-1)*2/3 が得られます。これは整数ではないため、シャンテン数にはなりません。これは私がこれを思いついた場所です：

N = ( (S + 1) / 3 ) - 1

N はシャンテン ナンバー、S はスコア サムを表します。スコアとは？不完全なセットを完全にするために必要なタイルの数です。たとえば、手札に (4,5) がある場合、完全な 3 セット、つまり 1 枚のタイルにするためには 3 または 6 が必要です。したがって、この不完全なペアはスコア 1 になります。したがって、(1,1) は 1 だけで 3 セットになります。1 つのタイルが 3 セットになるには明らかに 2 タイルが必要で、スコアは 2 になります。もちろん、完全なセットはスコア 0 になります。シングルがペアになる可能性は無視されることに注意してください。上記の手ですべての不完全なセットを見つけようとすると、次のようになります。

(4s,6s) (8m,9m) (7p,8p) 1s 1m 5m 9m 西 東 北

次に、そのスコアの合計を数えます = 1*3+2*7 = 17。この数値を上記の式に適用すると、(17+1)/3 - 1 = 5 が得られます。これは、このハンドが 5 シャンテンであることを意味します。 . アレクセイのものよりやや複雑で、証拠はありませんが、今のところうまくいくようです。そのようなハンドは別の方法で解析できることに注意してください。例えば：

(4s,6s) (9m,9m) (7p,8p) 1s 1m 5m 8m 西 東 北

ただし、計算式によると、それでも合計 17 と 5 シャンテンを取得します。私もこれを証明することはできず、これは Alexey の式よりも少し複雑ですが、他の何かに適用 (?) できるスコアも導入しています。

Answer 4

正しいアルゴリズムのサンプル: syanten.cpp

手から順番にフォームを再帰的にカットします: セット、ペア、不完全なフォーム、そしてそれを数えます。すべてのバリエーションで。結果は、すべてのバリアントの最小シャンテン値です: Shanten = Min(Shanten, 8 - * 2 - - )

C# のサンプル (c++ から書き直したもの) は、こちら(ロシア語) にあります。

Answer 5

手札が既にてんぱいになっているかどうかを判断するのは、複数のナップザックの問題のように思えます。貪欲なアルゴリズムは機能しません。Dialecticus が指摘したように、問題空間全体を考慮する必要があります。