問題タブ [game-theory]

https://www.hackerrank.com/challenges/chessboard-game-again-1

上記の質問を次の方法で試してみましたが、回答が間違っていると評価されました。 (解決策を求めているのではなく、アプローチの欠陥を求めています);

私のコード (c99 エラーは無視してください)

私のアプローチは、移動が不可能になるまで、すべてのコインに対してすべての移動を可能にすることです。しかし、これはいくつかのテストケースで間違った答えを出しています。

円の点のセットから形成された軸に合わせた最小境界ボックスの面積を計算することが目的であるという問題があります。

いえ

x - x 座標、y - y 座標と半径

アプローチ方法に関するヒントはありますか？

ナイーブ・シェディング・カード・ゲーム

シェディング タイプのカード ゲームの単純なバージョン (実際には、中国で最も人気のあるゲームである 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)

1. 各カードのBp値は、このカードで相手のカードを何枚倒すことができるかを示しています。

2. 同じ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 には線形アルゴリズムが存在すると思います。誰かがそのような方法と関連情報を提供したり、問題が指数関数的であることを証明したりできます。

わかりましたので、標準入力を受け取る必要があるプログラムをJavaで作成しています

最初の数値は IESDS を実行する必要があることを表し、2 番目の入力 (2) はプレーヤーの数を表し、3 3 はプレーヤーごとのアクションの数をそれぞれ表します。以下のマトリックスはペイオフマトリックスです。

マトリックスを調べて、純粋または混合の厳密に支配的な戦略に基づいて削除する必要があるアクションを決定する方法に本当にこだわっています。2d マトリックスをトラバースして、プレーヤー 1 の行を相互に比較し、プレーヤー 2 の列を相互に比較する方法がわかりません。最初の排除は最後の列であるべきだと知っています

プレーヤー 2 の 3 番目のアクション。次の反復のために以下のマトリックスを残します。

ゲーム ツリーと MinMax アルゴリズムに関するこの MIT レクチャーを見たところ、アルファ ベータ プルーニングとプログレッシブ ディープニングが議論されていました。
https://www.youtube.com/watch?v=STjW3eH0Cik

したがって、プログレッシブディープニングとは、すべてのレベルで答えを近似し、移動の制限時間に応じてリーフノードに向かって深く進んでいくことを正しく理解している場合です。どんな時でも答えを持っていることが重要です。さて、36:22 で教授は、十分な時間がなく、d が木の深さである (d-1) 番目のレベルまでしか行っていない場合について説明します。そして、彼はまた、いつでもおおよその答えが得られるはずなので、下に行くにつれてすべてのレベルで一時的な答えを得ることができると示唆しています。

私の質問は、誰がゲームに勝つことができるかを結論付けることができるのは葉ノードでのみであるため、葉ノードに行かずにどのように答えを得ることができるかということです. これを三目並べゲームと考えてください。(d-1) 番目のレベルでは、(d-1) のこのノードまでのこの一連の動きがゲームに勝つか負けるかを判断するのに十分な情報がありません。より高いレベルでは、(d-3) と言うと、さらにぼやけます! 私たちが降りるとき、すべてが可能です。ではない？したがって、アルゴリズムが (d-1) 番目のレベルまで計算することを決定した場合、それらのパス オプションはすべて等しくなります。(d-1) レベルでの勝利と敗北を保証するものは何もありません。なぜなら、私が正しく理解している場合、勝敗は葉ノードでしか計算できないからです。これは、特に純粋な MinMax アルゴリズムに当てはまります。

では、(d-1) レベルまたは (d-5) レベルで「おおよその答え」を得るにはどうすればよいのでしょうか?

ここでパターンを見る簡単な方法があるかどうか疑問に思っていました。私はこれについて何時間も考えてきましたが、完全に定式化することはできませんでした.

ゲームの仕組みは 2 人のプレーヤー、N石の塔です。プレーヤーの番になったら、塔から少なくとも 1 つの石を取り除く必要があり、最後の石を取り除いたプレーヤーが勝ちです。

塔の高さから誰が勝つかの地図として、これまでに描いたものは次のとおりです。

私が思いついた事実：

• 各タワーに石が 1 つある場合、タワーの数が奇数の場合はそのターンのプレイヤーが勝ち、それ以外の場合は負けです。
• 塔の数が でN、いずれかの塔の高さが より大きい場合N+1、その塔の高さが である場合と同じ結果になります。N+1

それどころか、線形解を書くのに十分なパターンを理解することはできません。

何か助けはありますか？

私は現在、組み合わせゲーム理論の研究を行っており、ニューラル ネットワークを使用して人工知能を開発しようとしています。これに対する私の最初のアプローチは、ゲームの統計を取得し、それらを入力として使用し、それらの入力の最大出力値を取得するために、それらの入力の最適な重み構成を開発するようにニューラル ネットワークをトレーニングすることです。入力の各セットは動きを表し、各動き (入力 x 重み) をニューラル ネットワークに渡すことで、どの動きが最大値を持つかを見つけることができます。したがって、その動きは行うのに最適な動きです。

これはすべて理論上であり、期待値を知らずにニューラル ネットワークを構築することがまったく可能であるかどうかに興味があります。これが合理的ではないと思われる場合、この種の問題を調査する必要がある他のアルゴリズムはありますか?

フィードバックをお待ちしております。よろしくお願いします。

Tic-Tac-Toe に多少似たゲームの AI をコーディングしようとしています。その規則はここで見ることができます。

私が使用している最小最大アルゴリズムと分析関数はここにあります

私がこれまでに試した方法：

1. 現在のプレーヤーに適したパターンをいくつか作成しました。(Pythonで)

例えばmy_pattern = " ".join(str(x) for x in [piece, None, piece, piece, None])

2. このようなパターンを、六角形のゲームボード上の 6 つの可能なすべての方向に一致させます (空白ではありません)。正確には、my_pattern6 つの異なる配列 (各配列は 6 つの異なる向きのいずれかを表します) と一致します。

では、この分析関数は実際に何を計算すればよいのでしょうか。

1. 盤面全体のスコアは？
2. 船上で行われた最後の動きのスコアは？

誰かが分析機能の目的を正確に説明できれば、それは素晴らしいことです。

プレイヤーがさまざまなターゲットを狙う必要があるコンテストの意思決定システムを設計しています。異なるターゲットで得点する確率はさまざまであり、各ターゲットで得点するプレーヤーが多いほど、そのターゲットで得点する確率は低下します。プレイヤーの試行チャンスは限られています。

頭に浮かぶのはマルコフ連鎖とゲーム理論だけですが、それらを実装する方法がわかりません.スコアを最大化するための他の数学的手法はあるのだろうか.

ご指導いただければ幸いです。