Ho notato che manca una trattazione completa del problema
del calcolo della probabilità relativo al caso di attacchi singoli e
iterati tra stati confinanti.
In effetti nella sua forma più completa non è immediato.
Userò la notazione seguente:
(A,D) con A,D > 0
per indicare uno stato con A armate ed uno stato confinante con D armate.
Il primo elemento della coppia è l'attaccante.
Fissiamo un tetto massimo per A,D: 0 <= A,D <= M
Usare lo 0 è utile nella implementazione degli algoritmi e
inoltre possiamo supporre M <= 130.
Quello che interessa è determinare la probabilità di passaggio da uno
stato i ad uno j in esattamente 'n' passi o attacchi.
Da questo risultato generale si ottengono poi tutti gli altri.
Identifico con i lo stato (A,D) e con j lo stato (A',D')
dove si ha
A' <= A
D' <= D
e A',D' sono coerenti in base al numero di dadi usati
dall'attacco/difesa (e almeno uno dei due è strettamente minore).
La formula per ottenere la corrispondenza tra i e (A,D) è la seguente:
i = A * (M + 1) + D
e per il passaggio inverso
A = i / (M + 1)
D = i % (M + 1)
i = 0,...,(M + 1) * (M + 1)- 1
Quindi ho trovato un modo di enumerare le (M+1) * (M+1) coppie (A,D) con
un indice [indice = stato della catena].
Quindi voglio calcolare
P(n){i -> j} = {probabilità di passare da i a j in esattamente n-passi, n > 0}
Ai casi in cui non esiste un attacco possibile assegno valore 0, quindi
P(n){i -> j} = 0 se non posso andare da i a j con n passi.
Es: P(n){(2,3) -> (2,2)} = 0 [non posso attaccare 2vs3]
Es: P(n){(2,1) -> (2,1)} = 0 [non posso attaccare 2vs1 ottenendo ancora (2,1)]
Es: P(n){(3,1) -> (0,7)} = 0 [non posso attaccare 3vs1 ottenendo 0 armate per chi attacca]
Es: P(n){(5,5) -> (5,4)} = 0 [non posso attaccare 5vs5 con la difesa che perde un'armata]
Dal punto di vista pratico risulterà utile assegnare valore 1 alle probabilità di
transizioni del tipo (A,D) --> (M,M) quando nessun altro attacco è possibile a partire da (A,D).
Ogni attacco indica il passaggio di una unità di tempo (n --> n+1).
Questa era la parte di "formalizzazione".
Per la parte di calcolo prendiamo in prestito la teoria
delle "catene di Markov a stato/tempo discreto e numero finito di stati".
Riassumendo:
- il tempo evolve in step ben determinati;
- la catena è omogenea infatti le probabilità di transizione non
dipendono da n (assenza di memoria);
- l'insieme degli stati, {(A,D) / 0<=A,D<=M} è finito;
Possiamo definire quindi la matrice bidimensionale stocastica Q[][] di transizione.
Qui è utile la convenzione fatta prima, cioè porre P(1){(A,D) --> (M,M)} = 1 in certi casi.
Quando in input viene fornito un valore massimo di M per generare tutte le informazioni
per le coppie (A,D) con A,D <= M, in realtà lo aumento di 1 (M = M + 1), in modo
da far collassare in questo "dummy state" tutti i casi degeneri che si presentano.
L'output interessante sarà poi fino a M-1.
Questo non lo dirò più e mi riferisco sempre a M.
Q[][] è facilmente descritta quando n = 1 essendo le prob
tutte note (sono le varie 30_3vs3, 21_3vs3, ... mostrate anche nel .pdf)
def: Q[i][j] = P(1){i --> j}
Per sapere lo stato del sistema al tempo n basta calcolare Q^n.
Il costo computazionale è piuttosto alto se n ed M sono grandi.
[Nota: per un metodo "ottimizzato" per la soluzione del
PROBLEMA DELLA CONQUISTA DEL TERRITORIO da
uno stato con A armate ad uno con D armate aspettiamo
un pò quando avrete digerito tutto questo.]
L'elemento Q(n)[i][j] indica appunto la probabilità che lo stato del sistema
sia j, partendo dallo stato i, e dopo che sono passati esattamente n passi.
Ad un certo punto non sarà più possibile fare attacchi e quindi esiste un numero nmax
per il quale tutte le matrici di ordine superiore saranno uguali a Q^nmax.
Gli elementi delle quali saranno tutti nulli tranne la colonna relativa allo stato (M,M).
Avendo a disposizione la famiglia {Q^1,...,Q^nmax} è possibile rispondere facilmente a
domande del tipo:
[ 1 ] qual'è la probabilità di conquistare un territorio A vs D ?
[ 2 ] qual'è la probabilità di finire con k armate di avanzo in un attacco riuscito A vs D ?
[ 3 ] qual'è la probabilità di conquistare un territorio A vs D in esattamente k passi ?
[ 4 ] qual'è la probabilità di conquistare un territorio A vs D in al più k passi ?
[ 5 ] qual'è la probabilità di conquistare un territorio A vs D in più di k e meno di m passi ?
[...] etc
Basta leggere le tabelle in un modo molto semplice.
A titolo di esempio ecco le matrici {Q^n} per il caso M = 5
Q^1
( 2 1) --> ( 1 1) 0.5833333333333333 sim 0.58341150
( 2 1) --> ( 2 0) 0.4166666666666666 sim 0.41683900
( 3 1) --> ( 2 1) 0.4212962962962962 sim 0.42130450
( 3 1) --> ( 3 0) 0.5787037037037037 sim 0.57909950
( 3 2) --> ( 1 2) 0.4483024691358024 sim 0.44768250
( 3 2) --> ( 2 1) 0.3240740740740740 sim 0.32368150
( 3 2) --> ( 3 0) 0.2276234567901234 sim 0.22734100
( 4 1) --> ( 3 1) 0.3402777777777777 sim 0.33985350
( 4 1) --> ( 4 0) 0.6597222222222222 sim 0.65948200
( 4 2) --> ( 2 2) 0.2925668724279835 sim 0.29224850
( 4 2) --> ( 3 1) 0.3357767489711934 sim 0.33571800
( 4 2) --> ( 4 0) 0.3716563786008230 sim 0.37174050
( 4 3) --> ( 1 3) 0.3830375514403292 sim 0.38258150
( 4 3) --> ( 2 2) 0.2646604938271604 sim 0.26478500
( 4 3) --> ( 3 1) 0.2146990740740740 sim 0.21497650
( 4 3) --> ( 4 0) 0.1376028806584362 sim 0.13714450
( 4 4) --> ( 1 4) 0.3830375514403292 sim 0.38288700
( 4 4) --> ( 2 3) 0.2646604938271604 sim 0.26509650
( 4 4) --> ( 3 2) 0.2146990740740740 sim 0.21495750
( 4 4) --> ( 4 1) 0.1376028806584362 sim 0.13767100
( 4 5) --> ( 1 5) 0.3830375514403292 sim 0.38345000
( 4 5) --> ( 2 4) 0.2646604938271604 sim 0.26503800
( 4 5) --> ( 3 3) 0.2146990740740740 sim 0.21488400
( 4 5) --> ( 4 2) 0.1376028806584362 sim 0.13768800
( 5 1) --> ( 4 1) 0.3402777777777777 sim 0.34035550
( 5 1) --> ( 5 0) 0.6597222222222222 sim 0.65991300
( 5 2) --> ( 3 2) 0.2925668724279835 sim 0.29258450
( 5 2) --> ( 4 1) 0.3357767489711934 sim 0.33545950
( 5 2) --> ( 5 0) 0.3716563786008230 sim 0.37125800
( 5 3) --> ( 2 3) 0.3830375514403292 sim 0.38293150
( 5 3) --> ( 3 2) 0.2646604938271604 sim 0.26450200
( 5 3) --> ( 4 1) 0.2146990740740740 sim 0.21425650
( 5 3) --> ( 5 0) 0.1376028806584362 sim 0.13793050
( 5 4) --> ( 2 4) 0.3830375514403292 sim 0.38292550
( 5 4) --> ( 3 3) 0.2646604938271604 sim 0.26508800
( 5 4) --> ( 4 2) 0.2146990740740740 sim 0.21499400
( 5 4) --> ( 5 1) 0.1376028806584362 sim 0.13757400
( 5 5) --> ( 2 5) 0.3830375514403292 sim 0.38322400
( 5 5) --> ( 3 4) 0.2646604938271604 sim 0.26450250
( 5 5) --> ( 4 3) 0.2146990740740740 sim 0.21494050
( 5 5) --> ( 5 2) 0.1376028806584362 sim 0.13793150
Q^2
( 3 1) --> ( 1 1) 0.2457561728395061 sim 0.24601600
( 3 1) --> ( 2 0) 0.1755401234567901 sim 0.17521150
( 3 2) --> ( 1 1) 0.1890432098765432 sim 0.18893500
( 3 2) --> ( 2 0) 0.1350308641975308 sim 0.13520700
( 4 1) --> ( 2 1) 0.1433577674897119 sim 0.14319250
( 4 1) --> ( 3 0) 0.1969200102880658 sim 0.19692000
( 4 2) --> ( 2 1) 0.1414615007239750 sim 0.14163450
( 4 2) --> ( 3 0) 0.1943152482472184 sim 0.19446000
( 4 3) --> ( 2 1) 0.0904519247256515 sim 0.09027150
( 4 3) --> ( 3 0) 0.1242471493484224 sim 0.12428250
( 4 4) --> ( 1 2) 0.0962501250285779 sim 0.09657000
( 4 4) --> ( 2 1) 0.0695784036351165 sim 0.06968100
( 4 4) --> ( 3 0) 0.0488705454103795 sim 0.04860500
( 4 4) --> ( 3 1) 0.0468232024462734 sim 0.04671200
( 4 4) --> ( 4 0) 0.0907796782121627 sim 0.09116250
( 4 5) --> ( 2 2) 0.0402580444313197 sim 0.04039050
( 4 5) --> ( 3 1) 0.0462038479165608 sim 0.04612200
( 4 5) --> ( 4 0) 0.0511409883105556 sim 0.05124450
( 5 1) --> ( 3 1) 0.1157889660493827 sim 0.11579500
( 5 1) --> ( 4 0) 0.2244888117283950 sim 0.22437650
( 5 2) --> ( 1 2) 0.1311584512968043 sim 0.13098550
( 5 2) --> ( 2 1) 0.0948133382868465 sim 0.09448400
( 5 2) --> ( 3 0) 0.0665950828443326 sim 0.06663050
( 5 2) --> ( 3 1) 0.1142573659693644 sim 0.11452450
( 5 2) --> ( 4 0) 0.2215193830018289 sim 0.22155050
( 5 3) --> ( 1 2) 0.1186479528654168 sim 0.11849900
( 5 3) --> ( 2 1) 0.0857696044810242 sim 0.08582950
( 5 3) --> ( 3 0) 0.0602429364807194 sim 0.06034650
( 5 3) --> ( 3 1) 0.0730573238168724 sim 0.07283800
( 5 3) --> ( 4 0) 0.1416417502572016 sim 0.14181700
( 5 4) --> ( 2 2) 0.0628138366150358 sim 0.06273400
( 5 4) --> ( 3 1) 0.0720909570997180 sim 0.07210300
( 5 4) --> ( 4 0) 0.0797942803593202 sim 0.07973450
( 5 4) --> ( 4 1) 0.0468232024462734 sim 0.04674950
( 5 4) --> ( 5 0) 0.0907796782121627 sim 0.09056050
( 5 5) --> ( 1 3) 0.0822378076298392 sim 0.08210700
( 5 5) --> ( 2 2) 0.0568223629686785 sim 0.05706450
( 5 5) --> ( 3 1) 0.0460956924082647 sim 0.04595500
( 5 5) --> ( 3 2) 0.0402580444313197 sim 0.04010100
( 5 5) --> ( 4 0) 0.0295432110672915 sim 0.02965650
( 5 5) --> ( 4 1) 0.0462038479165608 sim 0.04646700
( 5 5) --> ( 5 0) 0.0511409883105556 sim 0.05093800
Q^3
( 4 1) --> ( 1 1) 0.0836253643689986 sim 0.08345150
( 4 1) --> ( 2 0) 0.0597324031207133 sim 0.05970550
( 4 2) --> ( 1 1) 0.0825192087556520 sim 0.08254600
( 4 2) --> ( 2 0) 0.0589422919683229 sim 0.05892200
( 4 3) --> ( 1 1) 0.0527636227566300 sim 0.05274100
( 4 3) --> ( 2 0) 0.0376883019690214 sim 0.03797050
( 4 4) --> ( 1 1) 0.0405874021204846 sim 0.04059450
( 4 4) --> ( 2 0) 0.0289910015146319 sim 0.02908400
( 4 4) --> ( 2 1) 0.0197264417713466 sim 0.01970550
( 4 4) --> ( 3 0) 0.0270967606749267 sim 0.02710600
( 4 5) --> ( 2 1) 0.0194655100018844 sim 0.01947000
( 4 5) --> ( 3 0) 0.0267383379146764 sim 0.02665350
( 5 1) --> ( 2 1) 0.0487814625485825 sim 0.04898650
( 5 1) --> ( 3 0) 0.0670075035008001 sim 0.06698250
( 5 2) --> ( 1 1) 0.0553077806673271 sim 0.05506200
( 5 2) --> ( 2 0) 0.0395055576195193 sim 0.03938500
( 5 2) --> ( 2 1) 0.0481362051074637 sim 0.04823250
( 5 2) --> ( 3 0) 0.0661211608619007 sim 0.06624900
( 5 3) --> ( 1 1) 0.0500322692805974 sim 0.04993100
( 5 3) --> ( 2 0) 0.0357373352004267 sim 0.03559300
( 5 3) --> ( 2 1) 0.0307787799413675 sim 0.03071600
( 5 3) --> ( 3 0) 0.0422785438755048 sim 0.04239050
( 5 4) --> ( 2 1) 0.0303716532225663 sim 0.03013900
( 5 4) --> ( 3 0) 0.0417193038771516 sim 0.04187900
( 5 4) --> ( 3 1) 0.0159328952768569 sim 0.01599800
( 5 4) --> ( 4 0) 0.0308903071694165 sim 0.03076400
( 5 5) --> ( 1 2) 0.0180477807211394 sim 0.01810750
( 5 5) --> ( 2 1) 0.0324665329599281 sim 0.03257750
( 5 5) --> ( 3 0) 0.0358394231585168 sim 0.03579950
( 5 5) --> ( 3 1) 0.0157221426938297 sim 0.01570700
( 5 5) --> ( 4 0) 0.0304817052227310 sim 0.03062650
Q^4
( 4 4) --> ( 1 1) 0.0115070910332855 sim 0.01152300
( 4 4) --> ( 2 0) 0.0082193507380611 sim 0.00832650
( 4 5) --> ( 1 1) 0.0113548808344325 sim 0.01132750
( 4 5) --> ( 2 0) 0.0081106291674518 sim 0.00802200
( 5 1) --> ( 1 1) 0.0284558531533398 sim 0.02841650
( 5 1) --> ( 2 0) 0.0203256093952427 sim 0.02035700
( 5 2) --> ( 1 1) 0.0280794529793538 sim 0.02826200
( 5 2) --> ( 2 0) 0.0200567521281098 sim 0.01995800
( 5 3) --> ( 1 1) 0.0179542882991310 sim 0.01803250
( 5 3) --> ( 2 0) 0.0128244916422364 sim 0.01283950
( 5 4) --> ( 1 1) 0.0177167977131637 sim 0.01776700
( 5 4) --> ( 2 0) 0.0126548555094026 sim 0.01269500
( 5 4) --> ( 2 1) 0.0067124697694165 sim 0.00664150
( 5 4) --> ( 3 0) 0.0092204255074403 sim 0.00919650
( 5 5) --> ( 1 1) 0.0189388108932914 sim 0.01904850
( 5 5) --> ( 2 0) 0.0135277220666367 sim 0.01347250
( 5 5) --> ( 2 1) 0.0066236804867523 sim 0.00661500
( 5 5) --> ( 3 0) 0.0090984622070773 sim 0.00905400
Q^5
( 5 4) --> ( 1 1) 0.0039156073654930 sim 0.00392050
( 5 4) --> ( 2 0) 0.0027968624039235 sim 0.00282400
( 5 5) --> ( 1 1) 0.0038638136172721 sim 0.00383050
( 5 5) --> ( 2 0) 0.0027598668694801 sim 0.00277650
Tutti i dati sono stati verificati con simulazioni di 2000000 casi per ogni
situazione e l'errore è sempre < 0.001.
----------------------------------------
Esempio di lettura delle matrici.
Vado nella tabella [Q^3] e vedo che
( 5 2) --> ( 2 1) 0.0481362051074637 sim 0.04823250
quindi vuol dire che in esattamente '3' attacchi la probabilità
che partendo da 5 armate attaccandone 2 possa finire in una situazione
con 2 carri per l'attaccante e un carro per il difensore è
pari a 0.0481362051074637 (con la simulazione ho 0.04823250).
----------------------------------------
O ancora se vado in [Q^4] ho
( 5 3) --> ( 2 0) 0.0128244916422364 sim 0.01283950
quindi in una situazione 5vs3 conquisto il territorio (avanzandone 2)
in esattamente '4' attacchi con prob. 0.0128244916422364
----------------------------------------
Il metodo è generale e si possono avere risultati in
forma totalmente automatica, dato M.
Alle domande [1], [2], ... [5] esposte prima si può rispondere facilmente ora.
Basta leggere opportunamente i valori nelle tabelle.
Nel pdf aggiungo questa casistica per M = 5.
Potrei mettere anche il caso M = 10 ma forse
diventa troppo grande (500/600K credo).
Posso successivamente postare alcuni frammmenti per M maggiori.