Che il torneo challenge sia un postaccio è fuori da ogni dubbio.
E' un ricettacolo di psicocartinari, cronofrenici, geobulimici, aleopatici e nevrastitici
(D. Piergentili)
Il tuo post #6 ha evidenziato quanto io sia oggettivamente limitato.
Se avessi percepito il condizionamento nella distribuzione delle 42 carte sarei stato perfetto.
Cerco di vedere il lato positivo: la perfezione ha un difetto,....."manca di suspance".
Non sono riuscito a calcolare le distribuzioni "legali" per il 2° e 3° fattore della formula, non immaginavo che il condizionamento arrecasse tanta complicazione.
Mi devo accontentare del calcolo del solo 1° fattore, ergo non ho la risposta alla domanda a).
Avrei by-passato il problema se avessi avuto un software capace di gestire 42!
enumerando tutte le distribuzioni di 42 carte e poi eliminando quelle illegali, ma a quel punto sarebbe stato troppo banale.
Danilo Orsini, Roma (quartiere S.Paolo)
mmm... non scoraggiamoci
Secondo me non c'è necessità di arrivare a calcolare qualcosa di ordine 42 fattoriale per la stessa ragione per cui le distribuzioni "legali" non erano quelle da te calcolate inizialmente (un numero spaventoso). In pratica non devi enumerare tutte le distribuzioni di 42 carte e poi controllare quelle legali, illegali, ecc... è uno spreco immane di risorse di calcolo. Di fatto non ti interessa sapere se è uscita la carta Ontario o Groenlandia ma soltanto che 2 stati su 9 di NA sono occupati. Spero di essermi spiegato.
Tutte le plance possibili per 4 giocatori abbiamo detto che sono circa 6.7x10^22 (vedi post sopra). Quelle legali saranno certamente meno.
Secondo me è fattibile, dai proviamoci
pippman ultimo al Nazionale ...... sono salvo!!!!! link
Gli allegati del post #1, testimoniano che ho seguito proprio la logica che suggerisci.
Come dicevo, con un'intuizione di programmazione, ho isolato le 612 possibili modalità distributive rispetto alle quali calcolare la frequenza delle distribuzioni legali (caso di 10 carte - 1° Fattore).
Credevo di aver capito come calcolare anche il 2° fattore adoperando la medesima logica, ma il condizionamento complica non poco questo calcolo.
L'unica conclusione certa è che le 612 modalità permangono anche per il 2° fattore (ciò è dovuto alla regola del 50%); il punto è trovare la rispettiva frequenza legale, obiettivo al momento al di sopra delle mie capacità.
Forse riflettendo bene su quegli allegati,.....
D'accordo con Te sull'enumerazione (a proposito non è necessario considerare le permutazioni 42! [che scellerato che sono] al più bastano le combinazioni 6.7x10^22): è follia.
Un suo pregio però lo ha; risponde alla domanda a) ovvero si arriverebbe a conoscere in modo certo quante sono le distribuzioni legali per 4 giocatori.
Chissà tra un paio d'anni mi rifaccio vivo.
Certo che ha quel pregio, ma non è l'unico sistema. Ad esempio ho ridotto il problema, non risolto ma ridotto per ora, in questo modo. Calcolo prima in quanti modi è possibile distribuirsi in un dato continente in termini di colori. Lascio perdere per un attimo gli stati. Spiego ad esempio con l'Oceania. In una partita di 4 giocatori ci sono "solo" 19 modi validi (legali) per riempire l'Oceania:
CONT(6) OC - 1: 0 0 2 2 molt. 6
CONT(6) OC - 2: 0 1 1 2 molt. 12
CONT(6) OC - 3: 0 1 2 1 molt. 12
CONT(6) OC - 4: 0 2 0 2 molt. 6
CONT(6) OC - 5: 0 2 1 1 molt. 12
CONT(6) OC - 6: 0 2 2 0 molt. 6
CONT(6) OC - 7: 1 0 1 2 molt. 12
CONT(6) OC - 8: 1 0 2 1 molt. 12
CONT(6) OC - 9: 1 1 0 2 molt. 12
CONT(6) OC - 10: 1 1 1 1 molt. 24
CONT(6) OC - 11: 1 1 2 0 molt. 12
CONT(6) OC - 12: 1 2 0 1 molt. 12
CONT(6) OC - 13: 1 2 1 0 molt. 12
CONT(6) OC - 14: 2 0 0 2 molt. 6
CONT(6) OC - 15: 2 0 1 1 molt. 12
CONT(6) OC - 16: 2 0 2 0 molt. 6
CONT(6) OC - 17: 2 1 0 1 molt. 12
CONT(6) OC - 18: 2 1 1 0 molt. 12
CONT(6) OC - 19: 2 2 0 0 molt. 6
CONT(6) OC: 19 modi
I quattro interi dopo i due punti rappresentano gli stati posseduti da ciascuno dei 4 giocatori: il primo intero si riferisce al giocatore 1, diciamo "il giallo" attenendosi alla convenzione di RD, il secondo al giocatore rosso e così via. Ad esempio il 13° modo della lista sopra
CONT(6) OC - 13: 1 2 1 0 molt. 12
rappresenta la situazione in cui il giallo ha 1 stato, il rosso 2, il verde 1 mentre al blu non è capitato nessuno stato dellOceania. Il parametro "molt." sarebbe la molteplicità di questo modo, non ho infatti specificato quali sono gli stati posseduti. Sappiamo che il giallo ha uno stato ma non quale. Sappiamo che il rosso ne ha 2 ma non quali. Insomma questo "modo" descrive in realtà 12 diverse possibilità (se le conti sono 12, contarle è facile perché bastano i coefficienti binomiali). Se guardiamo all'obiettivo finale, vale a dire il numero di possibili plance valide, ovviamente ognuna di queste diverse 12 distribuzioni conterà, sono diverse. Ma per ora dimentichiamoci un attimo della molteplicità e andiamo avanti.
.
Allora se fai questo calcolo dei "modi" per ogni continente, sempre 4 giocatori, la situazione è la seguente (evito di inserire i singoli modi nel dettaglio)
nstat 42
ngioc 4 => 10 10 11 11
CONT(1) AS: 231 modi
CONT(2) NA: 80 modi
CONT(3) EU: 40 modi
CONT(4) AF: 44 modi
CONT(5) SA: 19 modi
CONT(6) OC: 19 modi
L'Asia essendo molto grande ha molti "modi" di essere riempita, e poi a scendere fino a SudAmerica e Oceania con soli 19 modi ciascuna (ovviamente sono identici). Il passo successivo è combinare tutti questi modi. Ciascuno dei 231 modi dell'Asia andrà combinato con ciascuno di quelli del NA e così via... il totale è un numero molto grande
231*80*40*44*19*19 = 11.741.452.800
Ma è comunque maggiore di quello che serve, perché non tutti i modi sono compatibili fra loro. Esempio stupido: uno dei 231 modi dell'asia sarà uno in cui il giallo e il rosso hanno 6 territori ciascuno. Uno del NA potrebbe essere quello in cui giallo e rosso hanno 4 stati a testa e il verde l'ultimo rimasto. In questo momento sia il giallo che il rosso possiedono già 10 territori, quindi è evidente che tutti (!) i modi di EU, AF, SA, OC che comprendono un qualsiasi territorio giallo o rosso andranno esclusi (vogliamo cercare le plance valide).
Insomma questo numero grande è un limite superiore.
Che cos'è che va fatto (non più di) 11mila741miliardi di volte? Solamente () controllare che i modi dei 6 continenti diano luogo ad una plancia valida (il totale del giallo e del rosso deve essere 10 territori, verde e blu ne devono avere 11). Isolate queste combinazioni di modi validi, allora tornano in gioco le molteplicità corrispondenti a ciascun modo che andranno tutte moltiplicate.
Per ora mi sono scontrato con la lentezza del pc nel fare questo ultimo step. Però i numeri in gioco non mi sembrano così spaventosi (non si parla di 10^22!), forse si può trovare un sistema per ridurre ulteriormente. Non so quanto possa essere chiara la strada che sto seguendo, però magari dà uno spunto.
Provando ad utilizzare un metodo "forza bruta" e con qualche espediente di programmazione ecco una serie di loop nidificati che permettono, con l'uso di test nei "punti giusti", di abbattere il numero di calcoli.codice:for (oc1 = 0; oc1 <= ns2_oc; ++oc1) { for (oc2 = 0; oc2 <= ns2_oc; ++oc2) { for (oc3 = 0; oc3 <= ns2_oc; ++oc3) { for (oc4 = 0; oc4 <= ns2_oc; ++oc4) { if (oc1 + oc2 + oc3 + oc4 == ns_oc) { for (sa1 = 0; sa1 <= ns2_sa; ++sa1) { for (sa2 = 0; sa2 <= ns2_sa; ++sa2) { for (sa3 = 0; sa3 <= ns2_sa; ++sa3) { for (sa4 = 0; sa4 <= ns2_sa; ++sa4) { if (sa1 + sa2 + sa3 + sa4 == ns_sa) { for (af1 = 0; af1 <= ns2_af; ++af1) { for (af2 = 0; af2 <= ns2_af; ++af2) { for (af3 = 0; af3 <= ns2_af; ++af3) { for (af4 = 0; af4 <= ns2_af; ++af4) { if (af1 + af2 + af3 + af4 == ns_af) { for (eu1 = 0; eu1 <= ns2_eu; ++eu1) { for (eu2 = 0; eu2 <= ns2_eu; ++eu2) { for (eu3 = 0; eu3 <= ns2_eu; ++eu3) { for (eu4 = 0; eu4 <= ns2_eu; ++eu4) { if (eu1 + eu2 + eu3 + eu4 == ns_eu) { for (na1 = 0; na1 <= ns2_na; ++na1) { for (na2 = 0; na2 <= ns2_na; ++na2) { for (na3 = 0; na3 <= ns2_na; ++na3) { for (na4 = 0; na4 <= ns2_na; ++na4) { if (na1 + na2 + na3 + na4 == ns_na) { as1 = NA10 - (sa1 + af1 + eu1 + na1 + oc1); as2 = NA10 - (sa2 + af2 + eu2 + na2 + oc2); as3 = NA11 - (sa3 + af3 + eu3 + na3 + oc3); as4 = NA11 - (sa4 + af4 + eu4 + na4 + oc4); if (as1 + as2 + as3 + as4 == ns_as && as1 >= 0 && as1 <= ns2_as && as2 >= 0 && as2 <= ns2_as && as3 >= 0 && as3 <= ns2_as && as4 >= 0 && as4 <= ns2_as) { ++totx; /* sommare tenendo conto dei coefficienti binomiali ... */ } } ... }
Il totale modi (totx) il cui limite superiore era stato indicato con 11.741.452.800 risulta essere: 30646850 ( tempo di calcolo con il mio PC circa 4 secondi !!! )
Il codice mostrato è in linguaggio C per poter essere facilmente replicato e verificato.
[1] Le costanti NA10 e NA11 hanno valore 10 e 11.
[2] le variabili ns2_xx e ns_xx hanno valore intuibile dal nome stesso: la metà (o il valore intero) dei continenti.
Es:
ns2_oc = 2
ns_oc = 4
...
Le variabili con indice 1,2,3,4 sono indicative dei 4 colori.
Quelle 1 e 2 hanno 10 stati, 3 e 4 ne hanno 11.
Infine ho anche calcolato le plance legali come indicato nel commento nel codice:
TOTLEGALI 28800170543206893600000
Cioè il numero totale, a meno di errori, di plance legali iniziali del Risiko! ( tavolo da 4 ).
Ecco infine le plance con più casi, il numero a destra è la molteplicità del modo:
3222 1222 3333 1122 1111 1111 lmax 182511105638400000
2322 2122 3333 1122 1111 1111 lmax 182511105638400000
2232 2212 3333 1122 1111 1111 lmax 182511105638400000
2223 2221 3333 1122 1111 1111 lmax 182511105638400000
2232 2122 3333 1212 1111 1111 lmax 182511105638400000
2223 2122 3333 1221 1111 1111 lmax 182511105638400000
2232 1222 3333 2112 1111 1111 lmax 182511105638400000
2223 1222 3333 2121 1111 1111 lmax 182511105638400000
Il singolo modo si interpreta banalmente es:
2232 2122 3333 1212 1111 1111
indica che
in NA ci sono 2 carri del giocatore "1", 2 carri del giocatore "2", 3 carri del giocatore "3" e 2 carri del giocatore "4"
in EU ci sono 2 carri di "1" un carro di "2", 2 carri di "3" e 2 carri di "4"
in AS ...
in AF ...
in SA ...
in OC ...
Il numero a destra è il numero di occorrenze di quel modo
Trucchi di programmazione per abbattere il numero di operazioni.
[a] portare il più in alto possibile i test di ammissibilità per "tagliare" l'albero sottostante ( FONDAMENTALE ! )
[b] uso di tabella di valori pre-calcolati dei coefficienti multinomiali in modo da non perdere tempo nel ricalcolo.
Ovviamente i test si possono fare in modo ancora più intelligente ma il tempo di calcolo è già abbastanza basso, circa 4s, da non richiedere altro.
Sul nostro sito sarà possibile scaricare sia l'elenco dei modi con la molteplicità sia l'elenco delle plance (.7z).
Giorgio Silvestri - RC I TITANI RisiKo! Club - San Benedetto Del Tronto (AP)
Ciao Giorgio, interessante!!!!
Per capire meglio quello che hai scritto, una prima domanda: perché in quelle che indichi come "plance con più casi" ci sono solo quelle? Mi spiego, questo è il tuo elenco
Ecco infine le plance con più casi, il numero a destra è la molteplicità del modo:
3222 1222 3333 1122 1111 1111 lmax 182511105638400000
2322 2122 3333 1122 1111 1111 lmax 182511105638400000
2232 2212 3333 1122 1111 1111 lmax 182511105638400000
2223 2221 3333 1122 1111 1111 lmax 182511105638400000
2232 2122 3333 1212 1111 1111 lmax 182511105638400000
2223 2122 3333 1221 1111 1111 lmax 182511105638400000
2232 1222 3333 2112 1111 1111 lmax 182511105638400000
2223 1222 3333 2121 1111 1111 lmax 182511105638400000
Per quanto riguarda l'Oceania ad esempio (ultime 4 cirfre) le plance sono tutte quelle per cui c'è un giallo, un rosso, un verde e un blu (giusto per usare i colori "familiari" di RD). Nessun caso in cui uno o due giocatori sono assenti. Idem per gli altri continenti. Insomma, mancano gli "0", così come i 6 (ad esempio in Asia, dove una plancia potrebbe capitare con 6 stati di un solo colore). Forse con "plance con più casi" intendi dire quelle con molteplicità maggiore e hai omesso le altre? Se è così, ho capito. Se no, puoi spiegare meglio?
Comunque i 4 secondi mi sorprendono davvero, anche se devo ammettere che anni fa non avevo provato con un codice compilato ma solo con uno script. Ora provo anche io "rubandoti" l'approccio!