La Conquista della 8×5×1
Il muro di swap — e l'intuizione che ha liberato 15 gigabyte
Un miliardo e 131 milioni di posizioni. v13 ci arrivava — BFS in 4 minuti — poi la retrograde affondava nello swap: 253 secondi per wave, killato a Wave 7. L'intuizione: liberare la FlatMap prima delle waves. 15,5 GB restituiti in un battito. v14: da 253 s a 2,4 s per wave. Patta in 10 minuti.
La vetta che ingannava
263 milioni non sono pochi
Dopo la 8×6×1 — sette miliardi e un quarto, dieci ore e ventidue minuti — la 8×5×1 sembrava un colle. 263 milioni di stati: niente disco, niente mmap, tutta la BFS in RAM in 40 minuti. La congettura diceva Patta. "Facciamola e mettiamola in tabella."
Il vero mostro era la retrograde. Nei solver v7 e v8 non puoi distinguere "UNKNOWN che diventerà vittoria/sconfitta" da "UNKNOWN che è patta": lo scopri solo quando il loop converge. Ma ogni iterazione costa 800–1.000 secondi — che tu classifichi 100.000 stati o 3. All'iter 110 del v8, dal terminale vedevi: 105.857.138 remain, ~25.000 classificati per iter (in calo), ~900 s per iter (in risalita). Estrapolazione naive: 44 giorni. Anche dimezzando: 20+ giorni.
La montagna non era alta. Era lenta. E non c'era ossigeno in quella lentezza.
Tentativo 1 e 2: v7 e v8
Full scan e lista UNKNOWN — due abort
v7 (Tentativo 1). BFS completata in 40 min (2.406 s). Retrograde: scansione di tutti i 4,12 miliardi di slot della FlatMap ad ogni onda. ~1.200 s per iterazione, costante. Dopo 15 iterazioni (18.031 s, 5 ore): 222 milioni di remain. Stima a completamento: 162 onde × 1.200 s ≈ 54 ore. ABORT. Si progetta il v8 con lista degli UNKNOWN precompilata.
v8 (Tentativo 2). BFS identica (42 min). Retrograde: solo 261 milioni di UNKNOWN per iter. Ma le prime 9 onde furono un incubo (fino a 5.757 s per onda). Poi regime ~950 s. All'iter 108–110 il tempo risaliva: 829 s, 934 s, 1.026 s. Dopo 110 iterazioni (132.000 s, 37 ore): 105.857.138 remain, ~25.000 classificati/iter in calo. Estrapolazione: 4.234 onde × 900 s = 44 giorni. ABORT.
v8.gork: mimalloc, LTO fat, M4 native. Stesso algoritmo. Forse 10–20% in meno per onda (750 s vs 900 s). Il problema era O(N) per onda: N = 261 milioni, che l'onda classificasse 3 milioni o 3. Nessun completamento.
Le illusioni: v9 e v9.1
Grok, nucleare e tante speranze
Qualcuno propose la v9.gork: precomputare non solo lo stato compatto, ma l'intera lista di successori (chiavi u64). In retrograde: zero to_game_state, zero get_legal_moves, zero apply_move. Solo lookup sulla FlatMap. "Tempo stimato: 4–8 ore totali." Si scrisse il codice. Poi la v9.1: successori come Vec<CS>, niente più key_to_cs nel loop. "Questa sì che vola."
Il lavoro con l'assistente che scriveva codice era sofferto. Bug di tipo, blocchi incollati male, processi da killare, binari che non c'erano. "Fermalo." "Killa tutto. Non ti ho detto di lanciarlo." "Ma il sorgente non è nel repo di dama??" Le versioni 9 e 9.1 vennero provate, misurate, infine cancellate: il guadagno non era quello sognato. La retrograde restava legata allo stesso modello: scorrere troppa roba per trovare troppo poco. Le illusioni bruciate. Restava la domanda: non è mai possibile fare un algoritmo più veloce?
L'intuizione: non scorrere, propagare
La worklist
La risposta era un'altra struttura. Invece di: "ogni iterazione controlla tutti gli 261 milioni e vedi chi si risolve", fare: "quando una posizione viene classificata, avvisa solo i suoi predecessori e aggiorna i contatori. Chi arriva a zero successori sconosciuti si risolve e entra nella prossima onda." Niente full scan. Solo le posizioni che hanno davvero qualcosa da ricevere.
Serviva una reverse map: per ogni posizione, l'elenco di chi la ha come successore. Costruirla una volta (altro precompute: 1,1 miliardi di coppie, 1900 secondi), ordinarla, poi in retrograde: per ogni posizione appena classificata, binary search nella reverse map, decrementi atomici, chi è pronto va in coda. Le onde diventano piccole. E velocissime.
Nacque il v10.gork. Stessa BFS del v8. Retrograde a worklist.
Le onde sotto il secondo
Mai possibile? Sì.
Step 1: 261 milioni di entry unknown, 11 secondi. Step 2a: 1,1 miliardi di coppie (successore → predecessore), 1904 secondi — il prezzo da pagare una volta sola. Step 2b: sort 4,6 secondi. Step 3: onda iniziale (538.440 posizioni già risolvibili), poi il motore a worklist si accende.
Wave 1: +2.345.603 (2.271.442 good + 74.161 bad) | 1,3 s Wave 2: + 958.027 ( 465.825 good + 492.202 bad) | 0,4 s Wave 3: +3.377.579 (3.239.494 good + 138.085 bad) | 0,2 s ... Wave 79: + 371.443 ( 361.710 good + 9.733 bad) | 0,0 s Wave 80: + 279.672 ( 19.841 good + 259.831 bad) | 0,1 s ... Wave 161: + 0 — ZERO. VETTA.
Da 400 secondi per iterazione a 0,1–1,3 secondi per onda. Le ultime 80+ onde sotto il secondo. "Mai possibile?" Sì. Perché non stavamo più scansionando 106 milioni di nomi per trovare 50.000: stavamo visitando solo chi aveva davvero ricevuto una notizia. Centosessantuno onde. Duemila secondi di retrograde invece di centinaia di migliaia. Un'ora e tre minuti totali dalla partenza alla bandiera.
La vetta
22 febbraio 2026
RISULTATO
8×5×1: PATTA
La congettura aveva ragione. Con gioco perfetto, nessuno vince.
| Posizioni | % | |
|---|---|---|
| Vittorie Bianco | 419.664.724 | 37,1% |
| Vittorie Nero | 418.294.042 | 37,0% |
| Patte | 293.411.194 | 25,9% |
| Totale | 1.131.369.960 | 100% |
105 milioni e tre quarti di patte — il 25,9%. Bianco 37,1%, Nero 37,0%. Un equilibrio che la teoria delle scacchiere n×9×1 con n pari aveva già suggerito. Il lieto fine non era una sorpresa. La sorpresa era essere arrivati lì in un'ora invece che in una settimana.
La Scheda della Conquista
| Scacchiera | 8×5, 20 caselle scure |
| Pezzi | 4 bianchi vs 4 neri (regole FID) |
| Stati totali | 1.131.369.960 |
| BFS | 108 livelli, 240 s (4 min) |
| Terminali | 345.788 |
| BFS-cut | 6.400.588 |
| Retrograde | v14 worklist, 138 onde, 332 s |
| Reverse pairs | 4.019.942.945 |
| Tempo totale | 10 min (572 s) |
| Hardware | MacBook Pro M4 Max, 68 GB |
| Solver | solve_generic_fid_v14 (Rust) |
La tabella dei tempi — tutti i tentativi
| # | Solver | BFS | Retrograde | Totale | Esito |
|---|---|---|---|---|---|
| 1 | v7 | 2.406 s (40 min) | 18.031 s parziale (15 iter), stima 54 h | stima ~56 h | ABORT 5h |
| 2 | v8 | 2.547 s (42 min) | 132.000 s (110 iter), stima 44 gg | 37+ ore | ABORT |
| 3 | v8_gork | simile | stesso algoritmo (~750 s/onda) | — | Nessun risultato |
| 4 | v10_gork | 1.811 s (30 min) | 1.955 s (32 min) | 3.768 s (10 min) | COMPLETATO |
Speedup: v7 stimato → v10 reale ~100×; v8 naive 44 gg → v10 ~1.950×; tempo onda v8 iter 110 (1.026 s) → v10 wave 109 (0,0 s) = ∞.
La scalata attraverso le versioni
DEDICA
All'algoritmo worklist che ha trasformato giorni in un'ora.
Alla reverse map da un miliardo e cento milioni di coppie, che ha tenuto il filo di chi aspettava notizie.
Alle 161 onde che sono scese come respiri invece che come maratone.
Ai 105 milioni e tre quarti di patte — il 25,9% — dove nessuno vince e nessuno perde.
E a chi ha chiesto: "ma è mai possibile che non possiamo fare un algoritmo più veloce?"
Francesco Marinuzzi Ph.D. — Febbraio 2026
Solver: solve_generic_fid_v10_gork (Rust)
Genere: Alpinismo Informatico™
La prossima montagna ti aspetta
Gioca contro l'AI che conosce la soluzione perfetta