Les dames, resoltes

Si us dic que s'acaba d'obtenir un resultat important en teoria de jocs combinatòria potser no us impressionaré gaire; però potser si us dic que s'ha aconseguit solucionar el joc de dames us picarà un xic més la curiositat, no?

Per començar cal explicar dues coses. En primer lloc de quines dames parlem; les dames són una família de jocs amb moltes variants, aparentment no gaire diferents però prou des d'un punt de vista matemàtic com perquè no sigui trivial ampliar els resultats obtinguts per a una de les variants a totes les altres. En aquest cas es tracta de les dames angleses, que es juguen en un tauler de 8x8, amb les dames movent-se només una casella endavant o endarrere i sense bufar.

També cal explicar què s'entén per resoldre un joc matemàticament. Un dels objectius de la teoria de jocs combinatòria és determinar el valor d'un joc, és a dir, el resultat a què s'arriba suposant que els jugadors fan sempre la millor jugada possible en cada moment (és a dir, són el que s'anomena "jugadors perfectes"). Aquest resultat pot ser: el primer jugador guanya, el primer jugador perd o hi ha empat. En aquest sentit és útil la classificació feta per L. V. Allis, vàlida per a jocs de dos jugadors, de suma nul·la (si un guanya, l'altre perd) i amb informació perfecta (els dos jugadors coneixen en tot moment els moviments que ha fet l'altre):

• Un joc està molt feblement resolt quan se sap quin és el resultat però no se sap com obtenir-lo. Per exemple, es pot saber que existeix una estratègia guanyadora (una sèrie de moviments que fan que un jugador guanyi la partida, independentment de què faci l'altre jugador) però no se sap quina és aquesta estratègia. En aquest grup tenim diversos jocs, com ara l'Hex amb taulers superiors a 6x6 hexàgons o el Fanorona.


• Un joc està feblement resolt quan se sap quin és el resultat, com sempre suposant jugadors perfectes, i també se sap com obtenir el resultat. En altres paraules, la resolució feble proporciona un algoritme que, si s'aplica, garanteix la victòria d'un jugador o l'empat. Un exemple d'aquest cas és el Go Moku.


• Un joc està fortament o completament resolt quan se sap quin és el resultat, se sap com obtenir-lo i, a més, es coneixen totes les possibles posicions que es poden donar en el joc, de manera que també es pot obtenir el resultat per a qualsevol posició durant el joc. L'aualé, un dels jocs de mancala, és un joc completament resolt, com també ho són el tres en ratlla o el marro de nou.

Pot semblar estrany el cas de resolució molt feble; realment es pot saber quin és el resultat d'un joc sense saber com s'arriba a aquest resultat? Doncs sí, i, de fet, en matemàtiques són molt habituals els "teoremes d'existència", resultats que demostren l'existència de tal o qual solució a un problema, però sense poder determinar quina és aquesta solució. El fet que un joc estigui molt feblement resolt és força important matemàticament però, des del punt de vista dels jugadors, no els ajuda en res, precisament perquè no diu com és la possible estratègia guanyadora. Això, però, no li treu en absolut l'atractiu matemàtic al tema i, de fet, per demostrar l'existència de solució m'agraden especialment els arguments "de robatori d'estratègia", un tipus de demostració per reducció a l'absurd.

Bé, amb tot això ja podem anar a la notícia: el joc de dames angleses s'ha resolt feblement i el resultat és un empat. El resultat ha estat obtingut per Jonathan Schaeffer i col·laboradors i s'ha publicat a la revista Science. És un resultat important, perquè es tracta del joc més complex, pel que fa a posicions possibles, resolt fins ara, amb 5·10²⁰ posicions possibles (500 trilions, poca broma...). La demostració consisteix en l'obtenció per ordinador d'una estratègia explícita que mai perd, de manera que, com a mínim, sempre es pot obtenir un empat contra qualsevol oponent, jugant amb blanques o amb negres. Potser un altre dia comentarem amb més detall com són aquest tipus de demostracions i en quins mètodes es basen (mètodes de força bruta, basats en coneixement, etc.), així com també la polèmica per la validesa de les demostracions per ordinador (o numèriques) respecte a les demostracions analítiques (les "de tota la vida").

Ara, però, centrem-nos en el treball de Schaeffer. L'obtenció de l'estratègia s'ha aconseguit determinant conjunts de finals de partida amb poques peces, de manera que una posició anterior pogués simplificar-se a una altra de menys complexa ja inclosa en el conjunt de finals. Així successivament, en un procés que en bona part va des de finals de partida cap a la posició inicial (recerca inversa, o backward search), s'anaven comprovant totes les posicions possibles i es comprovava si el moviment era guanyador, perdedor o forçava un empat (ara en una recerca endavant, o forward search). L'equip de Schaeffer va utilitzar uns 200 ordinadors treballant a temps complet, posteriorment reduits a uns 50 més potents. Aquest procés "cap enrera" no es fa totalment a base de força bruta, però, ja que els investigadors sovint podien anar eliminant, amb diversos criteris, certes branques de l'arbre de jugades que no calia explorar.

Ara només cal esperar el següent resultat similar per a jocs amb una major complexitat de càlcul. Un dels més prometedors és l'Othello, amb un nombre de posicions de l'ordre de 10²⁸. Està clar que els escacs encara hauran d'esperar uns quants anys, i encara més el Go, que amb 10¹⁷² posicions possibles, desafia les capacitats d'anàlisi actuals. Recordem que en cap d'aquests jocs se sap si, suposant jugadors perfectes, la partida acaba en victòria per a un o l'altre jugador o en taules.