ナイーブ・シェディング・カード・ゲーム
シェディング タイプのカード ゲームの単純なバージョン (実際には、中国で最も人気のあるゲームである Dou Di Zhu ( https://en.wikipedia.org/wiki/Dou_dizhu ) の単純なバージョン) が与えられた場合、勝者 (各プレイヤーは最大 20 枚のカードを持つことができます) (問題を解決するための線形アルゴリズムは存在しますか)?
ゲームの目的は、対戦相手の前に手持ちのすべてのカードを取り除くことです。プレイヤーは A と B と呼ばれます。カードのランクは次のとおりです。
3 < 4 < 5 < 6 < 7 < 8 < 9 < T < J < Q < k < A < 2 < r < R (T は 10、r、R は小さくて大きなジョーカー)
定義1 : Give-Out-Ruleでコンパイルされた任意のカードを捨てることができるプレーヤーはFirstDiscard プレーヤーと呼ばれ、前に捨てられたカードよりもランクが高いカードのみを捨てることができるプレーヤーはBeatDiscard プレーヤーと呼ばれます。
A は最初にカードを捨てるプレイヤーなので、最初は常に A が FirstDiscard プレイヤーです。1 人がカードを捨てないことを選択した場合 (捨てないことを選択したか、または捨てる有効なカードが見つからないため)、別のプレイヤーがFirstDiscard プレイヤーになります。
ルール1：各プレイヤーは手札を1枚まで捨てることができます.同じランクのカードが複数ある場合でも、それらのうちの1つだけしか捨てることができません.
例 1: B 勝者 4,4,5 < B: 3,4,4,8,T
説明: B は常に勝者です。なぜなら、A がプレイすることを選択できる任意の戦略に対して、B は常に B の勝利につながるカードを捨てる戦略を見つけることができるからです。
例 2: 勝者 4,4,5,R > B: 3,4,4,8,T
説明: A は常に勝者です。なぜなら、B が反応することを選択した戦略に関係なく、A が使用することを選択できる戦略が存在し、それが A の勝利につながるからです。
赤と青はAとBの状態(手札に残っているカード)を表しています。
多角形とボックスの形状は、プレーヤーがFirstDiscard プレーヤー状態とBeatDiscard プレーヤー状態にあることを示します。
トウカードセットの相対グラフ(A: 4,4,5,R > B: 3,4,4,8,T)
各カードのBp値は、このカードで相手のカードを何枚倒すことができるかを示しています。
同じBp値を持つカードはブロックを形成します。
研究の進捗
今のところ、勝者を決定するためにゲーム検索ツリーの方法しか使用できませんが、この方法では処理に時間がかかりすぎます。Give out Rule1は実際には私の研究の最初のステップです。
定義2 :ソロ カードは、カウントが 1 である特定のランクを持つカードとして定義されます。一方、pair-card、trio-card、four-cardは、カウントが 2、3、4 の特定のランクを持つカードとして定義されます。
Definition3 :ソロカード、ペアカード、トリオカード、フォーカードは独立カードとも呼ばれます
ルール 2 を配る:各プレイヤーは毎回 1 種類の独立カードのみを捨てることができます。プレイヤーがBeatDiscard プレイヤー状態にある場合、彼は以前に捨てたカードと同じ種類の独立カードのみをより高いランクで捨てることができます。SplitCard は使用できません。(トリオカード555をお持ちの場合、カードをソロカード5とペアカード55に分割することはできません)
配付ルール 3: SplitCardが許可されていることを除い2 と同じ
定義4 :ソロカードを持つトリオ カードは、トリオ ソロ キッカーカードと呼ばれ、ランクはトリオ カードと同じです。
定義5 :ペアカードを持つトリオ カードは、トリオ ペア キッカーカードと呼ばれ、ランクはトリオ カードと同じです。
定義6 : 2 枚のソロ カードを持つ 4 枚のカードを4 枚のソロ キッカー カードと呼び、ランクは4 枚のカードと同じです。
定義7 : 2 枚のペア カードを持つ 4 枚のカードを 4 枚のペア キッカー カードと呼び、ランクは4 枚のカードと同じです。
ギブ アウト ルール 4:ギブ アウト ルール 3と同じで、さらに 4 種類のカード タイプ (防御 4 ～ 防御 7) を捨てることができます。
定義8 :フォーカードはボムカードとも呼ばれ、他のすべてのカードタイプとランクの低いフォーカードを打ち負かすために使用できます (6666 は33、5555、3331、8888KJを打ち負かすことができます)
定義 9 :ロケット カードは r と R の組み合わせであり、他のすべてのカード タイプを打ち負かすことができます。
ギブ アウト ルール 5:ギブ アウト ルール 4と同じで、さらに 2 種類のカード タイプ (防御 8 ～ 防御 9) を捨てることができます。
ルール 6 を与える:プレーヤー C は B のチームメイトとして追加され、B に続いてカードを破棄します。B または C のいずれかが最初にすべての手札を破棄し、B と C の勝者となります。
Give out Rule1 ~ Rule3 には線形アルゴリズムが存在すると思います。誰かがそのような方法と関連情報を提供したり、問題が指数関数的であることを証明したりできます。