Traba jo de Fin de Grado Juegos Combinatorios Ignacio Amat Perez Universidad de La Rio ja 2 Dedicado a mi familia I II Agradecimientos que dicultad tiene el juego

Traba jo de Fin de Grado
Juegos Combinatorios
Ignacio Amat Perez
Universidad de La Rio ja

2

Dedicado a
mi familia
I

II

Agradecimientos
que dicultad tiene el juego?.
Entonces uno puede comenzar a buscar respuesta a esta pregunta analizando
el grafo del arbol de juego del mismo y de este modo obtener de forma exacta
el numero de casos favorables, desfavorables o neutros (empate), de forma que
dada una posicion cualquiera sea facil establecer la complejidad del mismo
teniendo en cuenta las jugadas posibles. Esto, a primera vista, parece una
opcion factible en el proceso de busqueda de la dicultad de un juego, pero
por 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 en
3 estados diferentes, sean cruz, crculo o en blanco, se tiene que existen 3 9
situaciones diferentes. Sin embargo, hay que tener presente que muchos de
estos estados son imposibles o incongruentes dada la naturaleza del juego;
ademas, por las caractersticas del tablero y las simetras del mismo se tienen
en total 765 posibilidades diferentes. Parece obvio que analizar todos estos
estados, 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. Por
lo tanto, surge ahora la pregunta: >es posible calcular todos y cada uno de
los estados de un juego? , y en caso de que esto sea posible, >cuanto tiempo
llevara calcularlos? ,>de que forma se podran calcular? ,>sera esta forma
de 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-
17

18
CAP
ITULO 2. COMPLEJIDAD
das con anterioridad para poder comprender mas facilmente las propiedades
de un juego. Por desgracia, solo unos pocos juegos han logrado ser resuel-
tos por completo, siendo posible conocer todas las diferentes posiciones del
juego. Para otros muchos se conocen ciertas propiedades como el tama~no del
arbol de decision o a que clase de complejidad computacional pertenece y
otros para los que no se conoce con exactitud. Sobre este ultimo concepto
traba jaremos mas en profundidad en este captulo, por ser de gran interes a
la hora de poder ver la clase de complejidad a la que pertenece un juego, y
de esta forma poder tener conocimiento del tiempo que requerira realizar los
calculos.
Entrando un poco mas en contexto, la complejidad computacional es un
tema de estudio muy importante para los matematicos, hasta tal punto que
en el a~no 2000 el Clay Mathematics Institute ofrece un millon de dolares
para aquel que consiga resolver el problema Pvs NP . Aqu no se demostrara
dicha cuestion, pero se estudiaran distintas clases de complejidad y la relacion
existente entre ellas.
Sin mas preambulos, veamos ahora diferentes formas de medir y clasicar
la complejidad de un juego cualquiera.
2.1. Medidas de Complejidad La teora de juegos combinatorios, a la hora de poder estudiar los juegos en
profundidad y mas en concreto propiedades relacionadas con su complejidad.
Por ello, se han establecido diferentes tipos de medidas para catalogar esta
complejidad y clasicar as los mismos.
En primer lugar, veremos la complejidad del estado-espacio que estudiara
el numero de posiciones posibles desde la posicion inicial; despues se estudiara
todo lo relacionado con el arbol de juego, esto es, ya sea su tama~no, la
complejidad de su arbol de decision o de su arbol de jugadas. Por ultimo, se
analizara la complejidad computacional y la pertenencia de un juego a los
diferentes 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 complejidad
del juego, se emplearan diferentes algoritmos de busqueda para encontrar, da-
da una disposicion inicial, el coste de llegar a una posicion determinada. Estos
algoritmos de busqueda poseen a su ver diferentes propiedades como saber
si es un metodo de busqueda de la solucion es optimo o no, si es completo o
su complejidad en espacio y tiempo.

2.1. MEDIDAS DE COMPLEJIDAD
19
Denicion 2.1.1. Se dice que un algoritmo de busqueda en un grafo de un
juego 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 un
juego Jes optimo si en el momento en que encuentra una solucion (posicion
determinada deseada), esta es la mejor (en el sentido en que es la menos
costosa de alcanzar). (PUEDE QUE NO QUEDE CLARO EL CONCEP-
TO)(CREO QUE ESTE NO INTERESA VERLO, PORQUE EL GRAFO
DE UN JUEGO NO TIENE COSTES)
Denicion 2.1.3. La complejidad-tiempo de un algoritmo de busqueda en
un grafo de un juego Jes la cantidad de tiempo que lleva ejecutarlo del
peor de los casos posibles.
Este se expresa en terminos del camino de mayor
longitud ( m) y del mayor factor de ramicacion de sus nodos ( h).
Denicion 2.1.4. La complejidad-espacio de un algoritmo de busqueda en
un grafo de un juego Jes la cantidad de memoria que se utiliza para ejecutarlo
en 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 descripcion
parezcan complejos en cuanto al numero de posiciones diferentes que pueden
existir, pero que en realidad debido a ciertas propiedades como simetras o
estados incongruentes, este numero sea mucho menor del esperado. En otros
casos, este hecho puede darse de forma inversa; es decir, juegos que en un
principio puedan parecer simples, pero que en realidad no sea as.
Demos una denicion mas formal sobre este concepto de complejidad
estado-espacio:
Denicion 2.1.5 (Complejidad estado-espacio) .El termino complejidad del
estado-espacio de un juego combinatorio Jse dene como el cardinal del
conjunto 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 de
posiciones distintas que se pueden alcanzar en un juego. Por ello hay que
tener en cuenta que al calcular el total de las posiciones, no todas ellas son
validas ya que el juego puede presentar simetras, lo que producira estados
repetidos, o tambien situaciones imposibles o estados ilegales.

20
CAP
ITULO 2. COMPLEJIDAD
Ejemplo 2.1.1. Teniendo en cuenta las reglas de un simple juego como el
famoso 3 en raya, tal y como se menciono con anterioridad, existen 3 estados
diferentes posibles para cada una de las casillas (cruz, crculo o en blanco), lo
que supone un total de 39
= 19683 posiciones. Sin embargo, en estos calculos
se 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 no
importa en cual de el las lo ha puesto, ya que la situacion actual del juego
sigue siendo la misma. Como entre las posibilidades calculadas, hay casos
repetidos, estos deben ser descartados de las cuentas realizadas. Ademas, si se
considera 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, o
que ambos jugadores posean 3 en raya. Como es obvio, estos casos tambien
deben ser descartados puesto que no cumplen las reglas del juego y por ello
son escenarios imposibles en el desarrollo de una partida. De esta forma,
los posibles estados diferentes de este juego se reducen a 765, algunos de los
cuales 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 deben
ser tenidos en cuenta a la hora de estudiar el estado-espacio de un juego, la
tarea de calcular exactamente cual sera dicho numero no sera facil puesto
que en ciertas ocasiones los calculos se vuelven demasiado complejos que
aun no han podido ser estudiados por completo. Ante estos casos, casos
en que no se sabe como obtener dicho numero exacto de estados o no sea
posible calcularlo con los procedimientos actuales, se procedera a establecer
lmites con la nalidad de acotar dicho numero y poder tener un conocimiento
estimado de la complejidad del juego.
A la hora de abordar este problema, se plantean dos vas diferentes, por
un lado la busqueda no informada y por otro la busqueda informada; cada
cual con sus respectivos metodos de busqueda.
Segun denieron Poole y Mackworth 3, los siguientes tres algoritmos
de busqueda se caracterizan por ser metodos de busqueda estado-espacio
no informados, considerados as porque no consideran ninguna informacion
sobre los diferentes estados ni los ob jetivos para decidir que camino explorar
en primer lugar, son por lo tanto algoritmos genericos que no tienen en cuenta
los intereses del problema:
Denicion 2.1.6 (Algoritmo de busqueda profunda (ABP)) .Metodo para
recorrer y buscar ciertas estructuras en un grafo. Para ello se toma un nodo

2.1. MEDIDAS DE COMPLEJIDAD
21
como inicio (normalmente le nodo raz, salvo interes en otro nodo particular)
y se recorren sus ramas tan lejos como sea posible antes de retroceder al
nodo previo y tomar otra rama continuando con el procedimiento (NO SE
SI QUEDA CLARA LA EXPLICACI 
ON).
Denicion 2.1.7 (Algoritmo de busqueda en anchura (ABA)) .Metodo para
recorrer y buscar estructuras en un grafo. Se toma un nodo inicial (normal-
mente le nodo raz, salvo interes en otro nodo particular) y a continuacion
se recorren todos los nodos inmediatamente inferiores antes de proceder con
la busqueda en el siguiente nivel.
(CREO QUE ESTE NO INTERESA VERLO, PORQUE EL GRAFO
DE 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 con
el menor coste al nodo deseado. Se toma un nodo inicial (normalmente le
nodo 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 QUEDA
CLARO??)
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 es
completo (salvo ramicacion innita de algun nodo), su complejidad-tiempo
es 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 de
busqueda 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 GRAFO
DE 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 jugadas
Retomando la denicion 1.2.9 (hacer referencia) del arbol de jugadas de
un 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 siga

22
CAP
ITULO 2. COMPLEJIDAD
sus correspondientes ramas asociadas a los posibles movimientos disponibles
dado 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 juegos
combinatorios conocidos, sin embargo podemos destacar algunos en que esta
idea de arbol no es del todo util puesto que existen situaciones en que algunos
estados 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 la
puntuacion total y no por quien ha sido el ultimo en mover. Surge as una
nuevo 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 J
tiene un grafo de juego nito si tiene un grafo directo bipartido nito cuyo
conjunto de nodos (estados del juego) Qesta dividido en dos conjuntos. Por
un lado el conjunto de los nodos para los que el jugador Izquierda puede
mover ( JI
) y por otro, el conjunto para los que el jugador Derecha puede
dirigirse ( 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 grafo
directo y xes un vertice de H. Se tiene que Ges nito si Hes nito. Las
opciones de Gson juegos de la forma G0
= ( H; x 0
), donde existe un arco
directo 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 de
nodos corresponde al numero total de estados diferentes del juego J. Este
no es el caso, es mucho mas complicado que eso, las posiciones o estados
diferentes 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 que
incrementa el numero de nodos y as el tama~no del arbol de juego.
Vease esto con un simple ejemplo, como es el DOMINEERING (gura 1
y 2 dibujo esquema + reglas anexo) en donde como se observa en las guras 1
y 2, es posible alcanzar un estado de mas de una forma diferente, sobre todo
cuantas mas piezas haya sobre el tablero. Por lo tanto, el arbol de jugadas
es mas complejo que el de estado-espacio.
(gura 1 y 2)
Para algunos de estos juegos no siempre es posible obtener el numero
exacto de estados, por ello se han establecido formas para obtener un lmite
superior que acote este numero. Sin embargo, en otro tipo de juegos el tama~no

2.1. MEDIDAS DE COMPLEJIDAD
23
del arbol de jugadas puede ser innito debido a la repeticion de estados por
tener 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 es
un juego? o >que dicultad tiene?, surge a su vez la pregunta de >como se
puede medir esta complejidad? Sabiendo que cada juego es a priori diferente
del resto, ya sea por el tama~no, su forma del tablero, por sus reglas o por el
numero de piezas que intervienen; trataremos de agrupar algunos de ellos en
diferentes clases de complejidad y entenderlas un poco mas.
Para ello, es necesario estudiar estas complejidades teniendo en cuenta el
concepto 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 modelo
abstracto de computacion a traves del cual parece posible recrear todos los
diferentes modelos y estados con la mayor eciencia, es decir, con el menor
gasto posible. Al hablar del concepto de eciencia computacional aparece
tambien el termino de la Ogrande, que se emplea para medir la eciencia
de un algoritmo o metodo mediante el numero de operaciones basicas que
este 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 funcion
T :N ! Ntal que T(N ) es el maximo de operaciones basicas que el
algoritmo es capaz de realizar con datos de tama~no n.
Veamos mas formalmente estos conceptos para proseguir con el estudio
de 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 ! N
entonces decimos que:
1. f= O(g ) si existe una constante ctal que f(n ) cg(n ) para cada nlo
sucientemente 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 nsucientemente
grande.
5. f= !(g ) si g= o(f ).

24
CAP
ITULO 2. COMPLEJIDAD
Denicion 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 es
una 7-tupla M=
donde; Q
es un conjunto nito no vaco de estados. es un conjunto nito no vaco de smbolos.
b
2 es el smbolo del vaco.
n f bg es el conjunto de smbolos de entrada. q
0 2 Q
es 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 I
es un desplazamiento a izquierda y Dun desplazamiento a derecha.
Denicion 2.1.16 (Computo de una funcion y tiempo de ejecucion) .(6
def 1.4) Sea f:f0;1 g
! f 0;1 g
y sea T:N ! Nalgunas funciones, y
sea Muna maquina de Turing. Decimos que M computa f en T(n)-tiemposi
para todo x2 f 0;1 g
, si Minicializa a la conguracion del principio de la
entrada x, entonces despues de al menos T(jx j) pasos se detiene con f(x ) en
la cinta de salida.
Decimos que M computa f si computafen un tiempo T(n ) para alguna
funcion T:N ! N.
Teorema 2.1.2 (Jerarqua de espacios) .(10) Para cada funcion de un
espacio 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) Una
maquina de Turing no determinista solo puede computar valores de funciones
que tomen valores 0 y 1. LA maquina toma el valor 1 con un valor de entrada
x 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 devuelve
valor 0.
Denicion 2.1.18. (8 def 5.3) Una maquina de Turing no determinista M
se 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 COMPLEJIDAD
25
Denicion 2.1.19. (8 def 5.4) Una maquina de Turing no determinista
M se ejecuta en un espacio T(n ) si para cada dato de entrada de longitud
n , cada computacion de Mvisita como mucho S(n ) regiones de la cinta de
traba jo.
Ahora s que estamos en condiciones de poder presentar las diferentes
clases de complejidad y comprender mejor de esta forma como categorizar los
juegos combinatorios segun su dicultad para encontrar todas las soluciones.
Esta clasicacion se realiza teniendo en cuenta dos aspectos diferentes; por
un lado si se tiene en cuenta el tiempo de ejecucion del algoritmo entonces
se hablara de complejidad-tiempo, por otro lado, si se tiene en cuenta el
espacio ocupado en memoria durante la ejecucion del algoritmo se hablara
de complejidad-espacio.
Clases complejidad-tiempo 12
Suponiendo que t( n ) es una funcion construible en tiempo y que Tes
el modelo de las clases de las maquinas de Turing, se tiene que la clase
TIME (t( n )) es como sigue:
TIME (t( n )) = fX f 0;1 g
:9N 2T 8n (time
N(
n ) t( n )) y Ndecide
X g
Denicion 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 no
determinista 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 maquinas
de Turing no deterministas son capaces de ejecutar a su vez operaciones
deterministas. Veanse ahora las clases de complejidad computacional mas estudiadas en
cuanto a la complejidad-tiempo se reere.
Denicion 2.1.22. (8, def 4.2) Dado un conjunto A, decimos que A2P
sii hay una maquina de Turing determinista que acepta a Ay se ejecuta en
un tiempo O(n k
) para alguna constante k.

26
CAP
ITULO 2. COMPLEJIDAD
Denicion 2.1.23. (8,def 5.6) Dado un conjunto A, decimos que A2N P
sii hay una maquina de Turing no determinista que acepta a Ay se ejecuta
en 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 sii
hay una maquina de Turing determinista que acepta a Ay se ejecuta en un
tiempo O(2 n
k
) para alguna constante k.
Clases complejidad-espacio
Denicion 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 no
determinista 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 = NPSPACE
Esto sigue del hecho que el cuadrado de una funcion polinomica s(n ) sigue
siendo 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 A2
P S P AC E sii hay una maquina de Turing determinista para alguna constante
k 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 A2
N P S P AC E sii hay una maquina de Turing no determinista para alguna
constante 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 E
sii hay una maquina de Turing determinista para alguna constante kque
computa la funcion caracterstica de Aen un espacio O(2 n
k
).
hardness, completness.. bilibi

2.2. EJEMPLOS
27
Lmites superior e inferior Puede que sea adecuado todo el contenido de: . O
n globally sparsey Ramsey
graphs”del sitio
2.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 )

28
CAP
ITULO 2. COMPLEJIDAD

Captulo 3
Estrategias ganadoras
Uno de los principales ob jetivos de la Teora de Juegos general y de la
Teora 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 algunas
de 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 asuncion
por 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 analiza
previamente las posibles consecuencias que tendra dicho movimiento para el
desarrollo del juego actuando en consecuencia. Es decir, una estrategia es
una planicacion de las jugadas que un jugador realizara en cada uno de los
diferentes estados del juego.
Estos conceptos mas bien teoricos, ya que si fuesemos capaces de, a cada
estado, calcular todos uno no perdera nunca; sin embargo esto no es as. Por
lo general cuando decidimos jugar a un juego cualquiera, lo que uno puede
pensar que esta llevando a cabo, una serie de pasos que considera adecuados,
no es una estrategia propiamente dicha. Uno se limita a ganar la jugada
actual, a no dejar que el oponente en su siguiente turno termina la partida
llevandose la victoria sino hacer todo lo posible para ser uno mismo quien lo
consiga, o en su defecto terminar en empate.
Para dar una denicion formal de estrategia, se debe presentar antes la
nocion 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 subconjuntos
29

30
CAP
ITULO 3. ESTRATEGIAS GANADORAS
arbitraria de Vque representa la familia de conjuntos ganadores. Los dos
jugadores, ocupan alternadamente las posiciones del tablero Vque permane-
cen libres. El jugador que primero ocupe todos los elementos de un conjunto
ganador A2 F gana, de otro modo el juego termina en empate.
Notar que un juego posicional puede denirse tambien solo a traves de
su 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 conjunto
subsecuencias de longitud par (resp. impar) de diferentes elementos del ta-
blero V, y su rango es V. Si denotamos como x
1; x
2; x
3; : : :
los movimientos
del primer jugador y como y
1; y
2; y
3; : : :
los del segundo, entonces el i-esimo
movimiento x
i (resp.
y
i) esta determinado por
Strcomo sigue
x i =
Str (x
1; y
1; x
2; y
2; : : : ; y
i 1)
2 V n f x
1; y
1; x
2; y
2; : : : ; y
i 1g
( resp: y
i=
Str (x
1; y
1; x
2; y
2; : : : ; y
i 1; x
i)
2 V n f x
1; y
1; x
2; y
2; : : : ; y
i 1; x
ig
)
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 jugador
signica que de todas las formas posibles en que el primer jugador siga la
estrategia Strpara elegir su proximo movimiento es una victoria (o empate)
para el. Formalmente, cada jugada
x 1 =
S tr (; ); 8 y
1; x
2=
S tr (x
1; y
1)
; 8 y
2; x
3=
S tr (x
1; y
1; x
2; y
2)
; 8 y
3; : : : ;
8y
N= 2
(3.1)
si N =jV jes par, y
x 1 =
S tr (; ); 8 y
1; : : : ;
8y
(N 1) =2 ; x
(N +1) =2 =
S tr (x
1; y
1; x
2; y
2; : : : ; 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 segundo
jugador signica que de todas las formas posibles en que emplee su estrategia
Str para encontrar su proximo movimiento es una victoria (o empate) para
el. Formalmente, cada jugada
8x
1; y
1=
S tr (x
1)
; : : : ; 8x
(N= 2); y
N= 2=
S tr (x
1; y
1; x
2; y
2; : : : ; x
N=2) (3.3)

31
si N es par, y
8 x
1; y
1=
S tr (x
1)
; 8 x
2; y
2=
S tr (x
1; y
1; x
2)
; 8 x
3; : : : ;
8x
(N +1) =2 (3.4)
si N es impar, es una victoria (o empate) para el segundo jugador.
En ambos casos
x i 2
V n f x
1; y
1; x
2; y
2; : : : ; y
i 1g
y y
i2
V n f x
1; y
1; x
2; y
2; : : : ; y
i 1; x
ig
(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. Se
entiende por estrategia optima a las estrategias ganadoras y a las estrategias
de empate (cuando no existe estrategia ganadora). Ahora bien, tal y como
se se vio en el apartado de Complejidad (hacer referencia ??) a la hora de
calcular los diferentes estados del juego o el tama~no del arbol de jugadas,
por lo general se establecan lmites para acotar el numero exacto. Calcular
el numero total de estrategias optimas no va a ser una excepcion, esta tarea
es ardua y complicada, es mas facil establecer el numero total de estrategias
que el de estrategias optimas.
(EL N o
DE 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, pese
a que ya se conozca el ganador), el total de estrategias se puede acotar supe-
riormente por NeN
!
(ver pg 681 beckcombinatorial games). Sin embargo, es
posible dar un resultado exacto del numero total de estrategias.
Sea un juego tal que x
1; x
2; x
3; : : :
las casillas ocupadas por el primer
jugador y y
1; y
2; y
3; : : :
las ocupadas por el segundo jugador,con un esquema
de jugadas x
1; y
1; x
2; y
2; x
3; y
3; : : :
.
Sea Struna estrategia del segundo jugador, que viene denida de forma
que el i-esimo movimiento y
i depende de los anteriores,
y
i =
S tr (x
1; y
1; x
2; y
2; : : : ; y
i 1; x
i2
V n f x
1; y
1; x
2; y
2; : : : ; y
i 1; x
ig
.
As, dado el primer movimiento del primer jugador x
1, la funcion
Str
determina unicamente y
1(
6
= x
1), el primer movimiento del segundo jugador.
De igual forma, dados x
1; x
2,
Str determina unicamente y
2(
=
2 f x
1; y
1; x
2g
), y
as sucesivamente. Se puede escribir que
yi =
S tr (x
1; y
1; x
2; y
2; : : : ; y
i 1; x
i) =
S tr
i(
x
1; x
2; : : : ; x
i)

32
CAP
ITULO 3. ESTRATEGIAS GANADORAS
ya que los y
1; y
2; : : : ; y
i 1 vienen determinados por los
x
1; x
2; : : : ; x
i 1. Por
tanto, Strpuede considerarse como un vector S tr= (S tr
1; S tr
2; S tr
3; : : :
)
de cada i-esima componente S tr
ide la estrategia
Str. El numero total de
componentes S tr
1es por denicion (
N1)N
, el de S tr
2es (
N3)N
(N 2)
,
el de S tr
3es (
N5)N
(N 2)( N4)
, y as sucesivamente. Se sigue que el total
de estrategias de un juego es el producto
(N 1)N
(N 3)N
(N 2)
(N 5)N
(N 2)( N4)

= b
N= 2c 1
Y
i =0 (
N 1 2i) Q
i
j =0 (
N 2j)
= ee
N
log N=2+O(N )
: (3.6)
Ahora bien, si uno se pone a pensar detenidamente, total de estrategias
de un juego cualquiera puede ser una cantidad demasiado grande como para
poder probar cada una de ellas y determinar as cuales son las estrategias
optimas, es por ello que nos conformamos con calcular el total de estrategias
del juego, lo que supondra una cota superior para el numero de estrategias
optimas. Sin embargo, todas esas estrategias van a conducir a solamente 3 resulta-
dos posibles, sean estos victoria, derrote o empate. Por ello, suele decirse que
los juegos posicionales estan determinados. Siguiendo las ideas del teorema
de 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 en
dicho hipergrafo. Entonces existen unicamente tres alternativas diferentes: el
primer jugador tiene una estrategia ganadora, o el segundo jugador tiene una
estrategia ganadora, o ambos tienen una estrategia de empate.
Demostracion 3.0.2.No se incluira en este traba jo esta demostracion, pero
si 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 este
traba jo, puede encontrarse en la pg 683 de beckcombinaotrialgames.
Puesto que la Teora de Juegos Combinatorios (y la Teora de Juegos
general tambien) buscan resolver y encontrar la solucion a los diferentes jue-
gos, las estrategias optimas en cada estancia del juego requieren de jugadores

33
perfectos que puedan llevar a cabo dichas estrategias. El hecho de que sean
perfectos se reere a que conocen cuales son dichas estrategias optimas y que
no cometan en errores al llevarla a cabo. Sin embargo, en la practica esto no
ocurre, ya que ambos jugadores no conocen su estrategia optima y por tanto
cometen 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 a
seguir, esta debera obtenerse estudiando cada caso. Pero, en general, eso es
algo que ni los ordenadores mas potentes podran hacer dado el gran numero
de estrategias diferentes que existen, un ejemplo sera el a jedrez, que aun no
se es capaz de saber todas las estrategias optimas para cada estado del juego
debido a su complejidad y numero de estados diferentes. Por ello, en lugar
de examinar caso a caso cada una de las estrategias a seguir, se estudian las
diferentes posiciones del juego, una cantidad notablemente inferior.
La busqueda de las estrategias a traves de las diferentes posiciones del
juego se lleva a cabo sobre su arbol de jugadas, y la manera de proceder para
encontrarlas es mediante induccion regresiva, esto es, analizando en primer
lugar 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 debe
pasar y as los movimientos a ejecutar para conseguir la posicion nal desea-
da. Retomando los conceptos previos a cerca de arboles vistos en el captulo
2 (hacer referencia), podemos denir una estrategia en base a los subarboles
del arbol de jugadas.
(NO ENTIENDO LA DEFINICIION DE ESTRATEGIA APARTADOS
2 Y 3)
Denicion 3.0.4 (Estrategia).(pg 686 beckcombinatorialgames) Una estra-
tegia para el primer (resp. segundo) jugador es un subarbol G0
del arbol de
jugadas Gtal que:
(1) la raz de Gesta en G0
(2) in G0
each even-distance (odd-distance) vertex has out-degree 1
(3) in G0
each odd-distance (even-distance) vertex has the same out-degree
as in the whole game-tree G.
Una estrategia de empate o de victoria para el primer (segundo) jugador
es un subarbol G0
del arbol de jugadas Gque satisface (1)-(2)-(3) y cada ho ja

34
CAP
ITULO 3. ESTRATEGIAS GANADORAS
de G0
corresponde a una situacion de empate o victoria para el primero, o
solo victoria para el primero (situacion de empate o victoria para el segundo,
o solo victoria para el segundo).
Introduccion de . A
ppendix 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 montecarlo
concepto de weak win, strong win, strong draw… “1.4 Game Theoretic
Values”de (ideas sobre estrategias dominadas y reversibles en “def2.20, lema
2.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 solved

Captulo 4
Estudio de muestra
Estudio completo ya realizado del “3 en raya. o
del “nim”
3en raya es un empate y no empate fuerte (pg 44-49 BeckCombinatorial-
Games) numero estrategias (pg 682 beckcombinatorialgames)
35

36
CAP
ITULO 4. ESTUDIO DE MUESTRA

Captulo 5
Estudio particular
Estudio de”La dama 2
.
El
perro y las cabras”
37

38
CAP
ITULO 5. ESTUDIO PARTICULAR

Apendice A
Reglas domineering
Fotograar libro Winning ways for your matematical plays
39

40
AP
ENDICE A. REGLAS DOMINEERING

Apendice B
Enunciados juegos canarios
Fotocopia ho ja de Eduardo
41

42
AP
ENDICE B. ENUNCIADOS JUEGOS CANARIOS

Apendice C
Reglas a jedrez
Winning ways ?
43

44
AP
ENDICE C. REGLAS AJEDREZ

Apendice D
Reglas 3 en raya
Winning ways?
45

46
AP
ENDICE D. REGLAS 3 EN RAYA

Apendice E
Reglas damas
winning ways ?
47

48
AP
ENDICE E. REGLAS DAMAS

Bibliografa
Denicion 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.pdf
thm 3.1.4 https://ia800906.us.archive.org/6/items/arxiv-1107.5092/1107.5092.pdf
2 https://ia801001.us.archive.org/26/items/arxiv-1202.4652/1202.4652.pdf
thm fundamental TJC Aaron N.Siegel Combinatorial Game Theory 2013.pdf
3 Poole, David; Mackworth, Alan. “3.5 Uninformed Search Strategies
Chapter 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/016800729390036D
6 http://theory.cs.princeton.edu/complexity/book.pdf
7 Soring Play COmbinatorial Games, FRaser IAn Dowall Stewart, 2011
8 https://www.nada.kth.se/ johanh/complexitylecturenotes.pdf
9 AllanScottPhDThesis.pdf
10 R. E. Stearns, J. Hartmanis, and P. M. L. II. Hierarchies of memory
limited 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 complexity
of algorithms. Transactions of the American Mathematical Society, 117:285-
306, 1965
49