Newsgroup: it.hobby.scacchi
Titolo: Scacchi e matematica

Dando uno sguardo a un vecchio libro di Pierre Morra ("Le jeux des échecs",  Parigi,
1952), mi sono imbattuto in una pagina che si occupa di uno dei miei soggetti preferiti:
"Scacchi e matematica" (p. 177).
Dunque, sapevo gia' che dopo la prima mossa (del Bianco e del Nero) si possono verificare
400 posizioni diverse. Dopo la seconda mossa le possibilita' salgono a 72.084 e dopo solo
4 mosse si va a 318.979.564.000 posizioni possibili!
Ma che dire delle posizioni possibili dopo 10 mosse (del Bianco e del Nero)? Sono la
bellezza di:
169.518.829.100.544.000.000.000.000.000 (ma come si leggera' questo numero?).
Se si mettono due soli Re sulla scacchiera si possono ottenere fino a 3.612 posizioni
diverse!
Con 10 pezzi, invece si passa a:
34.254.125.120.000.000 (niente male!).
Con tutti i 32 pezzi le posizioni possibili sono:
7.534.686.312.361.225.327.000.000.000.000.000.000.000.000.000.000.000!!!
Una domanda per i numerosi matematici e fisici che bazzicano su IHS:
Ma come fanno i matematici a calcolare queste possibilita'??
In altre parole: Quali sono le formule in gioco?
C'e' qualcuno che potrebbe spiegarlo in termini comprensibili anche ai non-matematici??
Grazie
Ivo

 Ivo
prego, edo


In realtà non credo siano riusciti a calcolare il numero massimo di
posizioni valide possibili, almeno stando ad un lunghissimo thread che ho
lurkato su rec.games.chess.computer . Di più, nin zò!

C'e' qualcuno che potrebbe spiegarlo in termini comprensibili anche ai non-matematici??
Calcolo combinatorio?
--
Paolo Fasce

 wrote in message
392e1c71...@News.CIS.DFN.DE...

Ciao,
credo che il metodo che hanno usato sia proprio quello,che perņ ahimč non
tiene conto delle posizioni illegali  o impossibili.Bisognerebbe trovare una
formula per calcolare il numero di queste posizioni,il che credo che sia
umanamente improbabile.
Ciao,
Ajeje Brazov

 Ma come fanno i matematici a calcolare queste possibilita'??
Qui le risposte sono due:
- o barano e non lo fanno,
- o usano il calcolo combinatorio e danno un numero "sbagliato" per gli
scacchisti.
Mi spiego: dire che ci sono tot posizioni date disponendo 32 pezzi sulla
scacchiera significa poco per lo scacchista. Questo e` un numero che si puo`
calcolare con il calcolo combinatorio in maniera piuttosto semplice, un po'
piu` difficile e` calcolare le posizioni che si ottengono tenendo presente
che alcuni dei pezzi sono equivalenti: ovvero se tu scambi la posizione di
due pedoni (o due cavalli o due alfieri, o due torri) sulla scaccchiera non
cambia la posizione che stai considerando. E` possibile, sempre con il
calcolo combinatorio, correggere questo.
Pero` questo non direbbe nulla sulla legalita` delle posizioni considerate
(in quante posizioni si avrebbe un re sotto scacco o tutti e due, o una
posizione irraggiungibile da quella iniziale....).
Quindi le posizioni da "cancellare" dalla lista sarrebebro ancora di piu`.
Infine andrebbero aggiunte le posizioni derivanti da possibile promozioni,
il che e` ancora piu` difficile.
Infine ancora di meno si sa fare nel calcolo delle mosse derivanti "dalla
posizione iniziale in avanti", ovvero quando ti dicono ci sono tot mosse,
nessuno le ha esattamente calcolate oltre un certo livello (non so quale ma
gia 20 mosse e` un grandissimo numero), sono stime approssimate. E
sopprattutto di nuovo in questo calcolo 'in avanti' non si sa fare
l'eliminazione delle mosse che portanoa  posizioni equivalenti (inversioni e
ripetizioni di mosse).
L'unica cosa che si sa calcolare esattamente negli scacchi sono: l'albero
esatto delle mosse in avanti per un livello di qualche mossa (generalemnte i
programmi arrivano ad un numero inferiore a 10), e soprattutto
"all'indietro" le tabelle dei finali.
Queste sono costruite in maniera interessante: mettendo all'inizio i due re
sulla scacchiera poi aggiungendo i pezzi ad uno ad uno, una donna e si
calcola chi vince in maniera esatta da tutte le posizioni della scacchiera,
una torre (al posto della donna) e si ripete.
Un pedone (al posto della torre) e si calcola di nuovo. La vincita passa
ovviamente per la promozione, caso in cui (ovviamente) si deve prendere o
una donna o una torre per vincere. Quindi il file di "tablebase" per il
finale di KPK (re pedone contro re) viene "costruito" dopo quelli KQK e KRK,
e dipende da questi per darti le soluzioni "in avanti" mentre giochi.
E si prosegue poi aggiungendo i pezzi. Bene come sai questi file per i
finali esistono in comemrcio per i finali fino a 5 pezzi (che richiedono
alcuni GB) e sono stati prododtti (tutti o quasi) queeli per i finali a 6
pezzi da Bob Hyatt, e se no sbaglio si tratta dell'ordine di ~80-100 GB di
spazio (non sono sicuro di questo numero).
La generazione successiva (i finalli a 7 pezzi) richiedono ancora di piu`
ovviamentre e quindi aspetteremo le prossime genrazione di HD della IBM e
CPU della intel...
ciao
Franz


Sicuramente sara' stato usato il calcolo combinatorio, e facendo qualche
prova si vede che almeno in generale non e' stato utilizzato in maniera
"brutale", ma tenendo in considerazione anche alcune regole del gioco degli
scacchi.
Per esempio, nel caso dei 2 Re sulla scacchiera, il calcolo dei modi di
disporre due oggetti diversi su 64 caselle darebbe 64x63 = 4032
Il numero riferito da Ivo, invece (3612) tiene conto del fatto che i due Re
non si possono fronteggiare. In questo caso il calcolo e' 4x60 + 24x58 +
36x55 = 240 + 1392 + 1980 = 3612
(Il primo addendo si riferisce al caso in cui uno dei Re e' in una casella
d'angolo, il secondo al caso in cui il Re e' in una casella di bordo, il
terzo al caso in cui il Re e' in una delle restanti caselle.)
In questo caso, quindi, il calcolo e' stato fatto tenendo conto delle regole
degli scacchi.
Ovviamente all'aumentare del numero dei pezzi le cose si complicano.
Certo bisognerebbe conoscere i dettagli dell'articolo.
Nel caso di 10 pezzi, per esempio, il brutale calcolo combinatorio,
considerando tutti i pezzi distinguibili, darebbe
64x63x62x61x60x59x58x57x56x55 che da' un numero dell'ordine di 5x10^(17)
(Un numero di 18 cifre !)
Il numero citato da Ivo, invece, e' 34.254.125.120.000.000 cioe' ridotto di
oltre un fattore 10.
Questo significa che anche in questo caso non e' stato usato il calcolo
combinatorio brutale.
D'altro canto, per tentare di ricavare il numero preciso, bisognerebbe per
lo meno sapere quali sono i 10 pezzi coinvolti. In primo luogo perche' le
possili posizioni legali dipendono dal tipo di pezzi, e anche perche' se tra
i 10 pezzi ci sono per esempio due cavalli bianchi, le posizioni
diminuiscono gia' di un fattore 2 perche' i due cavalli sono
indistinguibili.
Sarebbe interessante vedere lo studio originale ...
Ciao,
Francesco
--
_______________________________
-- TIOs , i Tornei Italiani Online
-- Website: 
http://frengo.spedia.net/
-- Email Address: 
ti...@interfree.it
------------------------------------------------------
" La mente non è un vaso da riempire ma un legno da far ardere perché
s'infuochi il gusto della ricerca e l'amore della verità"
PLUTARCO - Operette morali -

 7 x 10^51, un numero letteralmente astronomico.
Il calcolo iper-brutale fornirebbe 64!/32! = 4.8 x 10^53 (troppo grande)
 Proviamo a considerare che i pedoni sono indistinguibili, e cosě i cavalli
e le torri.
Le configurazioni possibili si dividono di un fattore (8! x 8! x 2^4 ) = 2.6
x 10^10. e diventano quindi 1.8 x 10^43. Troppo piccolo ! Come mai ? In
realta' noi ci aspetteremmo che la nostra stima fosse per eccesso , in
quanto non abbiamo tenuto conto della legalita'. Per esempio con la formula
usata i piedoni possono stare messi come gli pare, mentre se ci sono ancora
tutti e 32 i pezzulli i pedoni DEVONO stare ognuno sulla sua brava colonna.
Secondo me l'autore ha considerato anche tutte le posizioni derivanti da 1 ,
2 , 3 fino a 16 promozioni. Effettuare il calcolo delle configurazioni in
questo caso (sempre senza tener conto della legalita') , non e'
concettualmente difficile, ma e' palloso assai.
Mi sembra ovvio pero' che anche a occhio in questo caso il numero delle
configurazioni debba essere piu' grande di 7 x 10^51, e quindi secondo me
lui in qualche modo ha considerato la legalita'. Comunque queste sono solo
supposizioni. Trattandosi dopotutto di matematica, bisognerebbe sapere
esattamente quali sono le ipotesi di partenza del tizio, e il significato
matematico dei risultati finali.
Ivus, non e' che sai darci dettagli bibliografici su sto lavoro matematico ?
Chiudo con una citazione di Toto',sulle supposizioni. utilizzata spesso dal
mio amico Marco Ledro
"Al mondo esistono le cose vere e le cose solamente supposte.
Quelle vere stanno dove stanno.......
Ma le supposte......dove le mettiamo le supposte ?"
Principe Antonio De Curtis "Totň"



Come avevo detto nel mio post iniziale, ho tratto questi dati dal vecchio libro di Pierre
Morra ("Le jeux des échecs",  Parigi, 1952), che ha un paragrafo su "Scacchi e matematica"
(p. 177).
L'autore non cita direttamente le sue fonti, ma in fondo al paragrafo fa un elenco di
matematici che si sono dedicati agli scacchi e cita: Euler, Bernouilli, Vandermonde,
il professore Duport, Lucien Poincaré e il dr. Kraitchick.
Credo che i dati siano stati tratti dai lavori di questi matematici, che a me risultano
sconosciuti, ma che senz'altro saranno noti a chi si occupa del campo!
Tra l'altro ho appena "trovato" un libro "ad hoc" in tedesco. Mi ci vorra' un po'
di tempo per averlo (devo ordinarlo in Finlandia!), ma quando mi capita sottomano
postero' sicuramente altri dati su questo aspetto degli scacchi che, devo dire, mi
affascina molto!
A proposito, se qualcuno ha dei riferimenti bibliografici sul soggetto, lo prego vivamente
di postarli. Mi riferisco a libri e articoli nelle lingue principali (inglese, francese,
tedesco, spagnolo e magari anche olandese!).
Se poi qualcuno conosce qualche misterioso sito su "Matematica e scacchi" gli sarei
gratissimissimo se lo segnalasse!!!
A presto
Ivo

 gratissimissimo se lo segnalasse!!!
Chiamato in causa anche se indirettamente dal "Mitico Frengo" per meriti
umoristici legati al compianto Principe De Curtis mi preme segnalare i
seguenti volumi ( purtroppo non in lingua originale dato il mio semplice
bilinguismo Italiano-Dialetto )
La Vendetta di Archimede
Paul Hoffmann
Bompiani 1^ ed 1990
argomenti trattati in stretta relazione agli scacchi:
algoritmo alfa-beta
approccio della ricerca selettiva
computer contro giocatori umani
configurazioni
euristiche
funzione variabile continua
intelligenza artificiale
mobilità
mosse e contromosse
posizioni quiescienti
scacchiere di n per n caselle
macchina di turing
valutazione minimax
Imperdibile per chi si interessa di IE
il Capolavoro Assoluto
il libro in grado di sostituire gli scacchi per almeno un paio di mesi nelle
attività di Voi tutti:
Godel, Escher, Bach  un'Eterna Ghirlanda Brillante
Douglas R. Hofstadter
gli Adelphi 1^ edizione 1990 ( X Ivo esiste anche in tedesco, l'ho regalato
ad una amica ordinandolo per posta a Monaco quando non esisteva Amazon nel
tentativo di far colpo su di lei per
trombarla...............................................................
.....ho fatto colpo, ......ha iniziato a leggerlo e non è più uscita di casa
per tre mesi....poi quando è uscita di casa si è fatta trombare da un altro
.....tra l'altro uno che mi pare fosse istruttore di sub o di windsurf non
ricordo.....)
Trovate centinaia di pagine, disegni, viaggi allucinanti all'interno del
mondo della logica, dei linguaggi, una cosa da non perdere.
Assolutamente !!
Chiaro che di partite senza orologi nelle vicinanze di Milano con Voi non se
ne parla....
Sarò bilingue ma sono uomo di mondo...ho fatto il militare a Cuneo !
Ciao
--
Al mondo esistono le cose vere e le cose solamente supposte.
Quelle vere stanno dove stanno.......
Ma le supposte......dove le mettiamo le supposte ?
Principe Antonio De Curtis "Totò"

 affascina molto!
Mi raccomando ! Sarebbe bello risalire ai lavori originali, anche se ho
l'impressione che non sarano proprio elementari :)
Ciao,
Francesco


--------------------------------------------
Cancella "BIT" dopo @ per inviarmi un'e-mail
Delete "BIT" after @ to send me an e-mail
--------------------------------------------