1

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

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

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

4

2 に答える 2

1

マルコフ過程: 非解決策

ここでマルコフ過程がうまくいくとは思えません。マルコフ特性は、プロセスの将来の状態の確率分布が現在の状態 (または限られた数の過去の状態) のみに依存することを要求します。

確率的プロセスは、プロセスの将来の状態の条件付き確率分布 (過去と現在の状態の両方を条件とする) が、それに先行する一連のイベントではなく、現在の状態のみに依存する場合、マルコフ特性を持ちます。ターゲットにヒットする確率はヒットが成功するたびに減少するため、プロセスの未来は過去に依存するため、プロセスはマルコフではありません。

再帰的ブルートフォース検索: 適切なソリューション

これを解決する 1 つの方法は、検索ツリーを探索することです。次の C++ コードは、操作を説明しています。

#include <limits>
#include <iostream>
#include <cstdio>
#include <vector>

std::vector<float> ScoreOn(const std::vector<float> &probs, int target){
  std::vector<float> temp = probs; //Copy original array to avoid corrupting it
  temp[target]          *= 0.9;    //Decrease the probability
  return temp;                     //Return the new array
}

std::pair<float,int> Choice(
  const std::vector<float> &probs,
  const std::vector<float> &values,
  int depth
){
  if(depth==0)                      //We gotta cut this off somewhere
    return std::make_pair(0.0,-1);  //Return 0 value at the end of time

  //Any real choice will have a value greater than this
  float valmax = -std::numeric_limits<float>::infinity();
  //Will shortly be filled with a real choice value
  int choice = -1;

  //Loop through all targets
  for(int t=0;t<probs.size();t++){
    float hit_value  = values[t]+Choice(ScoreOn(probs,t),values,depth-1).first;
    float miss_value = 0        +Choice(probs           ,values,depth-1).first;
    float val        = probs[t]*hit_value+(1-probs[t])*miss_value;
    if(val>valmax){ //Is current target a better choice?
      valmax = val;
      choice = t;
    }
  }
  return std::make_pair(valmax,choice);
}

int main(){
  //Generate sample data and print the current best answer
  int target_count = 8; //Number of targets
  std::vector<float> probs,values;
  for(int t=0;t<target_count;t++){
    probs.push_back(rand()/(float)RAND_MAX);
    values.push_back(80.0*(rand()/(float)RAND_MAX));
  }

  std::cout<<Choice(probs,values,6).first<<std::endl;
}

ここで、的を射ることを考えてみましょう。ヒットした場合、アクションの値 ( Hと呼びます) は、ターゲットの値に将来のすべてのアクションの値を加えたものになります。( M )を逃した場合、値はゼロに将来のすべてのアクションの値を加えたものになります。これらの値をそれぞれの確率pで重み付けして、次の式を取得します。

値 = pH +(1- p ) M

同じ方法で将来の値を計算し、再帰関数を生成します。これは永遠に続く可能性があるため、再帰の深さをいくつかのレベルに制限しました。t各レベルで、決定木はターゲットごとに 2 つのパスに沿って分割されるため(2t)**(Depth+1)-1、ツリーにノードがあります。したがって、永遠に考えないように、深さを賢く選択してください。

上記のコードは、最適化されており、私の Intel i5 M480 CPU (現在は約 5 年前) で、深さ = 5 の場合は 0.044 秒、深さ = 6 の場合は 0.557 秒で実行されます。深さ = 6 の場合、ツリーには 268,435,455 個のノードがあり、各リーフの可能性は 16,777,216 分の 1 しか実現されません。あなたの価値関数が奇妙でない限り、それ以上の未来を考える必要はありません。

分岐限定: 改善されたソリューション

ただし、より広い空間を探索したり、より高速に移動する必要がある場合は、Branch and Bound メソッドの使用を検討できます。これは同じように機能しますが、既に見つけたソリューションよりも小さいことが証明されているサブツリーを展開しないことを選択します。厳しい上限を証明することが主要な課題になります。

于 2016-12-21T05:19:27.847 に答える
1

貪欲なアルゴリズムを使用しないのはなぜですか?

各時点で、期待値が最も高いターゲットを選択するよりも優れた方法はありません (ヒットの確率にターゲットの値を掛けた値)。

于 2016-12-21T17:44:54.817 に答える