問題タブ [game-theory]

GAMBIT ファイルには、n-player 戦略フォーム ゲームの入力が含まれています。これは、各プレーヤーの戦略のペイオフ値で構成されています。データを操作するには、データを何らかのデータ構造に効率的に格納する必要があります。

プレイヤーの数とアクションの数はユーザー入力であるため、これは少し問題を引き起こしています。データを格納するための線形配列よりも優れたデータ構造を思いつくことができません。どんな助けでも大歓迎です。

コードは C/C++/Java である必要があります。そのため、MATLAB または他のソフトウェアでそれを行うことに関する提案は役に立ちません。

GAMUT と GAMBIT について知りたい方は、http://gamut.stanford.edu/download.htm を参照して ください。

ありがとう。

私は現在、完全な情報状況でSkatと呼ばれるトリックベースのカード ゲームのソルバーを開発しています。ほとんどの人はゲームを知らないかもしれませんが、ご容赦ください。私の問題は一般的な性質のものです。

Skat の簡単な紹介:
基本的に、各プレイヤーは 1 枚のカードを交互にプレイし、3 枚のカードごとにトリックを形成します。すべてのカードには特定の値があります。プレーヤーが達成したスコアは、それぞれのプレーヤーが獲得したトリックに含まれるすべてのカードの値を合計した結果です。誰が誰と対戦するか、またはいつトリックに勝つかなど、私の問題にとって重要ではない特定の事柄を省略しました。 私たちが心に留めておくべきことは、ランニングスコアがあり、特定のポジション（->その履歴）を調査するときに誰が以前に何をプレーしたかがそのスコアに関連しているということです。

Java でアルファ ベータ アルゴリズムを作成しましたが、これは正常に動作しているように見えますが、遅すぎます。最も有望と思われる最初の拡張機能は、転置テーブルの使用です。Skat ゲームのツリーを検索すると、既に調査済みの多くのポジションに遭遇することを読みました。
ここで問題が発生します。以前に調査済みのポジションを見つけた場合、そのポジションに至る動きは異なっていました。それに伴い、一般的に、スコア (およびアルファまたはベータ) も異なります。
これは私の質問につながります: 同じポジションの値を知っていても、履歴が異なる場合、どのようにしてポジションの値を決定できますか?
言い換えれば、どうすればデカップリングできますか新しいパスに適用できるように、そのパスからルートまでのサブツリー?
私の最初の衝動は、アルファまたはベータが現在の位置に適用できない可能性がある他のパスの影響を受けている可能性があるため、それは不可能であるということでしたが...

すでに解決策がある
ようです...私には理解できないようです。Sebastion Kupferschmid の Skat ソルバーに関する修士論文で、次のコードを見つけました (おそらく C っぽい / 疑似コード?):

それはかなり自明であるはずです。succ(p)現在の位置で可能なすべての動きを返す関数です。t(q)は、それぞれのポジションの実行中のスコア (ディクレアラーがこれまでに達成したポイント) であると私が信じているものです。理解せずにコピーするのは好きではないので、これは私を助けたい人の助けになるはずです. もちろん、私はこのコードについて少し考えましたが、1 つのことに頭を悩ませることはできません: 関数を再度呼び出す前にアルファ/ベータから現在のスコアを差し引くことによって [例ab_tt(q, res - t(q), beta - t(q))]、何らかのデカップリングが行われているようです。の上。しかし、ここでも同じ減算を行わずに位置の値を転置テーブルに格納すると、正確にはどのような利点があるのでしょうか?以前に調査した位置が見つかった場合、なぜその値を返すだけでよいのでしょうか (それが の場合VALID)、またはアルファまたはベータにバインドされた値を使用できますか? 私の見方では、転置テーブルからの値の保存と取得の両方が、これらの位置の特定の履歴を考慮していません。それともそうなるでしょうか？

文献:スケート ゲームでAI
を扱っている英語の情報源はほとんどありませんが、私はこれを見つけました。残念ながら、論文全体、特に転置表の詳細はかなりコンパクトです。

編集：

すべてのカードがプレイされるまで、Skat ゲーム全体でスコアがどのように発展するかを誰もがよりよく想像できるように、ここに例を示します。ゲームのコースは、下の表に 1 行に 1 トリックで表示されます。各トリックの後の実際のスコアは左側にあり、+Xはディクレアラーのスコアです ( -Yは防御チームのスコアであり、アルファ ベータには関係ありません)。前述したように、トリックの勝者 (ディクレアラーまたはディフェンディング チーム) は、このトリックの各カードの値をスコアに追加します。

カードの値は次のとおりです。

ゲームに MinMax アルゴリズムを使用していますが、多くの可能性があるため、「アルファ ベータ プルーニング」を使用しても、MinMax 再帰に時間がかかりすぎます。

私のコードは次のようになります。

for再帰の代わりにループを使用できる場合があることは知っていますが、それを変換する方法が見つかりませんでした。

誰かが良いアイデアを持っているなら、私はそれを聞いてうれしいです!

ありがとう、

編集:この質問は、2048 年のゲームに最適なアルゴリズムは何ですか?の複製ではありません。

• その質問は、「ゲームに勝つための最良の方法は何ですか?」と尋ねます。
• この質問は、「どうすればゲームの複雑さを解決できるでしょうか?」と尋ねます。

それらはまったく異なる質問です。「勝利」状態に移行するために必要なステップには興味がありません。可能なステップの総数を計算できるかどうかを調べることに興味があります。

ゲームをうまくプレイするアルゴリズムを作成するための戦略について説明しているゲーム2048に関するこの質問を読んでいます。

受け入れられた回答には、次のことが記載されています。

ゲームは離散状態空間、完全な情報、チェスのようなターンベースのゲーム

その複雑さについて考えさせられました。チェスのような決定論的なゲームでは、(理論的には) 勝利状態につながる可能性のあるすべての動きを計算し、逆方向に作業して、その結果につながり続ける最良の動きを選択することができます。私はこれが多数の可能性のある動きにつながることを知っています（宇宙の原子数の範囲内の何か）..しかし、2048年は多かれ少なかれ複雑ですか？

擬似コード:

この時点で、これが実行されるのを待っている間、ここにいると思います...

そこで私の質問は、このアルゴリズムをどのように書き始めるかということです。ゲームの複雑さを計算するのに最適な戦略は何ですか?

2048 とチェスの大きな違いは、プログラムが新しい牌を追加するときに 2 から 4 の間でランダムに選択できることです。

最終的には、ゲーム内で可能な順列の数を示す 1 つの図をプログラムに出力してもらいたいと考えています。これは可能ですか？

次のようなゲームに関するプログラミング コンテスト ( Andrew Stankevich Contest 21 )の問題にしばらく苦労しました。

Nick と Peter は次のゲームをするのが好きです [...]。彼らは無向二部グラフ G を一枚の紙に描き、その頂点の 1 つにトークンを置きます。その後、彼らは順番に動きます。ニックが先に動く。

移動は、グラフ エッジに沿ってトークンを移動することで構成されます。その後、移動前にトークンがあった頂点とそれに付随するすべてのエッジがグラフから削除されます。有効な動きがないプレイヤーはゲームに負けます。

グラフが与えられ、与えられた開始ノードについて、両方のプレイヤーが最適にプレイした場合に開始プレイヤーが勝つか負けるかを見つけることがタスクになります。要約する

• 二部グラフ
• 開始ノードが与えられます (左側にあるとします)。
• 順番に移動します。移動はエッジをたどることで構成されますが、既にアクセスしたノードにアクセスすることはできません
• 動けなくなったプレイヤーが負け

グラフは 2 部構成であるため、Nick (最初のプレーヤー) は常に左側からノードを削除し、Peter は常に右側からノードを削除します。

グラフには最大 1000 個のノード (各辺で最大 500 個) と 50000 個のエッジを含めることができるため、優れた多項式時間アルゴリズムが必要です (ここでの制限時間は、すべての開始位置を解決するのに 2 秒ですが、多くのことを共有できると思います)。異なる開始位置間の情報)。

グラフは 2 部構成であるため、これはある種の頂点カバーまたはパッキングの問題に帰着できると確信していますが、これらのいずれかに関連する戦略を見つけることができません。

私は特別な場合の解決策を知っています: 辺にそれぞれn ₁とn ₂の頂点があるとしましょう。サイズmin(n ₁ , n ₂ )のマッチングがあり、小さい側のプレイヤーが開始した場合、勝利戦略が存在します。彼はマッチしたエッジをたどるだけで、自動的に勝利します。

何か案は？

ゲーム2048で、プレーヤーが最適にプレイし、最適な場所でタイルがスポーンすると仮定すると、達成できる最大のタイルはいくつですか?

単純に、達成可能な最大のタイルは65536 * 2 = 131072、可能な限り最高のボードが次のように思われるためです。

しかし、どうかはわかりません

1. あたりです
2. 私の直感が本当に正しいことを証明する方法。

( gaming.stackexchangeで質問する必要があった場合は申し訳ありませんが、これはゲームに関する質問というよりは CS に関する質問です)

Python でゲーム理論シミュレーションを書いています。シミュレーションの一環として、世代ごとに 2 人のプレーヤーがペアになり、互いに対戦します (各プレーヤーはPlayer1またはPlayer2クラスのインスタンスです)。少し簡略化すると、コードは次のようになります。

ペイオフはプレイヤーの属性として保持されます。各ラウンドの終わりに、プレイヤーの動きに応じて、ゲームは続行または終了します (play_gameそれぞれ True または False を返します)。

このコードを並行して実行するにはどうすればよいですか? つまり、一度に複数のペアをプレイするにはどうすればよいですか? 少しグーグルで調べたところ、Pythonマルチプロセッシングライブラリが見つかりましたが、それをこのコード スニペットに適用する方法がわかりません。

ありがとう！

問題定義

n同じ容量のバケットがm隣り合っています。1 つのバケツから右のバケツに水を注ぐことができます。目標は、すべてのバケツを別の容器に空にすることですが、空にできるのは右端のバケツだけです。それらはそれぞれ、特定の初期量の水を持っています。wここで0 <= w <= m、 とwは整数です。6 6 -> 3 9 で 3 だけを注ぐ場合、それは許可されません。注ぐ場合は、できるだけ注ぐ必要があるため、合法的な動きは 6 6 -> 2 10 になります。

すべてのバケツを空にするために必要な移動の最小数は? バケットの最大数は 1000 で、最大容量は 100 です。

例

例 1

4 つのバケツ容量 10 以下の量の水: 4 0 6

答えは 4 0 6 -> 0 4 6 -> 0 0 10 -> 0 0 0 で、3 手です。

例 2

3 バケット容量 10、8 9 3

8 9 3 -> 8 2 10 -> 0 10 10 -> 0 10 0 -> 0 0 10 -> 0 0 0 = 合計 5 回の移動

最初にさまざまな種類のアルゴリズム (貪欲、動的、バックトラッキングなど) で試してみましたが、どれもうまくいかないようでした。私はかなり直感的な解決策を見つけたと思っていましたが、これらの答えをチェックするプログラムはそれが間違っていると私に言ったので、間違っているかもしれません. もう1つのことは、このプログラムは以前に正解を拒否したため、よくわかりません.

これが私の解決策です：

各バケットの前にあるすべてのバケットの合計を計算し、その数の上限をバケットの容量で割って、それらの数をすべて加算します。

例: 6 6 6 6 6 -> 6 12 18 24 30

ceil(6/10) ceil(12/10) ceil(18/10) ceil(24/10) ceil(30/10) = 1 + 2 + 2 + 3 + 3 = 11

それが正しい答えです: 6 6 6 6 6 -> 6 2 10 6 6 -> 0 8 10 6 6 -> 0 8 10 2 10 -> 0 8 2 10 10 -> 0 0 10 10 10 -> 0 0 10 10 0 -> 0 0 10 0 10 -> 0 0 10 0 0 -> 0 0 0 10 0 -> 0 0 0 0 10 -> 0 0 0 0 0 = 11 ステップ

ロジックはL、特定のバケツの前に 1 リットルの水がある場合、少なくともceil(L/Capacity)その位置を通過する動きがなければならないということです。これまでに約 30 のテスト ケースを試しましたが、すべてうまくいきました。反例を見つけたと思うたびに、手で何度か試してみると、自分が間違っていることに気づきました。問題は、これが正しい答えだと確信していますが、このようなことを証明する方法がわからないか、単に間違っている可能性があることです。

この答えが正しいかどうか誰か教えてもらえますか?

譲渡可能効用特性関数ゲーム (協力ゲーム理論) で最も有名な解の概念は、どの連合によっても改善できない実行可能なペイオフ配分のセットとして定義されるゲームのコアです。幾何学的には、コアは閉じた凸多面体です: http://www.jstor.org/stable/2630190

これらのゲームでは、ペイオフの割り当てはコアにあるか、コアにないかのいずれかです。TUGlab の一連のツールには、ペイオフの割り当てがコアにあるかどうかを計算できるコマンドが あります: http://webs.uvigo.es/mmiras/TUGlab/特定のペイオフ配分の距離はコアまでです。閉じた凸多面体としてコアの幾何学的特徴付けがある場合、点とその多面体の間の幾何学的距離を特性関数の「コアからの距離」として計算する方法があるはずです。残念ながら、MATLAB で実装できるこの距離を計算するための式またはアルゴリズムを実際に示している論文は見つかりませんでした。

私の推測では、2 つの多面体間の距離を計算する Stephen Cameron のコードに手がかりがあるかもしれません。しかし、私の問題はそれよりも単純なはずです。点と多面体の間の距離だけです。最後に、a) 特性関数、b) ペイオフ分布を入力として取り、ペイオフ分布と特性関数のコアとの間の距離を出力として与える MATLAB プログラムが必要です。もちろん、コアが空でないと仮定します。