如何在比赛中优化得分

Question

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

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

我将非常感谢任何指导。

Answer 1

马尔可夫过程：无解

我认为马尔可夫过程在这里行不通。马尔可夫属性要求过程未来状态的概率分布仅取决于其当前状态（或有限数量的过去 st

如果过程的未来状态的条件概率分布（以过去和现在状态为条件）仅取决于当前状态，而不取决于事件的顺序，则随机过程具有马尔可夫属性在它之前。由于每次成功命中都会降低命中目标的概率，因此您的过程的未来取决于它的过去，因此您的过程不是马尔可夫。

递归暴力搜索：一个适当的解决方案

解决这个问题的一种方法是探索搜索树。以下 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 个节点。因此，明智地选择你的深度，避免永远思考。

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

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

但是，如果您确实需要探索更大的 space 或更快，您可以考虑使用 Branch and Bound methods。这以相同的方式工作，除了我们选择不展开任何可证明小于我们已经找到的解决方案的子树。证明严格的上限成为主要挑战。

Answer 2

为什么不用贪心算法？

在每个时间点，您最好选择具有最高期望值（命中概率乘以目标值）的目标。

如何在比赛中优化得分

How to optimize scoring in a match

algorithm

optimization

markov-chains

game-theory

mathematical-optimization