マジョンのシャンテン数を計算するにはどうすればよいですか？

Question

これは私のフォローアップです 手が準備ができているかどうかを決定することについての以前の質問.

マジョンのルールに関する知識は優れているでしょうが、ポーカーまたはロムベースの背景もこの質問を理解するのに十分です。

Mahjongでは、14タイル（タイルはポーカーのカードのようなものです）は、4セットとペアに配置されています。ストレート（ "123"）は常に正確に3つのタイルを使用しますが、それ以上ではありません。同じ種類（ "111"）のセットも、正確に3つのタイルで構成されています。これにより、3 * 4 + 2 = 14タイルの合計につながります。

カンや13の孤児のようなさまざまな例外がありますが、ここでは関連していません。色と値の範囲（1-9）もアルゴリズムにとって重要ではありません。

手は13個のタイルで構成されており、順番になるたびに、新しいタイルを選択し、タイルを破棄して13個のタイルにとどまる必要があります。

4セットとペアを形成するように配置できる手は「準備ができています」。交換するのに1タイルのみを必要とする手は、「テンパイ」または「1つの準備ができている」と言われています。他の手には、テンパイにあるために交換する必要があるタイルの数を表すシャンテン番号があります。したがって、シャンテン数の1つの手には、1タイルがテンパイ（それに応じて準備が整うために2つのタイル）を必要とします。シャンテン番号のある手には、5つのタイルがテンパイなどである必要があります。

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

ルール

実際のルール（簡素化）について少し説明し、次にこのタスクに取り組む方法について説明します。マジョンには、「マン」、「ピン」、「sou」と呼ばれるカードゲーム（エース、ハート、...）のような3つの通常の色があります。これらの色はそれぞれ1〜9で動作し、同じ種類のグループと同様にストレートを形成するために使用できます。フォースカラーは「名誉」と呼ばれ、同じ種類のグループにのみ使用できますが、ストレートでは使用できません。 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-Shantenに手を入れました。つまり、テンパイにするには追加のタイルが必要です。この場合、2Pを3Pと交換すると、Tenpaiに戻り、3PとEを描画することで勝ちます。

1p, 1p, 5p, 5p, 9p, 9p, E, E, E, S, S, W, W 2シャンテンの手です。完成したトリプレットと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でさまざまな検索結果のいずれかを使用します。それらはすべてもう少し技術的なものですので、上記の説明が十分であることを願っています。

アルゴリズム

述べたように、私は手のシャンテン数を計算したいと思います。私の考えは、その色に応じてタイルを4つのグループに分割することでした。次に、すべてのタイルは、それぞれのグループ内のセットに分類され、最終的には、名誉グループのトリプレット、ペア、または単一のタイル、さらには3つの通常のグループのストライトがあります。完了したセットは無視されます。ペアがカウントされ、最終番号が減少します（最終的には1ペアが必要です）。この番号に単一のタイルが追加されます。最後に、数を2で割っています（テンパイに近づく良いタイルを選ぶたびに、別の不要なタイルを取り除くことができます）。

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

Answer 1

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

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

まず第一に、私はブルートフォースアプローチを書きました。 1分以内に3シャンテンを識別することができましたが、それはあまり信頼できませんでした（時にはずっと長すぎることもあり、3シャントだけでもスペース全体を列挙することは不可能です）。

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

頭に浮かぶのは、ブルートフォースのアプローチに知性を追加することでした。素朴な方法は、残りのタイルのいずれかを追加し、それがマジョンを生成したかどうかを確認し、発見されるまで次の再帰的に試してみることです。約30の異なるタイルが残っており、最大深度は6であると仮定します（7+-Shantenの手が均一であるかどうかはわかりません 編集：後で開発された式によると、可能な最大のシャンテン数は（13-1）*2/3 = 8]です。）、（13*30）^6の可能性を取得します。これは大きい（10^15の範囲）。

ただし、手のすべての位置にすべての残りタイルを置く必要はありません。すべての色はそれ自体が完全である必要があるため、それぞれの色グループにタイルを追加し、グループがそれ自体が完全であるかどうかを書き留めることができます。全体で正確に1ペアを持つなどの詳細は、追加するのが難しくありません。これにより、最大（13*9）^6の可能性があります。

より良い解決策：既存のマジョンチェッカーの変更

私の次のアイデアは、私が早く書いたコードを使用してマジョンをテストし、2つの方法で変更することでした。

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

これは最適なアイデアである必要があり、いくつかのヒューリスティックを追加することで、最適なアルゴリズムである必要があります。しかし、私は実装することが非常に難しいと感じました - しかし、それは間違いなく可能です。最初に解決策を書き、維持しやすいことを望んでいます。

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

より経験豊富なプレーヤーと話すと、使用できる法律がいくつかあるように見えます。たとえば、3つのタイルのセットを分割する必要はありません。これは、Shanten数を減らすことはないためです。ただし、さまざまな方法で使用する場合があります（たとえば、111または123の組み合わせのいずれか）。

可能なすべての3セットを列挙し、それぞれに新しいシミュレーションを作成します。 3セットを削除します。次に、結果の手にすべての2セットを作成し、3セットに改善するすべてのタイルをシミュレートします。同時に、削除される1セットのいずれかをシミュレートします。すべての3セットと2セットがなくなるまでこれを続けてください。最終的に1セット（つまり、単一のタイル）を残す必要があります。

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

上記のアルゴリズムを実装しました。理解しやすくするために、私はそれをpseudocodeで書き留めました：

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. 。 aを削除します 567 3セット残り残りになります 6 5シャンテンにつながるタイル。 2つの単一タイルを使用して形成する方が良いでしょう 56x と 67x, 、全体的に4-Shantenにつながります。

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

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倍の破棄があり、4つを追加します。

これは、単純な式につながります shanten_added = (number_of_singles - 1) * (2/3).

説明されているアルゴリズムはうまく機能し、すべてのテストに合格したので、正しいと思います。述べたように、私はそれを証明することはできません。

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

Answer 2

私の最善の推測は、A*インスピレーションを受けたアプローチです。 Shanten数を過大評価しないヒューリスティックを見つける必要があり、それを使用して、すぐにすぐに準備ができている状態に入ることができる地域でのみブルートフォースツリーを検索します。

Answer 3

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

手からの再帰カットフォーム：セット、ペア、不完全なフォーム、およびカウント。すべてのバリエーションで。結果はすべてのバリエーションの最小限のシャンテン値です：shanten = min（shanten、8- * 2--）

C＃サンプル（C ++から書き換え）が見つかります ここ （ロシア語で）。

Answer 4

私は少し考えて、マフーとは少し異なる式を思いつきました。まず第一に、手を考えてください（非常にひどい手）：

1S 4S 6S 1M 5M 8M 9m 9m 7p 8p West East North

Mafuのアルゴリズムを使用することで、できることはペア（9m、9m）をキャストすることです。その後、11のシングルが残ります。 Mafuの式を適用すると、整数ではないため、Shanten番号になることはできません（11-1）*2/3が得られます。これが私がこれを思いついたところです：

n =（（s + 1） / 3）-1

nは、スコア合計のShanten番号とSの略です。スコアとは何ですか？不完全なセットを完全にするために必要なタイルの多くです。たとえば、手に（4,5）がある場合は、完全な3セット、つまり1つのタイルのみにするために3または6のいずれかが必要です。したがって、この不完全なペアはスコア1を取得します。したがって、（1,1）は3セットになるために1だけ必要です。 3セットになるには、明らかに2タイルが必要であり、スコア2を取得します。コースの完全なセットはスコア0を取得します。シングルがペアになる可能性を無視することに注意してください。さて、上記の手で不完全なセットをすべて見つけようとすると、

（4s、6s）（8m、9m）（7p、8p）1s 1m 5m 9m西イーストノース

次に、そのスコアの合計= 1*3+2*7 = 17をカウントします。この数値を上記の式に適用すると、この手は5 -Shantenであることを意味します。 。それはアレクセイのものよりもやや複雑であり、私は証拠を持っていませんが、これまでのところ私にとってはうまくいくようです。そのような手は逆に解析される可能性があることに注意してください。例えば：

（4s、6s）（9m、9m）（7p、8p）1s 1m 5m 8m西イーストノース

ただし、フォーミュラに従ってスコア合計17と5シャンテンはまだ取得されます。また、これを証明することはできません。これは、Alexeyのフォーミュラよりも少し複雑ですが、他の何かに適用できるスコアを導入します。

Answer 5

あなたの手がすでにテンパイにあるかどうかを判断する マルチナプサックの問題. 。貪欲なアルゴリズムは機能しません - 弁指骨が指摘したように、問題空間全体を考慮する必要があります。