Questo è il problema per quanto posso vederlo:
- Ogni campo ha un "livello di pericolo" casuale, sconosciuto ℓ i che viene equamente distribuito su un determinato intervallo [ℓ min , ℓ max ]. Quindi, in media, il livello è ℓ = (ℓ min + ℓ max ) / 2.
- Il passaggio al campo successivo ha un costo fisso Δ c m .
- Ogni mossa aumenta il "pericolo" d di Δ d .
-
Se d > ℓ i dopo uno spostamento, quindi è possibile prendere due opzioni:
- Il costo totale può aumentare di Δ c r = 2 (scappando), o
- Il costo totale può aumentare di Δ c f = 15 (combattimento), nel qual caso d viene riportato a zero.
La probabilità p (F) che d > ℓ i , cioè che si verifica un combattimento, è 0 se d < ℓ min , else ( d - ℓ min ) / (ℓ max - ℓ min ).
Quindi il nostro problema ha i parametri fissi ℓ min , ℓ max , Δ d , Δ c < sub> m , Δ c r , Δ c f e le variabili di stato c e d . Abbiamo le seguenti transizioni di stato possibili:
-
Nessun combattimento: con una probabilità di 1- p (F), non succede nulla. poi:
c ← c + Δ c m
d ← d + Δ d
-
Un combattimento: con una probabilità di p (F), possiamo scegliere le opzioni
-
c ← c + Δ c m + Δ c r
d ← d + Δ d
-
c ← c + Δ c m + Δ c f
d ← 0
Le tue domande sembrano essere il modo in cui il costo totale c può essere ridotto al minimo. In questo modello statistico, non esiste un c definitivo. Invece, dovremo minimizzare il valore atteso per c . Possiamo forzare questa forza esaminando un albero delle decisioni. Ad ogni albero può essere assegnato un costo previsto, che può essere calcolato dalle sottostrutture come
c = min(cF, f, cF, r) · p(F) + c¬F · (1-p(F))
dove c F, f è il costo previsto quando si combatte un combattimento a queste condizioni ecc ..
Il seguente pseudocodice ottiene il costo previsto dato un determinato stato:
function expected_cost(i, c, d) {
return c if i == 0;
p = probability_of_fight(d);
c_no_fight = (1-p) * expected_cost(i - 1, c + Δc_m, d + Δd);
c_fight_run, c_fight_fight = 0, 0;
if (p > 0) {
c_fight_run = p * expected_cost(i - 1, c + Δc_m + Δc_r, d + Δd);
c_fight_fight = p * expected_cost(i - 1, c + Δc_m + Δc_f, 0 );
}
return c_no_fight + min(c_fight_run, c_fight_fight);
}
Ora tutto ciò che deve essere aggiunto è tenere traccia di quali decisioni sono state prese nei percorsi vincenti - nota che ci sono più percorsi vincenti, perché può verificarsi un combattimento, o non può in ogni campo. La decisione che teniamo traccia è se la lotta viene eseguita o fuggita. Analisi interessanti potrebbero essere la frequenza con cui una battaglia è fuggita o combattuta - in questo caso, restituire ulteriori valori con i rispettivi conteggi sembra la cosa da fare. Altrimenti, ispezionare un albero con le storie delle decisioni potrebbe essere interessante.
Bisogna fare attenzione a farlo con i molto piccoli, dato che l'albero può diventare molto grande (fino a 3 i ). La Memoizzazione aiuterà a prevenire alcuni calcoli inutili.
A seconda di come si codifica l'algoritmo di cui sopra, il runtime può variare estremamente. Di seguito è riportato uno script Perl che ho utilizzato, che utilizza un caching estensivo per ottenere un runtime nell'ordine dei secondi (se il costo corrente è anche una chiave nella cache, il runtime è nell'ordine dei minuti). Esegue un esempio di analisi del conteggio della frequenza con cui scappare e combattere è più vantaggioso. Con questi parametri, l'impegno a combattere non è una strategia praticabile prima che il gioco sia lungo 123 campi.
use strict;
use warnings;
no warnings qw/recursion/;
use feature qw/state/;
use utf8;
use Math::BigInt; # not neccessary. alternatively: no warnings 'imprecision'
# parameters as explained in answer
my ($ℓ_min, $ℓ_max, $Δd, $Δc_m, $Δc_r, $Δc_f) =
(0xFF, 0xFF**2,113, 1, 2, 15 );
my ($steps) = @ARGV or die <<USAGE;
usage:
$0 iterations
parameters:
iterations -- the number of fields to traverse
USAGE
my ($cost, $fight, $run) = expected_cost($steps, 0);
printf "expected cost for i=%d steps is %g\n",
$steps, $cost;
printf "fight won %.3e times\n",
$fight;
printf "run won %.3e times\n",
$run;
printf "fight:run relation: %s\n",
($run > $fight) ? sprintf('1:%.3e', $run/$fight) : sprintf('%.3e:1', $fight/$run);
sub probability_of_fight {
my ($d) = @_;
return $d < $ℓ_min ? 0 : ($d - $ℓ_min)/($ℓ_max - $ℓ_min);
}
# Takes number $i of fields left and accumulated danger $d
# Return expected cost for that subtree, plus favourable fights and fleeings.
sub expected_cost {
my ($i, $d) = @_;
return 0, 0, 0 if $i == 0;
state $cache = [];
my $retval = $cache->[$i][$d] //= do {
my $p = probability_of_fight($d);
# variable prefixes:
# nf -- no fight
# f -- fight
# fr -- fight, but run away
# ff -- fight, and carry out the fight
my ($nf_c, $nf_fight, $nf_run) = expected_cost($i - 1, $d + $Δd);
my $f_c = 0;
my ($f_fight, $f_run) = (Math::BigInt->new, Math::BigInt->new);
if ($p > 0) {
my ($fr_c, $fr_fight, $fr_run) = expected_cost($i - 1, $d + $Δd);
$fr_c += $Δc_r;
my ($ff_c, $ff_fight, $ff_run) = expected_cost($i - 1, 0 );
$ff_c += $Δc_f;
if ($ff_c < $fr_c) {
# fighting is cheaper
$f_c = $ff_c;
$f_fight = $ff_fight + 1;
$f_run = $ff_run;
}
elsif ($ff_c > $fr_c) {
# running away is cheaper
$f_c = $fr_c;
$f_fight = $fr_fight;
$f_run = $fr_run + 1;
}
else {
# both are equivalent
$f_c = $ff_c;
$f_fight = $ff_fight + $fr_fight;
$f_run = $ff_run + $fr_run;
}
}
my $expected_cost = $Δc_m + (1-$p) * $nf_c + $p * $f_c;
[$expected_cost, $nf_fight + $f_fight, $nf_run + $f_run];
};
return @$retval;
}
Sessione di esempio:
$ perl decide.pl 128
expected cost for i=128 steps is 154.27
fight won 2.432e+17 times
run won 5.317e+36 times
fight:run relation: 1:2.186e+19
... dove "vinto" significa "si verifica spesso nel miglior albero delle decisioni". Questo si traduce approssimativamente in una probabilità di quale decisione è probabile che sia più economica.
Ho avuto un po 'di tempo per ulteriori analisi. Per ogni campo, possiamo calcolare se, quando un combattimento si verifica in questa posizione, dovremmo piuttosto fuggire o combattere. Ho tracciato il risultato qui sotto:
... che utilizza i parametri dello script precedente.
Come leggere questo grafico: l'asse x è la distanza dalla fine del campo, cioè il numero di passi (e quindi di combattimenti) che possono ancora verificarsi. L'asse y è il livello di pericolo che hai accumulato. Se un giocatore deve combattere, può trovare la sua coordinata distanza-pericolo. Se quella coordinata è rossa, il combattimento avrà il minor costo. Se la coordinata è di colore blu, la fuga è probabilmente più economica.
Possiamo vedere che, ad esempio, durante gli ultimi 7 passaggi il combattimento non è mai la scelta migliore (il grafico è già al massimo). Altrimenti, la preferenza varia periodicamente. È probabile che il combattimento sia interessante a circa 70-60 passi dalla fine.
