問題タブ [game-theory]

ゲームには、期待される出力値を指定して「ペイアウト」をランダム化するインスタンスがいくつかあります。たとえば、毎回「10クレジット」を獲得するのではなく、少し予測不可能にすることでより「楽しい」ものにすることを目的として、長期的には平均10の報酬をランダムに投入します。

ランダムな量で変更したり、正規分布にしたりするのは簡単ですが、それは「楽しみ」のために実際には最適化されていません。5クレジットと15クレジットのユーザーの効用の違いは比較的小さいですが、たまに100クレジットを獲得する可能性があれば、それは大きな魅力であり、期待できることです。

ギャンブラー向けに最適化されたアルゴリズムはありますか？それは基本的に非常にシンプルなスロットマシンです-誰かがこの中毒で楽しいものを作るものを決定するために研究をしたと思いますが、私はそのようなものをどこから探し始めるのかさえわかりません。

20*20 グリッドの迷路に 1 匹のネズミと 4 匹の猫がいる迷路ゲームがあるとします。迷路内の各エージェントが N、E、S、W に移動できると仮定します。この大規模なゲーム ツリーの各ノードの子の数について、最も適切な推測はどれですか?

これは私の最善の推測ですが、よくわかりません。何か考えはありますか？

私はニューラルネットワークの初心者です。コンピューターにチェッカーのプレイを教えることで、ニューラル ネットワークの基礎を学びたいです。実は、習いたいゲームはドミニアリングとヘックスです。

これらのゲームは非常に簡単に保存でき、ルールはチェスよりもはるかに単純ですが、プレイする人はあまり多くありません. このアイデアを軌道に乗せることができれば、組み合わせゲーム理論を実験するのに最適です。

PyBrainは明らかに Python ニューラル ネットワークの勝者のようですが、ゲームをプレイするタスクのためにニューラル ネットワークを設定する方法を教えてくれる人はいますか? Google 検索で 2001 年にBlondie24が見つかりましたが、いくつかの遺伝的アルゴリズムを使用しています。複雑にしたくありません。

私は機械学習の初心者です。コンピューターにチェッカーを教えることで基本を学びたいです。実際、私が学びたいゲームはDomineeringとHexです。私が選んだ言語はPythonです

これらのゲームは保存が非常に簡単で、ルールはチェスよりもはるかに単純ですが、プレイする人はそれほど多くありません。このアイデアを実現できれば、組み合わせゲーム理論を実験して、コンピューターかどうかを確認し、最適な動きを見つけることができれば素晴らしいと思います。

私はIBMの男による1960年代のチェッカーに関するこの古い論文を見つけました。もともとニューラルネットワークについて聞いていたのですが、間違ったツールだと言われています。

編集：機械学習が適切な戦略ではない可能性があります。その場合、何が問題になりますか？そして、より良い方法は何ですか？

私は最近、要素が山積みになっている Nim ゲームの基本的な戦略を学びました。次に、パイルを選択し、そのパイルから任意の数の要素を削除する必要があります。Nim と呼ばれる問題を見つけたのですが、杭を表す標準の Nim 問題に変換できませんでした。

問題は、チェスの違いのような正方形のチェッカー ボードがあることを示しています - ポーンだけがここに存在します。したがって、各列には 2 つのポーンがあります。1 つは白、もう 1 つは黒です。ポーンは反対側を追い越すことはできませんが、ポーンが前方にのみ移動できるチェスとは異なり、前後に移動できます。相手のポーンを食べてチェスのように列を変更することはできません。いずれかの側に移動するオプションがない場合、ゲームは終了します。ポーンの初期設定が与えられた場合、プログラムは勝者 (白/黒) を出力する必要があります。

それを標準のものに変換する方法について何か考えはありますか？

ゲームの名前はwizwozです。

赤（rと呼ばれる）と金（gと呼ばれる）の2人のプレーヤーは、最初に2つの値nとkを選択します。n×nのボードは、ボード上にランダムに配置されたk"r"とk"g"で作成されます。プレーヤーrから始めて、各プレーヤーはボード上の空の四角の1つに自分の文字（プレーヤーrの場合は「r」、支払人gの場合は「g」）を置きます。ボードがいっぱいになると、各プレイヤーのスコアは、そのプレイヤーの色で塗りつぶされたボード上の最大の接続領域に等しくなります（接続領域とは、領域内の任意の2つの正方形に対して、N / S/Eのみで構成されるパスが存在する領域です。 / Wが移動します）。スコアが最も高いプレイヤーが勝ち、自分のスコアと他のプレイヤーのスコアの差が与えられます。完成したゲームの2つの例を以下に示し、各プレーヤーの最大の接続領域の概要を示します。

アルファベータ法のアルゴリズムを作成していて、評価関数を使い続けています。

何か助けはありますか？擬似コードが望ましい。

A、B、C の 3 つの人気ビーチ リゾートが並んでいます。

リゾート間の距離は 1k です。ジョンは、ビーチ リゾート A とビーチ リゾート C にある別のアイスクリーム トラックを所有しています。明日、アイスクリームを欲しがっている子供たちでいっぱいの 2 台のバスがビーチ リゾート (A、B、C) に到着しますが、ジョンは来ません。各バスがどのリゾートに向かうか、各バスがいつ到着するかを把握します (バスは異なる時間に到着する可能性があります)。彼は、バスがビーチ リゾートに到着したらすぐに、アイスクリーム トラックを現在の場所からビーチ リゾートに派遣する予定です。各トラックは 1 つのビーチ リゾートにのみサービスを提供できます。つまり、トラックがビーチ リゾートに派遣されると、1 日中そこに留まらなければなりません。ジョンは、バスの場所に到達するためにトラックが移動する距離の合計を最小化するアルゴリズムを設計したいと考えています。

すべての決定論的アルゴリズム ALG について、ALG の下でジョンのトラックが移動する合計距離が 3OPT であるシナリオ (つまり、バスの到着予定と場所) があることを示します。ここで、OPT はそのシナリオにおける最適解の値です。

私は、MinMax アルゴリズムがどのように機能するかを理解しようとして、髪の毛を引っ張ってきました。うまくいけば、アルファ ベータ プルーニング アルゴリズムが機能することを願っています。発生する再帰について混乱しています。

• まず、各中間ボードは採点されますか? または端末ゲームボードのみ。
• 第二に、正確には何が返されますか? プログラムは次の手をどこに置くべきかをどのように知るのでしょうか? ボード スコア (tictactoe では -1,0,1) を返すことになっているようですが、プログラムはどの手が次にプレイされるべきかをどのように認識しますか。

これを実証する単純な C または C++ プログラムを見つけようとしましたが、うまくいきませんでした。私はこのアルゴリズムを学ぼうとしています。コンピューター プログラミング クラスの残りの部分でプレゼンテーションを作成できます。

どうもありがとう！Ⅴ

Code Chef フォーラムで回答が得られなかったので、ここで質問しています。

codechef のスレッド。

これは私が取り組んだ最初の問題です。TLE エラーが発生します。

問題 - ASRGAME。

したがって、これに対する私の最初のアプローチは、Min-Max ゲーム ツリーを作成することでした。これが私の最近の解決策です。

擬似コード アルゴリズムは次のとおりです。

（これは正しいと思います）。

つまり、再帰的に分岐しますが、確実に勝つ分岐が見つかった場合は、そのレベルの他の分岐をスキップできます。

しかし、もちろん、TLE エラーが発生するので、ここでそれを行うためのガイドを探しました。

社説では、Sprague-Grundy の定理を使用することを提案しています。SG定理の使用について少し読んだ。いくつかの良い情報源: One Two .

これらのチュートリアルは両方とも、Nim のゲームのコンテキストで SG の定理について説明しています。Nim を使用すると、各ゲームの厄介な番号を見つけるためにツリーを再帰的に分岐する必要がないことを理解しています。最初から XOR 関数を適用するだけで、すぐに解決できます。(nim のツリーを拡張する必要がない理由は、N 枚のコインの山が N の汚れた数を持っていることを知っているためです。これは、よく考えてみればわかります。たとえば、3 枚の山、拡張された缶2、1、または 0 の山であり、2 の山は 0、1 になる可能性があり、1 の山は 0 になることしかできないため、1 はグランディ番号 1、2 はグランド番号 2、3 は3の汚れた数...）。

同様に、このチュートリアルで言及されている馬のチェス ゲームでは、ボード上の各位置の汚れた数字を前処理し、それらの汚れた数字をボード構成で調べて、XOR 関数を適用できます。

しかし、これをこの問題にどのように適用するかは、それほど明確ではありません。社説でさえ、いくつかの再帰が含まれていることを示唆しているようです:

ゲームは S(i, a-1) と S(b+1, j) の 2 つのサブゲームに分割されます。プレーヤーは自分のターンに任意のゲームを選択できるため、ゲームのグランディ数は、2 つのサブゲームのグランディ数の単純な XOR です。

つまり、負けたポジションが見つかるまでツリーを拡張し、それを上に渡す必要があるようです。

つまり、次のようなものです。

これが最小最大ソリューションと根本的に異なることはわかりません。そして実際には - 最小 - 最大の方が高速ではありませんか? - ミニマックスは勝利の分岐が見つかったら終了できますが、SG はすべての単語を試行し続ける必要があります。

したがって、SG定理の使用法を明確にする必要があるか、単に現在のアルゴリズムを最適化するかのどちらかです。たとえば、反復ごとに文字列検索を行う必要はないと思います。インデックス位置を格納するだけで済みます。

以下のグラフの問題を分類するか、その解決策のヒントを見つけようとしています。

ユニット、ポイント、単純な地形の3種類の要素を含むことができる（隣接）行列があります。

地形には特別な意味はありません。

ユニットには、位置（x、yはマトリックスによって定義されます）と、取得できるポイントの数があります。
ポイントには位置があります（x、yは行列によって定義されます）。
ポイントを取得するためのコストは、ポイントとユニットの間のマンハッタン距離です。
各ポイントは1ユニットでのみ取得できます。

問題は、ユニットのすべてのリソースが使い果たされるように、ポイントを取得するユニットの最小コスト構成をどのように見つけるかです。

例：
u1は3ポイントを獲得
できますu2は2ポイントを獲得できます

最適なソリューションの1つは次のとおりです。

（この構成では最小限）

注：均一コスト探索とA *（単純なヒューリスティックを使用）でこれを解決しようとしましたが、マトリックスのサイズが小さい場合でも、非常に多くの状態が発生し、メモリが不足します。