Il concetto di complessità deriva dal mondo dell'informatica e in particolare della "ricerca operativa".
Dato un problema, si definisce complessità il numero di operazioni che bisogna eseguire per risolverlo.
Per esempio, se io ho un insieme di n numeri in ordine sparso, quante operazioni devo compiere per verificare se un dato numero x è presente tra quelli dati? Nel caso peggiore (ovvero il numero non è presente), dovrò eseguire n confronti tra i numeri dell'insieme e x.
Se invece i numeri di partenza sono ordinati, possiamo partire dal centro e capire se il numero x che cerchiamo si trova nella prima o nella seconda metà dell'elenco. Capito in quale metà si trova, ripetiamo il procedimento fino a individuarlo. Il numero di confronti necessari è inferiore, per l'esattezza è al massimo log2n.
Analogamente, la complessità dell'Othello è data dal numero di operazioni necessarie per trovare la partita perfetta, quella che rappresenta il finale perfetto calcolato dalla prima mossa.
All'inizio di questo capitolo abbiamo visto come si calcola il finale perfetto a partire da una posizione. A questo punto facciamo queste osservazioni:
Generalizzando, alla n-esima mossa ci sono 60 - n caselle vuote (non 64 - n perché si parte con 4 caselle già occupate) e quindi 60 - n possibili mosse. Ripetendo a ritroso fino alla prima mossa questo ragionamento abbiamo che il numero totale di sequenze possibili è dato da:
60 ⋅ 59 ⋅ 58 ⋅ ... ⋅ 4 ⋅ 3 ⋅ 2 ⋅ 1
Questa catene di moltiplicazioni è "sintetizzabile" in:
60!
dove il punto esclativo "!" indica l'operazione di fattoriale. Quindi il numero di sequenze possibili è "60 fattoriale".
Confessa che muori dalla voglia di sapere quanto fa 60!... Ebbene:
60! ≃ 8,321 ⋅ 1081
come dire, un 8 seguito da 81 zeri!!!
Immagina ora di avere un calcolatore in grado di calcolare 1000 miliardi di nodi dell'albero delle mosse in un secondo. Per costruire tutto l'albero ci impiegherà:
8,321 ⋅ 1081 nodi : 1012 nodi/secondo = 8,321 ⋅ 1069 secondi = 2,639 ⋅ 1062 anni
Decisamente troppo tempo!
In effetti questa è la logica del fattoriale: se, per esempio, per calcolare l'albero con 15 caselle libere ci metti 1 secondo, per calcolare l'albero con 16 caselle libere ci metterai 16 secondi: per ciascuna mossa possibile arriverai a un albero da 15 caselle che avrà bisogno di 1 secondo per essere percorso. Quindi con 17 caselle libere ci metterai 272 secondi (4 minuti e mezzo), con 18 caselle libere ci metterai 4896 secondi (1 ora e 20 minuti), eccetera eccetera eccetera...
Come ti sarà molto facile comprendere, la tecnica sopra utilizzata sbaglia in eccesso e di molto. Alla prima mossa, quando ci sono 60 caselle libere, abbiamo conteggiato 60 mosse possibili. In verità sappiamo benissimo che sono solo 4, e per di più simmetriche, quindi potremmo contarle come una sola. Più generalmente è assai difficile che alla n-esima mossa ci siano 60 - n mosse giocabili.
C'è inoltre un secondo difetto, più sottile. Se potessimo calcolare tutte le mosse, troveremmo spesso posizioni uguali in nodi diversi dell'albero. In quel caso ci sarà sufficiente calcolare le rimanenti mosse una sola volta.
Un conteggio diverso può nascere allora da questa osservazione: se costruiremo l'albero delle mosse troveremo sicuramente tutte le posizioni ottenibili.
Proviamo allora a contare le posizioni possibili.
Ciascuna casella può trovarsi in tre possibili stati:
In un'ipotetica tavola di due caselle avremo 9 posizioni possibili: per ciascuno degli stati possibili della prima (che sono tre), la seconda ha tre stati possibili. 3 ⋅ 3 = 9.
In un'ipotetica scacchiera di tre caselle, per ciascuno degli stati possibili della prima (che sono sempre tre), le altre due avrebbero 9 stati possibili, per un totale di 3 ⋅ 9 = 27.
Generalizziamo per una scacchiera di 64 caselle raggiungiamo il numero di:
364
stati possibili.
Ok, ok, ti dico subito quanto fa:
364 = 3,434 ⋅ 1030
Molti meno rispetto a quelli precedenti... ma pur sempre tantissimi!
Anche questo conteggio è sovrabbondante: per esempio stiamo conteggiando una gran quantità di posizioni impossibili, o perché le quattro caselle centrali sono vuote o perché le pedine sono in gruppetti staccati tra loro. Comunque sia siamo riusciti a ottenere una stima un po' più precisa rispetto all'esagerato 60!
Rifacciamo un po' i conti... Dunque un calcolatore che analizza 1000 miliardi di posizioni in un secondo, per calcolare tutte le posizioni possibili impiegherebbe:
3,434 ⋅ 1030 nodi : 1012 nodi/secondo = 3,434 ⋅ 1018 secondi = 1,089 ⋅ 1011 anni
Molto meglio... :-) Ma ancora troppo!!!
Per ora non mi pare il caso di tentare calcoli ancora più precisi. Tanto credo che il numero di posizioni possibili sia comunque enorme!
E con una scacchiera più piccola? Beh, le cose cambiano molto!
Una variante simpatica dell'Othello é quella di utilizzare una tavola 6×6.
Con il nostro calcolo sovrabbondante il numero di mosse possibili è:
336 = 150.094.635.296.999.121
che un (più reale) calcolatore che calcola 1 milione di nodi al secondo analizza in:
150.094.635 secondi = 4,8 anni
Beh, dell'Othello 6×6 è stata calcolata la partita perfetta (in meno di 4 anni, ovviamente) e si è scoperto che il bianco vince per 20 a 16. Se invece si mettono le quattro pedine iniziali parallele il bianco vince per 19 a 17.
Anno 2052, un super-mega calcolatore quantistico trova la partita perfetta dell'Othello... Fine del gioco?
No, sicuramente no!!! Anche se tutti memorizzassero la partita perfetta, non appena uno cambia mossa (anche alla seconda), va rifatto il calcolo per trovare il finale perfetto... E non è umanamente possibile memorizzare tutti i finali perfetti di tutte le posizioni.
Alcuni giochi più "semplici" (nel senso che hanno una complessità inferiore) dell'Othello sono già stati risolti, come la dama e alcune versioni più famose del mancala, eppure sono tuttora giocati!!!
Non è stato risolto l'Othello. Non è stato risolto il gioco degli scacchi. E non è ancora stato risolto il Go, che, tra i giochi che conosco, è sicuramente quello con complessità più elevata, pari a 3(19 ⋅ 19).
Ma i computer sono ormai imbattibili in tutti questi giochi. E di questo parleremo in un apposito capitolo.