divendres, 10 d’octubre del 2014

L'abisme dels escacs (Primera part)

Aquells que diuen que entenen els escacs, no entenen res". (R. Hubner).
«Imaginem-nos una formigueta desplaçant-se en línia recta. La formigueta recorre l'equador d'una enorme esfera de ferro que te un diàmetre igual al de la Terra. Imagineu-vos el temps que trigarà a fer una volta completa i tornar al punt de partida. Després de molts milions de voltes, si tenim una bona vista podrem observar uns subtils puntets sobre la superfície de ferro: petjades que les potetes de la formigueta han anat deixant al llarg de tot l'equador. Al cap de molt, molt de temps, s'anirà creant un estret solc que amb el temps serà cada cop més i més profund. Passat un llarg temps l'esfera de ferro es partirà en dos... Doncs bé, l'eternitat encara és molt més llarga...» (Reconstrucció de la resposta d'un professor de primària quan un company de classe va preguntar: "Què és l'eternitat?").

Resulta difícil imaginar nombres molt grans. Tenim idea del valor d'un euro (un cafè), de mil euros (un sou justet), de tres-cents mil euros (un pis)... Però la diferència entre cent mil milions d'euros i un bilió d'euros ja queda fora del nostre abast racional.

Recordo que en un capítol de la sèrie Cosmos, Carl Sagan explicava que, el 1938, el matemàtic Edward Kasner volia il·lustrar la diferència entre l’infinit i un nombre grandiós. Treballava amb el nombre deu mil hexadecillons, dit d'una altra manera, deu elevat a cent, un u seguit de cent zeros. Kasner va demanar al seu nebot de nou anys que donés un nom a aquest nombre i el nen el va batejar com "Googol" (pronunciat "Gúgœl",... per si algú volia saber d'on prové el nom de Google). Carl Sagan afirma: «Un googol està tan aprop de l’infinit com l’1».

Pàgina del llibre de Sagan on parla del Googol (traduït al castellà com a "gugol")



Però anem als escacs. Els escacs són un sistema finit i limitat. A primera vista no sembla molt gran. L'escenari el forma un espai bidimensional de tant sols 64 nodes (les caselles). Els actors són setze peces blanques i setze peces negres de les quals la meitat són peons. Hi ha sis tipus de peces amb moviments diferents: rei, dama, torres, alfils, cavalls i peons. Després hi ha algunes regles particulars com les taules per repetició de jugades, l'enroc, la captura al pas o la coronació. I això és tot. No obstant, el nombre d'esdeveniments que es poden produir en aquest petit espai és monstruós, per dir-ho d'alguna manera.

Comencem amb l'escenari. El tauler. Molts haureu sentit la famosa llegenda dels grans d'arròs (o de blat) de la qual hi ha diferents versions, però totes expliquen més o menys el mateix:

«Fa mil cinc-cents anys, Kaid, un poderós rei de l'Índia, després d'haver aconseguit tot el que desitjava a la vida, va acabar en un estat crònic d'avorriment i tristesa. Kaid va demanar al savi Sassa Ben Dahir que l'ajudés, i aquest va inventar un joc per al rei: els escacs. El rei Kaid va aprendre ràpidament, es va entusiasmar i va sortir de la seva letargia. ─Com et puc recompensar? ─li va dir. ─Sa Majestat, ─respongué el savi ─tot el que demano és això: col·loquin un gra d'arròs a la primera casella del tauler, dos grans a la segona casella, quatre grans en la tercera casella i així, doblant els grans d'arròs successivament fins omplir les 64 caselles ─. Al rei Kaid li va semblar una recompensa raonable, però mai podria arribar a complir-ho».

Els grans d'arròs que va demanar Sassa al rei Kaid.                  El número de grans d'arròs per cada escac.



D'acord al que va demanar el savi Sassa, en l'última casella hi hauria d'haver 263, o sigui, 9.223.372.036.854.775.808 grans d'arròs. Sumats als de la resta del tauler serien exactament 18.446.744.073.709.551.615 grans d'arròs, que equivalen més o menys a dos mil anys de la collita actual mundial d'aquest cereal.

Bé, afegim ara al tauler les peces i les regles del joc. Preguntem-nos: quantes partides d'escacs diferents es poden arribar a jugar?...

Els vint possibles moviments de les blanques
quan comença una partida
Quan comença una partida, les blanques trien un d'entre vint moviments possibles.

A continuació les negres tenen vint opcions de resposta, qualsevol que hagi estat el moviment de les blanques. És a dir, després de la primera jugada de blanques i negres, poden sorgir 20 × 20 = 400 posicions diferents.

Dos jugades més tard, el nombre de posicions possibles creix fins a unes 20.000.

Després de les deu primeres jugades, la xifra ja és descomunal: 165.518.829.100.544.000.000.000.000 possibles posicions.

A principis del segle XVIII, el matemàtic francès Jacques Ozanam, en el seu llibre Recreations mathématiques et Phisiques afirmava: «Un mètode infal·lible de vèncer als escacs no és teòricament impossible. No obstant això, ningú, fins ara l'ha descobert, i crec que mai es descobrirà, perquè implicaria manegar un nombre massa elevat de combinacions». Aquesta opinió no seria refutada fins dos degles i mig més tard.

Claude Shannon, enginyer i matemàtic nord-americà, és recordat com «el pare de la Teoria de la informació». Entre altres coses, el 1950 va publicar un article on esbossava els algoritmes bàsics per desenvolupar un programa que jugués als escacs, malgrat que encara no existia cap ordinador prou potent per poder-lo executar. El fet és que la majoria del programari d'escacs actual, es basa en aquests principis. (Vegeu l'article original de Shannon Programming a Computer for Playing Chess, en PDF).

Shannon va fer un càlcul del nombre total de partides possibles, que formarien l'arbre complert del joc dels escacs. Va obtenir l'esgarrifosa xifra de 10120, és a dir:
10.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000. 000.000.000.000.000.000.000.000.000.000.000.000.000 partides d'escacs diferents. (Actualment s'estima que aquest nombre és "una mica" més gran: 10123 ). L'anomenat nombre de Shannon és dons, un nombre exorbitant, un nombre molt més immens que un Googol.

Claude Shannon fent un experiment








Tornem a la nostra entranyable formigueta. Imaginem que a més de perdurable i incansable, és intel·ligent i coneix les regles dels escacs. Per entretenir-se en el seu llarg camí, juga mentalment contra si mateixa una partida cada hora sense parar. Suposem que la formigueta va començar el seu viatge en el moment del Big Bang, l'inici de l'univers conegut. Actualment s'estima que l'edat de l'univers és d'uns 13.700 milions d'anys. O sigui, que des del Big Bang fins avui, la nostra formigueta porta jugades unes 1014 partides d'escacs, un nombre que fa riure al costat del nombre de Shannon. De poc ens serveix doncs, aquesta referència per fer-nos la idea de l'immensitat de possibilitats que hi ha en els escacs.

             Gra d'arròs (Oryza sativa)
Ampliem la comparació. Prenguem el gra d'arròs que el rei Kaid va posar en el primer escac del tauler.

Un gra d'arròs està compost aproximadament d'uns 1015 àtoms (zero més, zero menys). Un nombre comparable a les partides que la formigueta ja ha jugat fins avui des dels inicis de l'espai-temps. Per a un quilo d'arròs calen uns 30.000 grans. Imaginem per un moment, si podem, el nombre de grans d'arròs que cabrien dins del nostre sol. Només en la nostra galàxia ja hi ha uns dos-cents mil milions de sols, però això no és res, tenint en compte que en l'univers observable s'estima que hi ha més de cent mil milions de galàxies repletes de sols. Això representa molts i molts àtoms.

A l'esquerra, el sol. Al centre, Andròmeda, la nostra galàxia veïna (visible a ull nu si ens allunyem de les llums de la ciutat). A la dreta, una ínfima porció de l'univers: el cúmul Abell-1703 (a uns tres mil milions d'anys llum de la Terra) format per milers de galàxies.



Doncs bé, l'estimació actual del nombre total d'àtoms que hi ha a l'univers oscil·la entre 1072 i 1087. Una xifra ridícula si la comparem amb el nombre de Shannon.

De les 10120 partides d'escacs possibles de Shannon, la immensa majoria no tenen cap interès, algunes podrien ser més o menys coherents, i un percentatge molt petit seran unes bones partides. Per posar un nombre qualsevol, imaginem que per cada cent mil bilions de partides possibles, hi ha una bona partida. Això significaria que hi hauria 10103 possibles bones partides (mil gugols), la qual cosa ens indica que el potencial dels escacs és inesgotable i que, per tant, queda un nombre inimaginable de boníssimes partides que mai s'han jugat, la majoria de les quals, dit sigui de pas, mai arribaran a jugar-se, ja que la humanitat haurà desaparegut molt abans.

L'ex-campió d'escacs del món i matemàtic Max Euwe va calcular que si dotze mil escaquistes estiguessin ocupats constantment en la recerca de les millors jugades en totes les posicions imaginables i en cadascuna d'elles invertís una dècima de segon, necessitarien més d'un trilió de segles per analitzar-les totes.

El nombre de partides possibles és només un exemple de la vertiginosa profunditat d'aquest joc. S'han fet també altres càlculs interessants com el nombre de posicions que es poden obtenir en el tauler amb 2 o més peces, que donen xifres sorprenents.

Comencem per reduir al mínim el nombre de peces que pot haver-hi en un tauler: dos reis. De quantes maneres els podem col·locar dos reis? Podem posar un rei a 'a1' i l'altre a 'a3', podem posar un rei a 'd5' i l'altre a 'g3'... I així fins aconseguir el total de posicions possibles. La solució és que els dos reis poden situar-se al tauler en 3.612 posicions diferents.

·



Afegim ara un peó. Al tauler es poden donar 163.328 posicions diferents amb dos reis i un peó. Amb dos reis i tres peces més, podem obtenir uns quatre-cents milions de posicions. Amb les trenta-dos peces sobre el tauler s'ha calculat que poden produïr unes 7.534.686.312.361.225.327.000.000.000.000.000.000.000.000.000.000.000 posicions diferents.

·






Paradoxalment, el nombre de moviments que pot tenir una partida (el nombre de torns) és limitat i acotat. Més enllà del moviment 5.949 de les blanques ja no és possible fer cap més jugada dons la posició és definitivament de taules. A fi de no permetre que s'eternitzin les partides, s'ha dotat als escacs d'unes regles que limiten dràsticament el nombre de moviments que poden fer ambdós jugadors, forçant situacions de taules, en les quals la partida es considera finalitzada. Una regla diu que si es produeix una posició idèntica en tres torns de joc diferents, la partida és taules. Una altra és la regla dels 50 moviments: si durant 50 moviments no hi ha cap captura i no es mou cap peó, la partida acaba en taules.

Una partida el més llarga possible comença esgotant els primers 50 moviments de les blanques (49 de les negres) conservant la posició inicial i després movent un peó o capturant peça, impedint es produeixin les taules. A continuació es tornen a esgotar altre cop els 50 moviments per fer després un altre moviment de peó o captura. No val qualsevol moviment, sinó aquells on els peons no quedin obstaculitzats. S'ha calculat matemàticament que es pot donar l'oportunitat d'evitar les taules fins a 118 vegades en seqüències de 50 moviments. La partida es pot allargar, dons, fins a poc més de 118x50 moviments, 5.949 jugades com a màxim, moment en qual el resultat de la partida és inevitablement de taules.

·
Al diagrama de l'esquerra podem veure la posició després de la jugada 1400...c4xd3! que correspon a una de les possibles partides de 5.949 moviments de durada, en la qual les negres acaben de capturar amb un peó un cavall blanc que hi havia a 'd3'.

Els peons negres han anat avançant una casella cada 49 jugades de tal  manera que més endavant permetin que avancin els peons blancs.

Les blanques, únicament han fet moviments de cavall fins que aquests han estat capturats a ‘d3’ i ‘e3’. En aquest moment de la partida, ja s’ha conseguit evitar les taules 28 vegades.


5.949 és un nombre de jugades absurd. En la pràctica, la majoria de partides d'escacs tenen entre 20 i 60 moviments. La partida registrada més llarga que es coneix, va acabar amb 159 moviments (Samuel Lipschutz vs. Henry Bird, Congrés Americà d'Escacs de 1889 a New York). Tot i que una partida de 5.949 moviments seria la més avorrida que hom podria imaginar, resulta interessant veure també com hi ha límits que determinen l'enorme abast de possibilitats dels escacs.

Fins aquí, una pinzellada sobre immensitat dels escacs a nivell quantitatiu. En la segona part d'aquest article, enfocarem els números a un nivell més qualitatiu. Descobrirem, per exemple, elements interessants de la particular geometria que caracteritza el joc dels escacs.


4 comentaris:

  1. Ha quedat absolutament clar: tot i la enormitat dels nombres, estem tant aprop de l'infinit, com al començament de la partida

    ResponElimina
  2. Enhorabona per l'article, ple de curiositats que lliguen el món dels escacs amb les matemàtiques i la informàtica. Com a curiositats, afegiria que en el reportatge de Carl Sagan també es definia el nombre de 10 elevat a Googol: "googol plex". També comentar que en algorítmica d'IA és clàssic el problema de les 8 reines: com colocar 8 reines al tauler sense que es puguin matar.

    ResponElimina
  3. Bon dia.
    No hi entenc gaire de matemàtiques; però en la primera casella no hi hauria de posar-se un 1 en lloc de un 2?

    ResponElimina
    Respostes
    1. A la primera casella hi ha:
      Dos elevat a zero = Un gra d'arròs.

      Elimina