問題タブ [mahjong]

タイルに使用されているレイアウトに関係なく、ゲームの開始時に、パズルを完了してゲームに勝つためのパスが少なくとも 1 つ存在することをユーザーに保証できるように、タイルを分割する良い方法はありますか? ?

明らかに、ユーザーの動きによっては、勝利から切り離される可能性があります。私は、うまくプレイすればパズルに勝てるということを常にユーザーに伝えられるようにしたいだけです。

ゲームの開始時にタイルをランダムに配置すると、ユーザーがいくつかの動きをして、それ以上動けなくなる可能性があります。パズルが少なくとも解決可能であるという知識は、プレイをより楽しくするはずです。

麻雀 (麻雀ソリティアではなく、実際のゲーム) は、基本的なルールとゲームプレイの点ではかなり単純ですが、特定の最終的なゲームの目標を目指すために AI が移行するための目標の設定は、かなり複雑に見えます。

このトピックに関連する論文、研究、またはその他の資料を知っている人はいますか?

私は麻雀ソリティアソルバーを開発していて、これまでのところ、かなりうまくやっています。ただし、私が望むほど速くはないので、皆さんが知っているかもしれない追加の最適化手法を求めています。

すべてのタイルはレイアウトからわかりますが、解決策はわかりません。現時点では、同じタイルの特定のペアを安全に削除することを保証するルールはほとんどありません（これは可能な解決策の障害にはなりません）。

明確にするために、タイルはいつでも選択できる場合は無料で、他のタイルをまったくバインドしていない場合はタイルが緩んでいます。

• 無料の無料タイルが4つある場合は、すぐに削除します。
• 拾うことができるタイルが3つあり、そのうちの少なくとも1つが緩いタイルである場合は、緩んでいないタイルを取り外します。
• 拾うことができるタイルが3つあり、フリータイルが1つ（ルーズ2つ）しかない場合は、フリータイルとランダムルーズ1つを削除します。
• 使用可能なルーズタイルが3つある場合は、そのうちの2つを削除します（どちらでも構いません）。
• まったく同じタイルが4倍あるので、2つ残っている場合は、残っているのはそれらだけなので削除します。

私のアルゴリズムは、複数のスレッドでソリューションを再帰的に検索します。ブランチが終了し（これ以上移動がない位置に）、それが解決に至らなかった場合、それは悪いものを含むベクトルにその位置を置きます。これで、新しいブランチが起動されるたびに、その特定の位置がすでにチェックされているかどうかをチェックするために、悪い位置を繰り返し処理します。
このプロセスは、解決策が見つかるか、すべての可能な位置がチェックされるまで続きます。

これは、たとえば36または72タイルを含むレイアウトでうまく機能します。しかし、それ以上になると、検索する位置が膨大になるため、このアルゴリズムはほとんど役に立たなくなります。

ですから、安全なタイルの削除やアルゴリズムに関するその他の特定の高速化のために、より多くのルールを実装する方法について良いアイデアがあれば、もう一度お聞きします。

よろしくお願いいたします。nhaa123

JavaScriptで麻雀関連の関数を書いています。

これが私が以下に持っているもので、テストケースのコードがあります。

麻雀の手は配列で表されることに注意してください。

• 要素 0 は手札のタイルの総数です
• 要素 1 ～ 34 は、手札にある各タイプのタイルの数です。
  • 最初にクラック、次にドット、次にバム、次に風、そして最後にドラゴン

待機を見つける関数は非常に遅く実行されます。どうすれば高速化できますか？

カードゲームを作ります。ゲームは麻雀のようになります。最初に参照コードまたはリンクが必要です。もしあれば、それを共有してください。

麻雀はアジアで最も人気のあるゲームの1つです（Windows 7に見られるソリティアスタイルではありません）。YahooのオンラインゲームやDOS時代のオフラインゲームなど、麻雀ゲームはたくさんありました。

ちょうど別の日、私は自分自身に考えていました、どうすれば（GUIを除いて）それを書くことができますか？

データモデリングの部分は簡単です。

勝ちと得点のルールは...パターンマッチングですか？

どのタイルを捨てるか、いつチョウやポンを動かすかなど、ゲームの戦略的な部分は最も難しい部分です。これを実装する方法は？

ありがとう！

リサーチ：

• 麻雀のデモ（和風）：http ：//www.nobleflash.com/game/4495/Japanese-Mahjong.html
• http://www.ninedragons.com/-私がプレイしていた麻雀ゲーム、そのスコアリングシステム：http ://www.ninedragons.com/mahjong/scoring2.html
• 関数言語の方が適していますか？どのように？F＃はカードゲームAIに適した言語ですか？
• AI麻雀-http ://www.stanford.edu/class/cs229/proj2009/Loh.pdf

これは実際には麻雀ベースの質問ですが、Rommeベースまたはポーカーベースの背景でも簡単に理解できます。

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

ここでは関係のないKanや13Orphansのようなさまざまな例外があります。色と値の範囲（1〜9）もアルゴリズムにとって重要ではありません。

私は、上記のように手を配置できるかどうかを判断しようとしています。特定の理由で、14だけでなく、任意の数のタイルを処理できる必要があります。（次のステップは、ハンドを完了するために交換する必要のあるタイルの数を見つけることです。）

例：

11122233344455-簡単、4セットとペア。
12345555678999--123、456、789、555、99-123、123、789、888、99-有効なハンドではありませ
11223378888999ん
11223344556789

私の現在の、まだ実装されていないアイデアは次のとおりです。タイルごとに、a）通りb）セットc）ペアを作成してみてください。何も機能しない場合（またはペアが1つを超える場合）、前の反復に戻って次のオプションを試すか、これが最高レベルの場合は失敗します。それ以外の場合は、残りのタイルのリストから使用済みのタイルを削除して、次の反復を続行します。

このアプローチは機能し、適度に高速であると思います（パフォーマンスは「素晴らしいボーナス」です）が、これについてのあなたの意見に興味があります。別の解決策を考えられますか？これまたは類似のものはすでに存在しますか？

（宿題ではなく、麻雀を習っています。）

関連する質問は複数ありますが、自分のケースに固有の解決策を探しています。（通常）14個の整数の配列があります。各intが正確に2回表示されるかどうか（つまり、7つのペアがあるかどうか）をすばやく判断するにはどうすればよいですか？値の範囲は1〜35です。ここでの主な側面はパフォーマンスです。

参考までに、これが私の現在の解決策です。これは、パフォーマンスを考慮せずに可能な限り仕様に類似するように作成されているため、大幅に改善できると確信しています。

Linqの使用はオプションです。それが速い限り、私はどのように気にしません:)

編集： intがn> 1で2n回出現するという特殊なケースがあります。この場合、チェックは失敗するはずです。つまり、7つの異なるペアが存在するはずです。

編集：結果 私は小さな変更を加えてAniとJonのソリューションをテストし、ターゲットアプリでの複数のベンチマーク実行中に、AniのマシンでのJonのスループットが約2倍であることがわかりました（Win7-64の一部のCore 2 Duo）。intの配列の生成には、それぞれのチェックと同じくらいの時間がかかるので、結果に満足しています。皆さんありがとう！

関連する質問が複数ありますが、私のケースに固有の解決策を探しています。(通常) 14 個の整数の配列があり、それぞれが 1 ～ 34 の範囲にあります。特定の静的リスト内の各 int がこの配列に少なくとも 1 回出現するかどうかをすばやく確認するにはどうすればよいでしょうか?

参考までに、私は現在このコードを使用しています。このコードは可能な限り仕様に似せて作成されているため、大幅に改善される可能性があります。

必要なリストは動的ではありません。つまり、実行時に常に同じになります。Linq の使用はオプションです。主な側面はパフォーマンスです。

編集：

• 入力配列はソートされていません。
• 入力値は複数回表示される場合があります。
• 入力配列には、少なくとも 14 個の項目が含まれます。つまり、必要な配列よりも 1 つ多くなります。
• 必要な配列は 1 つだけで、静的です。
• 必須の値は異なります。
• ヒストグラムは安価に作成できると考えるかもしれません。

更新:ソートされた入力配列のソリューションにも興味があります。

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

麻雀のルールの知識は優れていますが、この質問を理解するには、ポーカーまたは 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 で開発していますが、疑似コードや読み取り可能な言語も歓迎します。