Garry Kasparov ne rimarrebbe allibito, ma non troppo. Bob Fischer direbbe "ehi, ragazzi, non ci volevano mica le formiche per capirlo". Per uno specialista informatico dell'Università di Nottingham, un tale Graham Kendall, invece sì.
Il matematico ha infatti scovato circa 500 mila varianti in più per chiudere il cosiddetto "tour del Cavallo" nel gioco degli scacchi. Ha ricorso a un algoritmo basato sul comportamento delle formiche, quando queste sono intente a procurarsi cibo nella loro colonia.
Ma andiamo per passi. Il percorso del cavallo è un problema algebrico riguardante lo spostarsi di del pezzo su una scacchiera vuota. Il cavallo è posizionato su una prima casella e, spostandosi secondo le regole degli scacchi, deve occupare ogni casa esattamente una volta.
Un percorso del cavallo si dice "chiuso" se l'ultima casa su cui si posiziona il cavallo è vicina alla casa da cui è partito, in modo tale che il cavallo, dalla posizione finale, possa compiere da capo lo stesso percorso (ad esempio, se il cavallo inizia in d8 e conclude il suo percorso in f7).
In caso contrario il percorso del cavallo è detto "aperto". Il numero esatto di possibili percorsi del cavallo aperti è ancora sconosciuto, come ricorda Popsci. Le variazioni del problema del percorso del cavallo prevedono scacchiere di dimensioni diverse dalla classica 8x8, e anche di forma rettangolare.
Su una scacchiera 8x8, ci sono esattamente 26.534.728.821.064 percorsi chiusi "diretti" (due percorsi lungo lo stesso cammino che procedono in direzioni opposte sono contati separatamente, essendo rotazioni e riflessioni). l numero dei percorsi chiusi "indiretti" è la metà di questo numero, dato che ogni percorso può essere tracciato all'inverso.
Sostanzialmente, il problema del percorso del cavallo è un esempio del più generale "problema del cammino hamiltoriano", nella teoria dei grafi. Similmente, trovare un percorso del cavallo chiuso è un esempio del "problema del ciclo hamiltoniano". Notare, tuttavia, che, a differenza del generale problema del cammino hamiltoniano, il problema del percorso del cavallo può essere risolto in tempo lineare.
Spiegato quanto era necessario, Kendall si è avvalso della comunicazione tra formiche per giungere alla profondità di uno dei misteri matematici più affascinanti degli ultimi secoli. Ha utilizzato un programma per simulare il comportamento di una popolazione di formiche. Ognuna di loro aveva il compito di trovare una variante in più al tour del cavallo.
Come? Semplice: ogni formica se ne va in giro deponendo una traccia di feromoni - una sostanza maleodorante usata per comunicare tra loro. Nell'algoritmo studiato, le formiche di maggior successo (ovvero quelle che risolvono meglio il problema), depongono più feromoni delle altre.
Ripetendo il sistema per centinaia di migliaia di volte, e quindi depositando più "feromoni" possibili sui percorsi che completano uno dei tanti percorsi del cavallo, Kendall ha scoperto circa 500.000 nuove soluzioni in più per il tour. E dire che per secoli i matematici hanno preferito rincorrere numeri e formule...
Capablanca
Leggi anche: