[PYTHON] Calculation of probability / expected value of FGO star concentration

Caution

This article is about an algorithm of a social game called FGO, Fate / Grand Order.

Introduction

Critical is a big part of the tactics in FGO, but calculating the concentration of critical stars is a bit tedious.

Servant / Hidden Status --Fate / Grand Order @wiki [FGO] -atwiki

The specifications are

• Concentration (SW) is set for each servant. (10-200)
• Increases or decreases depending on the effect of increasing or decreasing the degree of concentration.
• Randomly deal 5 cards from 3 Servants.
• For each card, bonuses (+ 0x2, + 20x2, + 50x1) will be randomly added to the concentration.
• Sort the critical stars you have according to the degree of concentration after adding the bonus.
• No more cards can be distributed to 10 cards.

Calculation example

Consider the following servants.

• SW
• Servant 1: 200
• Servant 2:50
• Servant 3:10

Servants 1 to 2, 2 to 2, 3 to 1 will be distributed, and if you think about the bonuses as +0, +0, +50, +20, +20 ...

• When all cards are less than 10 stars

• When card A has 10 stars

• When cards A and B have 10 stars

……… And the probability changes like this.

Calculation

Bonuses do not change during the distribution process, so ignore them and generalize them. The probability that $ y $ stars will be distributed to the card $ n $ is

• Probability that card $ n $ has $ y-1 $ stars and card $ n $ has 1 star
• Probability that there are $ y $ stars on card $ n $ and one star is distributed in addition to card $ n $

Is the total of. Implement this in your Python program.

Implementation

fgostarcalc.py

import math
#SW of each card (including bonus): Card 1 to Card 5
SW = [200, 200, 100, 70, 30]

#Holds the probability of 0 to 10 star states for each card
Probabilities = [None for _ in range(11**6)]
Probabilities[0] = 1

#Get numbers of any digit(Number of stars on each card)
def digitnum(decim, base, ind):
    return(math.floor((decim % (base**ind))/(base**(ind-1))))

#Sum of numbers in each digit(Star total)
def sumdigit(decim, base):
    if decim == 0:
        return 0
    else:
        return(sum([digitnum(decim, base, i) for i in range(1, 2+math.ceil(math.log(decim, base)))]))

#Validity verification
def is_valid(decim, base, totalstar, card, holdstar):
    if digitnum(decim, base, card) == holdstar:
        if sumdigit(decim, base) == totalstar:
            return True
    return False
        
#Recursive function of probability calculation for each state
def calc_starprob(decim, base, totalstar, card, holdstar):
    #print(decim, base, totalstar, card, holdstar)
    starweights = [0 if digitnum(decim, base, x+1)
                   == base-1 else SW[x] for x in range(5)]
    starprob = [SW[x]/(sum(starweights)-starweights[x]+SW[x])
                for x in range(5)]
    starweights[card] = SW[card]
    if decim < 0 or totalstar < 0 or holdstar < 0:
        print("Error: ", decim, base, totalstar, card, holdstar)
        raise
    if Probabilities[decim] != None:
        return(Probabilities[decim])
    else:
        tmp = [0]
        for x in range(5):
            if digitnum(decim, base, x+1) == 0:
                continue
            else:
                if x+1 == card and holdstar > 0:
                    tmp += [calc_starprob(decim-base**x, base,
                                          totalstar-1, card, holdstar-1)*starprob[x]]
                elif x+1 != card:
                    tmp += [calc_starprob(decim-base**x, base,
                                          totalstar-1, card, holdstar)*starprob[x]]
        Probabilities[decim] = sum(tmp)
        return(Probabilities[decim])

#Probability of collecting holdstar stars on the card when there are totalstar stars
def calc_probability(totalstar,card,holdstar):
    return(sum([calc_starprob(x, 11, totalstar, card, holdstar)
                 for x in range(11**5) if is_valid(x, 11, totalstar, card, holdstar)]))

#Probability of collecting more than holdstar stars on the card when there are totalstar stars
def calc_moreprobability(totalstar,card,holdstar):
    tmp=0
    for star in range(holdstar, 11):
        tmp+=sum([calc_starprob(x, 11, totalstar, card, star)
                for x in range(11**5) if is_valid(x, 11, totalstar, card, star)])
    return(tmp)

#Probability of collecting stars less than holdstar on the card when there are totalstar stars
def calc_lessprobability(totalstar,card,holdstar):
    tmp=0
    for star in range(0,holdstar+1):
        tmp+=sum([calc_starprob(x, 11, totalstar, card, star)
                for x in range(11**5) if is_valid(x, 11, totalstar, card, star)])
    return(tmp)

#totalstar Expected value of the number of stars gathered on the card when there are stars
def calc_expectation(totalstar,card):
    tmp=0
    for star in range(0, 11):
        tmp+=calc_probability(totalstar, card, star)*star
    return(tmp)

#The number of stars required for the expected number of stars gathered on the card to be star(Integer value)
def calc_totalstar_expectation(card,star):
    if star>10:
        star=10
    for totalstar in range(50):
        if calc_expectation(totalstar,card)>star:
            return(totalstar)

test

#sample(Probability that 8 will be collected on card 1 when there are 25 stars)
print(calc_probability(25, 1, 8))
#0.1693947010897705

#sample(Expected number of stars to collect on card 1 when there are 20 stars)
print(calc_expectation(20, 1))
#6.862519232471602

#sample(Number of stars required to collect 4 or more expected values on card 1)
print(calc_totalstar_expectation(1,4))
#12

in conclusion

It's not a very fast implementation, but I was able to calculate it. You can also calculate the probability, expected value, required number, etc. Random bonuses are also $ \ frac {5!} {2! 2!} = 30 $, so if you apply this, you can calculate all patterns.