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).Resolució de 5x5 Go
Llista de jocs resolts 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 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 Dames angleses: Jonathan Schaeffer demostrà, en un article publicat a Science l'abril de 2007, que el resultat és un empat. 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. Marro de nou: Ralph Gasser demostrà que el resultat és un empat.Nine Men's Morris is a Draw de Ralph Gasser. Qubic
Jocs resolts completament 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 Othello Escacs Go Jocs m,n,k (k en ratlla en taulers de m x n)
Referències
Categoria:Teoria de jocs Categoria:Llistes de matemàtiques