BoardGame Math: Calcolo Combinatorio

pubblicato in: Scienza & Giochi | 0

Con il concorso STEM che, ieri sera, ha finalmente una data (5 luglio per la mia prova scritta),  ho deciso di spiegare, anche ai meno matematici di voi, alcune basi di calcolo combinatorio che vi aiutino ad analizzare i giochi (per lo più analogici).

Ma partiamo dalle basi…

Elementi

Quando si parla di calcolo combinatorio, si parla di avere a disposizione un certo numeri di elementi che possono essere, in base al tipo di calcolo, presi in gruppi coppie, triplette, gruppi di tre ecc.
In alcuni casi, come vedremo, l’ordine in cui questi elementi sono presi è importante e in altri no.
Quello che conta è: a cosa dovrebbero poter servire questi calcoli?
Potrebbero essere utilizzati per capire, ad esempio, quante possibili coppie o triplette di risorse avete a disposizione nel vostro gioco, oppure quanto è probabile estrarre un determinato token, o ancora quanto è possibile che determinate carte escano con un certo ordine…

Permutazioni 

Partiamo dal calcolo più semplice, tanto nel concetto quanto nella matematica: la permutazione semplice.

Permutare significa scambiare di posizione due elementi: un calcolo delle permutazioni mi permette di sapere in quante maniere sia possibile disporre in ordine un determinato set di elementi precostituiti.

Facciamo un esempio semplice: se in un gioco ci sono quattro giocatori (denominati A, B, C e D), le loro Permutazioni mi diranno quanti possibili “ordini di turni” possano esistere (o, se giocate a Dungeons & Dragons, in quanti modi questi quattro potranno essere “in ordine di iniziativa”).

General Strategies for Terra Mystica | Meeple Mountain

Per calcolare una permutazione, si prende il numero totale degli elementi e lo si moltiplica per se stesso -1, poi se stesso -2 e così via fino ad 1.

Se prendiamo il nostro ordine di turni, essendo i giocatori 4, le possibilità sono 4 x 3 x 2 x 1 = 24.
Possiamo anche divertirci a contarle tutte: sono ABCD, ABDC, ACBD, ACDB, ADBC, ADCB, BACD, BADC, BCAD, BCDA, BDAC, BDCA, CABD, CADB, CBAD, CBDA, CDAB, CDBA, DABC, DACB, DBAC, DBCA, DCAB, DCBA.

La formula generica per N elementi è dunque N x (N-1) x (N-2)… x 3 x 2 x 1, che in matematica viene detto Fattoriale di N, o “N Fattoriale”, scritto “N!”.

Permutazioni con ripetizione

Ma che succede se invece gli elementi possono essere ripetuti?
Questo potrebbe essere il caso di un set precostituito di azioni.

Immaginate che, per qualche motivo, durante il vostro turno voi possiate Muovervi (M) due volte, Attaccare (A) una volta e Raccogliere una risorsa (R).

In quanti possibili ordini potete effettuare queste precise azioni, immaginando di doverle fare sempre tutte?

Se partiamo usando le Permutazioni semplici, notiamo subito che, se consideriamo i due Movimenti come azioni distinte M1 e M2, produciamo la situazione paradossale nella quale, ad esempio “M1, M2, A, R” è diverso da “M2, M1, A, R”.
E’ dunque importante non cadere nella trappola di considerarle possibilità differenti, e questo sarà ancora più importanti negli altri tipi di calcolo combinatorio.

Per gestire una permutazione con ripetizione, bisogna dividere la Permutazione Semplice per il numero di elementi ripetuti, in fattoriale.

Per esempio, se avessimo tre movimenti (M), un attacco (A) e una raccolta (R):

  • Si calcola la permutazione semplice (3+1+1)! = 5! = 5x4x3x2x1=120
  • Si divide per il fattoriale del numero di ripetizioni dell’elemento ripetuto: i movimenti sono 3, dunque 3! = 3x2x1 = 6
  • Il totale sarà dunque 5! / 3! = 120 / 6 = 20. 

I più matematicamente smaliziati di voi però avranno anche notato che si può facilmente semplificare questo calcolo, infatti:
5! / 3! = (5 x 4 x 3 x 2 x 1) / (3 x 2 x 1) = 5 x 4 = 20

Se infine avessimo più elementi ripetuti, , bisogna dividere per il fattoriale del numero di elementi ripetuti, separato per ogni tipo di elementi.

Per esempio, se avessimo tre movimenti (M) e due attacchi (A):

  • Si calcola la permutazione semplice (3+2)! = 5! = 5x4x3x2x1=120
  • Si divide per il fattoriale del numero di ripetizioni dell’elemento ripetuto, separato per ciascun tipo: i movimenti sono 3, dunque 3! = 3x2x1 = 6, mentre gli attacchi sono due, per cui 2! = 2×1 = 2
  • Il totale sarà dunque 5! diviso 3! e ancora diviso per 2!, o anche

(5!/3!)/2! = 5!/(3! x 2!) = (5x4x3x2x1) / (3x2x1 x 2×1) = 5×4 / 2×1 = 5×2 = 10

Combinazioni

Passiamo ora a quello che è forse il tipo di calcolo combinatorio più utile per i game designer: le Combinazioni (che danno anche il nome all’intera branca).

Una Combinazione semplici di elementi di un insieme è un set non ordinato, ma di dimensione stabilita, di quei precisi elementi senza ripetizioni.

Esempi di combinazioni potrebbe essere una selezione di un certo numero di opzioni (es: oggetti) in un insieme prestabilito: per esempio, puoi prendere 3 oggetti tra spada, armatura, arco, scudo ed elmo.
Quante combinazioni esistono?

Medieval Weapons & Armor | Medieval Times Dinner & Tournament

La formula per le combinazioni non è esattamente banale.

Le combinazioni di k elementi presi in un insieme di n elementi (per esempio 3 oggetti da cui scegliere tra 5) sono:

n! / [ k! (n-k)!]

Nel nostro esempio, noi abbiamo n=5 e k=3. Il termine n-k sarà quindi uguale a 2.
Tutti e tre questi termini appaiono come fattoriali, per cui avremo:

5! / (3! x 2!) = 5 x 4 x 3 x 2 x 1 / 3 x 2 x 1 x 2 x 1 = 5 x 4 / 2 = 5 x 2 = 10

Approfondimento: combinazioni semplici e complessita’ del gioco

Le Combinazioni semplici sono utili nella mente di un designer perché danno una misura della complessità di un sistema, per esempio quello degli elementi che avete inserito in un gioco.

Se immaginiamo infatti di avere un insieme di differenti meccaniche o altro tipo di elementi, quante “interazionI” esistono tra di loro?

Immaginando ad esempio che ogni meccanica interagisca con tutte le altre “a coppie”, una misura semplice della complessità del sistema sarà il numero delle coppie di meccaniche.

Vediamo che, un gioco con tre “elementi” (qualunque cosa ciò significhi) avrà soltanto 3!/(2! x 1!) = 3 interazioni, ma uno con quattro ne avrà 6 e con sei ne avrà 15.

E’ evidente per cui come, all’aumentare degli elementi, la complessità del sistema cresca molto più rapidamente ed è per questo che una buona prassi di game design, a mio parere, è tenere relativamente basso il numero di componenti, regole ed elementi di meccanica e ragionare sulle loro reciproche interazioni.

hexagon connections by 10binary on DeviantArt

Combinazioni con ripetizione

Come per le Permutazioni, anche le Combinazioni hanno una versione con ripetizione, nella quale ogni elemento può essere preso più volte: ad esempio, in Magic le possibili combinazioni di tre mana colorati prevedono anche la possibilità di spendere due o tre mana dello stesso tipo.

Ciascuno degli elementi presi può essere uno qualunque dell’insieme di partenza (o, nell’esempio precedente, ciascuno dei tre mana può essere di uno qualunque dei 5 colori).

Le possibili combinazioni di k elementi presi da un insieme di n saranno pari a:

(n + k – 1)! / [ k! (n-1)! ]

Nel nostro esempio, i colori del mana sono n=5 e se ne prendono k=3.

(n + k – 1)! / [ k! (n-1)! ] = (5+3-1)! / [3! x (5-1)!] = 7! / [3! x 4!] = 7 x 6 x 5 / 3 x 2 = 8 x 7 x 5 = 35

E’ anche possibile verificarlo prendendo i cinque mana Bianco (W), Nero (N), Rosso (R), Verde (V) e Blu (B): le possibili combinazioni sono:

-Cinque con un solo colore: NNN RRR VVV BBB WWW

-Per ciascuno dei 5 colori, quattro con due di quel colore ed il terzo differente (es NNR NNW NNV NNB), per un totale di 20

-Dieci con tre colori differenti: NRV NRB NRW NVB NVW NBW RVB RVW RBW VBW

How the 'Magic: The Gathering' Color Wheel Explains Humanity | by Duncan A  Sabien | Human Parts

Per fare rapidamente conti di combinazioni come quest’ultimo c’è ovviamente un trucco, che ho usato e che potete anche voi rifare seguendo esattamente le triplette nell’ordine che ho scritto:
-Si parte con gli elementi più a sinistra (N, R, V)

-Si procede sostituendo l’elemento più a destra via via con gli altri disponibili (NRB e NRW).

-Quando non ho più possibili valori per l’elemento più a destra, si scala il secondo elemento da destra (la R in questo caso) e si continuano a fare le combinazioni possibili coi successivi (NVB, NVW) e di nuovo ogni volta che termino le possibili combinazioni.
-Arrivati a NBW, non posso più fare combinazioni con la N. Abbandono dunque l’elemento più a sinistra e comincio a fare combinazioni coi restanti (RVB e andando avanti).

Disposizioni

Arriviamo infine alle Disposizioni, che uniscono i concetti delle Combinazioni e delle Permutazioni.

In questo caso, si prende sempre un numero “k” di elementi da un insieme di “n”, tenendo conto tanto della presenza quanto dell’ordine, immaginando, inizialmente, che ciascun elemento possa essere preso una sola volta.


Questo, se vogliamo, è una visione più realistica e raffinata del possibile “set di azioni” in un turno, in cui le azioni sono scelte da un pool, oppure di un certo numero di carte estratte da un mazzo, contandone anche l’ordine.

Usando le stesse notazioni precedentemente introdotte, il numero delle disposizioni di k elementi presi da un pool di n è:

n! / (n – k)!

In questo caso, prendendo come possibili azioni Attaccare (A), Muoversi (M), Raccogliere (R) e Costruire (C), ogni giocatore può farne solo 2, differenti, e conta l’ordine, il totale delle possibilità sarà:

n! / (n-k)! = 4! / 2! = 4 x 3 x 2 x 1 / 2 x 1 = 12

Anche stavolta il pool è abbastanza piccolo da permettere facilmente di calcolarle tutte: usando il trucchetto già proposto abbiamo AM, AR, AC, MR, MC, RC più le stesse 6 invertite di ordine.

Disposizioni con ripetizione

Finiamo con le disposizioni con ripetizione: in tal caso non solo conta l’ordine e la presenza degli elementi, ma ciascun elemento può essere presente in più copie.

In tal caso, il numero di possibili disposizioni di k elementi presi in un pool di n diventa semplicemente n elevato alla k.

Nell’esempio precedente delle quattro azioni, se le azioni possono essere effettuate più volte nello stesso turno, il totale diventa semplicemente 4 elevato alla 2, ovvero 16.

Le combinazioni sono le 12 già elencate, alle quali si aggiungono le quattro coppie di azioni uguali.

Se volete continuare a seguirmi, potete aggiungervi al canale Telegram!
Ricordatevi di seguirmi su facebook mettendo like a questa pagina e soprattutto iscrivendovi a questo gruppo per ricevere le notifiche!
Se poi vi è piaciuto l’articolo, vi invito a leggere anche i seguenti:

Entrare nel mondo del game design
-Colti & Corti: XV Games

La Scienza di Mass Effect
K2 Games: giochi da tavolo e impegno ecologico
Lucca e il GDR per l’inclusione

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *