La tombola, il gioco di società della tradizione italiana forse più noto, nasconde dietro le sue cartelle una sorprendente complessità matematica.
Ho testato un approccio computazionale che sfrutta la potenza del multithreading per generare set di cartelle valide in modo efficiente.
Compito tutt'altro che facile in quanto ogni cartella deve soddisfare i seguenti requisiti:
I numeri sono compresi tra 1 e 90.
Ogni riga contiene 5 numeri e le colonne seguono la seguente logica:
Colonna 1 → numeri da 1 a 9
Colonna 2 → numeri da 10 a 19
Colonna 3 → numeri da 20 a 29
Colonna 4 → numeri da 30 a 39
Colonna 5 → numeri da 40 a 49
Colonna 6 → numeri da 50 a 59
Colonna 7 → numeri da 60 a 69
Colonna 8 → numeri da 70 a 79
Colonna 9 → numeri da 80 a 90
Non più di tre numeri consecutivi (non intervallati da caselle vuote) per riga.
Tradizionalmente, un tabellone completo è composto da 6 cartelle e ogni numero da 1 a 90 è presente in esse solo una volta.
Il codice Python, concordato con l'IA dopo l'ispezione visiva, qualche ritocco manuale e il debugging delle diverse proposte generate, implementa il calcolo parallelo per accelerare drasticamente il processo.
Caratteristiche chiave:
La Velocità Prima di Tutto
Il programma utilizza due tecniche sofisticate per ottimizzare le prestazioni. La prima è la compilazione “just-in-time” (JIT) attraverso Numba, una tecnologia che trasforma il codice Python in istruzioni macchina ottimizzate proprio come farebbe un compilatore C++.
È come avere un traduttore simultaneo che converte al volo le nostre istruzioni nel linguaggio macchina.
La seconda tecnica è il calcolo parallelo: invece di generare le cartelle una alla volta, il programma sfrutta tutti i core disponibili nella CPU, proprio come avere più operai impiegati nella realizzazione delle cartelle.
L'Arte del Bilanciamento
Creare una cartella della tombola non significa semplicemente distribuire numeri a caso. Il programma utilizza un sistema di pesi per garantire una distribuzione equilibrata dei numeri. È come se ogni numero avesse una propria probabilità di essere scelto, che viene continuamente aggiornata per mantenere l'equilibrio generale.
Questo approccio, chiamato “weighted choice”, assicura che i numeri siano distribuiti in modo uniforme tra tutte le cartelle, evitando concentrazioni anomale che renderebbero il gioco meno equo.
La Garanzia della Casualità
Il programma deve anche assicurare che le cartelle siano sufficientemente assortite pur rispettando le regole del gioco. Per questo utilizza il famoso metodo Monte Carlo: genera ripetutamente cartelle finché non ne trova una che soddisfa tutti i requisiti. È come lanciare ripetutamente un dado finché non si ottiene il risultato desiderato.
Regole e Vincoli
Le regole della tombola vengono tradotte in vincoli matematici precisi:
- Non più di tre numeri consecutivi in una riga
- Esattamente cinque numeri per riga
- Almeno un numero per colonna in ogni cartella
- Distribuzione bilanciata dei numeri tra le cartelle
- Nessun numero ripetuto nel set di 6 cartelle
Il programma verifica costantemente questi vincoli, scartando le soluzioni che non li rispettano. È come avere un arbitro molto efficiente che segue sempre la palla.
Gestione Intelligente della Memoria
Il programma utilizza strutture dati specializzate (array NumPy) per gestire efficacemente la memoria. È come avere un magazzino ben organizzato dove ogni numero ha il suo posto preciso e può essere ritrovato rapidamente quando necessario.
Performance
L'implementazione Python degli algoritmi genera in media un set di 6 cartelle ogni 20 millisecondi.
CPU vs. GPU
Il codice Python che utilizza i core CUDA può essere considerato un esempio di proof of concept che mostra come spostare parte della logica su GPU.
Purtroppo la velocità di generazione di un set consistente di cartelle, risente fortemente delle dipendenze sequenziali dell'algoritmo utilizzato per il multithreading (per esempio, l'aggiornamento del vettore globale e il controllo dei vincoli su ogni riga). Queste dipendenze rendono difficile sfruttare a pieno il parallelismo offerto dalla GPU.
N. B.: Le performance sono puramente indicative a causa della natura probabilistica di alcuni algoritmi.
Conclusioni
Se lo script non si presta bene a una parallelizzazione massiccia, anche ottimizzandolo per sfruttare la scheda grafica nei calcoli, le sue prestazioni potrebbero risultare al di sotto delle aspettative.
Se lo script non si presta bene a una parallelizzazione massiccia, anche ottimizzandolo per sfruttare la scheda grafica nei calcoli, le sue prestazioni potrebbero risultare al di sotto delle aspettative.
Hardware utilizzato:
- CPU Ryzen 5 5600H
- Scheda grafica NVIDIA RTX GeForce 3060
- RAM 32 GB DDR4