問題タブ [game-theory]

今年の 9 月に大学の最終学年が始まるので、論文のプロジェクトを行う必要があります。昨年大学が提案したプロジェクトのリストを見ましたが、どれもそれほど興味深いものではありませんでした。それは、「理論的な」コンピューターサイエンス全体に対する私の「愛」と相まって、夏休みの最後の月をCS分野のいくつかをより深く研究するのに費やすのがいいだろうと考えるようになりました. これまで大学では、コンピュータ サイエンスのより「理論的な」側面に関して、主に検索およびソート アルゴリズム、文字列マッチング、ゲーム理論、ソフトウェア エンジニアリングの設計パターン、および迷路解決アルゴリズムを調べてきました。来年のシラバスには、バイオインフォマティクス、コンパイラ、機械学習が含まれます。これらすべてについてのアイデアはありますが、信じられないほど詳細なものはありません (つまり、アルゴリズムの設計はまったく行っていません)。それで、リストからプロジェクトを選ぶか、愛好家でもできるプロジェクトを選ぶのではなく、コンピュータ サイエンスのいくつかの分野について研究し、その過程でブレインストーミングを行ってみませんか?

以下の分野に関する利用可能なリソース (書籍、電子書籍、PDF、オンライン コミュニティなど) を教えていただければ幸いです。

私はそれらが何であるかを理解したいだけであり、技術的な問題をまだ混乱させていないことに注意してください.

フィールド：

• Web セマンティクス

• アルゴリズム（分析、設計など）

• 機械学習

• 進化計算

• ゲーム理論

• 他の （？？？）

任意のペグソリティアボード構成を考えると、「ゲーム終了」の位置になる一連の動きを計算するための最も効率的な方法は何ですか。

たとえば、標準の開始位置は次のとおりです。

そして、「ゲーム終了」の位置は次のとおりです。

ペグソリテールについて詳しくは、ウィキペディアをご覧ください。「英語ボード」のバリエーションを検討しています。

P4 3Ghzのように、妥当なコンピューター上で、わずか数秒で任意の開始ボードを解決できると確信しています。

現在、これが私の最善の戦略です。

チェッカーのゲーム用です。古いバージョンのコードについては、改訂履歴を参照してください。

私は深さ0でそれを試しています、そしてスコアはゲームの約半分で正しいです、そしてそれから突然それは台無しになり始めます。プレーヤーの1人は、自分のスコアが実際よりも高いと宣言し始めます。なぜそれは半分のゲームでしか機能しないのでしょうか？！

チェッカーのゲームにNegaMaxを実装しようとしています。現在、深度0でテストしています。つまり、現在のプレーヤーは、他のプレーヤーが次に何をする可能性があるかに関係なく、すべての動きを評価するだけです。ゲームの約半分で完全に機能し（スコアを正しく計算します）、途中で意味のない答えを吐き出し始めます。

たとえば、白は1個残っていて、黒は5個ある場合がありますが、たとえば、白が負けているためにすべてが負である場合、白の動きは7のスコアとして評価されます。黒は次の手で勝つ可能性がありますが、1000であるはずなのに、勝った手は-4と評価されます。

一貫してガベージを出力していることは理解できますが、最初の数ターンは機能し、その後混乱し始めるのはなぜですか？

6x6のボードで、気に入らないボードの状態を分離しました。

これはプレイされた時間や移動回数の問題ではなく、特定のボードの状態が好きではないようです。しかし、この状態に特有のことは何も見当たりません。

この状態では、ブラックの4つの動きすべてを-13と評価します。私がどのように得点したかを見ると、1人あたり2ポイント、1人あたり3ポイント、他のプレイヤーが所有している場合はマイナスと表示されます。すべてのピースを白として扱っているように見えます...それが13を取得する唯一の方法です。

私は別の手がかりを見つけました。ボードスコア法では、私はそれが見ているものを印刷するようになりました..これはそれが私に言っていることです：

ボードの正方形に次のように番号が付けられている場合：

確かに黒い部分が白いと言っていると思います……これを引き起こしている原因を解明するために。

だから...今私は色が間違っていることを知っていますが、BoardScore機能だけです。私の通常の表示ルーチンはこれを理解していませんでした。さもなければ、私は数時間前に問題を理解していたでしょう。ApplyMove色が変わる機能にあるのではないかと思います。

しかし、それもあまり意味がありません...ピースは開始位置から終了位置にコピーされるだけです。何であるかを調査する必要m.Colorがあります...おそらくそれはより多くの手がかりを提供するでしょう！私は探偵のように感じます。

この征服クラブ (リスクのような) ゲームを再作成しようとしています:

http://conquerclub.barrycarter.info/ONEOFF/7460216.html

つまり、各時点での各領地の所有者と、その領地に何人の軍隊がいたかを知りたいのです。私の主な情報源はゲーム ログです。ノート：

% ゲームログにはありませんが、すべての領地は 3 部隊で始まります。

% ゲーム終了時に領地の所有者を把握しており、ゲーム ログにはすべての所有者の変更が記載されているため、いつでも領地の所有者を簡単に特定できます。

% 課題は、特定の時間に領土にいる軍隊の数を見つけることです。

% ゲームログは、部隊の配備、増援、および征服に関する情報を提供します。

%ただし、ゲームログは不完全です。領土 X が領土 Y の攻撃に失敗したが、その過程で両方の領土が軍隊を失ったとします。ゲームログはこれについて言及しません。

% 特定の時点で領土内の正確な部隊数を見つけることはおそらく (一般的には) 不可能なので、範囲を探しています。

% データを一連の不等式として Mathematica に入力しようとしましたが、マニュアルで警告されているように、不等式の数に応じて計算時間が指数関数的に増加します。不等式の数がかなり少ない場合でも、ハングします。さらに、ここで Mathematica が適切なツールであるとは確信していません。

％ 何かご意見は？別の例: http://conquerclub.barrycarter.info/ONEOFF/7562013.html

% http://userscripts.org/scripts/show/83035については知っていますが、\ 所有者のみを追跡し、部隊の数は追跡しません。

興味深い概念上の問題があり、誰かがそれを定量化するのを手伝ってくれるかどうか疑問に思っています. 基本的に、私は一連のゲームをプレイしています...各ゲームで、勝つ確率、引き分けの確率、負ける確率を知っています (各ゲームの確率は異なります)。

大まかに言うと、私が知りたいのは、どのゲームに注意を向けるべきかということです。たとえば、勝つ可能性が 0% のゲーム (または勝つ可能性が 100% のゲーム) には力を入れません。しかし、50/50 のゲームでは、私は多くのことに気を配り、最大限の努力をしたいと考えています。同点でなければ、次のように単純になります。しかし、関係があると、事態は複雑になります。

厳密に必要かどうかはわかりませんが、必要な場合は、勝利は 0 ポイント、引き分けは 1 ポイント、勝利は 2 ポイントと仮定できます。言い換えれば、負けから引き分けになることは、引き分けから勝ちになることと同じくらい価値があるということです。

すべてのゲームが独立していると仮定することもできます。基本的に、私は「ケア能力」の定量的指標 (たとえば、0 から 1 までの値) を探しているだけです。

このようなものにアプローチする方法について、誰かアイデアはありますか? あなたが経済学者なら、ゲームに勝つ可能性を高めるために使える金額は限られていると想像できます。期待される結果を最大化するために、これらの資金をゲーム全体にどのように配分しますか?

前もって感謝します！

編集：申し訳ありませんが、これはかなり不十分な表現の質問であることに気づきました。追加投資と生産された結果との関係は特定しません。直線的な関係であると仮定したかったのですが、その場合、どのゲームに投資しても、期待値は常に同じように増加するので問題ありません。私の実際の問題はもう少し複雑で、少し考え直す必要があります。助けてくれて素晴らしいアイデアをくれたみんなに感謝します！

2 人ゼロ ゲームのナッシュ均衡を解く Python ライブラリはありますか? 解決策は線形制約の観点から書き留めることができ、理論的には、scipy はそれを最適化できるはずです。ただし、2 人ゼロ ゲームの場合、解は正確かつ一意ですが、一部のソルバーは特定の問題で収束に失敗します。

Python の Web サイトで線形プログラミングに関するライブラリを一覧表示するのではなく、使いやすさと速度の点でどのライブラリが最も効果的かを知りたいと思います。

私は最近 Gambit に出くわしました - http://www.gambit-project.org/doc/index.html - C++ アルゴリズム ゲーム理論 API。

.NET Game Theory Library を知っている人はいますか?

私はこれがこの質問をするのに正確に正しい場所ではないことを知っています、しかし多分賢い人が出くわして解決策を持っています。

私はコンピューターゲームを書こうとしていますが、この質問を解決するためのアルゴリズムが必要です。

ゲームは2人のプレーヤーの間で行われます。それぞれの側に1.000ドルがあります。3つの「ボックス」があり、各プレーヤーはそれらのボックスに入れる予定の金額を書き留めます。次に、これらの金額が比較されます。ボックスにもっとお金を入れた人は誰でも1ポイントを獲得します（それぞれ半分のポイントを引く場合）。より多くのポイントを獲得した人は、対戦相手に1.000ドルを獲得します。ゲームの例：

プレーヤーA：[500、500、0]プレーヤーB：[333、333、334]

プレーヤーAは、ボックスAとボックスBを獲得したために勝ちました（ただし、ボックスCを失いました）。

質問：お金を入れるための最適な戦略は何ですか？

質問がもっとありますが（数学に関連するのではなく、アルゴリズムに関連する）、最初にこれに対する答えを知る必要があります。

更新（1）：さらに調査した結果、これらのタイプの問題/ゲームは大佐ブロットゲームと呼ばれていることがわかりました。私は最善を尽くし、この主題に関する（非常に技術的な）文書をほとんど見つけませんでした。簡単に言えば、私が抱えている問題（上記のとおり）は、単純なBlottoゲーム（対称的なリソースを持つ3つの戦場のみ）と呼ばれます。難しいのは、たとえば、非対称のリソースを持つ10以上の戦場があるものです。私が読んだすべての文書は、単純なBlottoゲームは簡単に解決できると言っています。問題は、それらのどれも実際にその「簡単な」解決策が何であるかを言っていないということです。

更新（2）： Tom Sirgedasが言及した論文で、戦略を示すために小さなactionscriptファイルを作成しました。megaswfでテストできます。手順：三角形の内側の点をクリックします。赤い領域は勝利事例を表しています。青い領域は負けたケースを表し、小さな白っぽい線は引き分けを表します。

根の張った木の森があります。2 人のプレーヤーが、次のルールに従って交互に移動します。1 つの移動は、頂点とそのすべての子をカットすることです。最後の移動 (頂点が残っていない) を行うプレイヤーが勝ちます。

ゲーム内の位置の Grundy 関数をどのように計算できますか?

木があり、現在の位置が勝っているか負けているかを言う必要があるとします。