問題タブ [game-theory]

ダークナイトを見た後、私は囚人のジレンマの概念に夢中になりました。状況に応じて自分自身の利益を最大化するアルゴリズムが存在する必要があります。

この外国人を見つける人のために: http://en.wikipedia.org/wiki/Prisoner%27s_dilemma

非常に興味深い内容です。

編集: 問題は、囚人のジレンマのために存在する最も効率的なアルゴリズムが存在する場合、それは何ですか?

私は最近、チェス コンピューターの可能性について、プログラマーではない人と話し合っていました。私は理論に精通していませんが、十分に知っていると思います。

私は、チェスで常に勝つか膠着状態になる決定論的チューリング マシンは存在し得ないと主張しました。player1/2 の手のすべての組み合わせの空間全体を検索したとしても、コンピューターが各ステップで決定する 1 つの手はヒューリスティックに基づいていると思います。ヒューリスティックに基づいているため、対戦相手が実行できるすべての動きに必ずしも勝つとは限りません。

それどころか、私の友人は、「間違い」の動きをしなければ、コンピューターは常に勝つか引き分けになると考えていました (ただし、それを定義しますか?)。しかし、CS を経験したプログラマーとして、賢明な対戦相手が与えられた場合、あなたの良い選択でさえ、最終的には「間違い」を犯す可能性があることを知っています。すべてを知っていても、次の一手はヒューリスティックに一致する貪欲です。

ほとんどのチェス コンピューターは、可能なエンド ゲームを進行中のゲームと一致させようとします。これは、基本的に動的プログラミングのトレースバックです。繰り返しますが、問題のエンドゲームは回避できます。

編集:うーん...ここでいくつかの羽を波立たせたように見えます. それは良い。

もう一度考えてみると、チェスのような有限のゲームを解くのに理論上の問題はないように思えます。チェスはチェッカーよりも少し複雑で、必ずしも駒を数的に使い果たすのではなく、メイトによって勝利が決まると私は主張します。私の最初の主張はおそらく間違っていますが、まだ十分に (正式に) 証明されていないことを指摘したと思います。

私の思考実験は、ツリー内のブランチが取られるたびに、アルゴリズム (または記憶されたパス) が、対戦相手の移動の可能性のあるブランチに対して (交尾することなく) メイトへのパスを見つけなければならないということだったと思います。議論の後、私たちが夢見ることができるよりも多くのメモリがあれば、これらすべてのパスを見つけることができるので、それを購入します。

良いアルゴリズムの推奨事項を探しています。

ユーザーと実績があります。ユーザーはアチーブメントを作成し、それを他のユーザーに提供します。各アチーブメントには、ユーザーが指定したポイント値が関連付けられています。ユーザーの合計ポイントは、すべての実績の合計です。

基本的：

わかりました、このシステムは明らかに非常にゲーム可能です。多くのアカウントを作成し、お互いにたくさんの成果をあげることができます。ポイント値をユーザーが指定したものとは異なる値にスケーリングすることで、それを少し削減しようとしています。

1. すべてのユーザーが正直であると仮定しますが、難しさを異なる方法で評価しているだけです。ポイント値を正規化するにはどうすればよいですか? AKA 1 人のユーザーは簡単な成果ごとに 5 ポイントを与え、別のユーザーは 10 ポイントを与えます。どうすればそれらを 1 つの値に正規化できますか。目標は、ポイントが難易度に比例する分布です。
2. ポイント値の判断が苦手なユーザーがいる場合、アチーブメントを獲得したユーザーの数から難易度を割り出すにはどうすればよいですか?
3. ユーザーはほとんどがバラバラなグループに分割され、1 人のユーザーが他のユーザーのセット全体に実績を与えることができると仮定します。それは前の 2 つのアルゴリズムに役立ちますか? たとえば、ユーザー A は奇数で終わるユーザーにのみ成果を与え、ユーザー B は偶数で終わるユーザーにのみ成果を与えます。
4. 誰もが悪意を持っている場合、ユーザーがポイント値を過大に膨らませることができないようにするには、どれくらい近づくことができますか?

注: ユーザーへの寄付の質は、彼が受け取った実績の数とはまったく関係ありません。多くのギバーは、自分自身は何も受け取っていない単なるボットですが、特定のアクションを実行したユーザーに自動的に報酬を与えます。

私の現在の計画はこのようなものです。私は、私から成果を得た 1 人あたり 10 ポイントの割り当てを持っています。合計 55 人に 10 個の実績を配布した場合、私の割り当ては 550 です。これは、それを取得した人数に基づいて各実績に割り当てられます。分布が[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]各アチーブメントを取得した人である場合、ポイント値は になります[50, 25, 16.6, 12.5, 10, 8.3, 7.1, 6.25, 5.5, 5]。

私のアプローチと代替の推奨事項に関する問題は大歓迎です。また、私が見逃したと思われる他のケースを投稿してください。リストに追加します. ありがとう！

私は時々ボードゲームの変種をプレイするプログラムを書いています。基本的な戦略は、標準的なアルファベータ法または同様の検索であり、エンドゲームやオープニングへの通常のアプローチによって強化されることもあります。私は主に変則チェスをいじっていたので、評価関数を選ぶときは、基本的なチェス評価関数を使用します。

しかし、今はまったく新しいボードゲームをプレイするプログラムを書いています。良いまたはまともな評価関数を選択するにはどうすればよいですか？

主な課題は、常に同じピースがボード上にあるため、通常のマテリアル機能が位置によって変化せず、ゲームのプレイ回数が1,000回未満であるため、人間が必ずしも十分にプレイできるとは限らないことです。まだ洞察を与えるには。（PS。私はMoGoアプローチを検討しましたが、ランダムゲームが終了する可能性は低いです。）

ゲームの詳細：ゲームは、片面に6個固定された10x10のボードでプレイされます。ピースには特定の移動ルールがあり、特定の方法で相互作用しますが、ピースがキャプチャされることはありません。ゲームの目標は、ボード上の特定の特別な正方形に十分な数のピースを置くことです。コンピュータプログラムの目標は、現在の人間のプレーヤーと競争力のある、またはそれよりも優れたプレーヤーを提供することです。

最終的な目標はアルゴリズムを考案することですが、これはそれ自体がプログラミングの問題ではありません。参考文献、または少なくともゲームの種類の名前を探しています。テレビのゲーム番組でかなり広まっています。ゲームは次のとおりです。

多数のスロットがあり、各スロットには (ある有限セットからの) アイテムが含まれていますが、それはわかりません。各スロットに何が含まれているかを推測する必要があります。ジャッジ (各スロットに何が含まれているかを知っている) に推測を伝えると、ジャッジはどれが正しいかは言わずに、いくつの推測が正しいかを教えてくれます。すべてのアイテムの推測に成功すると、ゲームは終了します。

このタイプのゲームに関する情報には、可能性が最も低い推測で解決するためのアルゴリズムへの参照など、興味があります。Google で検索できるように名前だけでも構いません。

ありがとう！

これは長い投稿であり、ただの楽しみですので、時間があまりない場合は、より重要な質問で人々を助けてください:)

最近xboxでリリースされた「Tower Bloxx」というゲームがあります。ゲームの一部は、最も価値のあるタワーの数を最大化するために、異なる色のタワーを最適な方法でフィールドに配置することです。最も効率的なタワーの配置を決定するアルゴリズムを作成しましたが、あまり効率的ではなく、考えられるすべての組み合わせを総当たりするだけです。4 つのタワー タイプの 4x4 フィールドの場合、約 1 時間で解決します。5 つのタワー タイプでは約 40 時間かかります。これは長すぎます。

ルールは次のとおり です。フィールドに配置できるタワーは 5 種類あります。フィールドにはいくつかのタイプがあります。最も簡単なものは 4x4 マトリックスで、他のフィールドには作成できない「空白」があります。あなたの目的は、できるだけ多くの最も価値のあるタワーをフィールドに配置して、フィールド上のタワーの合計価値を最大化することです (すべてのタワーが一度に建設されたと仮定して、ターンはありません)。

塔の種類(価値の低いものから順に):

• 青 - どこにでも配置可能、値 = 10
• 赤 - 青以外にのみ配置可能、値 = 20
• 緑 - 赤と青のほかに配置、値 = 30
• 黄 - 緑、赤、青のほか、値 = 40
• 白 - 黄、緑、赤、青のほか、値 = 100

つまり、たとえば、緑の塔には、北、南、西、または東の隣接セルに少なくとも 1 つの赤と 1 つの青の塔が必要です (対角線はカウントされません)。白い塔は他のすべての色で囲まれている必要があります。

4x4 フィールド上の 4 つのタワーのアルゴリズムは次のとおりです。

1. 組み合わせの総数 = 4^16
2. [1..4^16] をループし、タワーの配置をエンコードするためにすべての数値を base4 文字列に変換します。したがって、4^16 = "3333 3333 3333 3333" がタワーのタイプ (0=青、...、 3=黄)
3. タワー配置文字列を行列に変換します。
4. マトリックス内のすべてのタワーについて、隣接するタワーをチェックし、いずれかの要件が満たされない場合、この組み合わせ全体が失敗します。
5. すべての正しい組み合わせを配列に入れ、この配列を文字列として辞書順に並べ替えて、可能な限り最良の組み合わせを見つけます (最初に文字列内の文字を並べ替える必要があります)。

私が思いついた唯一の最適化は、最も価値のある塔を含まない組み合わせをスキップすることです. 一部の処理をスキップしますが、4^16 の組み合わせすべてをループします。

これをどのように改善できるか考えていますか？コード サンプルは、Java または php の場合に役立ちます。

- - - -アップデート - - - -

さらに違法な状態を追加した後 (黄色は隅に建設できず、白は隅と端に建設できず、フィールドには各タイプの塔が少なくとも 1 つ含まれている必要があります)、4x4 フィールドに建設できる可能性があるのは 1 つの白い塔のみであることに気付きました。 Java コードの最適化により、合計時間が 40 時間から 16 時間に短縮されました。スレッド化すると 10 時間に短縮される可能性がありますが、それはおそらくブルート フォースの限界です。

私はゲーム理論を勉強したことはありませんが、それは私を魅了します。私の直感では、ほとんどの「エンタープライズ アプリ」開発者は使用していません。ただし、大規模なオンライン サイト (レコメンデーション システムなど) には明らかに関連性があり、SO に大きな影響を与えます。

日常のプロジェクトでゲーム理論の原則を適用したことはありますか? もしそうなら、どの原則ですか？

欠陥防止の実践ガイドで、著者は、ソフトウェア開発の生産性を高めるための1つの創造的な方法は、StackOverflowで評判とバッジを獲得するのと同じように従業員が互いに競争する「生産性ゲーム」を実装することであると述べています。

彼らが挙げた一例は、Microsoftの「VistaInternal Beta 1 Game」で、チームメンバーは「beta1」を綴る手紙を受け取るタスクを実行するように求められました。彼らはこれらの手紙を次のように受け取った：

• b：ベータ1ビルドをインストールします
• e：ベータ1ビルドに投票する
• t：一晩実行
• a：3つの連続したベータ1ビルドをインストールします
• 1：一晩3回実行

彼らは毎週リーダーボードを追跡するウェブサイトを持っていました。著者は結果を説明します：

ベータ2ゲームは、コンセプトを拡張し、テストアクティビティに対してポイントを獲得しました。賞品とランダムな抽選には複数のレベルがあり、プレイヤーは参加に基づいてリストバンドを獲得できました。場合によっては、リストバンドは会議や廊下で競争に拍車をかけたシンボルになりました。

これらのゲームは、全社的に配布されたリリースゲームで最高潮に達しました。賞品は、設置と特定のテスト活動を完了した人のためのランダムな図面に基づいていました。繰り返しになりますが、結果は驚異的で、会社の大部分がWindowsVistaのテストの最終日に参加しました。

あなたの会社で似たようなことを実装したり、参加したりした人はいますか？どうだった？何がうまくいったのか、何がうまくいかなかったのか？

PSそれはまだWindows7の主要なコアであり、ゲームのアイデアにはいくつかのメリットがあると思うので、Vistaについての卑劣なコメントはありません。

更新：より多くのアイデアを得るために賞金を追加しました。バウンティウィークが終わったら、最も興味深いものを受け入れます。20人以上の開発チームでできる実用的なアイデアを探しています。

更新2：Facebookには、誰のコミットが一般的に良いかを判断するための「プッシュカルマ」のメタゲームがあるようです。

「近接」は、オセロ、ゴー、リスクに似た領土支配の戦略ゲームです。2人のプレーヤー、10x12のヘクスグリッドを使用します。2007年にブライアンケーブルによって発明されたゲーム。

a）最適なアルゴリズム、b）AIの構築方法について議論するのにふさわしいゲームのようです。
戦略は、ランダム性係数と非常識な分岐係数（20 ^ 120）により、確率的またはヒューリスティックベースになります。したがって、客観的に比較するのは少し難しいでしょう。 1ターンあたり最大5秒の計算時間制限は妥当なようです=>これはすべてのブルートフォース攻撃を除外します。（ゲームのAIをエキスパートレベルでプレイして感触をつかんでください-いくつかの単純なヒューリスティックに基づいて非常に良い仕事をします）

ゲーム： Flashバージョンはこちら、iPhoneバージョンiProximityはこちら、ウェブ上の他の場所に多数のコピールール：こちら

オブジェクト：すべてのタイルが配置された後、ほとんどの軍隊を制御すること。空のヘックスボードから始めます。毎ターン、空いているボードスペースに配置するためにランダムに番号が付けられたタイル（1から20軍の間の値）を受け取ります。このタイルがALLYタイルに隣接している場合、それらのタイルの防御力を+1（最大値20まで）強化します。それがいずれかの敵タイルに隣接している場合、その数が敵タイルの数よりも多い場合、それはそれらを支配します。

戦略についての考え：ここにいくつかの最初の考えがあります。コンピューターのAIをエキスパートに設定すると、おそらく多くのことがわかります。

1. 周囲を最小化することは、フリップを防ぎ、最悪の場合の損傷を最小限に抑えるための良い戦略のようです。
2. Goの場合と同様に、フォーメーション内に穴を残すことは致命的ですが、1回の移動で最大6マスの軍隊を失う可能性があるため、ヘクスグリッドの場合はさらに致命的です。
3. 番号の小さいタイルは責任があるので、メインの領域から離れて、ボードの端の近くに配置し、散らばらせます。また、番号の小さいタイルを使用して、フォーメーションの穴を塞いだり、敵が攻撃する傾向がないように周囲に沿って小さなゲインを作成したりすることもできます。
4. 3つのピースの三角形の形成は、相互に補強し、周囲を縮小するため、強力です。
5. 各タイルは最大6回、つまり隣接するタイルが占有されているときに反転できます。フォーメーションの制御は前後に流れることができます。フォーメーションの一部を失い、穴を塞いでボードのその部分を「デッド」にし、領土をロックして/それ以上の損失を防ぐことがあります。
6. 番号の小さいタイルは明らかですが、価値の低い負債ですが、番号の大きいタイルは、裏返されると（より困難になります）、より大きな負債になる可能性があります。20軍のタイルを使った1回の幸運なプレイでは、200のスイング（+100から-100軍）が発生する可能性があります。したがって、タイルの配置には、攻撃と防御の両方の考慮事項があります。

コメント1、2、4は、予想される最大の損失を最小化するミニマックス戦略に似ているようです（対戦相手が1..20から取得できる値ßの確率論的考察によって修正されます。つまり、ßによってのみ反転できる構造です。 = 20タイルは「ほとんど難攻不落」です。）コメント3、5、6が最適な戦略にどのような影響を与えるかはわかりません。Go、Chess、またはOthelloのプレーヤーからのコメントに興味があります。

（XBox Liveの続編ProximityHDは、4プレイヤーの協力的または競争力のあるローカルマルチプレイヤーを可能にします。これは、いつでも手札に5つのタイルがあり、そのうち1つしかプレイできないためです。味方のタイルの強化は味方ごとに+2に増加しました。）