Joc resolt
Un joc resolt, en teoria de jocs combinatòria, és un joc per a dos jugadors per al qual se sap quin és el resultat considerant jugadors perfectes (és a dir, que fan la millor jugada possible en cada moment). Aquest resultat pot ser: guanya el primer jugador, guanya el segon jugador o taules. En funció de si també es coneix quina és l'estratègia que duu al resultat en qüestió es consideren tres tipus bàsics de resolució d'un joc:
- Resolució molt feble: Se sap quin és el resultat del joc però no se sap quina és l'estratègia que duu a l'obtenció d'aquest resultat. Normalment les demostracions de resolució molt feble d'un joc es basen en algun argument de robatori d'estratègia i, per tant, són demostracions no constructives.
- Resolució feble: Se sap quin és el resultat del joc i se sap quina és l'estratègia òptima, ja sigui una estratègia guanyadora o una estratègia que garanteix l'empat. Això vol dir que es disposa d'un algorisme que, aplicat al joc, permet guanyar sempre, o com a mínim empatar, independentment de què faci l'altre jugador.
- Resolució forta o completa: Se sap quin és el resultat del joc i se sap quina és l'estratègia òptima a partir de qualsevol posició que es pot donar durant el joc. En aquests casos es coneixen totes les possibles posicions i jugades del joc.
A partir de les regles de qualsevol joc per a dues persones amb un nombre finit de posicions, hom sempre pot construir un algorisme minimax que recorri de forma exhaustiva l'arbre del joc. No obstant això, com que per a molts jocs no trivials un algorisme d'aquest tipus necessitaria un temps extraordinàriament gran per generar una jugada a partir d'una posició donada, només es considera que un joc està feblement o fortament resolt quan l'algorisme es pot executar amb el maquinari existent en l'actualitat i en un temps raonable. Sovint, l'algorisme depèn d'una gran base de dades creada prèviament.
Com a exemple molt trivial, el tres en ratlla es pot solucionar i demostrar que, suposant jugadors perfectes, el resultat és un empat. A més a més, el tres en ratlla és un joc fortament resolt, és a dir, es coneixen totes les possibles jugades. Nogenmenys, el fet que un joc estigui resolt no té necessàriament cap influència en l'interès que pugui tenir el joc per als jugadors humans; fins i tot un joc completament resolt pot seguir sent interessant si l'estratègia guanyadora és massa complexa com per recordar-la o deduir-la fàcilment. D'altra banda, el fet que un joc estigui molt feblement resolt, com ara l'Hex o el Chomp, no acostuma a afectar-ne la jugabilitat.
El go és el cas d'un joc molt complex computacionalment (molt més que els escacs), però del qual se n'han pogut resoldre totes les possibilitats per un tauler molt petit (de costats 5x5).[1]
Llista de jocs resolts modifica
A continuació es presenta una llista de jocs resolts classificats en funció del grau de resolució aconseguit: molt feble, feble i forta o completa, així com alguns jocs parcialment resolts. Es consideren els jocs tractats en teoria de jocs combinatòria, és a dir jocs per a dos jugadors, amb informació completa
Jocs resolts molt feblement modifica
- Chomp: amb un argument de robatori d'estratègia es pot demostrar que el resultat és victòria del primer jugador.
- Hex (per a qualsevol nombre d'hexàgons): John Nash demostrà que el resultat és victòria del primer jugador.
Jocs resolts feblement modifica
- Dames angleses: Jonathan Schaeffer demostrà, en un article publicat a Science l'abril de 2007, que el resultat és un empat.[2][3][4]
- Fanorona: Maarten Schadd demostrà que el resultat és un empat.
- Hex: Jin Yang demostrà una estratègia guanyadora per a taulers de 7x7, 8x8 i 9x9 hexàgons.[5]
- Marro de nou: Ralph Gasser demostrà que el resultat és un empat.[6]
- Qubic
Jocs resolts completament modifica
- Tres en ratlla: resoluble de forma trivial, el resultat és un empat.
- Nim
- Awari: John Romein de la Vrije Universiteit d'Amsterdam demostrà el 2002 que el resultat és un empat.
- Dakon
- Marro de tres: resoluble de forma trivial, el resultat és un empat.
- Hex, resolt per a taulers de fins a 6x6 hexàgons.
Jocs parcialment resolts modifica
- Othello
- Escacs
- Go
- Jocs m,n,k (k en ratlla en taulers de m x n)
Referències modifica
- ↑ Resolució de 5x5 Go (anglès)
- ↑ Schaeffer, Jonathan. «Checkers Is Solved». Science, 19-07-2007. [Consulta: 20 juliol 2007].
- ↑ «Project - Chinook - World Man-Machine Checkers Champion». [Consulta: 19 juliol 2007].
- ↑ Mullins, Justin. «Checkers 'solved' after years of number crunching». NewScientist.com news service, 19-07-2007. [Consulta: 20 juliol 2007].
- ↑ «Jing Yang homepage». Arxivat de l'original el 2004-09-30. [Consulta: 15 setembre 2008].
- ↑ Nine Men's Morris is a Draw de Ralph Gasser.