Joc resolt

En teoria de jocs, un joc resolt és un joc el resultat del qual (guanyar, perdre o empatar) es pot predir correctament des de qualsevol posició, assumint un joc perfecte per part d'abdós jugadors. Este concepte se sol aplicar als jocs d'estratègia abstractes, i especialment als jocs en informació completa i sense elements d'encert; la resolució d'un joc d'este tipo pot utilisar la teoria de jocs combinatoris i/o l'assistència informàtica.

Descripció general

Un joc de dos jugadors es pot resoldre en varis nivells:

Ultra-dèbil

Demostrar si el primer jugador guanyarà, perdrà o empatarà des de la posició inicial, en un joc perfecte en abdós costats. Esta pot ser una prova no constructiva (possiblement implicant un argument de robo d'estratègia) que no necessita determinar cap moviment de la jugada perfecta.

Dèbils

Proporcionar un algoritme que assegure una victòria per a un jugador, o un empat per a qualsevol, contra qualsevol possible moviment de l'oponent, des del començ del joc. És dir, produir a lo manco un joc ideal complet (tots els moviments comencen a terminar) en la prova de que cada moviment és òptim per al jugador que ho realisa. No significa necessàriament que un programa de computadora que use la solució jugarà de manera òptima contra un oponent imperfecte.

Fort

Proporcionar un algoritme que puga produir moviments perfectes des de qualsevol posició, inclús si ya s'han comés errors en un o abdós costats.

A pesar del seu nom, molts teòrics de jocs creuen que les proves "ultra dèbils" són les més profundes, interessants i valioses. Les demostracions "ultra dèbils" requerixen que un erudit raone sobre les propietats abstractes del joc i mostre cóm estes propietats conduïxen a certs resultats si es conseguix un joc perfecte.^{cita requerida}

Pel contrari, les proves "sòlides" a sovint procedixen per la força bruta, utilisant una computadora per a buscar exhaustivament un arbre de joc per a averiguar qué passaria si es realisara el joc perfecte. La prova resultant proporciona una estratègia òptima per a cada posició possible en el tauler. No obstant, estes proves no són tan útils per a comprendre les raons més profundes per les que alguns jocs es poden resoldre com un empat, i atres jocs aparentment molt similars es poden resoldre com una victòria.

Donades les regles de qualsevol joc de dos persones en un número finito de posicions, sempre es pot construir trivialmente un algoritme minimax que travesse exhaustivament l'arbre del joc. No obstant, ya que para molts jocs no trivials, tal algoritme requeriria una cantitat de temps inviable per a generar un moviment en una posició donada, un joc no es considera resolt dèbil o fortament a menos que l'algoritme puga ser eixecutat per hardware existent en un temps raonable. Molts algoritmes es basen en una enorme base de senyes pregenerada i, de fet, no són més.

Com a eixemple d'una solució sòlida, el joc de tic-tac-toe es pot resoldre com un empat per a abdós jugadors en un joc perfecte (un resultat que inclús els escolars poden determinar manualment). Jocs com Nim també admeten un anàlisis rigorós utilisant la teoria de jocs combinatoris.

Si un joc es resol no és necessàriament lo mateix que si seguix sent interessant per als humans. Inclús un joc fortament resolt pot ser interessant si la seua solució és massa complexa per a ser memorisada; a l'inversa, un joc resolt débilmente pot perdre el seu atractiu si l'estratègia guanyadora és lo suficientment simple de recordar (per eixemple, Maharajah i els cipayos). Una solució ultra-dèbil (per eixemple, Chomp o Hex en un tauler suficientment gran) generalment no afecta la jugabilitat.

Per una atra part, inclús si el joc no se soluciona, és possible que un algoritme produïx una bona solució aproximada: per eixemple, un artícul en Science de giner de 2015, afirma que el seu bot de pòquer Texas hold 'em Cepheus garantisa que una vida humana de joc no és suficient per a establir en significació estadística que la seua estratègia no és una solució exacta.

Joc perfecte

En la teoria de jocs, el joc perfecte és el comportament o l'estratègia d'un jugador que conduïx al millor resultat possible per a eixe jugador, independentment de la resposta de l'oponent. El joc perfecte per a un joc es coneix quan es resol el joc. En base en les regles d'un joc, cada possible posició final pot evaluar-se (com una victòria, una derrota o un empat). Per raonament cap a arrere, un pot evaluar recursivamente una posició no final com a idèntica a la posició que està a un moviment de distància i millor valorada per al jugador el moviment del qual és. Per lo tant, una transició entre posicions mai pot resultar en una millor evaluació per al jugador en moviment, i un moviment perfecte en una posició seria una transició entre posicions que s'evaluen per igual. Per eixemple, un jugador perfecte en una posició empatada sempre obtindria un empat o una victòria, mai una derrota. Si hi ha vàries opcions en el mateix resultat, el joc perfecte a voltes es considera el método més ràpit que conduïx a un bon resultat, o el método més llent que conduïx a un mal resultat.

El joc perfecte pot generalisar-se a jocs d'informació no perfectes, com l'estratègia que garantisaria el resultat mínim esperat més alt, independentment de l'estratègia de l'oponent. Per eixemple, l'estratègia perfecta para pedra, paper o tijera seria elegir aleatoriamente cada una de les opcions en la mateixa provabilitat (1/3). La desventaja d'este eixemple és que esta estratègia mai explotarà les estratègies no òptimes de l'oponent, per lo que el resultat esperat d'esta estratègia front a qualsevol estratègia sempre serà igual al resultat mínim esperat.

Encara que és possible que (encara) no es conega l'estratègia òptima d'un joc, una computadora de joc encara podria beneficiar-se de les solucions del joc des de certes posicions del final (en forma de bases de taules de finals), lo que li permetrà jugar perfectament despuix d'alguns anys. punt en el joc. Els programes d'escacs per computadora són ben coneguts per fer açò.

Vore també

• Escacs per computadora
• Go per computadora
• Otelo en computadores
• Complexitat en els jocs
• Teorema de Zermelo