Quella che sto per scrivere è un'idea che mi è venuta sul water, a Pasqua, tra una partita di
Machiavelli e l'altra, e che ho finalmente sviluppato in questi giorni. Cercavo un modo per scrivere un programma che rimettesse a posto il tavolo da solo (ma soprattutto cercavo un meccanismo per capire in anticipo se una certa mossa era possibile o no). All'epoca non conoscevo ancora gli strumenti per risolverlo, finché non mi sono accorto che è un bell'esempio di
problema di soddisfacimento dei vincoli (CSP).
Seguendo il percorso dall'inizio alla fine, formulerò il problema prima a parole, poi usando il formalismo matematico e infine lo tradurrò in un programma.
Il modello matematico che ho scelto è quello della
programmazione lineare intera.
È sempre bene riportarsi a un modello ben noto,
anche se il problema può essere più complicato da formulare. Per due motivi molto semplici. Da una parte non ho bisogno di scrivere un risolutore da me, perché per questo tipo di problema ne esistono parecchi in circolazione, con un risparmio di tempo notevole; dall'altra parte il "prodotto finale" normalmente è molto più efficiente rispetto a un sistema costruito direttamente "su misura", essendo ben note e studiate anche le ottimizzazioni che si possono applicare. Sembra una regola di buonsenso piuttosto ovvia – e lo è – ma è molto difficile abituarsi a usarla.
Attenzione: questo post contiene una grande quantità di formule matematiche. Se non le visualizzate correttamente, è colpa delle impostazioni del vostro browser (oppure aggiornate il vostro Internet Explorer 5, perdio!). Se non riuscite a capirle, saltatele. Forse il senso del post rimane chiaro.
Prima formulazione, a parole
Il problema, che in questo caso è un sottoproblema del gioco di carte
Machiavelli, è il seguente:
dato un insieme di carte mescolate sul tavolo, ricostruire un tabellone valido secondo le regole del Machiavelli, se possibile.
Le regole che ci interessano (non tutte le regole del gioco):
- Si usano due mazzi di carte francesi senza jolly; alcune di queste saranno sul tavolo.
- Ogni carta sul tavolo deve essere coinvolta o in una scala o in un tris/poker:
- un tris/poker è un gruppo di 3/4 carte con lo stesso numero ma di seme diverso;
- una scala è una sequenza di almeno tre carte contigue dello stesso seme.
- Non ci possono essere carte spaiate (discende dalle precedenti tre).
- Regola opzionale: sono accettate anche scale continue (cioè scale che contengono la sequenza KA2)
Alcune regole che possono servirci dopo, scritte già in modo "utile":
- Un giocatore può calare delle carte aggiungendole al tavolo se, aggiunte quelle carte al tavolo, riesce a disporre le carte secondo una configurazione valida (secondo le 6 regole precedenti).
- Dopo aver calato delle carte, il giocatore può terminare il turno.
- Se non aggiunge carte al tavolo, il giocatore deve pescare una carta e cedere il turno.
Formalizzazione
Proprio qui entra in gioco l'intuizione che ho avuto sul cesso. Il tabellone può essere codificato come una matrice binaria tridimensionale 4x13x4, formata cioè da quattro tabelle sovrapposte, fatte così:
Chiamerò ognuna delle 4 tabelle "
piano". I piani pari sono per le scale, i dispari per i tris/poker. I primi due piani sono per il primo "mazzo", gli altri due per il secondo "mazzo". Ogni carta può comparire solo una volta in un "mazzo": o in un tris o in una scala (con "mazzo" non intendo il mazzo fisico, ma la coppia di tabelle).
Chiaramente, se si giocasse con un numero diverso di mazzi cambierebbe il numero di piani, che deve essere il doppio del numero dei mazzi, ma il modello sarebbe lo stesso.
In ogni casella della matrice ci sarà un 1 se la carta corrispondente è impegnata in quel piano, 0 se non lo è.
Userò anche una tabella ausiliaria, la "proiezione" dei piani, ottenuta "schiacciando verticalmente" tutti i piani. Ogni casella della proiezione conterrà la somma delle corrispondenti caselle nei 4 piani, ossia il numero di carte che compaiono sul tavolo, per ogni combinazione di numero e seme. La proiezione è l'unica informazione che abbiamo quando il tavolo è completamente scombinato e dobbiamo riordinarlo secondo le regole, pertanto sarà l'input del nostro problema.
Ora, le formule. Chiamato \(x_{i,j,k}\) il valore della matrice per la riga (seme) \(i\), la colonna (numero) \(j\) e il piano \(k\), riscrivo le regole in termini di valori della matrice.
La regola 2 diventa: ci può essere al massimo un 1 nelle caselle che appartengono alla stessa riga, stessa colonna, stesso "mazzo" (coppia di piani). In formule:$$x_{i,j,2m} + x_{i,j,2m+1} \leq 1 \quad (\forall i \in \{0..3\},\ \forall j \in \{0..12\},\ \forall m \in \{0,1\})$$dove \(m\) è il numero del mazzo, che comprende quindi i due piani \(2m\) e \(2m +1\).
La regola 3: nei piani dei tris/poker, la somma degli elementi per ogni colonna può essere solo 0, 3 o 4.
$$\sum_{i=0}^3 x_{i,j,k} = 0 \lor \sum_{i=0}^3 x_{i,j,k} \geq 3 \quad (\forall j \in \{0..12\},\ \forall k \in \{1,3\})$$Scritto così, il vincolo non può essere usato in un risolutore lineare perché contiene un operatore logico. Per rendere questo vincolo lineare, devo introdurre una famiglia di variabili ausiliarie, \(y_{j,k}\), ossia una variabile per ogni colonna dei piani dispari, che
deve valere 1 se la somma della colonna corrispondente è diversa da 0 e
può valere 0 altrimenti. Tale corrispondenza deve essere garantita da un vincolo (lineare ovviamente). Eccolo:$$y_{j,k} \geq \frac{1}{4}\sum_{i=0}^3 x_{i,j,k} \quad (\forall j \in \{0..12\},\ \forall k \in \{1,3\})$$A questo punto posso riscrivere la regola 3:$$\sum_{i=0}^3 x_{i,j,k}\geq 3y_{i,j} \quad (\forall j \in \{0..12\},\ \forall k \in \{1,3\})$$
La regola 4 è più complessa: nei piani delle scale, per ogni riga, devono valere le seguenti condizioni:
- per ogni sequenza di tre caselle consecutive, non si può presentare la sequenza 010;
- per ogni sequenza di quattro caselle consecutive, non si può presentare la sequenza 0110.
Condizioni queste che devono essere valutate considerando ogni riga della tabella estesa con degli 0 a sinistra e a destra, oppure (se si accetta la regola 6, quella delle scale continue) considerando che la riga si ripeta infinitamente.
Come prima, devo formalizzare questa regola come vincolo lineare.
Prima parte:$$(1-x_{i,j-1,k}) + x_{i,j,k} + (1-x_{i,j+1,k}) \neq 3$$ ossia $$-x_{i,j-1,k} + x_{i,j,k} -x_{i,j+1,k} \neq 1$$
Poiché tutte le \(x\) sono variabili binarie, la parte sinistra della diseguaglianza non può mai essere maggiore di 1, quindi riscrivo:$$-x_{i,j-1,k} + x_{i,j,k} -x_{i,j+1,k} \leq 0 \quad (\forall i \in \{0..3\},\ \forall j \in \{0..12\},\ \forall k \in \{0,2\})$$con la seguente sostituzione: \(x_{i,j,k}:=0\) se \(j\lt 0\) o \(j\gt 12\). Altrimenti, se si accetta la regola 6, la sostituzione è \(x_{i,j,k}:=x_{i,j\%12,k}\) dove con \(\%\) indico l'operatore di resto ("modulo").
Analogamente ottengo la formula per la seconda parte della regola:$$-x_{i,j-1,k} + x_{i,j,k} + x_{i,j+1,k} - x_{i,j+2,k} \leq 1$$ $$(\forall i \in \{0..3\},\ \forall j \in \{0..12\},\ \forall k \in \{0,2\})$$con le stesse sostituzioni.
Ora manca solo l'ultima formula, la famiglia di vincoli che lega la matrice alla proiezione (la nostra informazione di partenza): la somma "trasversale" su ogni combinazione di riga e colonna deve essere uguale alla casella analoga nella proiezione. Dette \(c_{i,j}\) le caselle della proiezione, il vincolo è$$\sum_{k=0}^3 x_{i,j,k} = c_{i,j}\quad (\forall i \in \{0..3\},\ \forall j \in \{0..12\})$$
Riepilogo
Costanti
\(c_{i,j} \in \{0..2\},\quad i \in \{0..3\},\ j \in \{0..12\}\)
Variabili
\(x_{i,j,k} \in \{0,1\}, \quad i \in \{0..3\},\ j \in \{0..12\},\ k \in \{0..3\}\)
\(y_{j,k} \in \{0,1\}, \quad j \in \{0..12\},\ k \in \{1,3\}\)
Vincoli
Regola 2:$$x_{i,j,2m} + x_{i,j,2m+1} \leq 1 \quad (\forall i \in \{0..3\},\ \forall j \in \{0..12\},\ \forall m \in \{0,1\})$$
Regola 3:$$y_{j,k} \geq \frac{1}{4}\sum_{i=0}^3 x_{i,j,k} \quad (\forall j \in \{0..12\},\ \forall k \in \{1,3\})$$ $$\sum_{i=0}^3 x_{i,j,k}\geq 3y_{i,j} \quad (\forall j \in \{0..12\},\ \forall k \in \{1,3\})$$
Regola 4: $$-x_{i,j-1,k} + x_{i,j,k} -x_{i,j+1,k} \leq 0$$ $$-x_{i,j-1,k} + x_{i,j,k} + x_{i,j+1,k} - x_{i,j+2,k} \leq 1$$ $$(\forall i \in \{0..3\},\ \forall j \in \{0..12\},\ \forall k \in \{0,2\})$$
Senza regola 6: \(x_{i,j,k}:=0\) se \(j\lt 0\) o \(j\gt 12\).
Con regola 6:
\(x_{i,j,k}:=x_{i,j\%12,k}\).
Consistenza:$$\sum_{k=0}^3 x_{i,j,k} = c_{i,j}\quad (\forall i \in \{0..3\},\ \forall j \in \{0..12\})$$
Nella prossima parte mostrerò come questa formulazione si può tradurre in un programma.
