Solution en temps polynomial de forme fermée
Une stratégie qui permet de résoudre de nombreuses mises en commun de dés en un temps polynomial :
- Formulez le problème sous la forme d'une chaîne de Markov variable dans le temps, où les pas de temps = les visages, en allant du haut vers le bas.
- Les états de la chaîne de Markov sont définis comme suit :
- Le nombre de dés de chaque groupe (dans ce cas, action et danger) qui ont été consommés jusqu'à présent.
- Le résultat (en cours).
- Toute autre information nécessaire au calcul des résultats futurs. (Dans ce cas, seul le résultat courant est nécessaire).
- L'état initial est le suivant :
- Zéro dé consommé dans chaque réserve.
- Résultat nul.
- Les transitions hors de chaque état à un pas de temps particulier (face) sont définies par :
- Pour chaque réserve, le nombre de fois qu'un nombre particulier de dés non consommés peut obtenir la face courante. Il s'agit simplement d'une distribution binomiale.
- Pour chaque réserve, le nouveau nombre de dés consommés = le nombre précédent de dés consommés + les dés qui ont obtenu la face actuelle.
- Le résultat de la course est obtenu en lançant le plus grand nombre possible de faces courantes dans chaque groupe. Si plus de dés d'action que de dés de danger ont obtenu la face courante, cette face est prise si elle est meilleure que le résultat précédent.
Tant que l'espace d'état et les mises à jour des résultats sont polynomiales, l'algorithme dans son ensemble sera en temps polynomial. Ces gains sont possibles parce que cet algorithme élimine les informations qui ne sont pas ou plus pertinentes, telles que les dés spécifiques qui ont donné chaque numéro ou le nombre exact de dés précédemment consommés qui ont donné chaque numéro.
Voici un exemple de code :
import numpy
from math import comb
def neon_city_overdrive(action, danger):
"""
action: the number of action dice
danger: the number of danger dice
Returns:
A vector of outcome -> ways to roll that outcome.
Outcomes above 6 represent crits.
"""
# number of consumed action, danger dice, outcome ->
# number of ways to roll this outcome with all consumed dice >= the last processed face
# outcomes above 6 represent crits
state = numpy.zeros((action+1, danger+1, 6+action))
# initial state: 1 way to have rolled no dice yet
state[0, 0, 0] = 1.0
for face in [6, 5, 4, 3, 2, 1]:
next_state = numpy.zeros_like(state)
for (consumed_action, consumed_danger, outcome), count in numpy.ndenumerate(state):
remaining_action = action - consumed_action
remaining_danger = danger - consumed_danger
# how many action and danger dice rolled the current face?
for add_action in range(remaining_action+1):
for add_danger in range(remaining_danger+1):
# how many ways are there for this to happen?
factor = comb(remaining_action, add_action) * comb(remaining_danger, add_danger)
next_count = factor * count
if add_action > add_danger:
if face == 6:
# add crits
next_outcome = 5 + add_action - add_danger
else:
next_outcome = max(face, outcome)
else:
next_outcome = outcome
next_state[consumed_action+add_action, consumed_danger+add_danger, next_outcome] += next_count
state = next_state
result = state[action, danger, :]
return result
y = neon_city_overdrive(6, 6)
Il y a plus d'optimisation possible pour ce cas spécifique. Par exemple, étant donné que l'on va de la face la plus haute à la face la plus basse, on pourrait se retirer dès que l'on obtient plus de faces sur l'action que sur le dé de danger, avec un multiplicateur approprié pour les dés qui n'ont pas encore été consommés. Mais cela montre la stratégie générale et est suffisant pour n'importe quelle taille de pool pratique.
Voici un exemple de tracé de 6 dés d'action contre 6 dés de danger :
![enter image description here]()
