1

我正在为比赛设计一个决策系统，要求玩家瞄准不同的目标。在不同目标上得分的概率各不相同，每个目标上得分的球员越多，在那个目标上得分的概率就会降低。球员的尝试机会有限。

我想到的只有马尔可夫链和博弈论，但我不知道如何实现它们，我想知道是否有任何其他数学技术可以最大化我的分数。

我将非常感谢任何指导。

4

2 回答 2

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目标沿着两条路径分裂，我们(2t)**(Depth+1)-1在树中有节点。因此，明智地选择你的深度以避免永远思考。

上面的代码，在我的 Intel i5 M480 cpu（现在大约五年前）上，深度 = 5 的优化运行时间为 0.044 秒，深度 = 6 的优化运行时间为 0.557 秒。对于深度=6，树中有 268,435,455 个节点，每个叶子的可能性只有 16,777,216 分之一的可能性被实现。除非你的价值函数很奇怪，否则没有必要考虑更远的未来。

分支定界：改进的解决方案

但是，如果您确实需要探索更大的空间或走得更快，您可以考虑使用Branch and Bound 方法。其工作方式相同，只是我们选择不扩展任何可证明小于我们已经找到的解决方案的子树。然后证明一个严格的上限成为主要挑战。

于 2016-12-21T05:19:27.847 回答
1

为什么不使用贪心算法？

您不能在每个时间点都比选择具有最高期望值的目标（命中概率乘以目标值）做得更好。

于 2016-12-21T17:44:54.817 回答