Teoria de jocs combinatoris

Matemàtics jugant a Konane en un taller de teoria de jocs combinatoris.

La teoria de jocs combinatoris (CGT) és una branca de les matemàtiques i l'informàtica teòrica que normalment estudia jocs seqüencials en informació perfecta. L'estudi s'ha llimitat en gran mida als jocs de dos jugadors que tenen una posició en la que els jugadors es turnan per a canviar de formes o moviments definits per a conseguir una condició guanyadora definida. La CGT no ha estudiat tradicionalment els jocs d'encert o aquells que utilisen informació imperfecta o incompleta, favorint els jocs que oferixen informació perfecta, en els quals abdós jugadors coneixen sempre l'estat del joc i el conjunt de moviments disponibles. No obstant, a mida que alvancen les tècniques matemàtiques, els tipos de jocs que poden analisar-se matemàticament s'expandixen, per lo que els llímits del camp canvien constantment. Els acadèmics generalment definiran lo que volen dir en un "joc" al començ d'un artícul, i estes definicions a sovint varien, ya que són específiques del joc que s'analisa i no pretenen representar l'alcanç complet del camp.

Els jocs combinatoris inclouen jocs ben coneguts com escacs, dames i go, que es consideren no trivials, i tic-tac-toe, que es considera trivial en el sentit de ser "fàcil de resoldre". Alguns jocs combinatoris també poden tindre un àrea de joc illimitada, com l'escacs infinit. En la CGT, els moviments en estos i atres jocs es representen com un arbre de joc.

Els jocs combinatoris també inclouen rompecabezas combinatoris per a un jugador, com Sudoku, i autómates sense jugador, com el Joc de la vida de Conway, (encara que en la definició més estricta, es pot dir que els "jocs" requerixen més d'un participant, d'ahí les designació de "rompecabezas" i "autómates")

La teoria de jocs en general inclou jocs d'encert, jocs de coneiximent imperfecte i jocs en els que els jugadors poden moure's simultàneament, i tendixen a representar situacions de presa de decisions de la vida real.

La CGT té un émfasis diferent a la teoria de jocs "tradicional" o "econòmica", que inicialment va ser desenrollada per a estudiar jocs en estructura combinatòria simple, pero en elements d'encert (encara que també considera moviments seqüencials, vore joc de forma extensiva). Bàsicament, la CGT ha aportat nous métodos per a analisar arbres de jocs, per eixemple, utilisant números surreales, que són una subclasse de tots els jocs d'informació perfecta per a dos jugadors. El tipo de jocs estudiats per la CGT també és d'interés en inteligència artificial, particularment para planificació i programació automatizado. En la CGT s'ha fet menys recalcament en perfeccionar els algoritmes de busca pràctics (com la poda alfa-beta heurística inclosa en la majoria dels llibres de text d'inteligència artificial), pero més émfasis en els resultats teòrics descriptivos (com les mides de la complexitat del joc o les proves de l'existència d'una solució òptima sense especificar necessàriament un algoritme, com l'argument de robo d'estratègia).

Una noció important en la CGT és la del joc resolt. Per eixemple, el tic-tac-toe es considera un joc resolt, ya que es pot demostrar que qualsevol joc terminarà en empat si abdós jugadors juguen de manera òptima. És difícil obtindre resultats similars per a jocs en riques estructures combinatòries. Per eixemple, en 2007 es va anunciar que les dames s'havien resolt débilmente —el joc òptim d'abdós costats també conduïx a un empat— pero este resultat va ser una prova assistida per computadora. Atres jocs del món real són en la seua majoria massa complicats per a permetre un anàlisis complet en l'actualitat, encara que la teoria ha tingut alguns èxits recents en l'anàlisis de finals de go. Aplicar la CGT a una posició significa intentar determinar la seqüència òptima de moviments per a abdós jugadors fins que finalisa el joc i, en fer-ho, descobrix el moviment òptim en qualsevol posició. En la pràctica, este procés és tortuosamente difícil a menos que el joc siga molt simple.

Pot ser útil distinguir entre "jocs matemàtics" combinatoris d'interés principalment per a que els matemàtics i científics reflexionen i resolguen, i "jocs de joc" combinatoris d'interés per a la població en general com una forma d'entreteniment i competència. No obstant, varis jocs s'inclouen en abdós categories. Nim, per eixemple, és un joc fonamental en la formació de la CGT i un dels primers jocs computarizados. El tic-tac-toe encara s'utilisa per a ensenyar principis bàsics del disseny de jocs d'inteligència artificial a estudiants d'informàtica.

Història

La CGT va sorgir en relació en la teoria dels jocs imparcials, en la que qualsevol joc disponible per a un jugador deu estar disponible per a l'atre també. Un d'eixos jocs és Nim, que es pot resoldre per complet. Nim és un joc imparcial per a dos jugadors i subjecte a la condició de joc normal, lo que significa que un jugador que no pot moure's pert. En la década de 1930, el teorema de Sprague-Grundy va mostrar que tots els jocs imparcials són equivalents a montons en Nim, mostrant aixina que les grans unificacions són possibles en jocs considerats a nivell combinatori, en els que les estratègies detallades importen, no solament els pagaments.

En la década de 1960, Elwyn R. Berlekamp, John H. Conway i Richard K. Guy varen introduir conjuntament la teoria d'un joc partisano, en el que es relaixa el requisit de que una jugada disponible per a un jugador estiga disponible per a abdós. Els seus resultats varen ser publicats en el seu llibre Winning Ways for your Mathematical Plays en 1982. No obstant, el primer treball publicat sobre el tema va ser el llibre de Conway de 1976 On Numbers and Games, també conegut com ONAG, que va introduir el concepte de números surreales i la generalisació de jocs. On Numbers and Games també va ser frut de la colaboració entre Berlekamp, Conway i Guy.

Els jocs combinatoris generalment, per convenció, es posen en una forma en la que un jugador guanya quan a l'un atre no li queden moviments. És fàcil convertir qualsevol joc finito en sol dos resultats possibles en un equivalent quan s'aplique esta convenció. Un dels conceptes més importants en la teoria dels jocs combinatoris és el de la suma de dos jocs, que és un joc en el que cada jugador pot elegir moure's en un joc o en l'atre en qualsevol moment del joc, i un jugador guanya quan el seu oponent no té moviment en cap dels jocs. Esta forma de combinar jocs conduïx a una estructura matemàtica rica i poderosa.

Conway va declarar en ONAG que l'inspiració per a la teoria dels jocs partisanos es va basar en la seua observació del joc en els finals de go, que a sovint es poden descompondre en sumes de finals més simples aïllats entre sí en diferents parts del tauler.

Eixemples

El text introductori Winning Ways for your Mathematical Plays va presentar una gran cantitat de jocs, pero els següents es varen utilisar com a eixemples motivadores per a la teoria introductòria:

• Blue – Ret Hackenbush: en el nivell finito, este joc combinatori partisano permet la construcció de jocs els valors dels quals són números racionals diàdics. En el nivell infinit, permet construir tots els valors reals, aixina com molts infinits que cauen dins de la classe de números surreales.
• Blue – Ret – Green Hackenbush: permet valors de joc adicionals que no són números en el sentit tradicional, per eixemple, estrela.
• Sapos i Granotes: permet varis valors de joc. A diferència de la majoria dels atres jocs, una posició es representa fàcilment per mig d'una chicoteta cadena de caràcters.
• Domineering: varis jocs interessants, com els jocs calents, apareixen com a posicions en Domineering, perque a voltes hi ha un incentiu per a moure's i unes atres no. Açò permet discutir la temperatura d'un joc.
• Nim: un joc imparcial. Açò permet la construcció de nimbers. (També es pot vore com un cas especial sol vert d'Hackenbush blau-roig-vert).

El joc clàssic go va influir en la teoria dels jocs combinatoris inicials, i Berlekamp i Wolfe varen desenrollar posteriorment una teoria de finals i temperatura de jocs (vore referències). Armats en açò, varen ser capaços de construir posicions plausibles de finals de go des de les que podien donar als jugadors experts de go una opció de bandos i després derrotar-los de qualsevol manera.

Un atre joc estudiat en el context de la teoria de jocs combinatoris és l'escacs. En 1953, Alan Turing va escriure sobre el joc: "Si un pot explicar sense ambigüitats en anglés, en l'ajuda de símbols matemàtics si és necessari, cóm es deu fer un càlcul, llavors sempre és possible programar qualsevol computadora digital per a fer eixe càlcul, sempre que la capacitat d'almagasenament siga adequada". En un artícul de 1950, Claude Shannon va estimar que el llímit inferior de la complexitat de l'arbre de joc de l'escacs era 10¹²⁰, i hui en dia açò es coneix com el número de Shannon. L'escacs seguix sense resoldre's, encara que un estudi extens, inclós el treball que involucra l'us de supercomputadoras, ha creat bases de taules de finals d'escacs, que mostren el resultat d'un joc perfecte per a totes les partides finals en sèt peces o menys. l'escacs infinit té una complexitat combinatòria encara major que l'escacs (a menos que solament s'estudien partides finals llimitades o posicions compostes en una chicoteta cantitat de peces).

Vore també

• Poda alfa-beta
• Inducció cap a arrere
• Joc de conexió
• Base de senyes de taules de finals
• Arbre Expectiminimax
• Jocs en forma extensiva
• Classificació de jocs
• Complexitat en els jocs
• Joc de Grundy
• Sistema multiagente
• Joc posicional
• Resolució de l'escacs
• Acunyament de Sylver
• Joc de Wythoff
• Joc topològic
• Zugzwang
• PokerTracker

Bibliografia

• 2nd ed., A K Peters Ltd (2001–2004), ISBN 1-56881-130-6, ISBN 1-56881-142-X
• 2nd ed., A K Peters Ltd (2001–2004), ISBN 1-56881-143-8, ISBN 1-56881-144-6.
• See especially sections 21–26.
• 2nd ed., A K Peters Ltd (2001), ISBN 1-56881-127-6.
• (2009) Games, Puzles, and Computation, A K Peters, Ltd.. ISBN 978-1-56881-322-6.