Traba jo de Fin de GradoJuegos CombinatoriosIgnacio Amat PerezUniversidad de La Rio ja2Dedicado ami familiaIIIAgradecimientosque dicultad tiene el juego?.Entonces uno puede comenzar a buscar respuesta a esta pregunta analizandoel grafo del arbol de juego del mismo y de este modo obtener de forma exactael numero de casos favorables, desfavorables o neutros (empate), de forma quedada una posicion cualquiera sea facil establecer la complejidad del mismoteniendo en cuenta las jugadas posibles. Esto, a primera vista, parece unaopcion factible en el proceso de busqueda de la dicultad de un juego, peropor desgracia, no es as.
Veamos por ejemplo el 3 en raya jugado sobre un tablero de 3×3, tenien-do en cuenta que cada uno de las 9 casillas del tablero puede encontrarse en3 estados diferentes, sean cruz, crculo o en blanco, se tiene que existen 3 9situaciones diferentes. Sin embargo, hay que tener presente que muchos deestos estados son imposibles o incongruentes dada la naturaleza del juego;ademas, por las caractersticas del tablero y las simetras del mismo se tienenen total 765 posibilidades diferentes. Parece obvio que analizar todos estosestados, es un tarea ardua y que al mismo tiempo llevara un tiempo cal-cularlas todas. Ahora bien, no todos los juegos poseen la misma estructura,tampoco el mismo numero de posiciones legales diferentes; y, por consiguien-te, el tiempo y dicultad para calcular las mismas no sera el mismo. Porlo tanto, surge ahora la pregunta: >es posible calcular todos y cada uno delos estados de un juego? , y en caso de que esto sea posible, >cuanto tiempollevara calcularlos? ,>de que forma se podran calcular? ,>sera esta formade calcularlos similar para todos? , y en el caso de que no se puedan calcular,>se pueden establecer lmites para acotar su posible valor? .A lo largo de este captulo se tratara de responder a las cuestiones plantea-1718CAPITULO 2. COMPLEJIDADdas con anterioridad para poder comprender mas facilmente las propiedadesde un juego. Por desgracia, solo unos pocos juegos han logrado ser resuel-tos por completo, siendo posible conocer todas las diferentes posiciones deljuego.
Para otros muchos se conocen ciertas propiedades como el tama~no delarbol de decision o a que clase de complejidad computacional pertenece yotros para los que no se conoce con exactitud. Sobre este ultimo conceptotraba jaremos mas en profundidad en este captulo, por ser de gran interes ala hora de poder ver la clase de complejidad a la que pertenece un juego, yde esta forma poder tener conocimiento del tiempo que requerira realizar loscalculos.Entrando un poco mas en contexto, la complejidad computacional es untema de estudio muy importante para los matematicos, hasta tal punto queen el a~no 2000 el Clay Mathematics Institute ofrece un millon de dolarespara aquel que consiga resolver el problema Pvs NP . Aqu no se demostraradicha cuestion, pero se estudiaran distintas clases de complejidad y la relacionexistente entre ellas.Sin mas preambulos, veamos ahora diferentes formas de medir y clasicarla complejidad de un juego cualquiera.
2.1. Medidas de Complejidad La teora de juegos combinatorios, a la hora de poder estudiar los juegos enprofundidad y mas en concreto propiedades relacionadas con su complejidad.Por ello, se han establecido diferentes tipos de medidas para catalogar estacomplejidad y clasicar as los mismos.En primer lugar, veremos la complejidad del estado-espacio que estudiarael numero de posiciones posibles desde la posicion inicial; despues se estudiaratodo lo relacionado con el arbol de juego, esto es, ya sea su tama~no, lacomplejidad de su arbol de decision o de su arbol de jugadas. Por ultimo, seanalizara la complejidad computacional y la pertenencia de un juego a losdiferentes tipos de clases de complejidad, ya sea en el tiempo o en el espacio.(sacado de https://www.cs.
ubc.ca/ hutter/teaching/cpsc322/2-Search3.pdf )En el momento en que se deseen buscar las diferentes medidas de complejidaddel juego, se emplearan diferentes algoritmos de busqueda para encontrar, da-da una disposicion inicial, el coste de llegar a una posicion determinada.
Estosalgoritmos de busqueda poseen a su ver diferentes propiedades como sabersi es un metodo de busqueda de la solucion es optimo o no, si es completo osu complejidad en espacio y tiempo.2.1. MEDIDAS DE COMPLEJIDAD19Denicion 2.1.1. Se dice que un algoritmo de busqueda en un grafo de unjuego Jes completo si en el momento en que existe una posicion determinada,este algoritmo garantiza encontrarla en una cantidad nita de tiempo.Denicion 2.
1.2. Se dice que un algoritmo de busqueda en un grafo de unjuego Jes optimo si en el momento en que encuentra una solucion (posiciondeterminada deseada), esta es la mejor (en el sentido en que es la menoscostosa de alcanzar).
(PUEDE QUE NO QUEDE CLARO EL CONCEP-TO)(CREO QUE ESTE NO INTERESA VERLO, PORQUE EL GRAFODE UN JUEGO NO TIENE COSTES)Denicion 2.1.3. La complejidad-tiempo de un algoritmo de busqueda enun grafo de un juego Jes la cantidad de tiempo que lleva ejecutarlo delpeor de los casos posibles.
Este se expresa en terminos del camino de mayorlongitud ( m) y del mayor factor de ramicacion de sus nodos ( h).Denicion 2.1.
4. La complejidad-espacio de un algoritmo de busqueda enun grafo de un juego Jes la cantidad de memoria que se utiliza para ejecutarloen el peor de los casos posibles.2.1.1. Estado-Espacio No todos los juegos poseen el mismo numero de estados posibles diferen-tes, existiendo algunos que a priori por las reglas del juego y su descripcionparezcan complejos en cuanto al numero de posiciones diferentes que puedenexistir, pero que en realidad debido a ciertas propiedades como simetras oestados incongruentes, este numero sea mucho menor del esperado.
En otroscasos, este hecho puede darse de forma inversa; es decir, juegos que en unprincipio puedan parecer simples, pero que en realidad no sea as.Demos una denicion mas formal sobre este concepto de complejidadestado-espacio:Denicion 2.1.5 (Complejidad estado-espacio) .
El termino complejidad delestado-espacio de un juego combinatorio Jse dene como el cardinal delconjunto de todas las posiciones permitidas y accesibles a partir de la con-guracion inicial.Tal y como se puede apreciar en la denicion, se trata del numero deposiciones distintas que se pueden alcanzar en un juego. Por ello hay quetener en cuenta que al calcular el total de las posiciones, no todas ellas sonvalidas ya que el juego puede presentar simetras, lo que producira estadosrepetidos, o tambien situaciones imposibles o estados ilegales.
20CAPITULO 2. COMPLEJIDADEjemplo 2.1.
1. Teniendo en cuenta las reglas de un simple juego como elfamoso 3 en raya, tal y como se menciono con anterioridad, existen 3 estadosdiferentes posibles para cada una de las casillas (cruz, crculo o en blanco), loque supone un total de 39= 19683 posiciones. Sin embargo, en estos calculosse han tenido en cuenta casos repetidos, puesto que si tomamos por ejemplo,el caso en que un jugador haya colocado una cruz en el centro y el otro,un crculo en una de las esquinas; por simetra del tablero se tiene que noimporta en cual de el las lo ha puesto, ya que la situacion actual del juegosigue siendo la misma. Como entre las posibilidades calculadas, hay casosrepetidos, estos deben ser descartados de las cuentas realizadas.
Ademas, si seconsidera que en dichos calculos se han a~nadido posiciones ilegales del juego,como puede ser que un jugador haya colocado 5 veces y el otro ninguna, oque ambos jugadores posean 3 en raya. Como es obvio, estos casos tambiendeben ser descartados puesto que no cumplen las reglas del juego y por elloson escenarios imposibles en el desarrollo de una partida. De esta forma,los posibles estados diferentes de este juego se reducen a 765, algunos de loscuales se muestran en la gura del arbol de tic-tac-toe(hacer referencia).(a~nadir foto arbol estado espacio tic-tac-toe: https://upload.
wikimedia.org/wikipedia/commons/thumb/d/da/Tic-tac-toe-game-tree.svg/2000px-Tic-tac-toe-game-tree.svg.png) Si bien es facil comprender que casos deben ser rechazados y cuales debenser tenidos en cuenta a la hora de estudiar el estado-espacio de un juego, latarea de calcular exactamente cual sera dicho numero no sera facil puestoque en ciertas ocasiones los calculos se vuelven demasiado complejos queaun no han podido ser estudiados por completo. Ante estos casos, casosen que no se sabe como obtener dicho numero exacto de estados o no seaposible calcularlo con los procedimientos actuales, se procedera a establecerlmites con la nalidad de acotar dicho numero y poder tener un conocimientoestimado de la complejidad del juego.A la hora de abordar este problema, se plantean dos vas diferentes, porun lado la busqueda no informada y por otro la busqueda informada; cadacual con sus respectivos metodos de busqueda.Segun denieron Poole y Mackworth 3, los siguientes tres algoritmosde busqueda se caracterizan por ser metodos de busqueda estado-espaciono informados, considerados as porque no consideran ninguna informacionsobre los diferentes estados ni los ob jetivos para decidir que camino exploraren primer lugar, son por lo tanto algoritmos genericos que no tienen en cuentalos intereses del problema:Denicion 2.
1.6 (Algoritmo de busqueda profunda (ABP)) .Metodo pararecorrer y buscar ciertas estructuras en un grafo. Para ello se toma un nodo2.1. MEDIDAS DE COMPLEJIDAD21como inicio (normalmente le nodo raz, salvo interes en otro nodo particular)y se recorren sus ramas tan lejos como sea posible antes de retroceder alnodo previo y tomar otra rama continuando con el procedimiento (NO SESI QUEDA CLARA LA EXPLICACI ON).Denicion 2.1.
7 (Algoritmo de busqueda en anchura (ABA)) .Metodo pararecorrer y buscar estructuras en un grafo. Se toma un nodo inicial (normal-mente le nodo raz, salvo interes en otro nodo particular) y a continuacionse recorren todos los nodos inmediatamente inferiores antes de proceder conla busqueda en el siguiente nivel.(CREO QUE ESTE NO INTERESA VERLO, PORQUE EL GRAFODE UN JUEGO NO TIENE COSTES)Denicion 2.1.8 (Algoritmo de busqueda de coste mnimo (ABCM)) .Meto-do para recorrer y buscar estructuras en un grafo encontrando el camino conel menor coste al nodo deseado. Se toma un nodo inicial (normalmente lenodo raz, salvo interes en otro nodo particular) y seguidamente en cada ni-vel se busca el camino de menor coste en la frontera (NO SE SI QUEDACLARO??)Se tiene que ABP es completo cuando el grafo no posee bucles y es nito,su complejidad tiempo es O(h m) y su complejidad-espacio es O(hm ).
ABA escompleto (salvo ramicacion innita de algun nodo), su complejidad-tiempoes O(h m) y su complejidad-espacio tambien es O(h m).Siguiendo con el esquema propuesto por Poole y Mackworth 4, los si-guientes tres algoritmos de busqueda se caracterizan por ser metodos debusqueda estado-espacio informados, esto es, se tiene en cuenta la informa-cion correspondiente a un nodo concreto, considerado el ob jetivo: (CREO QUE ESTO NO INTERESA VERLO, PORQUE EL GRAFODE UN JUEGO NO TIENE COSTES)Denicion 2.1.9 (Algoritmo de busqueda heurstica (ABH)) .Denicion 2.1.
10 (Algoritmo de busqueda de Greedy (ABG)) .Denicion 2.1.11 (Algoritmo de busqueda A* (ABA*)) .2.1.2.
Arbol de jugadasRetomando la denicion 1.2.9 (hacer referencia) del arbol de jugadas deun juego J, a la hora de jugar sobre el grafo del juego, se movera alternati-vamente del nodo a una de sus ho jas, de forma que el jugador Izquierda siga22CAPITULO 2. COMPLEJIDADsus correspondientes ramas asociadas a los posibles movimientos disponiblesdado el estado actual del juego, y respectivamente para el jugador Derecha.(introducir imagen g2 pg3 de: https://perso.liris.cnrs.fr/eric.
duchene/articles/SUM.pdf )Este concepto de arbol de jugadas caracteriza a la mayora de juegoscombinatorios conocidos, sin embargo podemos destacar algunos en que estaidea de arbol no es del todo util puesto que existen situaciones en que algunosestados pueden visitarse varias veces, como es el caso del a jedrez o las damas,y otros como el Go u Othello, en los cuales el ganador se determina por lapuntuacion total y no por quien ha sido el ultimo en mover. Surge as unanuevo concepto de grafos con bucles y por tanto la idea de juegos innitos.Denicion 2.
1.12 (Grafo nito).5 (puede ser redundante) Un juego Jtiene un grafo de juego nito si tiene un grafo directo bipartido nito cuyoconjunto de nodos (estados del juego) Qesta dividido en dos conjuntos. Porun lado el conjunto de los nodos para los que el jugador Izquierda puedemover ( JI) y por otro, el conjunto para los que el jugador Derecha puededirigirse ( JD)Denicion 2.1.13 (Juego con bucles).
(aaron n siegel CGT 2013, def 4.1)Un juego imparcial con bucles es un par G= ( H; x ) donde Hes un grafodirecto y xes un vertice de H. Se tiene que Ges nito si Hes nito. Lasopciones de Gson juegos de la forma G0= ( H; x 0), donde existe un arcodirecto entre xyx0.A simple vista puede parecer que el tama~no de un arbol de jugadas co-rresponde con el tama~no del estado-espacio del juego; es decir, el numero denodos corresponde al numero total de estados diferentes del juego J. Esteno es el caso, es mucho mas complicado que eso, las posiciones o estadosdiferentes accesibles a lo largo del juego s que se contemplaran; sin embargo,el acceso a algunos de estos estados puede darse de formas diferentes, lo queincrementa el numero de nodos y as el tama~no del arbol de juego.
Vease esto con un simple ejemplo, como es el DOMINEERING (gura 1y 2 dibujo esquema + reglas anexo) en donde como se observa en las guras 1y 2, es posible alcanzar un estado de mas de una forma diferente, sobre todocuantas mas piezas haya sobre el tablero. Por lo tanto, el arbol de jugadases mas complejo que el de estado-espacio.(gura 1 y 2)Para algunos de estos juegos no siempre es posible obtener el numeroexacto de estados, por ello se han establecido formas para obtener un lmitesuperior que acote este numero.
Sin embargo, en otro tipo de juegos el tama~no2.1. MEDIDAS DE COMPLEJIDAD23del arbol de jugadas puede ser innito debido a la repeticion de estados portener un numero de movimientos ilimitado, como en el a jedrez o las damas.
2.1.3. Complejidad computacional En el momento en uno se plantea las cuestiones >como de complejo esun juego? o >que dicultad tiene?, surge a su vez la pregunta de >como sepuede medir esta complejidad? Sabiendo que cada juego es a priori diferentedel resto, ya sea por el tama~no, su forma del tablero, por sus reglas o por elnumero de piezas que intervienen; trataremos de agrupar algunos de ellos endiferentes clases de complejidad y entenderlas un poco mas.Para ello, es necesario estudiar estas complejidades teniendo en cuenta elconcepto de maquina de Turing ideada por Alan Turing en 1936 A. Turing,On Computable Numbers, with an Application to the Entscheidungsproblem,Proc. London Math.
Soc. 42 230{265 and 43 544{546. , que es un modeloabstracto de computacion a traves del cual parece posible recrear todos losdiferentes modelos y estados con la mayor eciencia, es decir, con el menorgasto posible. Al hablar del concepto de eciencia computacional aparecetambien el termino de la Ogrande, que se emplea para medir la ecienciade un algoritmo o metodo mediante el numero de operaciones basicas queeste es capaz de efectuar como funcion de su tama~no de entrada. Dicho de otra forma, la eciencia de un algoritmo puede ser medida con una funcionT :N ! Ntal que T(N ) es el maximo de operaciones basicas que elalgoritmo es capaz de realizar con datos de tama~no n.
Veamos mas formalmente estos conceptos para proseguir con el estudiode algunos de los distintos tipos de clases de complejidad existentes:(QUITAR LOS SALTOS DE LINEA, JUNTAR EL TEXTO)Denicion 2.1.14 (NotacionO()) .
(6 def 1.2 pg14) Sean f ; g:N ! Nentonces decimos que:1. f= O(g ) si existe una constante ctal que f(n ) cg(n ) para cada nlosucientemente grande.2. f= ( g) si g= O(f ).3. f= ( g) si f= O(g ) y g= O(f ).
4. f= o(g ) si para cada >0,f(n ) g(n ) para todo nsucientementegrande.5. f= !(g ) si g= o(f ).24CAPITULO 2. COMPLEJIDADDenicion 2.1.
15 (Maquina de Turing) .A. Turing, On Computable Num-bers, with an Application to the Entscheidungsproblem, Proc. London Math.Soc. 42 230{265 and 43 544{546.
Una cinta de una maquina de Turing esuna 7-tupla M=donde; Qes un conjunto nito no vaco de estados. es un conjunto nito no vaco de smbolos.b2 es el smbolo del vaco. n f bg es el conjunto de smbolos de entrada.
q0 2 Qes el estado inicial. F Q es el conjunto nal o estados aceptados. :Q n F $ Q f I ; D ges una funcion de transicion, donde Ies un desplazamiento a izquierda y Dun desplazamiento a derecha.Denicion 2.
1.16 (Computo de una funcion y tiempo de ejecucion) .(6def 1.4) Sea f:f0;1 g ! f 0;1 g y sea T:N ! Nalgunas funciones, ysea Muna maquina de Turing. Decimos que M computa f en T(n)-tiemposipara todo x2 f 0;1 g , si Minicializa a la conguracion del principio de laentrada x, entonces despues de al menos T(jx j) pasos se detiene con f(x ) enla cinta de salida.
Decimos que M computa f si computafen un tiempo T(n ) para algunafuncion T:N ! N.Teorema 2.1.2 (Jerarqua de espacios) .(10) Para cada funcion de unespacio construible f:N ! N, entonces existe un lenguaje lque es deter-minable en un espacio O(f (n )) pero no en un espacio o(f (n )) .Denicion 2.1.
17 (Maquina de Turing no determinista) .(8 def 5.1) Unamaquina de Turing no determinista solo puede computar valores de funcionesque tomen valores 0 y 1. LA maquina toma el valor 1 con un valor de entradax sii es posible alguna computacion para la entrada xque tiene como salida 1.Si no existe ninguna computacion que de como salida 1, la maquina devuelvevalor 0.
Denicion 2.1.18. (8 def 5.3) Una maquina de Turing no determinista Mse ejecuta en un tiempo T(n ) si para cada dato de entrada de longitud n,cada computacion de Mse procesa con T(n ) pasos.
2.1. MEDIDAS DE COMPLEJIDAD25Denicion 2.1.
19. (8 def 5.4) Una maquina de Turing no deterministaM se ejecuta en un espacio T(n ) si para cada dato de entrada de longitudn , cada computacion de Mvisita como mucho S(n ) regiones de la cinta detraba jo.Ahora s que estamos en condiciones de poder presentar las diferentesclases de complejidad y comprender mejor de esta forma como categorizar losjuegos combinatorios segun su dicultad para encontrar todas las soluciones. Esta clasicacion se realiza teniendo en cuenta dos aspectos diferentes; porun lado si se tiene en cuenta el tiempo de ejecucion del algoritmo entoncesse hablara de complejidad-tiempo, por otro lado, si se tiene en cuenta elespacio ocupado en memoria durante la ejecucion del algoritmo se hablarade complejidad-espacio.
Clases complejidad-tiempo 12Suponiendo que t( n ) es una funcion construible en tiempo y que Tesel modelo de las clases de las maquinas de Turing, se tiene que la claseTIME (t( n )) es como sigue:TIME (t( n )) = fX f 0;1 g :9N 2T 8n (timeN(n ) t( n )) y NdecideX gDenicion 2.1.20. (9,def 1, 2.1.1) DTIME( f(n )) es el conjunto de proble-mas de decision que pueden se resueltos por una maquina de Turing deter-minista usando un tiempo O(f (n )).Denicion 2.1.
21. (9,def 1, 2.1.
1) NTIME( f(n )) es el conjunto de pro-blemas de decision que pueden se resueltos por una maquina de Turing nodeterminista usando un tiempo O(f (n )).Teorema 2.1.3 (Teorema de jerarqua de tiempo) .
(13) Si f(n ) es cons-truible en el tiempo, entonces: DT I M E(o ( f(n ) log f(n ))))(DT I M E (f (n ))Hay que notar que DTIME( t) NTIME( t) puesto que las maquinasde Turing no deterministas son capaces de ejecutar a su vez operacionesdeterministas. Veanse ahora las clases de complejidad computacional mas estudiadas encuanto a la complejidad-tiempo se reere.Denicion 2.1.22. (8, def 4.2) Dado un conjunto A, decimos que A2Psii hay una maquina de Turing determinista que acepta a Ay se ejecuta enun tiempo O(n k) para alguna constante k.26CAPITULO 2.
COMPLEJIDADDenicion 2.1.23. (8,def 5.6) Dado un conjunto A, decimos que A2N Psii hay una maquina de Turing no determinista que acepta a Ay se ejecutaen un tiempo O(n k) para alguna constante k.Denicion 2.1.24.
Dado un conjuntoA, decimos que A2E X P T I M E siihay una maquina de Turing determinista que acepta a Ay se ejecuta en untiempo O(2 nk) para alguna constante k.Clases complejidad-espacioDenicion 2.1.25.
(9,def 2, 2.1.1) DSPACE( f(n )) es el conjunto de pro-blemas de decision que pueden se resueltos por una maquina de Turing de-terminista usando un espacio O(f (n )).Denicion 2.
1.26. (9,def 2, 2.1.1) NSPACE( f(n )) es el conjunto de pro-blemas de decision que pueden se resueltos por una maquina de Turing nodeterminista usando un espacio O(f (n )).Teorema 2.
1.4 (Teorema de Savitch) .(11) Para cualquier funcion s(n ) log (n ), entonces NSPACE( s(n )) DSPACE( s(n )2).
Del teorema anterior se deduce el siguiente corolario.Corolario 2.1.5. PSPACE = NPSPACEEsto sigue del hecho que el cuadrado de una funcion polinomica s(n ) siguesiendo una funcion polinomica.Veamos algunas de las clases de complejidad-espacio mas importantes:Denicion 2.1.
27. (8, def 4.3) Dado un conjunto A, decimos que A2P S P AC E sii hay una maquina de Turing determinista para alguna constantek que computa la funcion caracterstica de Aen un espacio O(n k).Denicion 2.
1.28. (8, def 5.7) Dado un conjunto A, decimos que A2N P S P AC E sii hay una maquina de Turing no determinista para algunaconstante kque computa la funcion caracterstica de Aen un espacio O(n k).Denicion 2.1.29. Dado un conjuntoA, decimos que A2E X P S P AC Esii hay una maquina de Turing determinista para alguna constante kquecomputa la funcion caracterstica de Aen un espacio O(2 nk).
hardness, completness.. bilibi2.2. EJEMPLOS27Lmites superior e inferior Puede que sea adecuado todo el contenido de: . On globally sparsey Ramseygraphs”del sitio2.2. Ejemplos el a jedrez es exptime.
.. dots-and-boxes es desconocido 5.
Solving dotx-and-boxes de (https://upcommons.upc.edu/bitstream/handle/2117/78323/memoria.pdf )28CAPITULO 2. COMPLEJIDADCaptulo 3Estrategias ganadorasUno de los principales ob jetivos de la Teora de Juegos general y de laTeora de Juegos Combinatorios es el estudio del problema de la(s) estrate-gia(s) a seguir. Esto es, busca dar respuesta a algunas preguntas del estilo:>que jugador tiene una estrategia ganadora? ,>cual es una estrategia optima? ,>que jugada llevar a cabo para evitar una derrota segura? ..
. Estas son algunasde las cuestiones a las que se intentara responder en este captulo.En primer lugar, debemos entender mejor el concepto de estrategia apli-cado a un juego combinatorio. Este termino se reere al proceso de asuncionpor parte de cualquiera de los jugadores, el cual, en lugar de realizar un movi-miento aleatorio de una posicion dada del juego a otra posicion, este analizapreviamente las posibles consecuencias que tendra dicho movimiento para eldesarrollo del juego actuando en consecuencia. Es decir, una estrategia esuna planicacion de las jugadas que un jugador realizara en cada uno de losdiferentes estados del juego.Estos conceptos mas bien teoricos, ya que si fuesemos capaces de, a cadaestado, calcular todos uno no perdera nunca; sin embargo esto no es as.
Porlo general cuando decidimos jugar a un juego cualquiera, lo que uno puedepensar que esta llevando a cabo, una serie de pasos que considera adecuados,no es una estrategia propiamente dicha. Uno se limita a ganar la jugadaactual, a no dejar que el oponente en su siguiente turno termina la partidallevandose la victoria sino hacer todo lo posible para ser uno mismo quien loconsiga, o en su defecto terminar en empate.Para dar una denicion formal de estrategia, se debe presentar antes lanocion de juego posicional.Denicion 3.0.
1 (Juego Posicional).(T5-BEckcombinatorialgames) Sea ( V ;F)un hipergrafo nito arbitrario. Un hipergrafo nito es un conjunto arbitra-rio nito V, denominado tablero del juego y Funa familia de subconjuntos2930CAPITULO 3. ESTRATEGIAS GANADORASarbitraria de Vque representa la familia de conjuntos ganadores. Los dosjugadores, ocupan alternadamente las posiciones del tablero Vque permane-cen libres. El jugador que primero ocupe todos los elementos de un conjuntoganador A2 F gana, de otro modo el juego termina en empate.Notar que un juego posicional puede denirse tambien solo a traves desu familia Fde conjuntos ganadores, puesto que el tablero Vsera la union A2F de todos los conjuntos ganadores.
Denicion 3.0.2 (Estrategia).(pg680 beckcombinatorialgames) Sea un jue-go posicional en un hipergrafo nito ( V ;F). Una estrategia para el primer(resp. segundo) jugador es una funcion Strcuyo dominio es un conjuntosubsecuencias de longitud par (resp. impar) de diferentes elementos del ta-blero V, y su rango es V.
Si denotamos como x1; x2; x3; : : :los movimientosdel primer jugador y como y1; y2; y3; : : :los del segundo, entonces el i-esimomovimiento xi (resp.yi) esta determinado porStrcomo siguex i =Str (x1; y1; x2; y2; : : : ; yi 1)2 V n f x1; y1; x2; y2; : : : ; yi 1g( resp: yi=Str (x1; y1; x2; y2; : : : ; yi 1; xi)2 V n f x1; y1; x2; y2; : : : ; yi 1; xig)dene el i-esimo movimiento del primer (segundo) jugador.Denicion 3.0.3 (Estrategia ganadora (o de empate)) .(pg 680 beckcombi-natorial) Una estrategia ganadora (o de empate) Strpara el primer jugadorsignica que de todas las formas posibles en que el primer jugador siga laestrategia Strpara elegir su proximo movimiento es una victoria (o empate)para el. Formalmente, cada jugadax 1 =S tr (; ); 8 y1; x2=S tr (x1; y1); 8 y2; x3=S tr (x1; y1; x2; y2); 8 y3; : : : ;8yN= 2(3.1)si N =jV jes par, yx 1 =S tr (; ); 8 y1; : : : ;8y(N 1) =2 ; x(N +1) =2 =S tr (x1; y1; x2; y2; : : : ; y(N 1) =2 )(3.
2)si N es impar, es una victoria (o empate) para el primer jugador.De modo similar, una estrategia ganadora (o de empate) para el segundojugador signica que de todas las formas posibles en que emplee su estrategiaStr para encontrar su proximo movimiento es una victoria (o empate) parael. Formalmente, cada jugada8x1; y1=S tr (x1); : : : ; 8x(N= 2); yN= 2=S tr (x1; y1; x2; y2; : : : ; xN=2) (3.3)31si N es par, y8 x1; y1=S tr (x1); 8 x2; y2=S tr (x1; y1; x2); 8 x3; : : : ;8x(N +1) =2 (3.4)si N es impar, es una victoria (o empate) para el segundo jugador.En ambos casosx i 2V n f x1; y1; x2; y2; : : : ; yi 1gy yi2V n f x1; y1; x2; y2; : : : ; yi 1; xig(3.5)se cumple para todo i 1.Como ya se menciono con anterioridad, otra de los conceptos importan-tes que trata la Teora de Juegos es el de estrategias de juego optimas.
Seentiende por estrategia optima a las estrategias ganadoras y a las estrategiasde empate (cuando no existe estrategia ganadora). Ahora bien, tal y comose se vio en el apartado de Complejidad (hacer referencia ??) a la hora decalcular los diferentes estados del juego o el tama~no del arbol de jugadas,por lo general se establecan lmites para acotar el numero exacto. Calcularel numero total de estrategias optimas no va a ser una excepcion, esta tareaes ardua y complicada, es mas facil establecer el numero total de estrategiasque el de estrategias optimas.(EL N oDE ESTRATEGIAS ES PARTICULAR DEL 3 EN RAYA ?)Teniendo en cuenta la convencion de juego completo (en donde los juga-dores continuan jugando hasta completar todas las casillas del tablero, pesea que ya se conozca el ganador), el total de estrategias se puede acotar supe-riormente por NeN!(ver pg 681 beckcombinatorial games). Sin embargo, esposible dar un resultado exacto del numero total de estrategias.Sea un juego tal que x1; x2; x3; : : :las casillas ocupadas por el primerjugador y y1; y2; y3; : : :las ocupadas por el segundo jugador,con un esquemade jugadas x1; y1; x2; y2; x3; y3; : : :.Sea Struna estrategia del segundo jugador, que viene denida de formaque el i-esimo movimiento yi depende de los anteriores,yi =S tr (x1; y1; x2; y2; : : : ; yi 1; xi2V n f x1; y1; x2; y2; : : : ; yi 1; xig.As, dado el primer movimiento del primer jugador x1, la funcionStrdetermina unicamente y1(6= x1), el primer movimiento del segundo jugador.
De igual forma, dados x1; x2,Str determina unicamente y2(=2 f x1; y1; x2g), yas sucesivamente. Se puede escribir queyi =S tr (x1; y1; x2; y2; : : : ; yi 1; xi) =S tri(x1; x2; : : : ; xi)32CAPITULO 3. ESTRATEGIAS GANADORASya que los y1; y2; : : : ; yi 1 vienen determinados por losx1; x2; : : : ; xi 1. Portanto, Strpuede considerarse como un vector S tr= (S tr1; S tr2; S tr3; : : :)de cada i-esima componente S tride la estrategiaStr. El numero total decomponentes S tr1es por denicion (N1)N, el de S tr2es (N3)N(N 2),el de S tr3es (N5)N(N 2)( N4), y as sucesivamente. Se sigue que el totalde estrategias de un juego es el producto(N 1)N(N 3)N(N 2)(N 5)N(N 2)( N4) = bN= 2c 1Yi =0 (N 1 2i) Qij =0 (N 2j)= eeNlog N=2+O(N ): (3.6)Ahora bien, si uno se pone a pensar detenidamente, total de estrategiasde un juego cualquiera puede ser una cantidad demasiado grande como parapoder probar cada una de ellas y determinar as cuales son las estrategiasoptimas, es por ello que nos conformamos con calcular el total de estrategiasdel juego, lo que supondra una cota superior para el numero de estrategiasoptimas. Sin embargo, todas esas estrategias van a conducir a solamente 3 resulta-dos posibles, sean estos victoria, derrote o empate.
Por ello, suele decirse quelos juegos posicionales estan determinados. Siguiendo las ideas del teoremade Zermelo 1912, el siguiente teorema es un caso particular.Teorema 3.0.1 (Teorema de estrategia) .(pg 682 beckcombinatorial) Sea( V ; F) un hipergrafo nito arbitrario y considerese un juego posicional endicho hipergrafo. Entonces existen unicamente tres alternativas diferentes: elprimer jugador tiene una estrategia ganadora, o el segundo jugador tiene unaestrategia ganadora, o ambos tienen una estrategia de empate.Demostracion 3.
0.2.No se incluira en este traba jo esta demostracion, perosi el lector esta interesado se encuentra en la pagina 683 de beckcombinato-rialgames.
Teorema 3.0.3 (Robo de estrategia) .(pg 683 beckcombinatorial) Sea (V ; F)un hipergrafo nito arbitrario. Entonces jugando un juego posicional en (V ; F),el primer jugador puede forzar al menos un empate (o posiblemente la victo-ria).Demostracion 3.
0.4.La prueba de este teorema no se vera tampoco en estetraba jo, puede encontrarse en la pg 683 de beckcombinaotrialgames.Puesto que la Teora de Juegos Combinatorios (y la Teora de Juegosgeneral tambien) buscan resolver y encontrar la solucion a los diferentes jue-gos, las estrategias optimas en cada estancia del juego requieren de jugadores33perfectos que puedan llevar a cabo dichas estrategias. El hecho de que seanperfectos se reere a que conocen cuales son dichas estrategias optimas y queno cometan en errores al llevarla a cabo.
Sin embargo, en la practica esto noocurre, ya que ambos jugadores no conocen su estrategia optima y por tantocometen errores que el rival aprovechara para tomar venta ja.El concepto de robo de estrategia revela quien sera el ganador del juego,pero no la forma con la que encontrar la estrategia ganadora o de empate.Dado que este resultado no dice nada sobre como conocer la estrategia aseguir, esta debera obtenerse estudiando cada caso. Pero, en general, eso esalgo que ni los ordenadores mas potentes podran hacer dado el gran numerode estrategias diferentes que existen, un ejemplo sera el a jedrez, que aun nose es capaz de saber todas las estrategias optimas para cada estado del juegodebido a su complejidad y numero de estados diferentes. Por ello, en lugarde examinar caso a caso cada una de las estrategias a seguir, se estudian lasdiferentes posiciones del juego, una cantidad notablemente inferior.La busqueda de las estrategias a traves de las diferentes posiciones deljuego se lleva a cabo sobre su arbol de jugadas, y la manera de proceder paraencontrarlas es mediante induccion regresiva, esto es, analizando en primerlugar las diferentes situaciones nales del juego y a continuacion ir remon-tando en el arbol de jugadas para conocer los estados por los que se debepasar y as los movimientos a ejecutar para conseguir la posicion nal desea-da.
Retomando los conceptos previos a cerca de arboles vistos en el captulo2 (hacer referencia), podemos denir una estrategia en base a los subarbolesdel arbol de jugadas.(NO ENTIENDO LA DEFINICIION DE ESTRATEGIA APARTADOS2 Y 3)Denicion 3.0.4 (Estrategia).(pg 686 beckcombinatorialgames) Una estra-tegia para el primer (resp. segundo) jugador es un subarbol G0del arbol dejugadas Gtal que:(1) la raz de Gesta en G0(2) in G0each even-distance (odd-distance) vertex has out-degree 1(3) in G0each odd-distance (even-distance) vertex has the same out-degreeas in the whole game-tree G.Una estrategia de empate o de victoria para el primer (segundo) jugadores un subarbol G0del arbol de jugadas Gque satisface (1)-(2)-(3) y cada ho ja34CAPITULO 3.
ESTRATEGIAS GANADORASde G0corresponde a una situacion de empate o victoria para el primero, osolo victoria para el primero (situacion de empate o victoria para el segundo,o solo victoria para el segundo).Introduccion de . Appendix C- Strategy pg679-690?”de (BeckCombinato-rialGames.pdf )(estos dos no les veo la utilidad) puede ser interesante (https://www.sciencedirect.com/science/article/pii/0166218X85900708)o tambien 2.2Wining a game de (http://www.
mathe2.uni-bayreuth.de/stoll/papers/games12.pdf )2.Outcome classes def de winning strategies y de outcome clases + prop de(https://upcommons.upc.
edu/bitstream/handle/2117/78323/memoria.pdf )3.0.
1. Arbol de decisiones(de mas utilidad para estra-tegias ganadoras)def de “T5-Positional Games- remarks+ “T5-2.Strategy Stealing- “T5-thm5.1 + proof”del (pg 72 BeckCombinatorialGames.pdf )algoritmos minimax y montecarloconcepto de weak win, strong win, strong draw.
.. “1.4 Game TheoreticValues”de (ideas sobre estrategias dominadas y reversibles en “def2.
20, lema2.21 + prueba, def 2.22, lema 2.
23 + prueba”de (http://www.mathe2.uni-bayreuth.de/stoll/papers/games12.pdf )”T5-7.Clasication of all nite hypergraphs”de (BeckCombinatorialGa-mes.
pdf )”T6-thm 6.1, thm6.2 Weak Win by Ramsey thy + proof”de (BeckCom-binatorialGames.pdf )”T10-thm1.4 Erdos-Selfridge + prueba”de (BeckCombinatorialGames.pdf )”T11-1.Pairing Strategy”de (BeckCombinatorialGames.
pdf )concepto de strongly solved, weakly solved, ultra weakly solvedCaptulo 4Estudio de muestraEstudio completo ya realizado del “3 en raya. odel “nim”3en raya es un empate y no empate fuerte (pg 44-49 BeckCombinatorial-Games) numero estrategias (pg 682 beckcombinatorialgames)3536CAPITULO 4. ESTUDIO DE MUESTRACaptulo 5Estudio particularEstudio de”La dama 2.Elperro y las cabras”3738CAPITULO 5. ESTUDIO PARTICULARApendice AReglas domineeringFotograar libro Winning ways for your matematical plays3940APENDICE A. REGLAS DOMINEERINGApendice BEnunciados juegos canariosFotocopia ho ja de Eduardo4142APENDICE B. ENUNCIADOS JUEGOS CANARIOSApendice CReglas a jedrezWinning ways ?4344APENDICE C. REGLAS AJEDREZApendice DReglas 3 en rayaWinning ways?4546APENDICE D.
REGLAS 3 EN RAYAApendice EReglas damaswinning ways ?4748APENDICE E. REGLAS DAMASBibliografaDenicion de juego http://dle.rae.es/?id=MaS6XPk teorema ramsey http://www.ams.org/journals/tran/1971-159-00/S0002-9947-1971-0284352-8/S0002-9947-1971-0284352-8.pdf Winning Ways https://annarchive.
com/les/Winning1 M. Albert, R.Nowakowski, D. Wolfe, Lessons in Play, A.
K. Peters (2007)criterio ganador http://math.uchicago.edu/ ac/cgt.
pdfthm 3.1.4 https://ia800906.us.
archive.org/6/items/arxiv-1107.5092/1107.5092.pdf2 https://ia801001.
us.archive.org/26/items/arxiv-1202.4652/1202.4652.
pdfthm fundamental TJC Aaron N.Siegel Combinatorial Game Theory 2013.pdf3 Poole, David; Mackworth, Alan. “3.5 Uninformed Search StrategiesChapter 3 Searching for Solutions Articial Intelligence: Foundations of Compu-tational Agents, 2nd Edition”. artint.
info. Retrieved 7 December 2017. 4 Poole, David; Mackworth, Alan. “3.6 Heuristic Search Chapter 3 Sear-ching for Solutions Articial Intelligence: Foundations of Computational Agents,2nd Edition”. artint.info.
Retrieved 7 December 2017. 5 https://www.sciencedirect.com/science/article/pii/016800729390036D6 http://theory.cs.princeton.edu/complexity/book.
pdf7 Soring Play COmbinatorial Games, FRaser IAn Dowall Stewart, 20118 https://www.nada.kth.se/ johanh/complexitylecturenotes.pdf9 AllanScottPhDThesis.pdf10 R. E.
Stearns, J. Hartmanis, and P. M. L. II.
Hierarchies of memorylimited computations. In FOCS, pages 179-190. IEEE, 1965.
11 W. Savitch. Relationship between deterministic and nondeterminis-tic tape complexities. Journal of Computer and System Sciences, 4:177-192,1970.
12 https://plato.stanford.edu/entries/computational-complexity/13 J. Hartmanis and R. E. Stearns. On the computational complexityof algorithms. Transactions of the American Mathematical Society, 117:285-306, 196549
