Il problema della valutazione delle mosse per risolvere il problema degli scacchi, ovvero per giocare in modo esatto, non è un problema di algoritmo, che anzi è concettualmente molto semplice:
data una configurazione valida della scacchiera, con la mossa al giocatore A, si può generare una lista di tutte le mosse permesse, ogni mossa porta ad una nuova configurazione valida, o ad uno scacco matto, o ad una patta; per tutte le mosse che portano a configurazioni valide si ripete il procedimento (ricorsione) generando così “l’albero delle mosse”.
Alla fine si avrebbe la radice con la posizione di partenza, tutte le possibili ramificazioni, e le “foglie” sarebbero tutte costituite da “scacchi matti” o “patte”.
Si scoprirebbe allora se per il giocatore bianco è possibile vincere con certezza, o se la soluzione esatta è la patta;
oppure, cosa assai meno probabile, il nero potrebbe avere sempre delle contromosse vincenti.
Come giustamente intuisce chi ha posto la domanda, e per la fortuna di tutti quelli che giocano a scacchi, il problema è la complessità computazionale dell’algoritmo, che è di tipo esponenziale: il numero di mosse da analizzare (e da memorizzare da qualche parte) cresce esponenzialmente col numero di mosse della partita.
Questo significa che si raggiungono presto dei numeri grandi ma così grandi che non bastano tutti i computer costruiti nel mondo per analizzare tutte le mosse in un tempo ragionevole; oppure se il più potente supercomputer mai costruito si imbarcasse in questa avventura gli ci vorrebbe un tempo pari a molte volte l’età dell’universo… d’altra parte il gioco degli scacchi a quanto si dice è cominciato proprio con un aneddoto “esponenziale”: il famoso compenso che il suo inventore, il bramino Sissa, avrebbe “modestamente” chiesto al Re, un chicco di riso per la prima casella, due chicchi per la seconda, quattro per la terza e così via… fanno per la sessantaquattresima casella circa sedici miliardi di miliardi di chicchi,
tenete presente la scorciatoia: 210~1000, 260~10006=1018
Proviamo a fare qualche conto di massima:
supponiamo per semplicità che ad ogni turno ogni giocatore abbia la possibilità di fare 10 mosse, (in realtà il numero di mosse possibili dipende dalla posizione, e spesso è molto maggiore di 10; ad esempio in apertura ciascuno ha a disposizione 20 mosse: 16 di pedone e 4 di cavallo); una partita di media lunghezza di solito supera le 50 mosse,
fanno 1050 posizioni da analizzare!
Per chi non ama gli esponenziali lo scrivo per esteso: 100.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.
Deep Blue analizza un miliardo di posizioni al secondo; supponiamo che un supercomputer possa analizzare 1 milione di miliardi di mosse al secondo, cioè 1015 mosse al s;
il tempo impiegato sarebbe 1050/1015=1050-15s=1035 s , peggio del decadimento del protone!
Supponiamo allora di far girare in parallelo un miliardo di questi supercomputer;
avremmo una capacità di calcolo pari a 109·1015 = 1024 mosse al secondo,
ma ci vogliono comunque 1026 secondi, cioè sempre alcuni miliardi di volte l’età dell’universo.
Quindi possiamo essere sicuri che con le attuali tecnologie il problema degli scacchi rimarrà insoluto.
Una possibilità futura potrebbe risiedere nel calcolo quantistico, che si dovrebbe prestare bene a questo tipo di problemi.
Gli attuali programmi per computer invece, per cavarsela analizzano solo alcuni rami dell’albero, quelli più appetibili, e solo fino ad un certo livello di profondità; per scegliere il ramo migliore utilizzano un punteggio legato alla posizione e alla quantità di materiale (i pezzi).
Gli esseri umani giocano in modo ancora diverso: i rami analizzati sono molti meno di quelli presi in considerazione da un computer, ma il giocatore umano si basa su un piano strategico, che magari si realizzerà in un numero di mosse superiore alla visibilità del computer.
Link:
Potete trovare quasi tutto sugli scacchi su questo splendido sito:
in particolare potete trovare le partite Deep Blue – Kasparov