Newsgroup: it.hobby.scacchi
Titolo: curiosità + pigrizia: quante sono le posizioni possibili?

per caso qualcheduno si è preoccupato di fare il conto di quante siano 
le posizioni possibili sulla scacchiera? intendo tutte le combinazioni 
lecite dei 32,31...2  pezzi (magari trascurando le promozioni)

 dei 32,31...2  pezzi (magari trascurando le promozioni)
Nelle prime 40 mosse è stato calcolato che sono 10 alla 115, x 25.
Ripeto, nelle prime 40 mosse...
Ciao
Valerio 

 Nelle prime 40 mosse è stato calcolato che sono 10 alla 115, x 25.
Assolutamente no: quelle sono le partite possibili. Le posizioni possibili
negli scacchi sono certamente meno di 3x10^48.
Alex

ca.10^43
vedi
http://mathworld.wolfram.com/Chess.html
"paolo beneforti"


 ha scritto nel messaggio
news:VCLJe.56831$fm.37...@news4.tin.it...

Hai una fonte? Come è stato fatto il calcolo?
CiccioSPICE

 Come è stato fatto il calcolo?
Si può rappresentare una qualsiasi posizione, con tratto e anche con pezzi
promossi, diritti d'arrocco ed eventuale enpassant, con 161 bit.
Alex

 ha scritto nel messaggio
news:FlNJe.57126$fm.37...@news4.tin.it...

Allora:
6 pezzi ->3bit
il colore dei pezzi ->1 bit
ci sono al più 32 pezzi per un totale di 128 bit.
La distanza tra i pezzi varia tra 1 e 6 -> 3bit
Il numero di interruzioni massime sulla singola riga è 4 -> 12 bit
Colore del tratto 1 bit
Possibilità di arrocco 2 bit
En passant 1 bit
Totale: 128+12+1+2+1=144 bit
Il numero max di posizioni è 2^144=2,23E43 < 2^161...dove è l'errore?
CiccioSPICE

 En passant 1 bit
Come?
Alex


Francesco

 Non si indica solo se è stata effettuata una presa e.p.?
No, che ci importa? Vogliamo sapere se è possibile effettuarla però, e dove.
Alex

 lecite dei 32,31...2  pezzi (magari trascurando le promozioni)
Temo sia molto, molto, molto complicato...
Non basta lavorare di permutazioni e cose simili, perché ci sono troppe
eccezioni (nel senso di posizioni teoricamente costruibili, ma
che non si possono realmente raggiungere in partita).
Quindi bisogna partire dalla posizione di partenza e iniziare a costruire
l'albero delle mosse... e in questo secondo metodo,
il tempo e lo spazio diventano i problemi insormontabili...
Ciao.Fabio.

 che non si possono realmente raggiungere in partita).
Questo "troppe" rispetto al totale, a quanto ammonta? Puoi dimostrare che
non è trascurabile?
Alex

 che non si possono realmente raggiungere in partita).
no, io pensavo al numero delle posizioni in totale, purché lecite; non 
solo quelle raggiungibili (un po' come nei problemi).
in pratica tutte le posizioni con tutti e 32 i pezzi, quelle con tutte 
le possibilità con 31 pezzi, quelle con 30 etc.
per avere una limitazione dall'alto del risultato, basterebbe anche 
avere un valore che non tenga conto affatto delle regole del gioco 
(comprese le posizioni non lecite, quindi).
questa stima di 10^43 non ho capito bene da dove vien fuori.
-- 
www.paolobeneforti.it
http://spazioinwind.libero.it/paolo_beneforti/perec/perec.htm

 per avere una limitazione dall'alto del risultato, basterebbe
La limitazione dall'alto te l'ho data.
Alex

 Il numero max di posizioni è 2^144=2,23E43 < 2^161...dove è l'errore?
1) non ho capito perche' 32 pezzi = 128 bit: perche' 4 bit a pezzo?
2) perche' il numero massimo di interruzioni sulla singola riga e' 4? e
soprattutto perche' tenerne conto?
3) mi sembra che consideri diversi i pezzi dello stesso tipo, non
conteggi che hai 6 pezzi (come tipo di pezzi) ma che di ogni (tipo di)
pezzo ne hai 1 (Re) 1 (Donna) 2 (Torri) 2 (Cavalli) 2(Alfieri) 8
(Pedoni)
Cosi' hai contato piu' o meno quante sono le posizioni rappresentabili
tramite la notazione FEN che potrebbero essere di piu' di quelle
possibili

 Puoi dimostrare che non è trascurabile?
No, senza prima definire matematicamente "trascurabile".
Ciao.Fabio.

 questa stima di 10^43 non ho capito bene da dove vien fuori.
Con i 32 pezzi in campo, esistono circa 4.6*10^42 modi diversi di disporre 
i pezzi sulla scacchiera (ignorando le regole degli scacchi, per cui, ad 
esempio, i 2 re possono stare vicini) e ignorando a chi sta la mossa, en-
passant e arrocchi, se non ho sbagliato i conti.
In pratica è la soluzione del problema: in quanti modi diversi posso 
disporre sulla scacchiera i 32 pezzi degli scacchi?
E' una semplice permutazione: in pratica hai i seguenti "simboli" da 
disporre in ordine:
1 re bianco;
1 re nero;
1 donna bianca;
1 donna nera;
2 alfieri bianchi;
2 alfieri neri;
2 cavalli bianchi;
2 cavalli neri;
2 torri bianche;
2 torri nere;
8 pedoni bianchi;
8 pedoni neri;
32 caselle vuote.
quindi soluzione = 64!/(8!*8!*2*2*2*2*2*2*32!), a patto che mi ricordi
la formula delle permutazioni :-).
Per passare a 31 pezzi poi, devi fare i vari casi (quale pezzo togli) e 
ricalcolare, per 30 i due pezzi che togli, ecc...
Viene comunque parecchio lungo calcolare il tutto, ma molto molto molto 
meno che non il problema delle posizioni lecite, e ancor peggio di quelle 
realmente raggiungibili in partita.
Spero di non aver scritto cazzate.
Magari chiedi un controllino su it.scienza.matematica.
Parti pure da questo post, chiedi se è tutto giusto, e se qualcuno ha 
voglia di sviluppare i conti per 31,30, ecc... pezzi.
Ciao.Fabio.

 solo quelle raggiungibili.
Ripensandoci, il calcolo delle posizioni "lecite" (nel senso che chi non ha 
la mossa non sia sotto scatto, che gli alfieri non siano su case dello 
stesso colore, che i pedoni non siano in prima o in ottava) si può 
fare "empiricamente" senza troppe complicazioni e con una buona 
approssimazione (non si trova il numero esatto insomma, ma ci si va vicino).
Sulle posizioni che possono realmente essere prodotte in partita, invece, 
continuo a pensare che sia parecchio difficile produrre una buona stima, ma 
si sa mai...  aprirò un thread su it.scienze.matematica, e vediamo cosa si 
riesce a tirar fuori.
E' una buona sfida per l'estate... 
Ciao.Fabio.

 passant e arrocchi, se non ho sbagliato i conti.
Il conto sarà giusto, ma hai ignorato le promozioni :)
Alex


optime, lo seguirò

 bhe, ci sono altre restrizioni, per restare nella liceità.
E sarebbero? Cosa mi sto dimenticando?
Se ti riferisci a cose tipo l'alfiere in giro coi pedoni b,d nella casa di 
partenza, ecco queste sono le cose che includevo in "posizioni non realmente 
raggiungibili in partita", e qui, per ora, non ho una buona idea per eliminarle 
dal conteggio.
Fabio.

 dal conteggio.
Un'idea potrebbe essere: calcoli la probabilità che un alfiere si trovi in
una delle case oltre i pedoni (direi 29/32) e la probabilità che i due
pedoni si trovino nelle case di partenza. Entrambe nel caso di pezzi/pedoni
piazzati a caso. Da queste due probabilità, ricavi la probabilità che in una
posizione casuale si verifichino entrambi gli "eventi". 1 meno quella,
moltiplicato per il nuemro di posizioni ti permette di scartare quelle
illegali (almeno dal punto di vista statistico).
Personalmente, sono invece più interessato al modo di rappresentare una 
posizione legale nel minor numero di byte/bit possibile.
Stefano

 posizione legale nel minor numero di byte/bit possibile.
161 bit...
Alex

Alex Brunetti ha scritto:

Scusa la domanda ma... è possibile sapere come fai? O è copyright by 
Brunetti? :)
Nel caso fosse copyright... almeno puoi dirmi se sono 161 a prescindere 
dal numero dei pezzi in gioco? (ovvero, una posizione di due re soli in 
mezzo alla scacchiera sono 161 bit come una stringa di tutti i 32 pezzi 
in gioco?)
Io, con un metodo a lunghezza variabile a seconda dei pezzi in gioco 
vado dai 74 ai 164 bit (74 con solo i due re e 164 con tutti i pezzi in 
gioco, ovviamente applicando sempre lo stesso algoritmo altrimenti i due 
re li puoi liquidare con 12 bit :) ).
A questi però devo attaccare gli eventuali bit di arrocco e prese e.p... 
vista l'ora non so quanto pesino e non ho voglia di pensarci... :)
Ciao
-- 
nobody
http://k2c.sourceforge.net
"what I make is what I am, I can't live forever"

 Brunetti? :)
No, è il sistema classico con la codifica di Huffman. Visto il numero di 74,
direi che è lo stesso metodo che usi tu, e immagino che arrivi a 164 per
comprendere quelle posizioni in cui un colore promuove due volte avendo
effettuato una sola cattura (e relative situazioni multiple), che io
trascuro perché a) di interesse pratico nullo, e b) perché sono talmente in
misura microscopica che si potrebbero rappresentare sfruttando qualcuna di
quelle illegali. Per quanto riguarda il diritto d'arrocco si usa un trucco:
al posto di una torre arroccabile si mette un pedone, senza aggravio di bit.
Il 161o bit serve per il tratto. Per la possibilità dell'enpassant c'è un
altro trucco, che però mi sono dimenticato (ma con Google si trova).
Alex

 illegali (almeno dal punto di vista statistico).
Ricordo che esiste anche la probabilità che l'alfiere sia stato
"generato" da una promozione.
-- 
Rossano Basile
http://web.tiscali.it/basilero/

 E sarebbero? Cosa mi sto dimenticando?
mah, pensavo solo a tutte le posizioni con entrambi i re sotto scacco 
e/o un re sotto scacco doppio (non di scoperta).
-- 
www.paolobeneforti.it
http://spazioinwind.libero.it/paolo_beneforti/perec/perec.htm

 ha scritto nel messaggio 
news:N19Ke.60413$fm.39...@news4.tin.it...

Lo so... ma è stato dimostrato che è il minimo?
Stefano 

 "generato" da una promozione.
Sì, ma se i pedoni sono al loro posto, non è possibile che ci sia anche 
l'alfiere, anche se derivato da promozione.
Stefano

 Lo so... ma č stato dimostrato che č il minimo?
No. Il minimo lo puoi stabilire se conosci il numero esatto delle posizioni
legali :)
Dovrebbe essere comunque il piů pratico: lo gestisci con poche righe di
programma.
Alex

 -- 
Aggiungerei anche le strutture pedonali a prima vista lecite ma in realtà
impossibili: ad es, doppiatura dei pedoni bianchi in f2 e f3 dopo una cattura
g2xf3 con il nero a cui manca solo l'alfiere camposcuro... 
lordste
-----------------------------------------
Messaggio inviato con Excite Newsgroup.
http://www.excite.it/newsgroup

 lordste
Queste sono appunto le cose troppo complicate... beccare tutto è improponobile.
La cosa più banale: la posizione iniziale con mossa al nero non è possibile.
Se però il pedone d è stato spinto in d3 o d4 allora sì. Se però ci sono fuori 
due pedoni di una casella ciascuno, allora no (il tutto se ho ragionato giusto).
E siamo ancora nella cose assolutamente banali.
Ciao.Fabio.


 due pedoni di una casella ciascuno, allora no (il tutto se ho ragionato
giusto).
Dipende dai pedoni: se sono entrambi di Torre hai ragione, altrimenti no.
Alex

 wrote:

Se *tutti* i pedoni sono al loro posto, io avevo capito si parlasse solo
dei pedoni "b" e "d" per l'alfiere di donna o "e" e "g" per quello di
re.


 No, è il sistema classico con la codifica di Huffman. Visto il numero di 74,
Ah, ok ... allora siamo allineati :)
Sebbene anche il mio 164 veniva fuori senza considerare le posizioni in 
cui in colore promuove due volte avendo effettuato una sola cattura... 
era probabilmente un errore di calcolo con l'albero di Huffman di ieri 
notte :)
Ciao e grazie.


 disporre sulla scacchiera i 32 pezzi degli scacchi?
Se invece si considera che gli alfiere devono stare su colori diversi, e si 
considerano solo le strutture pedonali realmente raggiungibili in partita, si 
scende a un ordine di 10^32...
insomma una differenza decisamente ragguardevole (10 ordini di grandezza!).
Fabio.

 re.
...
Infatti, è sufficiente che i due pedoni che ostruiscono il passaggio 
dell'alfiere siano al loro posto, perché sia impossibile avere l'alfiere 
proprio lì. Questo anche se l'alfiere deriva da promozione (i pedoni non 
possono tornare indietro, quindi come ha fatto a finire nella casa 
iniziale???). Ovviamente parlo di pedoni dello stesso colore dell'alfiere.
In queste posizioni, l'alfiere è un "fantasma", perché non può esistere:
8/pppppppp/8/8/2B5/8/4P1P1/8 w - - 0 1
8/8/5P2/8/2BP3P/2P5/PP2P1P1/8 w - - 0 1
Mentre in questa, apparentemente non potrebbe esistere, perché il pedone 
promosso non può avere catturato alcun pezzo... ma invece la posizione è 
legale perché...
rnbqkbnr/p1p1p1p1/8/8/4B3/8/4P1P1/4K3 w kq - 0 1
Stefano 

 scende a un ordine di 10^32...
Hai una dimostrazione?
Alex

 legale perché...
E' un quiz, vuoi la risposta?
Alex

 
Spiego il conto (x Alex, rispondo qui x "problemi tecnici").
Dovrebbe essere giusto (credo).
Allora i pedoni devono stare sulle loro colonne e non "scavalcarsi" (non ci 
sono state prese).
Quindi per ogni colonna ho 15 possibili disposizioni dei pedoni.
15^8 e ho tutte le configurazioni pedonali lecite.
Adesso piazzo gli alfieri. Prendo il caso che permette più combinazioni, cioè 
quello con 8 pedoni sul bianco e 8 sul nero (stimo in eccesso).
Saltano fuori 24*24*23*23 possibiltà.
Quindi piazzo il resto dei pezzi 44*43*42*41*40....*33 e divido per 16 perché 
ho 2 torri e 2 cavalli uguali per colore.
Questa è di nuovo una stima in eccesso delle posizioni possibili con 32 pezzi 
sulla scacchiera... ma abbiamo tagliato un bel po' di posizioni non 
raggiungibili... quante ne restano ancora da abbattere? Boh...
Fabio.

 sono state prese).
Ah, per la sola situazione di 32 pezzi, OK.
Alex

 [...]
Mi sono spiegato male.
Ciò che intendevo dire è che non mi sembra "irraggiungibile" una
posizione con (ad esempio) i due pedoni bianchi nelle case b2 e d2 e
l'alfiere in campo scuro del bianco non nella casa c1, dato che quello
"originale" potrebbe essere semplicemente stato catturato in precedenza
e quello che si trova sulla scacchiera potrebbe essere stato il frutto
di una promozione.


 molto lunga :-).
Un sito: 
http://www.chessbox.de/Compu/schachzahl1b_e.html
Alex

 ha scritto nel messaggio 
news:rSGKe.64672$fm.42...@news4.tin.it...

Sì, ma è talmente semplice che avresti fatto prima a scriverla che a 
chiedermi se era un quiz ;)))
A dir la verità, quando ho pensato a questa posizione mi sono detto "ecco, 
qui l'alfiere non può esistere". Poi l'ho riportata sulla scacchiera e mi 
sono accorto dell'errore. Coem quizzetto è facile, ma anche simpatico.
Stefano 

 sono accorto dell'errore. Coem quizzetto è facile, ma anche simpatico.
Allora ti potrebbe piacere questo mio antico problema, un po' meno facile ma
sempre riguardante gli alfieri che escono o non escono: il Nero muove e
matta in una mossa
8/1p1p4/8/8/pPk1r1q1/P2n1B1B/K1p1B1B1/b1rB1B1B b
Alex

 8/1p1p4/8/8/pPk1r1q1/P2n1B1B/K1p1B1B1/b1rB1B1B b
Sicuramente c'è di mezzo l'analisi retrograda, per dimostrare che un pezzo o 
è in più o è stato spostato (o qualcosa di simile). Il bianco deve aver 
promosso almeno 6 pedoni ad alfiere, sulle case bianche. Il pedone b2 
bianco, deve aver effettuato due catture, per scavalcare il pedone c7 (x2). 
Il pedone d2 ne deve avere effettuata una (x3), idem per f2 ed h2 (x5). Sono 
quindi a 5 catture necessarie. L'alfiere in c8 deve essere stato preso da un 
pezzo, non da un pedone. Il pedone c ha preso quindi 2 pezzi o un pezzo ed 
un pedone. Insomma... non ho tempo per continuare, ma si dovrebbe arrivare a 
dimostrare che il pedone nero ora in c7 è in realtà un alfiere promosso. Il 
nero gioca Ab3#.
Almeno ad occhio e croce ;))))
Stefano

 Almeno ad occhio e croce ;))))
Certo che il matto è ab3 (non A ovviamente), ma devi dimostrare che puoi
catturare ab3 :)
Alex

 nero gioca Ab3#.
Ho capito, intendi c2: no, in c2 c'è un pedone, non un Alfiere promosso.
Alex

Almeno ad occhio e croce ;))))
Non credo che ci siano "trucchi". Il matto e' la presa en
passant e perche' l'ultima mossa del bianco deve essere
stata b2-b4 (non ci sono alternative?).
Pero' c'e' il problema di dimostrare che questa e' una
posizione raggiungibile, e la cosa non e' banalissima
(almeno per me).
Andrea

 (almeno per me).
La posizione è legale, non lo deve dimostrare il solutore (al massimo si può
dimostrare che non è legale - non questa - per confutare ("to cook") il
problema.)
Alex

 
Bhè, che l'ultima sia stata b2b4 è ovvio... non ce ne sono altre 
disponibili visto che tutta la cricca di alfieri bianchi è bloccata, il 
pedone in A3 idem e il re bianco non poteva essere ne in b3 (il re nero 
non avrebbe potuto avvicinarsi)ne in b2 (la casa è minacciata dal 
cavallo in d3 e dall'alfiere in a1) e tantomeno in b1 (anche quì ci sono 
la torre ed il pedone a minacciare questa casa).
Io personamente, però, non ho visto neanche lontanamente la possibilità 
della presa en passant... credo che avrei potuto perdere tutta la vita a 
cercarla e non l'avrei mai trovata...
Ciao


 Bhè, che l'ultima sia stata b2b4 è ovvio...
Non è ovvio, va dimostrato. Come ho detto, c'è un'alternativa.
Alex

l'ultima mossa è stata b2b4.
E' vero... non avevo considerato la cattura.
Io avevo provato a creare quella posizione partendo
dalla posizione base ed effettivamente e' difficile
perche' il bianco deve mangiare un sacco di roba
per promuovere lo squadrone di alfieri campo chiaro.
Credo che la chiave sia dimostrare che il bianco
non puo' aver catturato nulla perche' al nero altrimenti
non sarebbe bastato il materiale per permettere i
cambi di colonna necessari a per le 6 promozioni
ad alfiere fatte dal bianco.
Da qui a dimostrarlo pero' ce ne passa...
Andrea

Alex Brunetti ha scritto:

Perdonami ma non vedo alcuna alternativa. L'ultima mossa del bianco è 
stata b2b4 in quanto tutte le altre mosse non sono possibili (le 
motivazioni sono quelle del post di prima). Oltre alle mosse scartate in 
precedenza vi è da scartare (per ovvi motivi) anche b3b4.
Probabilmente sono io che non capisco cosa intendi dire quando dici 
"dimostrare". Perchè non ci fai sapere l'alternativa? Tanto quelli che 
possono rispondere correttamente sono tutti in vacanza, quì sono rimasti 
solo Brunetti, i vari professori di matematica che contano il grano, e 
il super niubbo di turno (cioè io). :)


 Perchè non ci fai sapere l'alternativa?
Ma è una normalissima mossa! Mi rifiuto di dare questo aiuto, è troppo
semplice, se guardi bene la vedi :)
Alex

Alex Brunetti ha scritto:

Forse cxb4? Però la posizione non si può proporre in quanto c'è il 
pedone nero in c2 che non avrebbe potuto essere lì (se il bianco era in 
c3, il nero poteva arrivare in c2 solo tramite cattura ma il re bianco 
in a2 dimostra che non è possibile).
Ma bxa3? Perchè non potrebbe essere l'ultima? (c'entrerà mica il pedone 
in b7?)
P.S. Spero alludessi a quest'ultima altrimenti vado su 
it.hobby.qualsiasialtracosachecongliscacchisonnegato :) Ok, ok, inizio a 
prepararmi... ;)


 in b7?)
Sì, bxa3 è un'altra possibilità. Ora non ti resta che dimostrare che cxb4 o
bxa3 non possono essere state l'ultima mossa, per qualche ragione, e quindi
resta b2b4 come unica mossa possibile.
Alex

 resta b2b4 come unica mossa possibile.
lol fantastico il "non ti resta che dimostrare"... :)
Ok, ci provo. Mi risentirai su questo thread.
