Comment optimiser le score dans un match

Question

Je suis en train de concevoir un système de prise de décision pour un concours où les joueurs doivent viser différentes cibles. Les probabilités de marquer sur différentes cibles varient, et plus les joueurs marquent sur chaque cible, plus la probabilité de marquer des points sur cette cible diminue. Les joueurs ont des chances d'essai limitées. Ce qui me vient à l'esprit est seulement la théorie des chaînes et des jeux de Markov, mais je ne sais pas comment les implémenter, et je me demande s'il existe d'autres techniques mathématiques pour maximiser mon score.

J'apprécierais profondément toute pièce d'orientation.

Answer 1

Markov Processes: Une non-Solution

Je ne pense pas un processus de Markov va travailler ici. La propriété de Markov exige que la distribution de probabilité des états futurs d'un processus dépende seulement de son état actuel

Un processus stochastique a la propriété de Markov si la distribution de probabilité conditionnelle des états futurs du processus (dépendante des états passés et présents) dépend uniquement de l'état présent, et non de la séquence des événements qui l'ont précédé, puisque la probabilité de toucher une cible diminue avec chaque coup réussi, le futur de votre processus dépend de son passé et, par conséquent, , le votre processus ne Markov

récursive-force Brute Recherche. Une solution adéquate

Une façon de résoudre ce problème consiste à explorer un arbre de recherche. Le code C++ suivant décrit l'opération:

#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; 
} 

Maintenant, essayez d'atteindre une cible. Si nous le frappons, la valeur de notre action (appelez le H) est la valeur de la cible plus la valeur de toutes nos actions futures. Si nous manquons (M), alors la valeur est zéro plus la valeur de toutes nos actions futures. Nous pondérer ces valeurs par la probabilité p de chaque passe, pour obtenir l'équation:

Valeur = pH + (1- p) M

Nous calculons les valeurs futures dans le de la même manière, générant ainsi une fonction récursive. Puisque cela pourrait durer éternellement, nous avons limité la profondeur de la récursion à un certain nombre de niveaux. Puisque, à chaque niveau, l'arbre de décision se divise le long de deux chemins pour chacune des cibles t, nous avons (2t)**(Depth+1)-1 nœuds dans l'arbre. Par conséquent, choisissez judicieusement votre profondeur pour éviter de penser pour toujours.

Le code ci-dessus, avec des optimisations, fonctionne en 0,044s pour la profondeur = 5 et 0,557s pour la profondeur = 6 sur mon processeur Intel i5 M480 (qui a maintenant environ cinq ans). Pour la profondeur = 6, il y a 268.435.455 nœuds dans l'arbre et chaque possibilité de feuille n'a qu'une chance sur 16.777.216 de se réaliser. À moins que votre fonction de valeur soit bizarre, il n'y a pas besoin de considérer le futur plus loin que cela.

Branch and Bound: une solution améliorée

Mais, si vous avez besoin d'aller explorer un plus grand espace ou aller plus vite, vous pourriez envisager d'utiliser Branch and Bound methods. Cela fonctionne de la même manière, sauf que nous choisissons de ne pas étendre les sous-arbres qui sont prouvablement moins qu'une solution que nous avons déjà trouvée. Prouver une limite supérieure serrée devient alors le principal défi. Pourquoi ne pas utiliser un algorithme gourmand?

Answer 2

Vous ne pouvez pas faire mieux à chaque moment que de choisir la cible avec la valeur attendue la plus élevée (probabilité de succès multipliée par la valeur de la cible).