Jugado es au omá icos basados en
á boles de búsqueda de Mon e Ca lo
T abajo de Fin de G ado
Cu so 2017–2018
Au o
Gab iel Da id Modia Pozuelo
Di ec o es
Gonzalo Méndez Pozo
An onio Sánchez Ruiz-G anados
Doble g ado en Ingenie ía In o má ica y Ma emá icas
Facul ad de In o má ica y Facul ad de Ma emá icas
Uni e sidad Complu ense de Mad id
Jugado es au omá icos basados en
á boles de búsqueda de Mon e Ca lo
T abajo de Fin de Doble G ado Ingenie ía In o má ica y
Ma emá icas
Depa amen o de In eligencia A i icial
Au o
Gab iel Da id Modia Pozuelo
Di ec o es
Gonzalo Méndez Pozo
An onio Sánchez Ruiz-G anados
Con oca o ia: Sep iemb e 2018
Doble g ado en Ingenie ía In o má ica y Ma emá icas
Facul ad de In o má ica y Facul ad de Ma emá icas
Uni e sidad Complu ense de Mad id
14 de sep iemb e de 2018
Dedica o ia
A Mima y Manolo.

Ag adecimien os
Es e abajo no hab ía sido posible sin:
Mis u o es An onio y Gonzalo que me han guiado y di igido, g acias
po su disposición y a ención.
Mi mad e, mi he mano y mi pad e que, cada uno a su mane a, han
hecho un camino más ácil pa a mi.
Alba, que incluso en la más ad e sa de las si uaciones ha es ado a mi
lado.
Alicia, que an o en clase como en casa siemp e nos hemos apoyado.
Jose An onio, Miguel, Ma a y odos mis compañe os con los que he
compa ido innume ables ho as de es udio, abajo y dedicación.
A odos ellos, g acias.
ii
Resumen
Dada la eno me can idad de juegos exis en es, una p egun a ecu en e
ha sido ¿Cuál es la mejo es a egia a segui pa a maximiza mi bene icio? en
o as palab as, ¿Qué acciones debo elegi en e las posibilidades que engo
pa a ob ene la mayo ecompensa posible? Es a cues ión, al da le una pe s-
pec i a o mal esul a no se i ial, cada con igu ación del able o iene una
p obabilidad asociada de gana , de inida po odos los posibles desenlaces
que iene el juego desde esa posición. Sin emba go, ob ene es e alo es im-
posible compu acionalmen e ya que es o implica ía e isa odas las posibles
pa idas dado que el núme o de es as es descomunal. Pa a da solución a es o,
exis en di e sos algo i mos que in en an ap oxima es e alo , no malmen e
mezclando el conocimien o p e io del dominio con la búsqueda exhaus i a
en el conjun o de odas las pa idas, pa a comp oba si una acción mejo a
nues a si uación ac ual.
En es e abajo se p esen a Mon e Ca lo T ee Sea ch, un algo i mo que
in oduce una o ma comple amen e dis in a de es ima la p obabilidad de
gana de cada es ado de la pa ida. El mé odo se á gene a simulaciones de
pa idas en las que las decisiones se oman de o ma alea o ia. De es a o ma,
pod emos calcula el po cen aje de eces que una simulación esul a ic o-
iosa en compa ación con las eces que se ha simulado, dándonos así una
ap oximación del alo buscado. Ve emos que cuan as más simulaciones lan-
cemos, el esul ado se á más ajus ado a la ealidad. Conoce emos 2 e siones,
la e sión dinámica o MCTS, y la e sión plana o PMCTS. In oduci emos
mé odos de op imización y una pe spec i a eó ica del uncionamien o.
P oba emos es e algo i mo en juegos, y pa a ello ob end emos di e sas
implemen aciones de las 2 e siones y las adap a emos pa a juga al Re-
e si y al Ajed ez. Los ad e sa ios a ba i se án algo i mos a ios que i án
aumen ando g adualmen e su di icul ad y nos obliga án a i adap ando los
algo i mos y mejo ándolos pa a que sean capaces de domina .
Po úl imo in oduci emos algunos algo i mos u ilizados en el campo de
la In eligencia A i icial conocido como ap endizaje au omá ico o Machine
Lea ning, pa a que el lec o posea las he amien as necesa ias pa a en en-
de el uncionamien o del jugado au omá ico más po en e que exis e en la
ix

Índice de igu as
2.1. Ejemplo de á bol de decisión pa a un es ado dado en el juego
del esen aya.......................... 14
2.2. Simpli icación de la búsqueda de caminos en GPS . . . . . . . 17
2.3. Ob ención inicial de un á bol de juego . . . . . . . . . . . . . 18
2.4. Ejecución de la inducción hacia a ás en Minimax . . . . . . . 19
2.5. Comienzo del juego en el Re e si . . . . . . . . . . . . . . . . 21
2.6. Visualización de las casillas más y menos p o echosas . . . . . 23
2.7. Piezas del ajed ez y colocación inicial . . . . . . . . . . . . . . 24
3.1. Ejemplo de selección u ilizando UCB . . . . . . . . . . . . . . 28
3.2. Ejemplo de selección u ilizando UCT . . . . . . . . . . . . . . 30
3.3. Resul ado de una i e ación de MCTS . . . . . . . . . . . . . . 32
4.1. Resul ados de usa o no conocimien o del dominio con 750
simulaciones............................ 52
4.2. Compa ación de pa idas ganadas y pe didas en los di e en es
en en amien os.......................... 53
4.3. Visualización de los esul ados de los expe imen os . . . . . . 54
5.1. Reg esión (Izquie da) y clasi icación (de echa) . . . . . . . . . 62
5.2. Di ección del g adien e y p oblemas de elegi e óneamen e el
pa áme o α............................ 64
x ii
Índice de ablas
2.1. Modelo de disposición de la o ma no mal pa a dos jugado es 12
2.2. Dilema del p isione o plasmado en o ma no mal . . . . . . . 13
4.1. PMCTS y MCTS (70 simulaciones) s Random . . . . . . . . 41
4.2. PMCTS y MCTS (140 simulaciones) s Random . . . . . . . 42
4.3. PMCTS y MCTS (70 simulaciones) s búsqueda en p o undidad 44
4.4. PMCTS y MCTS (700 simulaciones) s búsqueda en p o un-
didad................................ 45
4.5. PMCTS y MCTS(140 simulaciones) s Alpha-be a (débil) . . 46
4.6. PMCTS y MCTS(140 simulaciones) s Alpha-be a ( ue e) . . 48
4.7. PMCTS (mejo ado y con 140 simulaciones) s Alpha-be a
( ue e) .............................. 49
4.8. PMCTS (750 simulaciones) s Alpha-be a ( ue e) . . . . . . 50
4.9. MCTS (70 simulaciones) s PMCTS (70 simulaciones) . . . . 51
4.10. Random (Blancas) s MCTS (Neg as) . . . . . . . . . . . . . 56
4.11. Random (Blancas) s PMCTS (Neg as) . . . . . . . . . . . . 57
4.12. MCTS(Blancas) s PMCTS (Neg as) . . . . . . . . . . . . . . 58
xix
Chap e 1
In oduc ion
Mo i a ion
One o he cu en challenges in A i icial In elligence is he de elopmen
o algo i hms o implemen e icien au oma ic playe s. These mus gi e a
answe , no only co ec bu also as wise as possible wi h he inali y o
winning he game hey we e designed o . This de elopmen is no i ial a
all.
The c ea ion o hese playe s, as he op imiza ion o hem o be be e
e e y ime, epo s bene i s u he han he wo ld o ideo games o able
games. A e all, he idea is o op imize he decision making p ocesses. Gi en
his, he e a e applica ions o hese algo i hms in economics, poli ics, e c.
The main p oblem is o decide which o he a ailable mo es mus be
chosen nex . Fo ha he mos di ec app oach is o explo e he game
ee and y o ind he bes op ion. This poin o iew is o e ed by some
algo i hms whose mos ema kable ep esen a i e is Minimax.
Howe e , al hough his is an op imal algo i hm, i p esen s a p oblem:
he gigan ic combina o ial explosion ha i gene a es. E en hough i o e s
good esul s o simple challenges, as soon as we y i in mo e complex
sys ems, i is impossible o ea .
The e a e se e al al e na i es o sol e his issue. Th oughou his wo k,
we will explo e one o hem: Mon e Ca lo T ee Sea ch, commonly sho ened
as MCTS. This algo i hm’s idea is, ins ead o gene a ing each and e e y
possible b anch in he game ee, o use s ochas ic p ocesses o choose which
node o expand, mo eo e , he way hey a e expanded will also ha e a e y
s ong p esence o andom elemen s. This way we ge o spend much less
memo y han wi h he adi ional app oaches. Fu he mo e, he de elop-
men o he ee will use simula ions o gene a e a heu is ic alue o each
1

2Chap e 1. In oduc ion
node, cha ac e izing hem acco ding o i hey a e mo e o less p omising,
op imizing he mo e elec ion p ocess.
Objec i es
We a e going o de ine some objec i es in o de o explo e he MCTS
algo i hm:
1. Ob aining a global ision o he p edecesso s o MCTS, as well as he
ools we will use.
2. Gi e a o mal explana ion o he unc ioning o MCTS as well as o
i ’s plain e sion known as PMCTS.
3. Ob ain an implemen a ion o MCTS o he game known as O hello,
compa e i wi h o he algo i hms and check how i ’s beha io imp o es
depending on he pa ame e chosen.
4. Implemen ing an MCTS based playe which is capable o playing chess
and check he di e ences wi h i ’s o hello e sion.
5. Re iewing he mos mode n app oaches using MCTS and he necessa y
ools o i .
In he conclusions sec ion, we will e iew how a we accomplished hem.
Memo y s uc u e
We will encompass he ma ked objec i es h oughou he memo y. The
i s chap e will gi e a heo e ical e iew o he algo i hms ha p eceded
MCTS as Minimax o Alpha-be a. In addi ion, i will p o ide a clea expla-
na ion o all he ools and si ua ions ha we will use in o he chap e s as
game heo y, game ee de elopmen , Chess, O hello, e c.
The second chap e will show he Mo e Ca lo T ee Sea ch algo i hm,
he way i wo ks and i ’s implemen a ion. On he o he hand, we will also
see a de ailed explana ion o PMCTS, he MCTS’ e sion wi hou g ow h.
Finally, we will analyze he possibili y o eusing memo y and how we can
app oxima e he heo e ical heu is ic o each node h ough simula ions.
In he hi d chap e we will ob ain an implemen a ion o MCTS and PM-
CTS. We will i ’s pe o mance wi h he some o he s algo i hms as Random,
Alpha-be a and Back acking in O hello and la e in Chess. We will show
and analyze he esul s ob ained. Nex we will modi y he pa ame e s so i
ge s be e esul s agains hei ad e sa ies.
1.3. Memo y s uc u e 3
Finally he ou h chap e will explain us how we can use machine lea n-
ing o imp o e he esul s ha MCTS o e s, o ha we will i s e iew
some o he cu ing edge machine lea ning algo i hms. Addi ionally we will
see how his has been applied o one o he mos popula a i icial in elligence
e en s o he las yea s: AlphaGo.
Capí ulo 1
In oducción
Mo i ación
Uno de los desa íos ac uales de la In eligencia A i icial es el desa ollo de
algo i mos pa a implemen a jugado es au omá icos e icien es. Es os deben
da una espues a no solo co ec a sino lo más ace ada posible con el in de
gana en el juego pa a el que se haya desa ollado. Es e desa ollo no es en
absolu o i ial.
La c eación de es os jugado es así como la op imización pa a que sean
cada ez mejo es, epo a bene icios más allá del mundo de los ideojuegos
o los juegos de able o. Al in y al cabo, se a a de op imiza la oma de
decisiones, dado es o, exis en aplicaciones de es os algo i mos pa a emas
como economía, polí ica, e c (B ams, 2001).
El p oblema p incipal es decidi cuál de las jugadas disponibles se debe
elegi a con inuación. Pa a ello, lo más di ec o es in en a p e e las jugadas
a las que podemos llega desde la posición en la que nos encon amos. La
es uc u a donde se almacenan las jugadas p edichas es conocida como el
á bol de juego. Es a es la ap oximación que o ecen algunos algo i mos de los
cuales el mayo exponen e es conocido como Minimax, el cual explo a emos
en más de alle en el siguien e capí ulo.
El p oblema de es a ap oximación es que es imposible e isa odo el
á bol pa a sabe con ce eza lo bueno que es un nodo. Po an o, pa a juegos
complicados, se ha in en ado palia es a si uación p e iendo únicamen e un
núme o de e minado de jugadas, pe o es o implica que debemos se capaces
de alo a si son buenos o malos es ados in e medios, de los que a p io i no
enemos in o mación. Una o ma de e alua lo es ob ene conocimien o ex-
pe o del dominio, es deci , ideas o es a egias que se hayan p obado y que
sepamos con ce eza que uncionan. Aunque puede sona como una buena
idea, el conocimien o expe o es muy di ícil de consegui , además, p ác ica-
5
12 Capí ulo 2. T abajo elacionado
1/2 a21 a22 . . .
a11 u1((a11, a21)), u2((a11, a21)) u1((a11, a22)), u2((a11, a22)) . . .
a12 u1((a12, a21)), u2((a12, a21)) u1((a12, a22)), u2((a12, a22)) . . .
a13 u1((a13, a21)), u2((a13, a21)) u1((a13, a22)), u2((a13, a22)) . . .
.
.
..
.
..
.
....
Tabla 2.1: Modelo de disposición de la o ma no mal pa a dos jugado es
conocemos como unciones de u ilidad que nos de uel en los pagos a cie o
jugado ipo el ec o de acciones elegido po odos los jugado es. (Jackson,
2011). Con es os ing edien es, la o ma no mal nos ep esen a una ma iz
donde los elemen os de la misma son los pagos que eciben los jugado es en
dependencia de la combinación de es a egias elegidas po cada uno. Es a
ep esen ación unciona especialmen e bien cuando se a a de dos jugado es,
ya que se puede dispone en una ma iz bidimensional. La abla 2.1 nos da
un ejemplo de cómo se disponen los da os en o ma no mal.
Ejemplo: El dilema del p isione o
P obablemen e el ejemplo más conocido de juego simul áneo es el dilema
del p isione o. La si uación es la siguien e: "La policía sabe que dos indi i-
duos han come ido un c imen aunque no puede p oba lo, pe o sí que iene
p uebas pa a inc imina los po un deli o meno . An e la ala ma social le an-
ada, se en obligados a ene un culpable ápido, po lo que ponen a ambos
sospechosos en celdas sepa adas y les hacen la siguien e p opues a: Si dela-
as al o o como au o del c imen e pe donamos u deli o meno "(Aguado,
2015).
En es e supues o nos encon amos an e dos acciones posibles, a las que
llama emos “Calla ” y “Dela a ”. Suponiendo una condena de 1 año po el
deli o meno , 3 en caso de cumpli la sen encia po el mayo indi idualmen e
y 2 po hace lo de o ma conjun a nues o juego queda de la siguien e o ma:
(N, a, u)=({1,2},{Calla , Dela a }, u)
u1((Calla , Dela a )) = u2((Dela a , Calla )) = 3
u1((Dela a , Calla )) = u2((Calla , Dela a )) = 0
u1((Calla , Calla )) = u2((Calla , Calla )) = 1
u1((Dela a , Dela a )) = u2((Dela a , Dela a )) = 2
Podemos ep esen a el p oblema de o ma ex ensi a como se mues a en la
abla 2.2.

2.2. Teo ía de juegos 13
P isione o 1 P isione o 2 Calla Dela a
Calla 1,1 3,0
Dela a 0,3 2,2
Tabla 2.2: Dilema del p isione o plasmado en o ma no mal
Juegos secuenciales
A di e encia de los juegos simul áneos, en los secuenciales, los di e sos
agen es se al e nan a la ho a de oma decisiones, se conoce cada una de es as
al e nancias como u no. Después del u no de cada jugado encon amos el
juego en una nue a con igu ación, debido a las decisiones omadas. A es as
las llama emos es ados. Po an o, podemos de ini los juegos secuenciales
como una 4- upla:
(N, S, a, u)
Donde una ez más N={1, ..., n}es el conjun o de jugado es. Po su pa e
Ses el espacio de es ado. En lo que concie en a las acciones, a:N×S→A
es una unción que nos de uel e las acciones disponibles pa a un jugado
en cie o es ado, po an o A={{ai}i=1...k1,{ai}i=1...k2...}, es impo an e
des aca que una acción en es e caso es una unción ai∈acc ∈A ai:S→S.
Po úl imo, u:N×S→Res una unción que nos de uel e los pagos pa a
un jugado en cie o es ado.
Pa a expone la e olución empo al inhe en e a la secuencialidad de los
juegos no podemos ale nos de la o ma no mal, po eso amos a u iliza la
es uc u a de á bol pa a c ea lo que llama emos o ma ex ensi a. U iliza e-
mos los nodos pa a gua da los es ados del juego y los hijos de cada nodo
se án el esul ado de la aplicación de cie a acción a dicho es ado. A es e
ipo de á bol lo llama emos á bol de juego.
Á boles de juego y ejemplos
El caso más sencillo de á bol de juego apa ece cuando aba camos juegos
con N={1}. En es e caso odas las decisiones ecaen sob e el mismo agen e.
Es o acili a la explo ación del á bol, pues nos bas a con indaga lo su icien e
has a llega a un nodo e minal ganado . Después bas a con ejecu a las
acciones de inidas po el camino que lle a al nodo en cues ión. Ejemplos de
es os juegos pueden se el soli a io o el blackjack.
La explo ación de los á boles de juego se complica al ag ega más juga-
do es, pues los demás agen es end án, en p incipio, an o pode de decisión
como el p ime o. Los nodos en el mismo ni el en es os á boles compa en
el jugado al que le oca ealiza una acción y la elección del jugado asig-
nado a cada ni el depende á de cómo es é de inida la a iación de u nos.
14 Capí ulo 2. T abajo elacionado
Figu a 2.1: Ejemplo de á bol de decisión pa a un es ado dado en el juego del
es en aya
La igu a 2.1 mues a un ejemplo isual del á bol de juego pa a el es en
aya pa iendo de un es ado dado. La ep esen ación comple a del á bol es
excesi amen e g ande pa a apa ece en un olio.
En es e ipo de á boles no nos bas a con una explo ación básica del á bol
pa a consegui una buena es a egia a segui , pues aunque encon emos un
camino que nos lle e a una si uación de ic o ia, no nos co esponde decidi
la o alidad del camino po lo que se ía inse ible. Pa a ob ene soluciones en
es a pa e se han desa ollado o os algo i mos, de los cuales el más conocido
es Minimax, que e emos en la siguien e sección.
Búsqueda en á boles e inducción hacia a ás
Explo a á boles pa a ob ene cómo llega a cie os nodos, es un p oblema
clásico en el campo de la in eligencia a i icial, al que hay que da solución en
muchos sis emas in eligen es ac uales. En es a sección explo amos soluciones
clásicas y su aplicación en la eo ía de juegos. De ahí, pasamos al algo i mo
Minimax que nos mos a á cómo explo a un á bol de juego con múl iples
agen es y e emos algunas op imizaciones.
Algo i mos adicionales
Explo a un á bol desde la aíz has a algún nodo que nos in e ese, es
un p oblema que se p esen a ecuen emen e, y que podemos encon a en
in inidad de si uaciones dis in as. En el caso que nos a añe son la he amien a
2.3. Búsqueda en á boles e inducción hacia a ás 15
pe ec a pa a da una solución a los juegos indi iduales. A pesa de habe
nume osas o mas de ealiza la explo ación, amos a habla de los mé odos
más conocidos: la búsqueda p ime o en p o undidad, la búsqueda p ime o en
anchu a y la búsqueda A*. Es a úl ima nos se i á ambién pa a in oduci
el concep o de heu ís ica que nos se á muy ú il más adelan e.
P ime o en p o undidad
El algo i mo de búsqueda p ime o en p o undidad (conocido como DFS
po Dep h Fi s Sea ch en inglés), explo a á de o ma ecu si a el á bol, des-
cendiendo po el p ime nodo que encuen e has a llega a un nodo hoja. Una
ez llegados a es e pun o, en caso de no se el nodo que buscamos, ol emos
al nodo p edeceso y elegimos la siguien e opción disponible. Podemos e el
algo i mo en pseudocódigo a con inuación:
DFS(nodo n)
SI n = obje i o
DEVOLVER n
SINO
PARA CADA hijo EN n.hijos
DFS(hijo)
Del mismo modo, exis e una e sión pa a la explo ación de o as es-
uc u as de da os di e en es a los á boles, que implemen a un con ol de
epe iciones, pe o no indaga emos en ella (Rusell y No ig, 2003).
P ime o en Anchu a
El algo i mo de búsqueda p ime o en anchu a (o BFS po B ead h Fi s
Sea ch en inglés), p opone explo a p ime o odas los nodos que es án al
mismo ni el y después pasa al siguien e. Pa a la implemen ación de es e
algo i mo amos a u iliza una cola. Vemos el pseudocódigo:
BFS(nodo aiz)
Q = Cola
Q.in oduci ( aiz)
MIENTRAS NO Q. acia
n = Q.ex ae ()
SI n = obje i o
DEVOLVER n
SINO
PARA CADA hijo EN n.hijos
Q.in oduci (hijo)
16 Capí ulo 2. T abajo elacionado
Igualmen e igno amos la e sión con con ol de epe iciones (Rusell y
No ig, 2003).
Búsqueda A*
El algo i mo A* apa ece como un ejemplo de búsqueda in o mada. Al
con a io que en las an e io es, en es a amos a con a con in o mación ex a
que nos in o ma de si nos es amos ace cando o alejando de la si uación
con o me explo amos el á bol. Es a in o mación se a a á de una heu ís ica
como se ha de inido an e io men e.
El ejemplo más isual de u ilización de A* es en los sis emas de guía po
GPS, en los que debemos esol e el p oblema de i desde un pun o A a o o
B en un mapa de la o ma más e icien e. La heu ís ica que se suele elegi en
es os casos es la dis ancia en línea ec a en e una posición in e media y el
des ino.
U iliza emos una cola de p io idad pa a que el siguien e nodo a e alua
sea aquel que sea más p ome edo . Es deci , aquel que minimice la unción:
(n) = g(n) + h(n)
Dónde h(n)es la heu ís ica del nodo ac ual al obje i o y g(n)el cos e eal
del camino desde la aíz al nodo ac ual (ZENG y CHURCH, 2007).
En la igu a 2.2, emos un ejemplo de los elemen os de A*. Se mues a
una simpli icación del uncionamien o de un so wa e de GPS pa a ob ene
un camino. En es e caso podemos e sob e los é ices la dis ancia eal
po ca e e a en e las ciudades que con o ma ían nues a g(n)mien as que
sob e los nodos (con núme os e des), se e la dis ancia en línea ec a a
nues o nodo obje i o, es os alo es con o man h(n). En el ejemplo el nodo
o igen es Mad id, ma cado en ama illo y el obje i o Cas ellón de la Plana,
en e de.
Minimax
Tenemos ya unas cuan as he amien as pa a explo a á boles. Aho a,
es os algo i mos no pueden se aplicados a los á boles de juego, ya que como
se ha mencionado an e io men e no co esponde a un mismo agen e elegi
odos los caminos. Dada es a di icul ad su ge Minimax.
En cada juego, debemos de ini una a iable de con ol a la que llama e-
mos alo de u ilidad, que se á di e en e pa a cada juego y nos indica á si el
nodo en cues ión p opo ciona un buen esul ado. Es e alo , end á de inido
2.3. Búsqueda en á boles e inducción hacia a ás 17
Figu a 2.2: Simpli icación de la búsqueda de caminos en GPS
po los nodos e minales. Debemos ene en cuen a que nues o ad e sa io
a a á de maximiza su alo de u ilidad, po lo que en e sus posibles accio-
nes, elegi á siemp e aquella que minimice nues o alo de u ilidad ( an den
He ik, 1999). Siendo así, el algo i mo unciona de es a mane a:
1. Gene a el á bol de juego comple o.
2. Ob ene el alo de u ilidad de los nodos e minales.
3. T aspasa el alo de u ilidad a los nodos supe io es, eligiendo el máxi-
mo en caso de que el u no co esponda al jugado , y el mínimo en caso
de que sea del oponen e. Es a pa e se llama inducción hacia a ás.
4. Elegi la acción co espondien e al nodo con el mayo alo de u ilidad.
El p oblema es p ecisamen e el p ime pun o, ya que en juegos complejos
es imp ac icable gene a el á bol de juego en e o. En el ejemplo que mos-
ábamos an e io men e del es en aya enemos un ac o de ami icación
inicial de 9 (en la p ime a jugada podemos coloca nues a icha en nue e
posiciones) que disminuye en uno en cada jugada. Sabe el núme o exac o de
pa idas posibles es complicado debido a que no odas las pa idas equie en
los 9 mo imien os, a pa i de 5 puede habe un ganado y e mina la pa -
ida. A pesa de es o, podemos e que el núme o de pa idas dis in as es á
aco ado supe io men e po 9·8·7·6..,1 = 9! = 362880 pa idas.
El p oblema es igualmen e complicado si que emos sabe el núme o o al
de nodos que iene el á bol, pe o podemos hace la misma aco ación. De
es a o ma, en cada ni el end emos 9!
(9−n)! nodos, po lo que gene a emos

18 Capí ulo 2. T abajo elacionado
Figu a 2.3: Ob ención inicial de un á bol de juego
un á bol de juego de amaño ce cano a:
9
X
n=1
9!
(9 −n)! = 986409
Si un juego an sencillo gene a p ác icamen e un millón de nodos, es e iden-
e que no esul a ac ible aplica lo a juegos más complejos. El ajed ez po
ejemplo iene un ac o de ami icación inicial de 20 (16 mo imien os de los
peones y 4 de los caballos) que puede aumen a , y du an e las e apas in e -
medias un alo ípico (La amée, 2000) po lo que simplemen e al p edeci
10 jugadas ob end íamos un á bol de ce ca de 2,75 ×1015 nodos.
Una solución común a es e p oblema es u iliza un Minimax limi ado
po p o undidad. Con es e algo i mo explo a emos has a p edeci odas las
jugadas posibles en los nsiguien es u nos y ob end emos igualmen e el alo
de u ilidad de los nodos hoja. La igu a 2.3 mues a cómo se gene a un á bol
de p o undidad 4, po su pa e, la 2.4 mues a cómo unciona la inducción
hacia a ás de Minimax.
El p oblema de limi a po p o undidad a Minimax es que es a emos
llegando a un nodo in e medio, no iene po qué se un nodo ganado o pe -
dedo . Po an o ¿Qué alo de u ilidad asignamos a es os nodos? La solución
suele se u iliza conocimien o expe o del dominio, es deci , azonamien os
basados en la expe iencia de juegos an e io es, es a egias que se conoce que
han dado un buen esul ado, e c.
La g an des en aja de es a idea es que el conocimien o expe o no solo
es complicado de consegui , sino que además no suele se ácil de codi ica
en o ma de eglas pa a que el algo i mo pueda abaja . O o p oblema
es que es e conocimien o no iene po qué se óp imo, puede habe es a-
egias mejo es que simplemen e no se hayan desa ollado. Ejemplos de es e
conocimien o se e án más adelan e cuando se expliquen los juegos que se
explo a án.
2.3. Búsqueda en á boles e inducción hacia a ás 19
Figu a 2.4: Ejecución de la inducción hacia a ás en Minimax
Poda Alpha-Be a
Vamos a p esen a aho a la op imización de Minimax conocida como
poda al a-be a (más conocido po el nomb e en inglés: Alpha-Be a p uning).
Dado el ele ado cos e de Minimax, debemos in en a aho a an os cálculos
como sea posible. En es e sen ido, nos damos cuen a de que podemos e i a
la explo ación de cie as amas si sabemos de an emano que no amos a
ob ene un alo mejo que el ya ob enido. Veamos el siguien e ejemplo de
una ope ación de maximización - minimización como las que encon amos
en Minimax:
m´ax{m´ın{3,12,8},m´ın{2, x, y},m´ın{14,5,2}} = m´ax{3, z, 2}= 3
Dado que z≤2, sabemos que nunca a a se elegido po lo que una ez
ob enido el alo 2, no hace al a explo a los alo es xeyya que no an a
in lui (Rusell y No ig, 2003).
Pa a o maliza es o amos a de ini dos a iables que llama emos αyβ
que de inimos de la siguien e o ma:
αEl alo de la mejo (es deci mayo ) elección que hemos encon ado
has a aho a en cualquie pun o de elección pa a el camino de MAX.
βEl alo de la mejo (es deci meno ) elección que hemos encon ado
has a aho a en cualquie pun o de elección pa a el camino de MIN.
Si en la explo ación de un nodo de maximización encon amos un alo que
supe e a β, no se á necesa io segui explo ando las demás amas de ese nodo.
Simé icamen e, si en un nodo de minimización encon amos una ama con
un alo de u ilidad meno que α, poda emos1igualmen e. Podemos e el
algo i mo en pseudocódigo a con inuación:
1E i a emos la explo ación de dicha ama
20 Capí ulo 2. T abajo elacionado
AlphaBe a(nodo)
= Maximiza (nodo, -in ini o, +in ini o)
DEVOLVER
Maximiza (nodo, alpha, be a)
SI esEs adoTe minal(nodo) ENTONCES DEVOLVER u ilidad(nodo)
= -in ini o
PARA CADA a EN Acciones(nodo)
= max( , Minimiza (Aplica Accion(a, nodo), alpha, be a))
SI >= be a DEVOLVER
alpha = max(alpha, )
DEVOLVER
Minimiza (nodo, alpha, be a)
SI esEs adoTe minal(nodo) ENTONCES DEVOLVER u ilidad(nodo)
= -in ini o
PARA CADA a EN Acciones(nodo)
= min( , Maximiza (Aplica Accion(a, nodo), alpha, be a))
SI alpha >= DEVOLVER
be a = min(be a, )
DEVOLVER
Juegos pa a expe imen a
P esen amos a con inuación algunos juegos que amos a u iliza pa a
nues a in es igación. Además de es o, p o undiza emos en es a egias y co-
nocimien os del dominio ú iles pa a implemen a jugado es e icien es.
Re e si
El Re e si, ambién conocido como O hello, es un juego de mesa cuyo
o igen p o iene de Ingla e a, donde ue come cializado po p ime a ez en
1880 po Lewis Wa e man y John W. Molle . A día de hoy, el juego es
conocido en odo el mundo, eniendo una ue e p esencia en Japón ( ançaise
dÓ hello, 1998).
Pa a juga necesi a emos un able o de 8x8 casillas y 64 discos de amaño
in e io a una casilla. Los discos debe án se de colo es dis in os en cada ca-
a, es os colo es adicionalmen e son neg o y blanco, aunque es muy ípico
ambién encon a los en ojo y azul. Las casillas del able o se suelen e e-
encia u ilizando una le a de la aa la hde izquie da a de echa pa a indica
la columna, y un núme o del 1 al 8 comenzando de a iba hacia abajo pa a
2.4. Juegos pa a expe imen a 21
Figu a 2.5: Comienzo del juego en el Re e si
señala la ila. Al implemen a el able o la elección de ep esen ación más
simple es u iliza un a ay bidimiensional de 8×8posiciones, de es a o ma,
las casillas quedan ep esen adas con un ec o [i, j]con 0≤i, j ≤7, es a
se á la ep esen ación que apa ece á en la mayo ía de las imágenes. Juga án
dos jugado es y cada uno end á asignado un colo .
Reglas
Según Rose (2005) las eglas del juego se de inen como sigue:
1. El juego comienza con discos neg os en d5 y e4, y discos blancos en d4
y e5 como se puede e en la Figu a 2.5.
2. Los jugado es al e nan u nos, comenzando el jugado de ichas de colo
neg o (o azul).
3. Un mo imien o legal consis e en coloca un nue o disco en una casilla
acía y da la uel a a uno o más de los discos del oponen e.
4. Se da á la uel a a cualquie disco del colo del oponen e, comp endido
en e el disco que se acaba de juga y cualquie o o del colo del juga-
do p eexis en e en el able o.Llama emos a es o hace un "Sándwich".
Se pueden c ea sándwiches en o ma e ical, ho izon al y diagonal.
Pa a c ea un sándwich, odas las casillas en e el disco nue o y el p e-
exis en e del mismo colo deben es a ocupadas po discos del oponen e
sin casillas acías.
28 Capí ulo 3. Funcionamien o de MCTS
Figu a 3.1: Ejemplo de selección u ilizando UCB
Dónde ¯
Xjes la ecompensa media ob enida en el nodo j,nel núme o
o al de ejecuciones y njel núme o de ejecuciones en el nodo j. El p ime
sumando a o ece la explo ación de nodos pues si un nodo es bueno end á
una ecompensa media al a que aumen a á el alo UCB, mien as que el
segundo la explo ación ya que es un alo al o en aquellos que han sido poco
explo ados en compa ación con el núme o o al de explo aciones. La igu a
3.1 nos mues a un ejemplo de aplicación de UCB, después de 13 i adas nos
encon amos con los siguien e alo es pa a los b azos donde se ma can las
eces que se ha i ado de cada b azo de ás de la ba a y las eces que se
ha ob enido ecompensa an es. Se mues a en azul el b azo que debe ía se
es i ado a con inuación.
Mon e Ca lo T ee Sea ch
El algo i mo del á bol de búsqueda de Mon eca lo o Mon e Ca lo T ee
Sea ch (MCTS) busca desa olla un á bol que explo e pa cialmen e el espa-
cio de es ados de un p oblema, in en ando que los nodos en los que se dedica
más es ue zo sean los que an a da un mejo esul ado.
La idea del algo i mo es p ecisamen e e i a la explo ación has a los
nodos e minales pues como se ha comen ado es o esul a imposible. Po
con a, amos a es ima la p obabilidad de gana desde el es ado in e medio
en el que nos encon emos, es deci , calcula un alo heu ís ico. El medio
pa a es ima es e alo se á ealiza simulaciones de pa idas en el que las
decisiones se oman de o ma alea o ia, po es o di emos que se llama de un
mé odo es ocás ico. La es imación del alo de cada nodo se hace únicamen e
median e la simulación de pa idas po lo que podemos cons ui jugado es
que omen buenas decisiones sin ninguna necesidad de conocimien o expe o
del dominio en el que se abaja.
Exis e una g an di e sidad de implemen aciones de MCTS, sin emba go,
en es a sección amos a explo a el uncionamien o más adicional y en las
subsiguien es e emos las a iaciones que han sido necesa ias pa a nues os
casos conc e os.
El algo i mo p e ende explo a un á bol y calcula un alo heu ís ico a
cada nodo pa a pode elegi el que sea posiblemen e el mejo . Pa i emos de

3.2. Mon e Ca lo T ee Sea ch 29
un único nodo aíz y en cada i e ación i emos ampliando el conocimien o que
enemos del espacio de es ados. Cada una de las men adas i e aciones del
código se di ide en 4 pa es cla amen e di e enciadas: selección, expansión,
simulación y e op opagación (B owne e al., 2012). Es a pa es con es an
espec i amen e a las p egun as ¿Qué nodo expandimos?¿Cómo lo expandi-
mos?¿Cuán bueno es el nodo esul an e?¿Qué e ec o iene es o sob e el es o
del á bol?
Vamos a necesi a gua da cie a in o mación en los nodos del á bol.
Cada uno almacena á:
El es ado del juego.
Un con ado de eces que ha sido expandido dicho nodo.
Un con ado de eces que la expansión ha esul ado en una ic o ia.
La acción po la que se ha llegado a ese nodo.
Pun e os al pad e y los hijos.
El obje i o es ob ene una es imación de cuán buenas son las dis in as ac-
ciones que enemos a nues a disposición. Pa a es o simplemen e al expandi
los nodos juga emos pa idas alea o ias desde cie o nodo y comp oba emos
si hemos ganado o pe dido, es e alo se manda hacia a iba en la je a quía
de nodos, de es a o ma, odos los nodos ienen la in o mación de sus hijos.
Selección
El p oceso de selección se ocupa de elegi qué nodo es el mejo exponen e
pa a se expandido. Es aquí dónde cob a sen ido el desa ollo p e io sob e las
máquinas agape as, pues u iliza emos el algo i mo UCB pa a selecciona
cuál es el siguien e nodo a expandi .
Sin emba go, apa ece un p oblema y es que como acabamos de comen a
(y como se explica en p o undidad en la sección sob e e op opagación) la
in o mación que encon amos en los pad es es la suma de la de los hijos.
Po es o no podemos u iliza UCB simple, nos emos obligados a in oduci
UCT (Uppe Con idence bound o T ees). Simplemen e sus i ui emos el
alo de npo el núme o de eces que se ha seleccionado el nodo pad e en
luga del o al, de es a o ma, se u iliza UCB de o ma local pe mi iendo un
uncionamien o co ec o del algo i mo. La igu a 3.2 mues a un ejemplo de
selección u ilizando UCT.
30 Capí ulo 3. Funcionamien o de MCTS
Figu a 3.2: Ejemplo de selección u ilizando UCT
Expansión
Una ez elegido el nodo a expandi , debemos dilucida cómo lo hacemos,
aquí empieza a apa ece la alea o iedad. Hay di e sas o mas, eamos algunas
de ellas:
Expansión simple
Es la opción más sencilla y con meno cos e compu acional. Consis e en
que, dada la lis a de acciones que enemos disponibles pa a el nodo seleccio-
nado, elegimos una de ellas, la ejecu amos y ob end emos un nue o es ado,
que con o ma á el nue o nodo hijo. Después con inuamos hacia la siguien e
ase (Chaslo e al., 2008).
Expansión múl iple
Se a a de una ampliación de la an e io , pa a ello, en luga de elegi una
única acción pa a expandi , escogemos ny pasamos a la siguien e ase. En
es e caso debe íamos in es iga cuál es el alo óp imo pa a npues un alo
muy ele ado signi ica ía un gas o excesi o en es a ase que mul iplica ía el
gas o en la siguien e.
Simulación
Una ez elegidos los nodos a expandi , debemos comp oba cuán buenos
son es os. Esa es la unción de la ase de simulación. Pa a conoce es e alo ,
pa i emos del es ado que nos mues a el nodo a simula y comenzamos a
oma decisiones alea o ias, den o de la lis a de acciones disponibles, pa a
de ini un camino has a llega a un nodo e minal. El es ado e minal end á
3.3. Simulación 31
un alo dependiendo del p oblema que es emos aba cando (gana o pe de ,
el ni el de bene icio ob enido, e c). Toma emos en onces es e como nues o
alo heu ís ico pa a el nodo.
El ejemplo más sencillo es un juego en que los posibles esul ados sean
gana o pe de . En es e caso, desde el es ado que nos p oponga el nodo
a simula , gene amos elecciones alea o ias de las jugadas disponibles has a
llega a un es ado en el que bien hab emos ganado o pe dido. En caso de
gana asigna emos 1/1al alo heu ís ico del nodo expandido, mien as que
en caso de pe de lo ma ca íamos a 0/1donde el núme o de ás de la ba a
indica el núme o de eces que se ha simulado.
La ase de simulación puede se len a si el p oblema que se es á a ando
iene muchos posibles mo imien os, si exis en ciclos o si el espec o es in ini o.
Po eso en muchas ocasiones es más e icien e, en luga de obliga al código a
llega a un es ado e minal, elegi algún o o ipo de alo que nos indique
cuán bueno es el nodo y hace una explo ación de p o undidad limi ada o
con un iempo limi ado. Es a opción, po con a, nos hace pe de uno de
los pun os más impo an es del algo i mo, la independencia del dominio,
pues no necesi a nunca conocimien o p e io del juego, solamen e sabe si ha
ganado o pe dido, la capacidad de alo a un es ado no e minal implica que
sabemos de an emano lo bueno que es un es ado.
Realiza emos simulaciones sob e los candida os a expandi se, aho a, de-
bemos elegi cuán as simulaciones lle a a cabo, ya que ealiza una sola sob e
cada candida o puede in oluc a un e o muy g ande a la ho a de alo a lo,
mien as que un núme o de simulaciones excesi amen e g ande alen iza de-
masiado el algo i mo. En gene al la oma de decisiones en las simulaciones
consumen muy poco iempo compu acional ya que no es necesa io de ene se
p ác icamen e a medi a las opciones. El mayo cos e de es as iene p ecisa-
men e de calcula las opciones posibles en cada es ado po lo que en juegos
complicados se alen iza de o ma signi ica i a.
Re op opagación
En es e momen o, enemos un alo de cuán bueno es el nodo (o los nodos)
nue o(s). Nues a a ea se á aslada es a misma in o mación a odos los
nodos y en pa icula a los hijos de la aíz que son, al in y al cabo, en e
los que enemos que elegi . Es e p oceso se llama e op opagación y es an
simple como eco e el á bol desde el nodo hoja que acabamos de c ea
has a la aíz sumando los alo es de esul ados e in en os a los con ado es
de cada nodo que encon emos po medio.
Una ez llegados a es e pun o, hemos comple ado una i e ación del MCTS,
y con ello, ob enido un á bol con más nodos y mejo in o mado sob e lo bue-
nas que son las dis in as decisiones. A con inuación se lle a a é mino la
32 Capí ulo 3. Funcionamien o de MCTS
Figu a 3.3: Resul ado de una i e ación de MCTS
siguien e i e ación, y es en onces cuando apa ece la p egun a: ¿Cuándo pa-
amos? En un p oblema con un espacio de búsqueda i ualmen e in ini o,
como puede se , po ejemplo, el ajed ez (del que se habla á más adelan e),
pod íamos explo a el á bol an o como quisié amos y siemp e mejo a ía-
mos la solución. Po ello, no malmen e la es a egia es de ene se dada una
condición que puede se un lími e de iempo, un núme o máximo de nodos
expandidos, una p o undidad máxima, e c. Al cumplimien o de es a condi-
ción es a emos obligados a elegi el nodo que enga mejo esul ado has a el
momen o.
Re omando el ejemplo expues o en la igu a 3.2, podemos e el esul ado
de ealiza una expansión múl iple con n= 2, 5 simulaciones po nodo y la
e op opagación del esul ado. Se mues a en la Figu a 3.3
Mos amos a con inuación la es uc u a gene al de MCTS en pseudocó-
3.3. Simulación 33
digo:
MCTS( aiz)
MIENTRAS hayTiempo() HACER
seleccionado = seleccion( aiz)
expandido = expansion(seleccionado)
esul ado = simulacion(expandido)
e op opagacion(expandido, esul ado)
DEVOLVER maxheu is ica( aiz.hijos)
seleccion(a bol)
PARA CADA nodo EN a bol
calcula UCT()
DEVOLVER a gmaxuc (a bol)
expansion(nodo)
PARA i=0 HASTA nume oExpansiones
accion = andomchoice(accionesDisponibles(nodo))
nue oNodo = ejecu a (accion, nodo)
nodo.ag ega Hijo(nue oNodo)
simulacion(nodo)
acie os = 0
PARA i=0 HASTA nume oSimulaciones
cnodo = copia (nodo)
MIENTRAS noTe minado(cnodo) HACER
accion = andomchoice(accionesDisponibles(cnodo))
cnodo = ejecu a (accion, cnodo)
SI gana (cnodo)
acie os = acie os +1
DEVOLVER acie os
e op opagacion(nodo, acie os)
nodo.acie os = nodo.acie os+acie os
nodo.in en os = nodo.in en os+nume oSimulaciones
MIENTRAS nodo.pad e != NULL HACER
nodo <= nodo.pad e
nodo.acie os = nodo.acie os+acie os
nodo.in en os = nodo.in en os+nume oSimulaciones

34 Capí ulo 3. Funcionamien o de MCTS
PMCTS
Vamos a implemen a ambién la e sión de MCTS conocida como Plain
Mon eca lo T ee Sea ch. Es a e sión di ie e de la o iginal en la ase de ex-
pansión que es igno ada. De es a o ma el á bol de juego se á es á ico sin
ningún ipo de c ecimien o. Recae sob e noso os decidi la o ma del á bol
que se á gene ado an es de comenza las i e aciones. La gene ación de es-
e á bol inicial es algo a iesgada, pues, según es é de inido pod ía ob ia
opciones bene iciosas que ya no se án omadas en conside ación en ningún
momen o.
En la e sión que hemos implemen ado, pa a da solución a es o, ge-
ne amos 2 ni eles del á bol comple os, odas las posibles acciones a oma
po noso os y po nues o con incan e. Una ez ealizado es e paso inicial
desa ollamos las o as es ases an as eces como i e aciones sean posi-
bles. Eligiendo el á bol de es a mane a podemos aho a el cálculo de UCT
como en el apa ado an e io y calcula di ec amen e UCB sob e los nodos
hoja, pues la selección del nodo aíz o de algún nodo no hoja implica ía
una simulación que o zosamen e pasa ía po alguna de las hojas, lo que es
ine icien e.
Podemos ap ecia en onces el pseudocódigo del cue po p incipal de es e
algo i mo:
PMCTS( aiz)
gene a A bolInicial( aiz)
MIENTRAS hayTiempo() HACER
seleccionado = SeleccionPo UCB()
Simulacion(seleccionado)
Re op opagacion(seleccionado)
DEVOLVER maxheu is ica( aiz.hijos)
Reap o echamien o de memo ia
Cada ez que nos encon emos en un es ado nue o, debe emos gene a
un á bol de juego que pa a únicamen e de la aíz, pa a es ima una ez más
la heu ís ica de cada nodo. Una idea in e esan e es eap o echa un á bol
que u ié amos c eado ya de la úl ima ez que lo gene amos, pa a ob ene
mejo es esul ados. El p oblema con es o es que no podemos p edeci qué
mo imien o a a elegi el ad e sa io o los ad e sa ios, con lo que es posible
que es e no es é en e los que noso os hemos conside ado.
Pa a ello lo más sencillo es gua da la es uc u a del á bol de la ejecución
an e io y an es de comenza las nue as i e aciones, descendemos dos eces
po la aíz del á bol imi ando las acciones omadas en el juego eal. En caso de
3.6. Ap oximación p obabilís ica 35
no ene un é ice a ese nodo empeza íamos de ce o, pe o si enemos sue e
podemos pa i de un á bol con unas cuan as heu ís icas ya calculadas, lo
que nos pe mi i ía en el mismo iempo compu acional ob ene los esul ados
equi alen es a más simulaciones.
Ap oximación p obabilís ica
En es a sección se u ilizan concep os de p obabilidad que no han sido
in oducidos en apa ados an e io es po lo que se ecomienda que el lec o
enga conocimien os de p obabilidad y es adís ica. En odo caso, si el lec o
desea epasa las de iniciones de es os concep os, puede hace lo en el apéndice
A.
U ilizando el mé odo de Mon eca lo es amos in en ando ap oxima la
dis ibución de p obabilidad de una a iable alea o ia disc e a que nos ma -
ca á las expec a i as de gana que podemos ene dada la elección de cie a
acción en un es ado dado. Si llamamos Xa es a VA. Tenemos dos esul ados
posibles:
X=gana X =no gana
Según es á de inido el algo i mo nues o obje i o es ap oxima p(X=gana |e)
median e simulaciones siendo euna con igu ación dada den o del espacio de
es ados. Vamos a comp oba que e ec i amen e la p obabilidad de que ob-
ene una ic o ia desde cie o es ado es igual a la de que una simulación
esul e ganado a. De es a o ma nos e emos en las condiciones de aplica
el eo ema de Gli enko-Can elli (que se enuncia y explica en la sección si-
guien e) y demos a que e ec i amen e median e es e p ocedimien o es amos
ap oximando la p obabilidad eal de gana desde ese es ado.
Es a úl ima p obabilidad la ob enemos de o ma ecu si a: comenzando
con el caso base, si el nodo ees un es ado e minal hab emos ganado o
pe dido po lo que:
p(X=gana |e) = 1si e es un es ado ganado
0ecc
Llama emos aj
ia ejecu a la acción aien el pun o de oma de decisión núme o
jy deno a emos po ai(e)al es ado esul an e de aplica la acción aiae. En
36 Capí ulo 3. Funcionamien o de MCTS
caso de no a a se de un es ado e minal end emos que:
p(X=gana |e) = X
i
p(X=gana |e, a1
i)p(a1
i)
=X
i,j
p(X=gana |e, a1
i, a2
j)p(a1
i, a2
j)
=...
=X
i,...,j
p(X=gana |e, a1
i, ..., ak
j)p(a1
i, ..., ak
j)
Siendo kel núme o necesa io pa a que a1
i(...(ak
j(e))) sea un es ado e minal.
La dis ibución de p obabilidad conjun a, iene dada po :
p(A, B) = P(A∩B) = p(A|B)p(B)
aplicando a nues o caso:
p(a1
i, a2
l..., ak
j) = p(a2
l..., ak
j|a1
i)p(a1
i)
=...
=Y
m
p(a
m|a −1
j, ..., a1
i)
Es os da os son conocidos pa a noso os, suponiendo que odas las acciones
ienen la misma impo ancia, podemos supone que p(a1
i) = 1
N(1) siendo
N(1) el núme o de acciones en e las que elegi . Así sucesi amen e p(a2
j|a1
i) =
1
N(2)
i
...
Es e es exac amen e el compo amien o que iene nues a simulación,
pues al elegi alea o iamen e la acción a oma la p obabilidad en nues a si-
mulación p(a)coincide con la ap oximada an e io men e. A su ez los es ados
e minales epo an 1 o 0 dependiendo de su alía po lo que la p obabilidad
de una simulación de ob ene una ic o ia es exac amen e la p obabilidad de
gana que hemos ob enido eó icamen e.
Las simulaciones ap oximan la dis ibución
Ya hemos comp obado que las simulaciones ienen la misma unción de
dis ibución Fque la a iable alea o ia de inida en el apa ado an e io .
Vamos aho a a e que e ec i amen e al aumen a el núme o de simulaciones
ealizadas nues o esul ado heu ís ico se ace ca a la dis ibución F. Es e
esul ado es á ecogido en el eo ema de Gli enko-Can elli que se enuncia a
con inuación (Ángel Villegas, 2005).
3.6. Ap oximación p obabilís ica 37
Teo ema 1 (Gli enko-Can elli) Si se iene una mues a alea o ia simple
de amaño n de una población X, con unción de dis ibución F(x), pa a
cualquie núme o eal posi i o a bi a io ε, se iene que
l´ım
n→∞ Psup
x∈R|F∗n(x)−F(x)| ≥ ε= 0
La demos ación de es e eo ema se puede consul a en Fisz (1963).
Es e eo ema nos indica que la p obabilidad de que el alo sup emo de la
di e encia en e la unción de dis ibución es imada con la mues a alea o ia
simple (en nues o caso los esul ados de las simulaciones) y la unción de
dis ibución eó ica, sea mayo que cie o alo εes 0 cuan o el amaño de
la mues a iende a in ini o.
Con es a sección hemos demos ado que a a és de las simulaciones
ob end emos un alo heu ís ico que e ec i amen e ap oxima el alo eó ico
co espondien e a cada nodo.
44 Capí ulo 4. Aplicación de MCTS a juegos
Expe imen o P o undidad PMCTS P o undidad MCTS
1 23 41 23 41
2 17 47 16 48
3 26 38 26 38
4 34 30 11 53
5 10 54 33 31
6 50 14 15 49
7 21 43 27 37
8 23 41 26 38
9 23 41 32 32
10 14 50 30 34
11 27 37 54 10
12 25 39 26 38
13 16 48 13 21
14 13 51 9 55
15 14 50 1 62
16 22 42 8 56
17 29 35 20 44
18 17 46 0 42
19 29 35 44 20
20 26 38 25 39
21 35 29 26 38
22 23 41 16 48
23 55 9 33 31
24 25 39 28 36
25 24 40 39 25
26 47 15 10 54
27 24 40 12 52
28 17 46 21 43
29 20 44 35 29
30 23 41 19 45
Media 25,066 38,8 22,6 39,633
Vic o ias 5 25 6 23
Tabla 4.3: PMCTS y MCTS (70 simulaciones) s búsqueda en p o undidad

4.1. Aplicación al Re e si 45
Expe imen o Bac acking PMCTS Back acking MCTS
1 18 46 11 53
2 19 45 12 52
3 24 40 52 12
4 22 42 20 44
5 23 41 42 22
6 21 43 21 43
7 24 40 30 34
8 21 43 26 38
9 16 48 23 41
10 26 38 21 43
11 29 35 22 42
12 20 44 28 36
13 13 51 31 33
14 37 27 26 38
15 16 48 40 24
16 20 44 19 45
17 18 46 17 47
18 17 47 29 35
19 14 50 18 46
20 24 40 28 36
21 15 49 31 33
22 25 39 36 28
23 19 45 21 43
24 23 41 21 43
25 18 46 20 44
26 14 50 24 40
27 21 43 25 39
28 17 47 30 34
29 20 44 22 42
30 25 39 42 22
Media 20,633 43,366 26,266 37,733
Vic o ias 1 29 5 25
Tabla 4.4: PMCTS y MCTS (700 simulaciones) s búsqueda en p o undidad
46 Capí ulo 4. Aplicación de MCTS a juegos
Expe imen o Alpha-Be a débil PMCTS Alpha-Be a débil MCTS
1 22 42 33 0
2 26 38 48 16
3 25 39 26 38
4 38 26 56 1
5 24 40 27 37
6 19 45 25 0
7 27 37 46 18
8 16 48 32 32
9 28 36 42 22
10 25 39 31 33
11 18 46 47 17
12 19 0 21 0
13 19 45 50 14
14 19 45 31 33
15 41 23 41 23
16 39 25 31 33
17 35 29 55 9
18 22 42 54 10
19 21 43 32 32
20 30 34 29 0
21 29 35 41 23
22 23 41 38 26
23 30 34 31 33
24 26 1 23 0
25 23 0 33 31
26 19 45 36 28
27 32 32 23 41
28 30 34 28 36
29 54 10 21 43
30 30 34 34 30
Media 26,966 32,933 35,5 21,966
Vic o ias 8 21 18 10
Tabla 4.5: PMCTS y MCTS(140 simulaciones) s Alpha-be a (débil)
4.1. Aplicación al Re e si 47
men a sus ancialmen e la capacidad de Alpha-be a, pues educe las ic o ias
de PMCTS al 36% y las de MCTS al 26,6 %.
Po úl imo, con el in de consegui ence con mayo ecuencia a Alpha-
be a, amos a in oduci con enido especí ico del dominio en nues o jugado
con mejo esul ado, que ha demos ado se PMCTS. U iliza emos la misma
heu ís ica que hemos p opo cionado a Alpha-be a, pa a ello, una ez ealiza-
do odo el algo i mo, an es de elegi el mo imien o a ealiza , aumen a emos
o disminui emos el alo de bondad del nodo sumando 20 acie os si la juga-
da nos ha ía domina una esquina, 2 en caso de una casilla ’X’y es a emos 5
pa a las casillas ’C’. A la is a de es o ob enemos los esul ados que se dispo-
nen en la abla 4.7. Podemos e una le e mejo ía espec o al caso an e io ,
subiendo el po cen aje de ic o ias al 43,3%. Vamos aho a a comp oba el
compo amien o al aumen a el núme o de simulaciones signi ica i amen e
pa a e si con es o podemos de ini i amen e sob epasa a Alpha-be a ue e.
MCTS s PMCTS
Po úl imo, en en amos ambas e siones de Mon eca lo T ee Sea ch en e
si y mos amos los esul ados en la abla 4.9. Ya habíamos is o en los
expe imen os an e io es que en gene al enemos un endimien o mejo en la
e sión plana que en la dinámica, aquí lo emos cla amen e plasmado cuando
PMCTS se alza con un 76 % de ic o ias.
Análisis de esul ados
Podemos e que ambas e siones del algo i mo dan muy buenos esul a-
dos con a el alea o io, ob eniendo un a io de no de o as siemp e en e el
90% y el 97 %. Es o nos indica que ealmen e el algo i mo oma buenas de-
cisiones. Podemos e aquí, una le e di e encia en e las dos e siones dando
pis as de que PTCMS iene un compo amien o li ianamen e mejo que su
e sión o iginal. Vemos que al aumen a las epe iciones disminuye en una
las ic o ias de MCTS. Podemos achaca es o a la simple p obabilidad o,
que el sal o de simulaciones no ha sido su icien e pa a asegu a un aumen o
sus ancial del endimien o.
Una si uación simila encon amos con a el algo i mo de búsqueda en
p o undidad, en es e caso, eniendo un ma gen mayo de mejo a, especial-
men e en MCTS, damos un sal o ca egó ico en la can idad de simulaciones
en e el p ime expe imen o y el segundo. Ap eciamos cla amen e cómo am-
bas e siones mejo an minimizando las opciones del ad e sa io.
Po o a pa e, el algo i mo Alpha-Be a ob iene un mayo po cen aje de
ic o ias con a ambos. Es o e a de espe a , pues como ya se ha explicado
an es, se a a de un algo i mo muy so is icado. Cabe des aca la impo an-
48 Capí ulo 4. Aplicación de MCTS a juegos
Expe imen o Alpha-Be a PMCTS Alpha-be a MCTS
1 44 20 21 43
2 31 33 31 33
3 41 23 43 21
4 25 0 47 17
5 44 20 34 30
6 37 27 38 26
7 42 22 46 18
8 21 43 38 26
9 55 9 27 37
10 28 36 30 34
11 37 27 52 12
12 43 21 46 18
13 20 44 58 5
14 26 38 61 1
15 46 16 56 8
16 20 44 25 0
17 51 13 51 13
18 42 22 30 34
19 59 5 32 32
20 59 5 32 33
21 48 16 35 29
22 31 33 29 35
23 55 9 22 42
24 29 35 52 12
25 31 33 38 26
26 31 33 29 0
27 41 23 49 15
28 53 11 42 22
29 49 15 33 31
30 27 37 36 28
Media 38,86 23,76 38,76 22,7
Vic o ias 19 11 21 8
Tabla 4.6: PMCTS y MCTS(140 simulaciones) s Alpha-be a ( ue e)
4.1. Aplicación al Re e si 49
Expe imen o Alpha - Be a PMCTS
1 25 39
2 27 37
3 41 23
4 25 39
5 39 25
6 24 40
7 31 33
8 43 21
9 46 18
10 21 43
11 61 3
12 43 21
13 44 20
14 55 9
15 39 25
16 26 38
17 60 4
18 26 38
19 44 20
20 10 54
21 49 15
22 31 33
23 44 20
24 54 10
25 51 13
26 56 5
27 29 35
28 40 24
29 28 36
30 20 44
Media 37,733 26,166
Vic o ias 17 13
Tabla 4.7: PMCTS (mejo ado y con 140 simulaciones) s Alpha-be a ( ue e)

50 Capí ulo 4. Aplicación de MCTS a juegos
Expe imen o Alpha - Be a PMCTS (in o mado) Alpha - Be a PMCTS
1 38 26 38 26
2 51 13 51 13
3 17 47 17 47
4 30 34 30 34
5 30 34 30 34
6 48 16 48 16
7 45 19 45 19
8 28 36 28 36
9 29 35 29 35
10 30 34 30 34
11 39 0 39 0
12 27 37 27 37
13 38 26 38 26
14 14 50 14 50
15 41 23 41 23
16 31 33 31 33
17 24 40 24 40
18 31 33 31 33
19 52 12 52 12
20 17 47 17 47
21 44 20 44 20
22 31 33 31 33
23 19 45 19 45
24 46 18 46 18
25 32 32 32 32
26 31 33 31 33
27 24 40 24 40
28 30 34 30 34
29 41 23 41 23
30 43 21 43 21
Media 33,36 29,8 36,46 26,06
Vic o ias 12 17 14 15
Tabla 4.8: PMCTS (750 simulaciones) s Alpha-be a ( ue e)
4.1. Aplicación al Re e si 51
Expe imen o MCTS PMCTS
1 24 40
2 28 36
3 38 26
4 17 47
5 16 48
6 23 41
7 28 36
8 19 45
9 17 47
10 19 45
11 27 37
12 3 61
13 19 45
14 37 27
15 23 41
16 34 30
17 12 52
18 40 24
19 29 35
20 16 48
21 17 47
22 49 15
23 22 42
24 30 34
25 35 29
26 24 40
27 3 51
28 28 36
29 44 20
30 22 42
Media 24,76 38,9
Vic o ias 7 23
Tabla 4.9: MCTS (70 simulaciones) s PMCTS (70 simulaciones)
52 Capí ulo 4. Aplicación de MCTS a juegos
Figu a 4.1: Resul ados de usa o no conocimien o del dominio con 750 simu-
laciones
cia de la op imización heu ís ica, pues emos que el α−βsaca más en aja
a los algo i mos de Mon eca lo cuando es á a mada con es a. A pesa de
odo, conseguimos un esul ado bas an e bueno con a ambas e siones, es-
pecialmen e de PMCTS que gana en la mayo ía de los casos con a la e sión
débil y es capaz de ob ene más de un e cio de las ic o ias con a la e -
sión ue e. Ap eciamos ambién en es e apa ado cómo el inyec a cie o
conocimien o del dominio hace mejo a a PMCTS has a es a casi igualado
con el algo i mo más ue e que hemos p esen ado en el caso de ealiza 140
simulaciones. Una ez damos el sal o a 750 emos que PMCTS es capaz de
domina en ic o ias, además, al esul ado es incluso mejo al inyec a cono-
cimien o del dominio. Es no able des aca que en es os úl imos expe imen os
se p oducen más ic o ias de PMCTS aunque es e consigue una pun uación
media peo .
Un pun o impo an e a des aca es la di e encia de endimien o en e la
e sión plana y la dinámica, ya que en gene al ob iene un esul ado mucho
más al o la p ime a. Una posible azón que explique es a di e encia es la
expansión inicial del á bol que ealiza PMCTS ya que gene amos dos ni eles
comple os con los que no cuen a MCTS que comienza desde la aíz, po lo
que con las mismas i e aciones, ealmen e ha p e is o más.
Pa a acaba es a sección, se mues an di e en es g á icas con la exposi-
ción de los esul ados. En la g á ica p esen ada en la igu a 4.2 podemos e
el esul ado medio ob enido en las dis in as ejecuciones, en la pa e supe io
se mues a MCTS y en la in e io PMCTS. En es a úl ima se señala como
Alpha-be a(mejo ado) el en en amien o en e Alpha-be a ue e y PMCTS
con conocimien o del dominio. Del mismo modo , la igu a 4.1 mues a los
esul ados del úl imo expe imen o que compa a el uso de conocimien o del
dominio con 750 simulaciones. Po o a pa e, emos que la igu a 4.3 nos
mues a dos g á icas de dispe sión con las dis in as pa idas en las que po-
demos e di e enciados los dis in os expe imen os y ob ene una idea global
del uncionamien o. Se mues a la ba a di iso ia en 32 pues es la pun uación
mínima que hay que ob ene pa a no pe de .
4.2. Aplicación al Ajed ez 53
Figu a 4.2: Compa ación de pa idas ganadas y pe didas en los di e en es
en en amien os
Aplicación al Ajed ez
El Ajed ez de po sí es un juego bas an e complicado, como ya hemos
comen ado an e io men e, iene un ac o de ami icación medio de 35, po
ello nos es imposible aba ca lo con algo i mos más clásicos como Minimax
pu o. Además, a di e encia del Re e si, en el Ajed ez se pueden p oduci
ciclos ya que odas las piezas, a excepción de los peones, pueden ol e a la
posición de inicio de su an e io mo imien o, po lo que in en a in es iga
el espacio de es ados comple o no esul a ac ible. Dadas es as bases, amos
a elegi el ipo de expansión y de simulación que nos in e esan.
Expansión
En es e caso amos a p oba con la misma e sión que u ilizamos pa a
el Re e si. Pa a la e sión plana debemos decidi sob e qué á bol amos a
u iliza . Comenzamos gene ando un á bol de 3 ni eles comple os (la aíz y
dos ni eles más), al igual que hacíamos an es.

Capí ulo 5
Mejo ando MCTS con edes
neu onales
En es e capí ulo amos a hace un eco ido sob e los mé odos más mo-
de nos implemen ados con el in de pe ecciona el endimien o de Mon eca lo
T ee Sea ch. Lo di idi emos en dos secciones, en la p ime a expond emos los
emas y concep os pe inen es pa a comp ende qué es el ap endizaje au o-
má ico o Machine Lea ning, y en el segundo cómo lo mezclamos con MCTS
pa a mejo a los esul ados. En es e ema se u iliza án di e sos concep os
sob e p obabilidad y álgeb a que no han sido in oducidos an e io men e en
el documen o, es os se pueden consul a ín eg amen e en los apéndices A y
B espec i amen e.
Ap endizaje au omá ico
El campo del ap endizaje au omá ico su ge de cuando in en amos que
un compu ado sea capaz de econoce pa ones y ob ene p edicciones a
pa i de un conjun o de da os. Des acamos dos casos p incipales a es udia :
eg esión y clasi icación.
El p oblema de eg esión in en a a on a el dilema de ene dos a iables
alea o ias co elacionadas XeYy necesi amos de e mina una ap oximación
a la elación exis en e en e ellas. Los da os nos gene a án una nube de pun os
y buscamos encon a una unción y(x)que sea la que mejo se ajus e a las
obse aciones (Rouaud, 2013). La ap oximación más ípica es conocida como
eg esión lineal, que ue za a ya de ini un hipe plano del espacio, po lo
que es a iene con o mada de la o ma:
y(x) = W x+b
con la ma iz W∈RD×Ky los ec o es x∈RDyb∈RKsiendo Dla
61
62 Capí ulo 5. Mejo ando MCTS con edes neu onales
Figu a 5.1: Reg esión (Izquie da) y clasi icación (de echa)
dimensión del espacio de los da os y Kla dimensión del esul ado a ob ene .
En la igu a 5.1 se mues a un ejemplo de eg esión lineal con D=K= 1.
Po su pa e, el p oblema de clasi icación pa e de un conjun o de da os
dis ibuidos en Kclases. Nos gus a ía, dado un da o de en ada, asigna lo a
una clase Ckcon 1≤k≤K. El p oblema que p obablemen e más se es udia
es el conocido como clasi icación bina ia, que se a a del caso en el que k= 2
(Smola y Vishwana han, 2008). Un ejemplo clásico son los il os de spam,
que, dado el con enido de cie o e-mail, son capaces de di e encia si es os se
a an de co eo basu a o no.
En caso de que K > 2conoce emos la si uación como clasi icación mul i-
clase. Encon amos igualmen e in inidad de ejemplos como de ec a de o ma
au omá ica el idioma en el que se encuen a un ex o o, dadas las mediciones
de los sín omas, diagnos ica la e apa del cánce en la que se encuen a una
pe sona, dando he amien as pode osas a los p o esionales sani a ios. Resul-
ados e óneos pueden aca ea se e as consecuencias, como en el caso de
diagnos ica e óneamen e una en e medad, po ello deben ene unas bases
ma emá icas bien undadas pa a asegu a la exac i ud de los esul ados.
Vamos a p esen a 3 algo i mos que dan solución a es os p oblemas, de
meno a mayo complejidad: mínimos cuad ados, el pe cep ón y las edes
neu onales. Aunque la can idad de algo i mos desa ollada es ex ensa, es os
son una buena ap oximación al campo de es udio, y cada uno ep esen a una
e olución del an e io . Nos apo a án he amien as pode osas pa a mejo a
MCTS.
Mínimos cuad ados
Pa imos de un conjun o de en enamien o, compues o po N ec o es1
de en ada y la co espondien e e ique a que nos indica á a qué clase pe e-
necen, es deci {(xj, j)}N
j=1. U iliza emos una clasi icación pa a las e ique as
1en desa ollo odos los ec o es son columnas, pa a indica un ec o ila se indica á
como aspues a
5.1. Ap endizaje au omá ico 63
conocida como one ho , en ella pa a odo j, jse á un ec o ekde la base
canónica2de RK.
Deseamos encon a una unción a ín y:RD→RK, con lo que ob en-
d emos un ec o de dimensión K. Al se a ín sabemos que nues a unción
end á la o ma: y(x) = W x+ben las mismas condiciones que se de ine
en la sección an e io . Asigna emos a la clase de la coo denada que haya
ob enido un alo mayo , es deci :
y∈ Ck|k= a g m´ax
1≤α≤Kyα(x)
Pa a simpli ica la no ación en el desa ollo llama emos ˜x=1
xy˜
W=
b
W. Ag upando aho a e ique as y ejemplos de en enamien o, llama emos
T= ( 1, ..., N)y˜
X= (˜x1, ..., ˜xn). En un caso ideal, que íamos consegui
que:
∀j y(xj) = W x+b=˜
W ˜x= j
o equi alen emen e debemos esol e el sis ema lineal de ecuaciones:
˜
W ˜
X=T
Sin emba go en la mayo ía de si uaciones es e sis ema no end á solución po
lo que debe emos con o ma nos con el esul ado que se ace que más, pa a
ello esol e emos el p oblema de op imización:
m´ın
˜
W|| ˜
W ˜
X−T||
Llama emos J(˜
W) = || ˜
W ˜
X−T||, unción de cos e. Dado que la no ma es no
nega i a, minimiza Jes equi alen e a minimiza E(˜
W) = 1
2|| ˜
W ˜
X−T||2,
es o nos acili a á los cálculos más adelan e. P esen amos a con inuación 2
o mas de soluciona lo, una de ellas es un mé odo de ap oximación y la o a
una solución eó ica.
Descenso de g adien e
El descenso de g adien e es un mé odo i e a i o que da solución a mini-
miza la unción E(˜
W). Pa a ello, calcula emos el g adien e de la unción,
2En el espacio ec o ial Knel conjun o o mado po los n ec o es
(1,0,0..., 0),(0,1,0, ..., 0), ..., (0,0,0, ..., 1) es una base que ecibe el nomb e de base
canónica de Kn. Es os ec o es habi ualmen e se denominan eidonde (ei)j= 1 si j=iy
(ei)j= 0 en cualquie o o caso (Me ino y San os, 2006).
64 Capí ulo 5. Mejo ando MCTS con edes neu onales
Figu a 5.2: Di ección del g adien e y p oblemas de elegi e óneamen e el
pa áme o α
es e nos indica la di ección de ascenso de máxima pendien e, po ello, si es-
amos es a can idad, es a emos dec eciendo el alo de la unción de cos e.
Tenemos:
∇E(˜
W) = ˜
X(˜
W ˜
X−T)
Es e esul ado se jus i ica en la sección siguien e. Teniendo es o, de inimos
la egla de ac ualización como:
˜
W( +1) =˜
W( )−α˜
X(˜
W ˜
X−T)
Donde αes un pa áme o conocido como asa de ap endizaje. La unción de
es e es de e mina el amaño del sal o exis en e en e una ac ualización y la
siguien e. Un alo muy g ande puede lle a a que el mé odo ob enga incluso
un esul ado opues o al buscado. Po o a pa e, un alo muy pequeño puede
lle a a que el algo i mo no con e ja en un iempo azonable. Se mues a una
isualización de es os esul ados en la igu a 5.2 en la que se puede e a la
izquie da los g adien es en los dis in os pun os y a la de echa el esul ado
de usa un αmuy g ande (en na anja) y el de u iliza uno muy pequeño (en
azul).
5.1. Ap endizaje au omá ico 65
Cálculo di ec o
Vamos a calcula el mínimo de la unción E(˜
W)de mane a explíci a.
Comenzamos obse ando que:
E(˜
W) = 1
2|| ˜
W ˜
X−T||2=1
2 (( ˜
W ˜
X−T) (˜
W ˜
X−T))?? (5.1)
=1
2 (˜
X ˜
W˜
W ˜
X−˜
X ˜
WT −T ˜
W ˜
X+T T)
(5.2)
Nos encon amos an e una unción di e enciable, podemos en onces encon a
los ex emos en los pun os que anulen a ∇E(˜
W). Po an o, dada una ma iz
cualquie a A∈RK×(D+1):
∇E(˜
W) = l´ım
ε→0
E(˜
W+εA)−E(˜
W)
ε
subs i uyendo en 5.2:
E(˜
W+εA) = 1
2 (ε2˜
X AA ˜
X−ε˜
X AT −εT AT˜
X
+ε˜
X ˜
WA ˜
X+ε˜
X A˜
W ˜
X+˜
X ˜
W˜
W ˜
X
−˜
X ˜
WT −T ˜
W ˜
X+T T)
si es amos E(˜
W)ob enemos que:
E(˜
W+εA)−E(˜
W) = 1
2 (ε2˜
X AA ˜
X−ε˜
X AT −εT AT˜
X
+ε˜
X ˜
WA ˜
X+ε˜
X A˜
W ˜
X)
di idiendo po εy eniendo en cuen a la p opiedad de la aza 1:
E(˜
W+εA)−E(˜
W)
ε=1
2 (ε˜
X AA ˜
X−˜
X AT −T AT˜
X
+˜
X ˜
WA ˜
X+˜
X A˜
W ˜
X)

66 Capí ulo 5. Mejo ando MCTS con edes neu onales
añadiendo el lími e y conside ando las p opiedades de la aza 3 y 4:
l´ım
ε→0
E(˜
W+εA)−E(˜
W)
ε=1
2 (˜
X AT −T AT˜
X
+˜
X ˜
WA ˜
X+˜
X A˜
W ˜
X)
=1
2[ (( ˜
X A)( ˜
W ˜
X−T))
+ ((( ˜
X A)( ˜
W ˜
X−T)) )]
= (( ˜
X A)( ˜
W ˜
X−T))
= (( ˜
W ˜
X−T)˜
X A)
= (( ˜
X(˜
W ˜
X−T) ) A)
=D˜
X(˜
W ˜
X−T) , AE
Dado que es o debe anula se ∀Aen onces debe se que:
˜
X(˜
W ˜
X−T) = 0
˜
X(˜
X ˜
W−T )=0
˜
X˜
X ˜
W−˜
XT = 0
˜
X˜
X ˜
W=˜
XT
˜
W= ( ˜
X˜
X )− ˜
XT
Es e mé odo da una solución ins an ánea y po an o es p e e ible su uso al
del descenso de g adien e explicado en la sección an e io , sin emba go, no en
odos los algo i mos nos a a se posible calcula explíci amen e el mínimo.
Pe cep ón simple
El siguien e algo i mo a es udia es conocido como pe cep ón, el pun o
más impo an e de es e es que de ine el elemen o básico con el que cons ui-
emos nues a ed neu onal: la neu ona.
Vamos a ob ene un algo i mo que sea capaz de ealiza una clasi icación
bina ia. Además, amos a u iliza una codi icación dis in a a la de la sección
an e io pa a las e ique as, en es e caso n∈ {1,−1}. De inido de es a o ma,
nos gus a ía que nues a unción y(x)de ol ie a 1 en caso de que el da o x
pe enezca a la clase C1y−1en caso de que co esponda a C2de es a o ma
de inimos (Bishop, 2006):
y(x) = (w x+b) = ( ˜w ˜x) = 1si w x+b≥0
−1si w x+b < 0
5.1. Ap endizaje au omá ico 67
eniendo w∈RD,b∈Ry, con la misma ab e ia u a que hemos in oducido
an es ˜x, ˜w∈RD+1, siendo Dla dimensión de los da os de en ada.
A la llama emos unción de ac i ación, su unción es lle a los alo es
al dominio que nos in e esa, en es e caso ±1. Pa a es e algo i mo la hemos
de inido como una unción de sal o, cuando eamos edes neu onales, nece-
si a emos alguna unción más po en e que es a pa a ob ene un esul ado
ace ado.
Nos in e esa ob ene un ˜wque consiga ˜w ˜xn>0si el da o xnpe enece
a la p ime a clase y ˜w ˜xn<0en caso de que lo haga a la segunda. Podemos
esumi es o en ˜w ˜xn n>0. Tenemos ya una o ma de de ini nues a unción
de cos e pa a cie o da o:
E( ˜w) = 0Si el da o es á bien clasi icado
−˜w ˜xn nEn caso con a io
la unción de cos e o al se á la suma de la unción de cos e asociada a cada
da o de en enamien o:
E( ˜w) =
N
X
i=1
Ei( ˜w)
Pa a en ena lo u iliza emos una e sión modi icada del en enamien o ex-
pues o pa a mínimos cuad ados: el descenso de g adien e es ocás ico. Es e
di ie e de la e sión o iginal en que en luga de u iliza la unción de cos e o-
al ac ualiza emos median e la unción pa icula de cada da o. Es conocido
como es ocás ico ya que en su implemen ación an es de comenza a epasa
los da os uno a uno y ealiza el descenso, se suelen eo dena los da os de en-
ada de o ma alea o ia. Dicho es o, bas a aho a con encon a el g adien e
de la unción de cos e que iene de inido i ialmen e po ∇En( ˜w) = −xn n
la egla de ac ualización queda en onces:
˜w( +1) =˜w( )Si el da o es á bien clasi icado
˜w( )+xn nEn caso con a io
Aunque es e algo i mo es á pensado pa a clasi icación bina ia, es ácil-
men e gene alizable al caso mul iclase, bas a con u iliza an os pe cep ones
como clases exis an y en ena cada uno pa a di e encia cie a clase Ckde
el es o. En el caso ideal se ob end ía en odos -1 excep o en 1, aunque
suele ocu i que más de uno de esul ado posi i o, en es e caso ha ía al a
compa a pa a cuál de ellos el esul ado de ˜w ˜xnes mayo .
Redes neu onales
Una ed neu onal, ambién conocida como pe cep ón mul icapa, gene-
aliza el concep o p esen ado po el pe cep ón. La idea es u iliza muchas
68 Capí ulo 5. Mejo ando MCTS con edes neu onales
neu onas que compa an la in o mación en e ellas y sean capaz de ealiza
las a eas de clasi icación y eg esión con mayo e icacia.
Dicho es o, de inimos una ed neu onal como una e na (N, V, w)siendo
Nun conjun o de neu onas y Vun conjun o {(i, j)|i, j ∈N}cuyos elemen os
son llamados conexiones en e la neu ona iy la neu ona j. La unción w:
V→Rde ine los pesos, donde w((i, j)), ep esen a el peso de la conexión
en e la neu ona iy la jque ab e ia emos como wi,j (K iesel, 2005).
Aho a, que emos da un poco más de es uc u a a es a de inición, po
ello amos a inclui el concep o de capa. Rede inimos en onces la de inición
como una e na (N, V, w)solo que aho a N={C1, C2...Cn}es un conjun o
de capas, cada uno de es os es en onces un conjun o de neu onas. Vamos
a modi ica ambién la de inición de Vpa a que únicamen e se pe mi an
conexiones en e una capa y la siguien e, de es a o ma V={(i, j, k)|i, j, k ∈
N} ep esen a la conexión en e las neu onas ide la capa Ck−1yjde Ck. Po
ende, el peso de es a conexión end á dado po w(i, j, k)que ab e ia emos
como wk
i,j, ambién u iliza emos la no ación Wkpa a e e encia la ma iz
cuyos elemen os son Wk
i,j =wk
i,j. Ob enemos así el concep o de ed neu onal
mul icapa.
Nues a ed de ine una composición de aplicaciones pues el esul ado
ob enido po la unción yse á la consecuencia de a a esa odas las capas
de la ed. Llama emos zk:RKk−1→RKka la unción cuyos da os de
en ada son los esul ados ob enidos en la capa an e io y gene a los nue os
da os. La dimensión del espacio de en ada es RKk−1se á igual al núme o de
neu onas de la capa Ck−1, lo mismo ocu e con la capa siguien e. A su ez,
las unciones zkson una composición de dos unciones:
zk=hk◦ak
aquí, akes una unción a ín simila a las que hemos is o en los algo i mos
an e io es:
ak(x) = Wkx+bk
Po su pa e, la unción hkha á el papel de la unción en el algo i mo
del pe cep ón, pe o amos a busca que es a sea una unción con inua. Una
elección común suele se la unción sigmoide σ:
σ(a) = 1
1 + e−a
que iene alo 0,5si a= 0, iende ápidamen e a 1cuando a→ ∞, y a 0
cuando a→ −∞. Aunque o as opciones pueden se la angen e hipe bólica
o la unción so max:
so max(a) = 




exp(a1)
K
P
k=1
exp(ai)
, ..., exp(aK)
K
P
k=1
exp(ai)





5.1. Ap endizaje au omá ico 69
Resumiendo:
y(x) = zk◦... ◦z1(x)(5.3)
=hk◦ak◦... ◦h1◦a1(x)(5.4)
Ya enemos pe ec amen e delimi ada nues a he amien a, aho a queda
en nues as manos de ini el núme o de capas, las neu onas que hab á en
cada capa, y la unción de cos e pa a asegu a nos de que e ec i amen e nos
ace camos a nues o obje i o. Po con enio se llama capa de en ada a C1
yCKse denomina capa de salida, las in e medias se conocen como ocul as.
Ve emos en un momen o que las edes con una capa ocul a nos se i án pa a
ap oxima cualquie unción, aunque dependiendo del dominio el aumen o
del núme o de capas puede lle a a un mejo compo amien o de la ed.
El núme o de neu onas en las capas de en ada y salida se á igual a la
dimensión de los espacios en los que se encuen an los da os de en ada y de
salida, aunque es e úl imo depende á del ipo de p oblema que aba quemos.
El núme o de neu onas en las capas ocul as se á decisión nues a, pueden da
esul ados dis in os dependiendo de es e núme o po lo que en la mayo ía de
las eces la de e minación iene dada po la ía expe imen al.
El único elemen o que nos al a aho a es la unción de cos e. P esen a-
mos es posibilidades, en caso de que u ilicemos la ed neu onal pa a da
espues a a un p oblema de eg esión busca emos minimiza la dispa idad
con los da os de en enamien o po lo que usa emos (Bishop, 2006):
E(w) = 1
2X
n||y(xn)− n||2
Pa a la clasi icación bina ia se suele u iliza :
E(w) = −X
n
nln yn+ (1 − n) ln(1 −yn)
po úl imo, pa a la clasi icación mul iclase se u iliza:
E(w) = −X
nX
k
nk log ynk
En enando las edes neu onales
En ena emos la edes neu onales median e un descenso de g adien e,
dada la g an can idad de da os que es as suelen maneja , es e suele se es-
ocás ico. Nos encon amos aho a en el p oblema de encon a el g adien e
en una unción de inida como en 5.4 lo que esul a no solo complicado eó i-
camen e sino que ambién muy cos oso a ni el compu acional, sin emba go,

Chap e 6
Conclusions and Fu u e Wo k
Gene al conclusions
Gi en he impossibili y o pe o ming a ull explo a ion o he game ee,
we ha e p esen ed 2 p ac ical me hods o sol e his issue: he one encom-
passed by Minimax using domain knowledge, and he one p oposed by MCTS
h ough simula ions. In bo h cases we a e ying o calcula e a heu is ic o
each node which e eals how good he node is. We ha e seen ha a mixed
app oach ha adds up expe knowledge o he one ob ained by simula ions
also b ings good esul s e en su passing algo i hms as Alpha-be a imp o ed
wi h a heu is ic.
I has been shown in his wo k ha he Mon e Ca lo T ee Sea ch al-
go i hm wo ks in a e y sol en way, in en i onmen s whe e i has been
p o en. I laun ed good esul s agains simple algo i hm as well as wi h ex-
pe au oma ic playe s wi h a wide knowledge o he domain in which hey
a e wo king. The aheu is ici y o MCTS allows us o adap i easily o e e y
game, ge ing a highly esolu i e playe in a sho ime and wi hou he need
o inqui e in he game.
The issues ha appea when applying i ha e also been shown. In pa ic-
ula , we app ecia e an impo an complexi y when using i o games which
con ain cycles, o ha do no ha e a de ined leng h. We also exposed a
p ac ical solu ion o his con lic by sac i icing he aheu is ici y.
In addi ion, we ha e seen ha he majo was e o compu a ional esou ces
is p oduced in he simula ion phase, and ha is in i in whe e we mus make
a s onge e o in op imiza ion. We ha e seen ha he mo e simula ions we
pe o m, he highe he eliabili y o he heu is ic calcula ed o each node.
77
78 Chap e 6. Conclusions and Fu u e Wo k
Objec i es e iew
Now we will e iew, one a he ime, each objec i e in he same o de
ha hey we e de ined in he in oduc ion:
1. Once ead his documen , he eade , wi hou p e ious knowledge o
he ma e , now unde s ands concep s o game heo y, da a s uc u es,
and se e al solu ions gi en by di e se esea che s o he p oblem o
explo ing a game ee. Besides, he games ha ha e been used in
his esea ch ha e also been p esen ed. I he eade ook he ime
o e iew he appendixes, hey will ha e ga he ed by now concep s o
algeb a and p obabili y.
2. The eade cu en ly knows he di e en pa s o he Mon e Ca lo T ee
Sea ch algo i hm, he way i wo ks, a ia ions and op imiza ions. This
way hey unde s and hese same concep s o PMCTS, and also hei
di e ences. Mo eo e , he eade has ecei ed he o mal p oo o why
he heu is ic alue es ima ion wo ks.
3. We ha e de eloped an MCTS based O hello playe as well as one PM-
CTS e sion. We aced i wi h Random,Dep h Fi s Sea ch and some
Alpha-be a e sions. Du ing he p ocess we ha e adap ed o each si -
ua ion o be able o ge a good esul .
4. Following he same pa h, we ha e implemen ed an au oma ic playe
base in each Mon e Ca lo e sion o play chess. These ha e shown
no o be as e icien as he ones exposed in he O hello sec ion. Ne -
e heless, gi en he low esou ces hey we e coun ing wi h, hey go
o o e some good esul s agains Random no mally domina ing he
game al hough hey almos ne e a i ed o a check ma e si ua ion.
5. Th ee powe ul ools ha e been in oduce o s udy he machine lea n-
ing ield: leas squa es, he pe cep on and neu al ne wo ks. Need ul
elemen s in he de elopmen o he cu en mos powe ul playe : Al-
phaGo. We also explained AlphaGo’s unc ioning and he oll ha
MCTS plays.
Fu u e wo k
In u u e lines o wo k, he simula ion’s execu ion ime should be im-
p o ed. Nowadays, he mos common idea o gene alize ela i ely easy cal-
cula ions is o make hem wo k in pa allel in sys ems wi h his capaci y. The
use o g aphic accele a o s could b ing MCTS o a new le el, ob aining mo e
6.3. Fu u e wo k 79
p ecise eedback in a lowe ime. The implemen a ion in sys ems like CUDA
could be a solu ion o his issue.
On he o he hand, we hink ha in chess game, he s a e space is so big
ha only wi h inc easing he simula ions p obably would no be enough. I
would be necessa y o enhance he powe o he sys em so he simula ions a e
un un il he end o he game and also i would be in e es ing o implemen
a machine lea ning sys em ha helps making i mo e accu a e as he ime
passes.
Apéndice A
Concep os de p obabilidad
Se mues an aquí la de inición de di e sos concep os que han sido u ili-
zados a lo la go del documen o.
Espacio medible. Un espacio medible o p obabilizable es el pa (Ω,A)
dónde Ωes un espacio mues al y Aes un σ-algeb a de conjun os de
Ω. (Gonzalez, 2016)
σ-álgeb a. Dado un espacio mues al Ω, se dice que una amilia de
subconjun os A⊂P(Ω) iene es uc u a de σ-álgeb a si y solo si se
e i ican:
1. Ω∈ A
2. ∀A∈ A, Ac∈ A
3. ∀{An:n≥1}⊂A,
∞
S
n=1
An∈ A
Medida de p obabilidad. Una unción de conjun o P:A → [0,1]
es llamada medida de p obabilidad si y solo si sa is ace:
1. P(A)≥0,∀A∈ A
2. P(Ω) = 1
3. ∀{An:n≥1}⊂A al que Ai∩Aj=∅,∀i6=j
P ∞
[
n=1
An!=
∞
X
n=1
P(An)
(Kolmogo o , 1956)
Aplicación medible. Sean (Ω1,A1)y(Ω2,A2)espacios medibles. Se
dice que : Ω1→Ω2es una aplicación medible si y solo si −1(B)∈
A1∀B∈ A2. (Co al, 2012)
81

82 Apéndice A. Concep os de p obabilidad
Función medible. Se llama unción medible a oda aplicación medible
donde el espacio de des ino es (Rn, βn)pa a algún n. (Co al, 2012)
Va iable alea o ia. Una a iable alea o ia es una unción medible
: (Ω,A, P)→(R, β); es deci , donde el espacio inicial es un espacio
de p obabilidad. (Co al, 2012)
Función de dis ibución. La unción
F(x)(a) = P(x)(−∞, a) = Px < a
donde −∞ y+∞son alo es pe mi idos de a, se llama unción de
dis ibución de la a iable alea o ia x.(Kolmogo o , 1956)
Mues a alea o ia simple. Dada una población Xse llama mues a
alea o ia simple de amaño na la epe ición de X1, ..., Xn a iables
alea o ias independien es con dis ibución igual a la de X. Es deci , la
unción de dis ibución de la mues a (x1, ..., xn)es
F(x1, ..., xn) =
n
Y
i=1
F(xi)
donde F(x)es la unción de dis ibución de la población X(Ángel Vi-
llegas, 2005)
Función de dis ibución empí ica. Dada una ealización pa icula
de una mues a (x1, ..., xn), llamamos unción de dis ibución empí ica
a
F∗
n(x) = 0si x < x(1)
k
nsi x(k)≤x<x(k+1)1si x ≥x(n)
donde (x(1), ..., x(n))es la mues a o denada de meno a mayo .(Ángel
Villegas, 2005)
Co elación Magni ud que mide el g ado de elación exis en e en e
dos a iables alea o ias. Es medido po el coe icien e de co elación.
Coe icien e de co elación El coe icien e de co elación de dos
a iables alea o ias XeYes la media a i mé ica de los p oduc os
de las des iaciones de los alo es co espondien es de sus espec i as
medias. (Kenney, 1939)
=
1
NP(x−¯x)(y−¯y)
σxσy
Apéndice B
Concep os de álgeb a y análisis
P esen amos a con inuación de iniciones y p oposiciones que se han u i-
lizado en el ex o.
Espacio ec o ial. Sea Kun cue po y Vun conjun o no acío; di e-
mos que Ves un espacio ec o ial sob e Ksi:
1. En Vhay de inida una ope ación in e na, que deno a emos po
+, de o ma que (V, +) es un g upo abeliano, es deci , e i ica
es as p opiedades:
a)(u+ ) + w=u+ ( +w); ∀u, , w ∈V
b)u+ = +u;∀u, ∈V
c)∃0∈V al que 0 + = + 0 = ;∀ ∈V
d)∀ ∈V∃− al que + (− )=(− ) + = 0
2. En Vhay de inida una ope ación ex e na de K, que deno a emos
po yux aposición, e i icando:
a)a(u+ ) = au +a ;∀a∈K,∀u, ∈V
b)(a+b)u=au +bu;∀a, b ∈K∀u∈V
c)a(bu)=(ab)u;∀a, b ∈K∀u∈V
d)1u=u;∀u∈Udonde 1es la unidad pa a el p oduc o en K
los elemen os del espacio ec o ial suelen llama se ec o es, mien as
que a los del cue po Klos llama emos escala es. (Me ino y San os,
2006)
Independencia lineal. Di emos que un conjun o de ec o es { 1, 2, ..., n}
son linealmen e independien es si de cada combinación lineal a1 1+
...+an n= 0 de deduce que a1=... =an= 0.(Me ino y San os, 2006)
Sis ema de gene ado es. Un conjun o de ec o es Sse dice que es
un sis ema de gene ado es del espacio ec o ial Vsi odo ec o de V
es combinación lineal de los ec o es de S.(Me ino y San os, 2006)
83
84 Apéndice B. Concep os de álgeb a y análisis
Base de un espacio. Dado un espacio ec o ial V, un subconjun o
B⊆Ves una base de Vsi
1. B es linealmen e independien e.
2. B es sis ema de gene ado es de V
Dimensión de un espacio ec o ial. Llamamos así al núme o de
ec o es en cualquie a de las bases.(Me ino y San os, 2006)
Subespacio ec o ial. Sea Vun espacio ec o ial sob e Ky sea Uun
subconjun o no acío de V. Decimos que Ues un subespacio ec o ial
de Vsi se e i ican las siguien es condiciones:
1. ∀u, ∈Uu + ∈U
2. ∀u∈U∀a∈K, au ∈U
Espacio a ín. Dado un conjun o no acío Ay un espacio ec o ial
Vdi emos que Aes un espacio a ín sob e Vsi se iene de inida la
aplicación
A×A → V
que a cada pa de elemen os de A,(A, B), le hace co esponde un
único ec o es ~
AB, y que e i ica las dos siguien es p opiedades:
1. Pa a cada A∈ A y cada ∈Vexis e un único elemen o B∈ A
al que ~
AB = .
2. Pa a cada e na A, B, C ∈ A ocu e ~
AB +~
BC =~
AC
di emos que Ves el espacio ec o ial asociado y de inimos la dimen-
sión del espacio a ín como la dimensión del espacio ec o ial asociado.
(Me ino y San os, 2006)
Hipe plano. Llama emos a iedad a ín a la gene alización de espacio
ec o ial a espacio a ín, y llama emos hipe plano a una a iedad a ín
de dimensión n−1en un espacio de dimensión n.(Me ino y San os,
2006)
T aza de una ma iz. Suma de los elemen os de la diagonal de una
ma iz. Dada una ma iz Adeno a emos su aza como (A)la aza
cumple las siguien es p opiedades:
1. (A) + (B) = (A+B)
2. a (A) = (aA)pa a odo aescala
3. (A) = (A )
4. (AB) = (BA)
85
No ma de un ec o . Dado un ec o ude inimos su no ma como:
||u|| =√< u, u >
(Me ino y San os, 2006)
De i ada. Sea I⊆Run in e alo, :I→Runa unción y c∈I.
Decimos que un núme o eal Les la de i ada de Fen csi dado cualquie
ε > 0exis e δ(ε)>0 al que si c∈Isa is ace 0<|x−c|< δ(ε)
en onces 
(x)− (c)
x−c−L
< ε
En es e caso di emos que es di e enciable en c y esc ibimos 0(c).
Podemos calcula es o en onces como:
0(c) = l´ım
h→0
(c+h)− (c)
h
. (Ba le y Shebe , 1927)
De i ada di eccional. En Rngene alizamos el concep o de de i ada
y lo llamamos de i ada di eccional:
D = l´ım
h→0
(x+h )− (x)
h
(Bombal e al., 1988)
G adien e. Llama emos g adien e de y lo deno a emos po ∇ al
ec o :
(De1 , ..., Den )
Siendo e1, ..., enlos ec o es de la base canónica.(Bombal e al., 1988)