경기에서 득점을 최적화하는 방법

Question

나는 선수들이 다른 목표를 목표로해야하는 대회를위한 의사 결정 시스템을 설계하고 있습니다. 각기 다른 목표에 따라 점수를 매기는 확률이 다르며, 각 목표에 점수를 매길 확률이 낮아집니다. 플레이어는 시도의 기회가 제한적입니다.

내가 마음에 떠오르는 것은 Markov Chain과 게임 이론이지만 아직 구현 방법을 모르며 점수를 최대화 할 수있는 다른 수학 기법이 있는지 궁금합니다.

나는 어떤 조언을 주셔서 감사합니다.

Answer 1

마르코프가 처리 : 비 솔루션

나는 생각하지 않는다 마르코프 프로세스가 여기서 일 것입니다. Markov 속성은 프로세스의 미래 상태의 확률 분포가 현재 상태 (또는 과거의 제한된 수)에만 의존 할 것을 요구합니다.

확률 프로세스는 미래 프로세스 상태의 조건부 확률 분포 과거와 현재의 상태에 따라 조건이 달렸 음)는 이전의 사건의 순서가 아니라 현재의 상태에만 의존합니다. 목표를 명중 할 확률이 성공할 때마다 감소하기 때문에 프로세스의 미래는 과거에 따라 달라 지므로 , 당신의 과정은 마르코프하지

재귀 브 루트 포스 검색 :. 적절한 솔루션

이 문제를 해결하는 한 가지 방법은 검색 트리를 탐색하는 것입니다. 다음 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)를 놓친 경우, 그 값은 앞으로의 모든 조치의 가치에 0을 더한 것입니다. 우리는 식 얻을 확률 각 P 발생하여 이들 값을 무게 :

값 = 산도 + (1- P) M

우리는의 미래 값을 계산할 동일한 방식으로, 재귀 함수를 생성합니다. 이것이 영원히 계속 될 수 있기 때문에, 우리는 재귀의 깊이를 몇 가지 수준으로 묶었습니다. 각 레벨에서 결정 트리는 t 대상 각각에 대해 두 경로를 따라 분할되기 때문에 우리는 (2t)**(Depth+1)-1 노드를 트리에 가지고 있습니다. 따라서 영원히 생각하지 않으려면 깊이를 현명하게 선택하십시오.

위의 코드는 인텔 i5 M480 CPU (현재 약 5 년)에서 깊이 = 5의 경우 0.044s, 깊이 = 6의 경우 0.557s에서 실행됩니다. 깊이 = 6 인 경우 트리에 268,435,455 개의 노드가 있고 각 리프 가능성은 실현 가능성이 16,777,216에 불과합니다. 귀하의 가치 기능이 이상한이 아니라면 그보다 더 먼 미래를 고려할 필요가 없습니다.

분기 및 바운드 : 개선 된 솔루션

그러나, 더 큰 공간을 찾아 이동하거나 빨리 갈 필요 않은 경우, 당신은 Branch and Bound methods를 사용하여 고려할 수 있습니다. 이것은 우리가 이미 발견 한 해답보다 훨씬 적은 서브 트리를 확장하지 않는다는 것을 제외하고는 같은 방식으로 작동합니다. 그런 다음 꽉 막힌 상한을 입증하면 주요 문제가됩니다.

Answer 2

왜 그리 디 알고리즘을 사용하지 않습니까?

가장 높은 예상 값 (타격 값에 목표 값으로 곱한 확률)을 선택하는 것보다 각 시점에서 더 잘할 수 없습니다.