Newsgroup: it.hobby.scacchi
Titolo: Numero di mosse possibili in una partita a scacchi

Qualche tempo fa e' stata postata nel NG la richiesta di questa
citazione, di cui al momento non ricordavo la fonte... Stamattina
mi e' capitata sott'occhio e la riporto di seguito:
"Le combinazioni possibili e giocabili [in una partita di scacchi - NdR]
sono, secondo studi fatti presso L'Artificial Intelligence Laboratory
dell'Universita' di Stanford negli USA 10[43], cioe' una cifra con 43
zeri. Di simili numeri mostruosi non e' possibile rendersi conto nemmeno con
paragoni assurdi. Ma proviamo. Supponete che tutte le stelle della Via Lattea,
che sono 100 miliardi, siano abitate come la Terra con 4 miliardi di abitanti
[Ndr: Il libro e' del 1982] ciascuna. Date ad ogni abitante di questo universo
una scacchiera elettronica capace di fare 10 mosse in ogni secondo e impegnateli
a giocare giorno e notte senza un istante di riposo. Tutti assieme questi
giocatori elettronizzati impiegherebbero 1000 miliardi di anni per eseguire le
10[43] mosse. Tenete conto che l'esistenza di questo nostro universo ha soltanto
(!) circa 15 miliardi di anni. E le scacchiere elettroniche non le abbiamo avute
per tutto questo tempo."
(Oscar F. Ghedina, Il gioco degli scacchi interamente visualizzato, Hoepli,
Milano, 1982, p. VI).
Saluti
Ivo

 Milano, 1982, p. VI).
well done IVO
 .. proprio una bella citazione.
la computabilita' del problema scacchi mi ha sempre affascinato!
Una riflessione: secondo il tizio da te citato la complessita' del problema
raggiungertebbe dei numeri cosi' grandi che non sembrerebbe un gioco che
possa essere esaurito.
Sfortunatamente non e' proprio cosi' semplice e io ho la senzazione che con
un po' di euristica e molto lavoro qualcuno potrebbe provare ad attaccarlo
dal punto di vista matematico.
AD ESEMPIO il passo citato da' per scontato che il bianco e il nero provino
tutte le mosse ...
ma quanta parte di queste mosse sono giocabili e degne di considerazione?
ad esempio che senso ha analizzare posizoni con una parte in netto
vantaggio?
di quanto si ridurrebbe il prolema in questo caso?
io credo di molto ... tanto e' vero che non e' raro che 2 GM al 20esimo
tratto si ritrovino in una posizione gia' nota pur magari provenendo da una
strada nuova ... questo perche' in realta' leposizioni teoricamente
possibili nelle prime 20 mosse sono per lo piu' assurde ... e quelle
"giocabili" saranno al massimo 1 su un milione di quelle possibili.
CON QUESTO NON VOGLIO DIRE che gli scacchi SARANNO RISOLTI MATEMATICAMENTE,
ma solo che il famoso numero di 43 cifre NON E' UNA RAGIONE SUFFICIENTE per
ESCUDERLO!!!
ciao
gianluigi
PS.su questo argomento mi piacerebbe di sapere l'opinione degli informatici
e i matematici di IHS.
ad esempio guido
Guido ci sei?
riciao

e i matematici di IHS.
Azzardo una considerazione: matematici ed informatici dovranno
inevitabilmente fare riferimento ad un input tecnico scacchistico.
Se devono chiedere al Capablanca degli anni '30 piuttosto che a Nigel
Short un repertorio di posizioni realmente possibili otterranno
risposte molto diverse.
Anche se il presente che stiamo vivendo sa molto di fine della storia
siamo sicuri che tra 20 anni (o due) la percezione di cosa e' davvero
giocabile e cosa no non sara' molto diversa?

 Ivo

 wrote in message
vUZOOMd85zPck6...@4ax.com...

Giorgio non ti basare su quello che ho detto sulle posizioni giocabili ...
era solo il tentativo di fare un controesempio ...
Il concetto che malamente cercavo di esprimere e' che ho la senzazione che
gli scacchi potrebbero presto avvicinarsi ad una situazione tipo DAMA dove
se non tirano a sorte l'apertura ad alto livello le partite finiscono tutte
in pareggio perche' il gioco  ha un livello di complessita'
(matematicamente parlando) piu' basso degli scacchi.
Infatti i software damistici sono da lungo tempo (diciamo una 15cina di
anni) a livello del campione del mondo se non sopra.
beh gli scacchi sono un osso piu' duro da rodere ... ma non e' detto che non
lo saranno mai.
ciao
gianluigi

 ;=)
ciao
gianluigi

lo saranno mai.
Che i programmi giochino molto presto meglio dei migliori umani e'
altamente probabile, per quanto mi riguarda lo considero gia' un fatto
acquisito.
Che siano in grado di dare risposte tali da condizionare il gioco
degli umani mi sembra molto meno probabile.
Quello che dici nella dama mi risulta essere accaduto prima
dell'avvento dei programmi, ed e' un fatto indipendente da
quest'ultimo.
In materia di aperture i programmi sono al momento impotenti quanto se
non piu' che nei finali con piu' di x pezzi, puoi usarli giusto per
vedere se nelle tue analisi ci sono sviste immediate.

 stati già visitati.
    Questa constatazione è interessante... peccato che per "risolvere" il
gioco servirebbero delle hash-table mostruosamente gigantesche. Io credo che
gli scacchi siano un sistema sufficientemente "caotico" per rendere
necessaria una ricerca esaustiva, per poterlo risolvere. Qualsiasi algoritmo
non esaustivo potrà dare solo risposte approssimate... sempre che qualcuno
non scopra qualche "formula magica", come l'algoritmo divino del cubo di
Rubik (che non mi pare sia mai stato trovato... ammesso ceh si chiamasse
così). Questo ci mette al riparo non tanto dal predominio (inevitabile) dei
programmi sugli umani ma dall'eventualità che esista un giorno un programma
imbattibile da tutti, compresi gli altri programmi. Se un giorno gli
scacchisti potrebbero restare disoccupati, così non sarà per i programmatori
:-)))))
    Aumentare le complessità del gioco potrà servire solo a renderlo troppo
difficile per poterci giocare. Portare la media delle mosse da 36 a 50,
significherebbe aumentare di sole 20000 volte la complessità (su 20
livelli). Dopo meno di un secolo ci si ritroverebbe al punto di partenza...
    Ciao!!!



Gianluigi Masciulli ha scritto:

<snip>

Una riflessione: secondo il tizio da te citato la
complessita' del problema

raggiungertebbe dei numeri cosi' grandi che non sembrerebbe un gioco
che

possa essere esaurito.

Sfortunatamente non e' proprio cosi' semplice e io ho la senzazione
che con

un po' di euristica e molto lavoro qualcuno potrebbe provare ad attaccarlo

dal punto di vista matematico.

AD ESEMPIO il passo citato da' per scontato che il bianco e il nero
provino

tutte le mosse ...

ma quanta parte di queste mosse sono giocabili e degne di considerazione?

ad esempio che senso ha analizzare posizoni con una parte in netto

vantaggio?

di quanto si ridurrebbe il prolema in questo caso?

io credo di molto ... tanto e' vero che non e' raro che 2 GM al 20esimo

tratto si ritrovino in una posizione gia' nota pur magari provenendo
da una

strada nuova ... questo perche' in realta' leposizioni teoricamente

possibili nelle prime 20 mosse sono per lo piu' assurde ... e quelle

"giocabili" saranno al massimo 1 su un milione di quelle possibili.

CON QUESTO NON VOGLIO DIRE che gli scacchi SARANNO RISOLTI MATEMATICAMENTE,

ma solo che il famoso numero di 43 cifre NON E' UNA RAGIONE SUFFICIENTE
per

ESCUDERLO!!!


ciao


gianluigi


PS.su questo argomento mi piacerebbe di sapere l'opinione degli informatici

e i matematici di IHS.

ad esempio guido

Guido ci sei?

riciao

Ci sono, ci sono!

Benché non sia un matematico, mi costringi a risponderti :-).


Avevo visto anch'io su Internet un valore estremamente preciso con esponente
43, probabilmente un intero anche se espresso in formato scientifico, per
il numero totale delle posizioni a scacchi. Il suo valore era stato calcolato
con librerie matematiche a precisione qualsiasi, e informo chi fosse interessato
che sotto Linux esiste la libreria gmp che fa all'uopo, se mai volesse
provarci.


Il calcolo viene eseguito generando tutte le possibili composizioni
di pezzi (cioè numero, tipo e colore dei pezzi presenti), e calcolando
il numero delle possibili posizioni per ciascuna di esse.


Nel calcolo delle composizioni il primo problema che sorge, ma che sembra
sia stato risolto, è quello delle promozioni. A parte il controllo
banale che non si possano avere più di 8 promozioni per colore,
vi sono altri vincoli relativi al fatto che per essere promossi i pedoni
devono attraversare le linee nemiche degli altri pedoni e ciò comporta
un certo numero di catture.


In un messaggio inviato al CCC (Computer Chess Club, un NG moderato
in inglese di scacchi) da un esperto di compressione dati, probabilmente
un matematico, venivano forniti tali vincoli, in un thread in cui egli
affermava che era possibile rappresentare tutte le posizioni possibili
degli scacchi su 155 bit (più un bit a mio parere per individuare
il giocatore che ha la mossa), ed esponeva il suo metodo in dettaglio.
In questo caso 2^156 varrebbe circa 10^47, ma questo è dovuto alla
presenza di codifiche in eccesso. Secondo i suoi calcoli il numero delle
possibili composizioni  (Material Content), era pari a 58.084.310.


Per ogni composizione di pezzi, il numero delle possibili disposizioni
è facilmente calcolabile se per semplicità non si tiene conto
della possibilità di arrocco e della cattura en passant.

Per il calcolo si devono prima disporre i Pedoni di entrambi i giocatori,
perché possono stare solo su 48 caselle, e successivamente gli altri
pezzi che possono stare su tutta la scacchiera. Per ogni insieme di pezzi
identici per valore e colore si deve dividere per N! se N è il numero
di tali pezzi, per tenere conto della loro intercambiabilità.


Presumo che il valore di 10^43 citato sia stato ottenuto con questo
o analogo procedimento.


Naturalmente vi sono un gran numero di posizioni non legali (scacco
al Re del partito che non ha la mossa, alcuni scacchi doppi e scacchi tripli
o più, posizioni irraggiungibili, ecc.), che non possono essere
eliminate perché il calcolo sarebbe troppo lungo, anche se lo distribuissimo
su 58.084.310 elaboratori!


Diverso discorso è invece quello di dire che le posizioni realmente
giocabili siano molto di meno. Ne sono convintissimo, però devo
dire che in questo tipo di valutazioni è facilissimo sbagliare.
Innanzitutto va distinto il concetto di posizione da quello di sequenze
di mosse (mi riferisco alla tua frase "il bianco e il nero provino tutte
le mosse ... "), le  quali ultime sono in numero estremamente maggiore
e ancora più incalcolabili. Questo è infatti il motivo per
cui si utilizzano i database dei finali, altrimenti anche un finale di
A+C sarebbe incalcolabile con rigore matematico da qualsiasi elaboratore.


Ora se anche supponiamo che di tutte le posizioni solo una su 1 miliardo
sia legale e scacchisticamente valida, da 10^43 scendiamo a 10^34. Non
siamo al punto di prima ma quasi.


Come esempio di previsione sbagliata, anche se leggermente OT perché
riguarda la dama, quando stavo sviluppando i relativi database dei finali,
mi era venuta la curiosità di partire dall'inizio partita per tabellare
tutte le possibili disposizioni delle Pedine, che come sai sono ben 24
su 32 caselle occupabili. Io pensavo che tenendo conto della cattura obbligatoria,
le disposizioni possibili fossero molto poche (qualche migliaio) e che
anche il numero di semimosse (cioè mosse del Bianco o del Nero)
senza cattura o promozione a Dama fossero a dir molto una trentina.

Con molta fatica sul mio PC da 64 Mb, ho trovato che le disposizioni
possibili delle 24 Pedine sono ben 9.697.698, compresa l'iniziale, e che
possono essere compiute ben 65 semimosse senza giungere ad una cattura
o ad una promozione! Non so se ho fatto i calcoli giusti perché
non ho mai confrontato questi dati con nessuno. Se a qualche damista interessa
gli spedisco una delle sequenze di 65 semimosse.


Naturalmente il numero 9.697.698, che rappresenta esattamente tutti
e soli i casi legali, è piccolo ma non piccolissimo rispetto al
numero delle disposizioni di 24 Pedine su 32 caselle che dovrebbe essere
pari all'incirca a   6.36 x 10^11, ma comunque avevo già
fatto un bel risparmio!


La mia idea, a cui ho dovuto ovviamente rinunciare almeno per ora, 
era quella di passare ad un'altra composizione (ad es. con 12 Pedine bianche
e 11 Nere) e ripetere il calcolo sapendo che questa composizione poteva
generarsi unicamente dalla precedente già calcolata ed in tal modo
ridurre i casi anche per questa seconda composizione, e così proseguire
in cascata per tutte le altre composizioni.


Questo sarebbe a mio avviso l'unico modo per generare effettivamente,
sia a dama che a qualsiasi altro gioco dello stesso tipo, 
tutte e sole
le situazioni legali
.


Purtroppo a scacchi questo procedimento risulta penalizzato dal fatto
che non vi è obbligo di cattura, però penso che sarebbe interessante
fare ugualmente un tentativo di calcolo delle disposizioni legali dei pezzi
nella composizione di inizio partita, anche se presuppongo che siano in
numero elevatissimo poiché le disposizioni possibili, legali ed
illegali, sono in questo caso pari a   (48! / (32!*8!))^2 / 64
= 2.1392 x 10^40.


Nota
: Per generare le sole posizioni legali si deve partire dalla
posizione iniziale e generare tutte le sequenze possibili di mosse con
qualsiasi profondità, tagliando le mosse che facciano cambiare composizione
e salvando in un vettore tutte le posizioni incontrate. Queste posizioni
devono essere mantenute ordinate in modo da poterle ricercare con algoritmo
binario (o di Fibonacci). Infatti ogni nuova posizione incontrata va aggiunta
nel vettore se non è ancora presente, mentre se viene trovata indica
che tutte le posizioni che da essa discendono sono già state precedentemente
salvate. Questo permette di avere un secondo criterio di "potatura" 
dell'albero delle mosse. Poiché certamente senza porre un limite
alla profondità, non sarà possibile arrivare alla fine del
calcolo, si può tuttavia analizzare i risultati con profondità
fissate crescenti, come avevo fatto con la dama, per la quale ho poi trovato
che la profondità sufficiente a concludere il calcolo era ovviamente
65, cioè il numero massimo di semimosse.


Sinceramente non me la sento di fare previsioni sul fatto che il computer
possa risolvere matematicamente il problema degli scacchi, anche se è
certo che prima o poi batterà  definitivamente l'uomo dato
che l'evoluzione biologica è più lenta di quella tecnologica.


Ciao

Guido