T´ecnicas de acele aci´on pa a el econocimien o de
piezas de ajed ez
Accele a ion echniques o chess piece
ecogni ion
TRABAJO DE FIN DE GRADO DEL GRADO EN
INGENIER´
IA INFORM´
ATICA
Cu so 2019/2020
UNIVERSIDAD COMPLUTENSE DE MADRID
FACULTAD DE INFORM´
ATICA
Di ec o : Albe o An onio del Ba io Ga c´ıa
Codi ec o : Manuel P ie o Ma ´ıas
Da id Mallas´en Quin ana
Mad id, 20 de junio de 2020
Resumen
La digi alizaci´on au om´a ica de pa idas de ajed ez median e isi´on a i icial es
un e o ecnol´ogico signi ica i o. Es imp escindible an o pa a los o ganizado es de
o neos como pa a jugado es ama eu s o p o esionales de ca a a e ansmi i en l´ınea
o analiza las pa idas median e mo o es de ajed ez. En es e abajo p ime o hemos
en enado y compa ado di e sas edes neu onales con olucionales pa a la clasi ica-
ci´on de piezas de ajed ez. Pos e io men e, hemos acele ado sob e una N idia Je son
Nano la de ecci´on del able o y la in e encia de es os modelos, necesa ios pa a una
comple a digi alizaci´on. Conseguimos as´ı un amewo k uncional que digi aliza au-
om´a icamen e la con igu aci´on de un able o de ajed ez sob e un sis ema empo ado
en menos de 5 segundos, con una p ecisi´on del 92 % al clasi ica las piezas y un 95 %
al de ec a el able o.
Palab as cla e
Acele aci´on de edes neu onales, N idia Je son Nano, ONNX, Tenso RT, Aje-
d ez, FEN, Visi´on a i icial, Redes neu onales con olucionales, Deep lea ning, Py -
hon.
Abs ac
Au oma ic digi iza ion o chess games by means o compu e ision is a signi ican
echnological challenge. I is essen ial bo h o ou namen o ganize s and ama eu
o p o essional playe s in o de o b oadcas online o analyze games using chess
engines. In his wo k, we ha e i s ained and compa ed di e en con olu ional
neu al ne wo ks o chess piece classi ica ion. Subsequen ly, we ha e accele a ed on
a N idia Je son Nano he de ec ion o he boa d and he in e ence o hese models,
equi ed o a comple e digi iza ion. Thus achie ing a unc ional amewo k ha
au oma ically digi izes he con igu a ion o a chessboa d on an embedded sys em in
less han 5 seconds, wi h an accu acy o 92 % when classi ying he pieces and 95 %
when de ec ing he boa d.
Keywo ds
Neu al ne wo k accele a ion, N idia Je son Nano, ONNX, Tenso RT, Chess,
FEN, Compu e ision, Con olu ional neu al ne wo ks, Deep lea ning, Py hon.
Ag adecimien os
En p ime luga , g acias a Albe o y Manuel po pensa en m´ı pa a es e abajo
y po odo su in e ´es e innume ables co ecciones e ideas du an e odo es e iempo.
Desde las p ime as euniones con un able o de ajed ez delan e, has a las sesiones
i uales de los ´ul imos meses.
G acias ambi´en a odos los dem´as p o eso es que du an e es os a˜nos hab´eis
hecho que descub a mi ocaci´on y que quie a con e i es a pasi´on en mi p o esi´on.
Que ´ıa ag adece ambi´en odo el apoyo desde siemp e po pa e de mi amilia.
En es e caso especialmen e el incon o mismo de mi mad e, que me empuj´o e hizo
que no haya es udiado “solo” ma em´a icas.
No que ´ıa ol ida me de odos mis amigos, es ´eis m´as ce ca o m´as lejos, de
odos aquellos con los que he compa ido echo e inquie udes, compa˜ne os de clase
y pe sonas en gene al con las que me he c uzado es os a˜nos. Sin oso os no se ´ıa ni
la mi ad de eliz de lo que soy aho a.
Es e abajo ha sido inanciado po la Uni´on Eu opea (FEDER), el Gobie no de
Espa˜na y la Comunidad de Mad id a a ´es de los p oyec os RTI2018-093684-B-I00
y S2018/TCS-4423.
´
Indice gene al
´
Indice de igu as III
´
Indice de ablas IV
´
Indice de algo i mos V
1. In oducci´on 1
1.1. An eceden es ............................... 1
1.2. Obje i os y plan de abajo . . . . . . . . . . . . . . . . . . . . . . . 2
2. De ecci´on del able o 5
2.1. Desc ipci´on de las i e aciones . . . . . . . . . . . . . . . . . . . . . . 5
2.1.1. De ecci´on de l´ıneas ec as . . . . . . . . . . . . . . . . . . . . 7
2.1.2. B´usqueda de pun os de la cuad ´ıcula . . . . . . . . . . . . . . 8
2.1.3. Iden i icaci´on de la posici´on del able o . . . . . . . . . . . . . 10
2.1.4. Fin de la i e aci´on . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2. Ob enci´on de las casillas indi iduales . . . . . . . . . . . . . . . . . . 13
2.2.1. Nue om´e odo........................... 14
3. Clasi icaci´on de las piezas 17
3.1. No aci´onFEN............................... 17
3.2. Da ase e ique ado de piezas . . . . . . . . . . . . . . . . . . . . . . . 17
3.3. En enamien o de los modelos . . . . . . . . . . . . . . . . . . . . . . 18
3.4. In e encia ................................. 20
3.4.1. In e encia en able os consecu i os . . . . . . . . . . . . . . . 21
4. Acele aci´on 25
4.1. Pla a o mas de in e encia . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.2. Op imizado es: ONNXRun ime y Tenso RT . . . . . . . . . . . . . . 26
4.3. De ecci´on del able o . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.3.1. P ime an´alisis: Op imizaci´on median e ONNX . . . . . . . . 29
4.3.2. Segundo an´alisis: Reducci´on del sob ecos e de NumPy . . . . . 29
4.3.3. Te ce an´alisis: Reducci´on del sob ecos e de Ben ley-O mann 30
4.4. Clasi icaci´on de las piezas . . . . . . . . . . . . . . . . . . . . . . . . 31
4.4.1. Elecci´on del modelo . . . . . . . . . . . . . . . . . . . . . . . . 32
4.4.2. Op imizaci´on de la in e encia . . . . . . . . . . . . . . . . . . 34
i
5. Resul ados 37
5.1. De ecci´on del able o . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
5.2. Clasi icaci´on de las piezas . . . . . . . . . . . . . . . . . . . . . . . . 38
5.3. Digi alizaci´on o al . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
6. Conclusiones y abajo u u o 44
7. In oduc ion (English) 46
7.1. Rela edwo k ............................... 46
7.2. Objec i es and wo k plan . . . . . . . . . . . . . . . . . . . . . . . . 47
8. Conclusions and u u e wo k 49
Re e encias 51
ii

´
Indice de igu as
Figu a 1.1. Ejemplo de o o omada po la c´ama a. . . . . . . . . . . . . . 3
Figu a 1.2. Esquema de la si uaci´on de la c´ama a y del ha dwa e que
ealiza ´a el c´ompu o en el uso inal. . . . . . . . . . . . . . . . . . . . 4
Figu a 2.1. Ejemplo de las im´agenes ob enidas despu´es de cada i e aci´on. 6
Figu a 2.2. Ejemplo de dos e apas en la p ime a ase de de ecci´on de l´ıneas. 7
Figu a 2.3. Ejemplo de las e apas inales de ase de de ecci´on de l´ıneas. . . 8
Figu a 2.4. Ejemplo de pun os que s´ı o man pa e de la cuad ´ıcula. . . . 10
Figu a 2.5. Ejemplo de las e apas de ase de iden i icaci´on del able o. . . 12
Figu a 2.6. Ejemplo del inal de la p ime a i e aci´on. . . . . . . . . . . . . 13
Figu a 2.7. Esquinas de ec adas en la imagen o iginal. . . . . . . . . . . . 14
Figu a 2.8. Reco e de las casillas. . . . . . . . . . . . . . . . . . . . . . . 16
Figu a3.1. No aci´onFEN. .......................... 18
Figu a 3.2. Ejemplo de ec o de p obabilidades pa a una casilla del able o. 20
Figu a 3.3. Esquema de los da os empleados en la in e encia de la con i-
gu aci´ondel able o. ........................... 22
Figu a 4.1. Ejecuci´on sob e un n´ucleo CUDA de 32 bi s de dos ope aciones
delmismo ipoenFP16.......................... 26
Figu a 4.2. Flujo de abajo pa a la acele aci´on de la in e encia. . . . . . . 27
Figu a 4.3. Imagen de p ueba pa a la clasi icaci´on de las piezas. . . . . . . 32
Figu a 5.1. P ecisi´on ob enida po cada modelo en unci´on del iempo. . . 40
iii
´
Indice de ablas
Tabla 4.1. Modelos iniciales ejecu ando la in e encia median e Ke as. . . . 32
Tabla 4.2. Modelos m´as sencillos ejecu ando la in e encia median e Ke as. 33
Tabla 4.3. Modelos ejecu ando la in e encia median e ONNXRun ime. . . 34
Tabla 4.4. Modelos ejecu ando la in e encia median e Tenso RT. . . . . . 35
Tabla 4.5. Modelos ejecu ando la in e encia median e Tenso RT en un
ba ch de64im´agenes............................ 36
Tabla 5.1. Tiempo medio po imagen pa a cada una de las e siones de la
de ecci´ondel able o............................ 37
Tabla 5.2. Valo Top-1 y p ecisi´on as in oduci conocimien o del domi-
nio pa a cada uno de los modelos. . . . . . . . . . . . . . . . . . . . . 38
Tabla 5.3. Mejo es iempos po able o y p ecisiones ob enidas pa a cada
modelo sob e la Je son Nano, jun o con el op imizado u ilizado. . . . 39
Tabla 5.4. Resumen de iempos o ales sob e la Je son Nano po able o
de p ueba pa a cada uno de los modelos que o man el en e de Pa e o. 41
Tabla 5.5. Resumen de iempos o ales pa a cada uno de los modelos que
o man el en e de Pa e o sob e la Je son Nano cuando la comp o-
baci´on de la posici´on del able o de uel e cie o. . . . . . . . . . . . . 43
i
´
Indice de algo i mos
Algo i mo 2.1. Desc ipci´on de una i e aci´on. . . . . . . . . . . . . . . . . . 5
Algo i mo 2.2. De ecci´on de l´ıneas ec as (SLID)................ 7
Algo i mo 2.3. B´usqueda de pun os de la cuad ´ıcula (LAPS). ........ 9
Algo i mo 2.4. Iden i icaci´on de la posici´on del able o (CPS)......... 11
Algo i mo 3.1. C´alculo de la con igu aci´on del able o a pa i de los ec-
o es de p obabilidades de cada casilla. . . . . . . . . . . . . . . . . . . 23
Algo i mo 3.2. In e encia del ipo de pieza a pa i de su mo imien o. . . . 24
Algo i mo 5.1. Comp obaci´on de la posici´on del able o. . . . . . . . . . . . 42
Cap´ı ulo 1
In oducci´on
El econocimien o de piezas y able os de ajed ez es un p oblema de isi´on a -
i icial que a´un no se ha esuel o de mane a e icien e. Sin emba go, su soluci´on es
c ucial pa a muchos jugado es expe imen ados que desean compe i con a mo o es
de ajed ez y p og amas especializados, pe o que ambi´en p e ie en oma decisiones
usando un able o de ajed ez ´ısico. Adem´as, es impo an e pa a los o ganizado es
de o neos de ajed ez que desean digi aliza el juego pa a la e ansmisi´on en l´ınea
o pa a los jugado es a icionados que desean compa i sus pa idas con amigos. Po
lo gene al, es as a eas de digi alizaci´on son ealizadas po humanos o con la ayuda
de able os de ajed ez y piezas especializadas.
Pa a consegui digi aliza una pa ida de o ma au om´a ica, es necesa io se
capaz de econoce an o el able o de ajed ez como pos e io men e las posiciones
de las piezas. En el escena io de las pa idas en i o, adem´as de la p ecisi´on es
c ´ı ico minimiza el iempo necesa io pa a ealiza dicho econocimien o, ya que las
jugadas pueden sucede se muy elozmen e. Es e es el caso de las modalidades de
juego conocidas como “Bli z” y “Bulle ”, en las que cada jugado iene en e 1 y
5 minu os pa a juga oda la pa ida. Tambi´en ocu e es o mismo en las pa idas
cl´asicas cuando queda poco iempo.
1.1. An eceden es
Una soluci´on ha dwa e pa a la digi alizaci´on au om´a ica de las pa idas son los
able os especializados que de ec an las piezas ´ısicamen e. Ejemplos ecien es que se
usan ac ualmen e en g andes o neos los podemos encon a en [Squ]o[DGTa]. Sin
emba go, es os able os son cos osos y di ´ıcilmen e desplegables en muchos ´ambi os.
A modo de ejemplo, un se de able o y piezas de DGT (ma ca usada en o neos
o iciales) cues a desde unos 500ehas a m´as de 1000e[DGTb].
O as al e na i as son las p opo cionadas po obo s que mue en las piezas de
un able o, como pueden se [Ma +11] o m´as ecien emen e [CW19]. Es os obo s se
basan en posiciona una c´ama a ceni al sob e el able o y de ec a los di e enciales
en e un mo imien o y el siguien e. Un incon enien e de es o es que se necesi a pa i
de un es ado inicial conocido, no se pod ´ıa digi aliza de es a o ma un able o con
una con igu aci´on de piezas gen´e ica. Adem´as, hab ´ıa que ene en cuen a los allos,
po que se pod ´ıan encadena en cada nue a jugada.
Las soluciones que o ece la isi´on a i icial son una al e na i a a ene en cuen a,
ya que p opo cionan sis emas m´as ba a os y cada ez m´as p ecisos, adem´as de se
un e o ecnol´ogico impo an e. Como compa aci´on, la pla a o ma que u iliza emos
1
2.2b como a ias de las l´ıneas de la cuad ´ıcula del able o se de ec an de o ma
discon inua como segmen os di e en es. La unci´on que decide si dos segmen os se
deben uni o no es ´a desc i a en [CLW17]. A la ho a de es udia la colinealidad, iene
en cuen a ambi´en la longi ud de los segmen os en compa aci´on con el ama˜no de la
imagen. Es o se debe a que segmen os muy co os ce ca de un segmen o muy la go
en ealidad pueden o ma pa e de la misma ec a, aunque el ´angulo que o men
en e ellos sea ela i amen e g ande. Con o me c ece la longi ud, es a es icci´on
sob e el ´angulo se uel e m´as es ic a.
Finalmen e, los conjun os de segmen os colineales ob enidos se usionan en una
´unica ec a. Pa a ello, p ime o se con ie en los segmen os en pun os, eniendo en
cuen a que a mayo longi ud m´as n´ume o de pun os, y pos e io men e se busca la
ec a que mejo se ajus e a ellos (Figu a 2.3a). Es o ´ul imo se consigue a pa i de un
M-es imado pa a modelos ap oximadamen e lineales [Wie96] que encuen a dicha
ec a i e a i amen e median e el algo i mo de m´ınimos cuad ados. Es a ap oxima-
ci´on busca sol en a algunos de los p oblemas que p esen an los algo i mos que se
basan en el es udio de los cen oides de inidos po los segmen os. De es a o ma, el
m´e odo se ajus a a la in uici´on de que la ec a de mejo ajus e se debe ap oxima
lo m´aximo posible a los segmen os m´as la gos del conjun o.
(a) L´ıneas ob enidas a pa i de los pun-
os o mados po los segmen os.
(b) Resul ado inal de la ase de de ec-
ci´on de l´ıneas.
Figu a 2.3: Ejemplo de las e apas inales de ase de de ecci´on de l´ıneas.
2.1.2. B´usqueda de pun os de la cuad ´ıcula
A pa i de las l´ıneas de ec adas en el paso an e io , se ob ienen odos los pun os
de in e secci´on de las mismas. De es os, se selecciona el subconjun o de pun os
que enga una al a p obabilidad de o ma pa e de la cuad ´ıcula o mada po las
casillas del able o de ajed ez. Pa a consegui lo hay dos ´ıas que se complemen an:
un p ime de ec o geom´e ico que se enca ga de il a posi i amen e los casos m´as
sencillos y una ed neu onal que e mina de disc imina los pun os m´as complicados
(Algo i mo 2.3).
8

Algo i mo 2.3: B´usqueda de pun os de la cuad ´ıcula (LAPS).
En ada: Imagen que con iene un able o.
L´ıneas de ec adas po SLID.
Salida: Conjun o de pun os que o man pa e de la cuad ´ıcula del able o.
1pun os cuad icula ←[ ];
2pa a cada pun o ∈in e secciones(lineas)hace
3ma iz ←p ep ocesa ( ecindad(imagen,pun o));
4es pun o cuad icula ←de ec o geome ico(ma iz);
5si es pun o cuad icula en onces
6pun os cuad icula.inse a (pun o)
7en o o caso
8es pun o cuad icula ← ed neu onal(ma iz);
9si es pun o cuad icula en onces
10 pun os cuad icula.inse a (pun o)
11 in
12 // Si no pe enece a la cuad ´ıcula, pasamos al siguien e
13 in
14 in
15 de ol e pun os cuad icula
Pa a iden i ica odas las in e secciones de las l´ıneas ob enidas en el m´odulo an-
e io , se u iliza el algo i mo de ba ido de Ben ley-O mann [BO79]. Las ecindades
de es os pun os en la imagen se ´an lo que se es udie pa a comp oba si e ec i amen e
se a an de pun os con una al a p obabilidad de o ma pa e de las in e secciones
del able o. Pa iendo de una peque˜na ma iz de p´ıxeles cen ada en cada uno de los
pun os, se p ep ocesa pa a man ene solo la in o maci´on ele an e y, como hemos
comen ado an e io men e, p ime o se aplica un de ec o geom´e ico pa a ma ca
´apidamen e como posi i os las si uaciones m´as comunes.
Es e de ec o geom´e ico busca con o nos y comp ueba si el en o no del pun o
es ´a o mado po cua o omboides. En caso a i ma i o, es amos an e un pun o que
muy posiblemen e o me pa e de la cuad ´ıcula del able o que buscamos. Es o se
debe a que los cua o omboides se co esponde ´an con las cua o casillas que o man
pa e de cada in e secci´on (Figu a 2.4a).
En caso de que no se de ec e es e pa ´on en los al ededo es del pun o, el siguien e
paso es in en a dis ingui si es o se debe, po ejemplo, a que una de las piezas es ´a
ocul ando pa cialmen e la in e secci´on (Figu a 2.4b). Pa a ello se u iliza una ed
neu onal con olucional en enada sob e un conjun o de casos muy di e sos. As´ı
se ob ienen las p obabilidades de que el pun o pe enezca al conjun o con el que
segui emos abajando en el siguien e m´odulo. Solo en caso de que el esul ado sea
posi i o con una p obabilidad muy al a, se da el pun o como ´alido y se u iliza ´a
pa a iden i ica el able o.
9
(a) Bas a el de ec o geom´e ico. (b) Es necesa ia la ed neu onal.
Figu a 2.4: Ejemplo de pun os que s´ı o man pa e de la cuad ´ıcula.
2.1.3. Iden i icaci´on de la posici´on del able o
El paso inal de cada i e aci´on es iden i ica el able o a pa i de los pun os y
las l´ıneas encon adas an e io men e. Pa a ello, el algo i mo analiza los conjun os
de cua o ec as que o men un cuad il´a e o pa a decidi cu´al de ellos es el que
se co esponde con el able o que es amos buscando (Algo i mo 2.4). N´o ese que,
como los pun os que hemos encon ado son los que o man las in e secciones de la
cuad ´ıcula, en ealidad no es amos encuad ando el able o comple o, sino el espacio
6×6 o mado po las casillas cen ales. Es o no se ´a un p oblema po que al inal
de la i e aci´on se oma un ma gen del ancho de una casilla, eniendo en cuen a la
pe spec i a, al ededo de es e ma co. De es a o ma, en ´ul ima ins ancia, se ´a es e
ma gen el que se co esponda con los bo des eales del able o ( e Figu a 2.6a).
El algo i mo oma la decisi´on de qu´e cuad il´a e o es mejo en base a una unci´on
de cos e que iene su m´aximo cuando las cua o l´ıneas o man pe ec amen e el ma co
de un able o de ajed ez, con la limi aci´on al espacio 6 ×6 que hemos comen ado
an e io men e. Es a unci´on polysco e [CLW17] es ´a de inida como, dado un ma co
F:
P(F) = L4
A2
F
W3(k)W5(l).
Donde Les el n´ume o de pun os den o del ma co, AFes el ´a ea del ma co F,kes
la dis ancia media de los pun os den o del ma co a su bo de m´as ce cano, les la
dis ancia del cen oide del g upo de pun os den o del ma co al cen oide del ma co
yWes la unci´on de peso siguien e 1:
Wj(x) = 1
1 + j
px
L
.
In ui i amen e, pa a maximiza P(F) hay que maximiza Ly minimiza AF,kyl.
Pa a e i a la comp obaci´on de las n
4posibles o mas de elegi cua o ec as,
se op imiza el algo i mo pa a solo e isa algunas de las combinaciones. Es a op i-
mizaci´on empieza encon ando el mayo cl´us e de pun os de la cuad ´ıcula median e
el algo i mo DBSCAN [Es +96] y desca a el es o, ya que es e debe ´ıa ep esen a
1Exis e una e a a en [CLW17] con i mada po los au o es. La ´o mula es ´a co egida en la
implemen aci´on y el denominado es e ec i amen e Len luga de AF.
10
Algo i mo 2.4: Iden i icaci´on de la posici´on del able o (CPS).
En ada: L´ıneas de ec adas po SLID.
Pun os de la cuad ´ıcula de uel os po LAPS.
Salida: Coo denadas en la imagen de las cua o esquinas de la cuad ´ıcula.
1// Ob ene las l´ıneas que bo dean al mayo cl´us e de pun os de la
cuad ´ıcula.
2clus e s ←DBSCAN(pun os cuad icula);
3clus e able o ←max(clus e s);
4lineas candida as ←es a ce ca bo de(lineas,clus e able o);
5// Escoge el pa de l´ıneas e icales y ho izon ales que se ajus e
m´as al bo de del able o
6lineas e icales ←es e ical(lineas candida as);
7lineas ho izon ales ←es ho izon al(lineas candida as);
8 alo max ← −∞;
9pa a cada 1, 2∈lineas e icales,h1, h2∈lineas ho izon ales hace
10 alo ←polysco e( 1, 2, h1, h2);
11 si alo >max alo en onces
12 max alo ← alo ;
13 mejo ma co ←[ 1, 2, h1, h2];
14 in
15 in
16 de ol e in e secciones(mejo ma co)
11
al able o que buscamos. A con inuaci´on, de odas las l´ıneas que se han ob enido en
el p ime paso, solo se ienen en cuen a las que es ´en ce ca de alguno de los pun os
an e io es, que adem´as no pasen ce ca del cen oide del cl´us e y, ayud´andose de la
unci´on de polysco e, comp ueba que ambi´en es ´en en las ecindades del bo de del
able o.
Finalmen e, se di iden las ec as an e io es en ho izon ales y e icales, eniendo
en cuen a la pe spec i a. De es a mane a, bas a con oma pa es de es as ec as
e icales y ho izon ales pa a elegi el ma co que maximiza la unci´on de polysco e
(Figu a 2.5a). Las cua o ec as ob enidas de e mina ´an el espacio cen al del able o
y, a pa i de es o, se pod ´a deduci su posici´on exac a (Figu a 2.5b).
(a) Pa es de l´ıneas ho izon ales y e i-
cales que se conside an.
(b) Espacio cen al del able o iden i ica-
do jun o con los pun os de la cuad ´ıcula
de ec ados.
Figu a 2.5: Ejemplo de las e apas de ase de iden i icaci´on del able o.
2.1.4. Fin de la i e aci´on
Pa a pasa del cuad ado 6 ×6 al able o comple o, se o ma un bo de que, en
´ul ima ins ancia, con e ge ´a a sus l´ımi es eales. Es o se consigue a˜nadiendo un
ma gen a una dis ancia ija. Es a dis ancia se ´a la co espondien e a una casilla
cuando el able o ocupe la o alidad de la imagen en la ´ul ima i e aci´on. Como en
i e aciones in e medias el able o ocupa solo un subconjun o del o al, es e bo de
siemp e se ´a mayo o igual que el necesa io, con eniendo al able o eal (Figu a
2.6a).
Veamos c´omo ob ene es a imagen inal de la i e aci´on. Es o se i ´a an o como
inicio de la siguien e i e aci´on, si la hubie a, como imagen eco ada del able o
despu´es de ans o ma lo eniendo en cuen a la pe spec i a.
La imagen inal de cada i e aci´on se ´a un cuad ado de 1200 p´ıxeles de lado.
As´ı, el obje i o es que los pun os de ec ados que con ienen al able o (los pun os
e des en la Figu a 2.6a) sean los nue os ex emos de la imagen pa a la siguien e
12
i e aci´on. Pa a consegui es o, se calcula la ma iz de la p oyecci´on pe spec i a que
lle a los cua o pun os que hemos ob enido a los pun os (0,0), (1200,0), (0,1200)
y (1200,1200). A pa i de es a ma iz, se ans o ma ´a la imagen inicial, eco ada
po los cua o pun os, en el cuad ado que buscamos (Figu a 2.6b).
(a) Cuad ado 6 ×6 cen al del able o
( ojo) y ma gen que omamos ( e de).
(b) Imagen despu´es de aplica la
ans o maci´on en pe spec i a.
Figu a 2.6: Ejemplo del inal de la p ime a i e aci´on.
2.2. Ob enci´on de las casillas indi iduales
Una ez conocida la posici´on del able o en la imagen o iginal, enemos que
sepa a la en las casillas indi iduales de ca a a clasi ica las pa a ob ene el esul ado
inal. La p ime a ap oximaci´on consis e simplemen e en di idi la imagen de la
´ul ima i e aci´on de la de ecci´on del able o en un 8 ×8. Sin emba go, es o p esen a
un p oblema impo an e que a a emos de esol e median e un nue o m´e odo.
Como se puede obse a en la Figu a 2.1, con o me las i e aciones se ajus an
al able o, las piezas que es ´an en los bo des se en eco adas pa cialmen e. Es e
p oblema es a´un m´as g a e en el caso de la ila supe io de la imagen, en la que solo
se puede e la base de las piezas seg´un el ´angulo con el que se haga la o o. Sal o
que la imagen se ome desde un plano ceni al lo su icien emen e alejado del able o,
lo no mal es que cada pieza in ada el espacio ocupado po sus casillas ecinas.
Adem´as, po es o ´ul imo, la pa e in e io de cada casilla es la m´as p opensa
a con ene in o maci´on de casillas ecinas. Po es e mo i o, debe ´ıamos ija nos en
m´as pa es de la imagen adem´as de en los l´ımi es o mados po la p opia casilla
exclusi amen e.
13

Figu a 2.7: Esquinas de ec adas en la imagen o iginal.
2.2.1. Nue o m´e odo
Como nues o obje i o es oma una o o desde un la e al del able o, ya que es
mucho m´as sencillo que ene que posiciona una c´ama a a cie a al u a po encima,
buscamos dise˜na o o m´e odo que se adap e mejo a es as ci cuns ancias. Pa a ello,
nos basamos en la idea u ilizada en [Din16] pa a ene en cuen a que las piezas is as
en pe spec i a son m´as al as que el la e al de una casilla.
El p oblema de es e m´e odo es que pa a pode ene en cuen a la o alidad de las
piezas, no nos bas a con la imagen inal del able o eco ado. Es deci , las casillas
indi iduales hay que pasa a ob ene las de la imagen o iginal. El esul ado de las
i e aciones al de ec a el able o no nos p opo ciona las coo denadas de es e en la
o o inicial, as´ı que enemos que in e i las ans o maciones pe spec i as que se
ealizan al pasa de una i e aci´on a la siguien e. Como ejemplo, en la Figu a 2.1
end ´ıamos que hace la ans o maci´on (d) →(c) →(b) →(a).
Pa a consegui es o, nos amos gua dando los cua o pun os de las esquinas
ob enidos al inaliza cada i e aci´on. De es a o ma, pod emos calcula las ma ices
de las ans o maciones en el o den con a io y bas a ´a con in e i cada una de las
ma ices ob enidas y mul iplica las pa a ob ene la unci´on que buscamos. A pa i
de es o ya end emos la ans o maci´on que nos pe mi i ´a calcula las coo denadas
en la o o inicial de un pun o en la imagen inal eco ada. Di idiendo el esul ado
de la ´ul ima i e aci´on en la cuad ´ıcula 8 ×8 del able o, ob end emos las esquinas
de cada una de las casillas (Figu a 2.7).
Una ez conocidas las coo denadas de las cua o esquinas de una casilla, enemos
que calcula el ec ´angulo po el que eco a emos. P ime o calculamos la al u a de
la imagen como la di e encia en e una esquina supe io y una in e io mul iplicado
po un ac o de 1,75. El hecho de oma una mayo al u a m´as hace que podamos
e mejo la pa e de a iba de las piezas, que al in y al cabo es la que mejo las
di e encia, sin llega a in oduci en el ec ´angulo m´as que la base de la posible pieza
de la casilla supe io (Figu as 2.8b y2.8a). As´ı, ampliamos el conocimien o de la
14
zona de la pieza que mejo las di e encia e in oducimos el meno uido posible.
En caso de sali nos de la imagen po a iba, ajus amos la al u a al m´aximo. Como
es amos asumiendo que las o os se oman desde un la e al del able o y no desde
una esquina, podemos oma la base del ec ´angulo como el ancho de las dos esquinas
in e io es (Figu a 2.8).
Como se puede obse a en la Figu a 2.8c, hay que ajus a el ac o po el que
mul iplicamos la al u a eniendo en cuen a ambi´en que los peones son m´as bajos y
se pod ´ıan solapa los unos con los o os. O a opci´on se ´ıa ajus a la al u a seg´un
es emos en la pa e in e io o supe io de la imagen (Figu as 2.8d y2.8c). A´un as´ı,
con la su icien e a iedad de casos en el da ase , nues a ed neu onal con olucional
que e emos en la secci´on 3.3 debe ´ıa se capaz de ap ende en qu´e zona de la imagen
ija se pa a di e encia las piezas m´as al as de las m´as bajas.
Veamos una posible gene alizaci´on de es e m´e odo en caso de que e ambi´en
admi i o os hechas desde las esquinas (en las que el able o se e ´ıa como un
ombo). Pod ´ıamos oma una combinaci´on lineal de las al u as de las esquinas de
cada casilla de o ma que se man u iese lo comen ado en el p´a a o an e io cuando
el bo de in e io de la imagen uese pa alelo al bo de in e io del able o. Una opci´on
sencilla que cumpli ´ıa es o es oma la media de las al u as de las esquinas in e io es
pa a si ua la base del ec ´angulo y ajus a el ac o po el que mul iplicamos la
al u a en unci´on de la di e encia en e el ancho y el al o de la casilla.
Nues a idea inicial e a ob ene una g an can idad de o os omadas a pa idas
eales en un club de ajed ez, pe o desg aciadamen e po las ci cuns ancias ac uales
no hemos podido cons ui un da ase de piezas ob enidas de es a o ma. Po lo
an o, como e emos en la secci´on 3.2, nos queda emos con la p ime a ap oximaci´on
que hemos is o al inicio de es a secci´on pa a eco a las casillas, ya que es la o ma
con la que se han ob enido los da ase que hemos podido u iliza . Plan eamos en el
cap´ı ulo 6, como abajo u u o, segui es e es udio pa a inco po a el m´e odo que
hemos p opues o.
15
(a) Dama neg a. (b) Rey blanco.
(c) Pe´on neg o. (d) To e blanca.
Figu a 2.8: Reco e de las casillas median e la p ime a ap oximaci´on ( e de) y con
el nue o m´e odo (ama illo). En las dos p ime as igu as, las m´as al as, emos como
con el ec ´angulo ama illo se llega a pode di e encia la pa e supe io de las piezas.
En las dos igu as in e io es, las piezas m´as bajas, emos la di e encia que puede
habe en e que es ´en si uadas en la pa e in e io o supe io del able o.
16
Cap´ı ulo 3
Clasi icaci´on de las piezas
Una ez de ec ada la posici´on del able o en la imagen o iginal, el siguien e paso
es clasi ica cada una de sus casillas. Cada casilla puede es a ac´ıa o puede es a
ocupada po una pieza de uno de los jugado es, po lo que end emos que decidi a
cu´al de las 13 clases an e io es co esponde cada una de las 64 casillas del able o.
Ac ualmen e, la mane a m´as u ilizada y los mejo es algo i mos pa a ealiza
la clasi icaci´on de una imagen en una se ie de ca ego ´ıas son median e el uso de
edes neu onales con olucionales [RW17]. Adem´as, es as edes se pueden acele a
eno memen e como e emos en el cap´ı ulo 4.
3.1. No aci´on FEN
El esul ado inal de la clasi icaci´on se ´a una cadena de ca ac e es que codi ica ´a
las posiciones de las piezas en el able o median e la no aci´on de Fo sy h-Edwa ds
(FEN) [Edw94]. Como solo end emos una ins an ´anea de la pa ida, ´unicamen e
pod emos sabe la posici´on de las piezas, no el jugado al que le oca mo e o si hay
posibilidad de en oque po ejemplo ( ac o es que s´ı que se ienen en cuen a en la
no aci´on FEN comple a). As´ı, la cadena se ´a una se ie de ocho bloques de ca ac e es
al anum´e icos ep esen ando cada ila del able o sepa adas po el ca ´ac e /.
Las ilas se esc iben de izquie da a de echa y de a iba a abajo desde la pe spec-
i a de las blancas. Los ca ac e es se co esponden con las iniciales de los nomb es
de las piezas en ingl´es (a excepci´on del caballo, que se ep esen a con una n), en
may´usculas si la pieza es blanca y en min´usculas si es neg a. Las casillas en blanco se
ab e ian con un n´ume o del 1 al 8 indicando el n´ume o de casillas ac´ıas con iguas.
La posici´on inicial de una pa ida se co esponde po an o con la siguien e
cadena: nbqkbn /pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR. En la Figu a 3.1
podemos e un ejemplo de una posici´on m´as a anzada de la pa ida.
3.2. Da ase e ique ado de piezas
Ob ene un da ase e ique ado de im´agenes de able os o de piezas de ajed ez
no es a ea sencilla, ya que no exis e ninguno disponible de o ma p´ublica que sea
comple o o a iado [Din16] [CLW17]. Usualmen e, en es os casos, cada au o se
c ea su peque˜na mues a de piezas con las que pode pone a p ueba su idea. Sin
emba go, pa a en ena un modelo de deep lea ning son necesa ias una g an can idad
17
Sabiendo es o, podemos deduci en unci´on de la casilla inicial y la inal qu´e
piezas son compa ibles con el mo imien o ealizado. De es a mane a pod emos a ina
m´as la pieza que se encuen e en la casilla inal del mo imien o (Algo i mo 3.2).
En las p uebas y esul ados que mos amos en los cap´ı ulos 4y5deshabili amos
es e algo i mo, ya que equie e in o maci´on que no end emos al oma una ´unica
ins an ´anea de un able o. Es o se ´a ´u il y se pod ´a amplia como comen a emos en
el cap´ı ulo 6de ca a a digi aliza pa idas comple as.
Algo i mo 3.2: In e encia del ipo de pieza a pa i de su mo imien o.
En ada: Cadena FEN de la imagen an e io .
Vec o es de p obabilidades de la imagen ac ual.
Salida: Conjun o de piezas compa ibles con el mo imien o ealizado.
1casillas ←casillas cambiadas(FEN an e io , ec o es p obs);
2(casilla ini,casilla in,accion)←mo in e ido(FEN an e io , ec o es p obs,
3casillas);
4piezas posibles ←piezas compa ibles(casilla ini,casilla in,accion);
5de ol e piezas posibles
24

Cap´ı ulo 4
Acele aci´on
El paso inal y la pa e m´as impo an e de nues o abajo es la acele aci´on
de odo el amewo k que hemos cons uido. Desde la de ecci´on inicial del able o
has a la clasi icaci´on de las piezas pa a ob ene la digi alizaci´on comple a. Exis en
mul i ud de ´ecnicas pa a hace m´as e icien e la ejecuci´on de un p og ama, espec´ı ica-
men e pa a la ejecuci´on e icien e de edes neu onales p o undas [Sze+17] [Kim+19]
[MDB20]. En es e cap´ı ulo e emos las que hemos u ilizado noso os y c´omo las
hemos adap ado a es e caso conc e o.
4.1. Pla a o mas de in e encia
En base al uso inal de nues o p og ama, decidimos que lo m´as ap opiado se ´ıa
su ejecuci´on en local en un sis ema empo ado con ha dwa e espec´ı ico pa a la
acele aci´on. Exis en di e sos sis emas que cumplen es as ca ac e ´ıs icas y se adap an
al c´alculo de la in e encia de modelos de deep lea ning. T es de ellos se ´ıan el In el
Neu al Compu e S ick 2 [In ], los sis emas Co al de Google [Goo] o la amilia Je son
de N idia [N ia].
Los Neu al Compu e S ick 2 de In el pe mi en a˜nadi median e una conexi´on
USB una unidad de p ocesamien o de isi´on (Vision P ocessing Uni o VPU), es o
es, un acele ado ha dwa e de bajo consumo dedicado al c´alculo de algo i mos de
isi´on a i icial, como pueden se las edes neu onales con olucionales. Los sis emas
Co al de Google es ´an compues os o bien po una unidad USB o bien po una placa
dedicada, pe mi iendo dispone en ambos casos de una unidad de p ocesamien o
enso ial (Tenso P ocessing Uni o TPU) pa a la acele aci´on de edes neu onales. La
di e encia undamen al de una TPU con espec o a un GPU es el olumen de c´alculo
que pueden alcanza , es ando las TPU op imizadas pa a ama˜nos de ba ch m´as
g andes. Adem´as, es ´an pensadas ´ın eg amen e pa a el c´ompu o u ilizando p ecisi´on
educida, de o ma simila a los n´ucleos enso iales que p opo cionan las GPU de
N idia m´as ecien es.
En nues o caso amos a u iliza la N idia Je son Nano [N ib], el disposi i o m´as
peque˜no de la amilia Je son. Es ´a compues o po una placa dedicada con dos modos
de consumo, 5 o 10 W. Unos alo es muy educidos en compa aci´on con su po encia
de c´ompu o, ya que puede llega a los 472 GFLOPs en FP16. Sus especi icaciones
´ecnicas p incipales son las siguien es:
Una GPU con a qui ec u a NVIDIA Maxwell de 128 n´ucleos CUDA.
Una CPU ARM de cua o n´ucleos Co ex-A57 a 1,43 GHz.
25
4 GB de memo ia RAM LPDDR4 a 25,6 GB/s.
Conec i idad Gigabi E he ne y conexi´on HDMI y DisplayPo .
Es as ca ac e ´ıs icas nos o ecen, adem´as de una GPU dedicada de N idia con
el po encial de Tenso RT pa a la in e encia (como e emos en la secci´on 4.2), una
CPU capaz de ealiza el c´ompu o secuencial necesa io pa a de ec a los able os.
Del mismo modo, hemos op ado po usa es a pla a o ma ya que, al inclui una GPU,
pe mi e acele a ambi´en las ases de de ecci´on del able o. Es e ipo de a qui ec u a
se iene usando con ´exi o desde hace m´as de una d´ecada en las a eas elacionadas
con el p ocesamien o de im´agenes [Se +07] [Ten+08].
Es e sis ema o ma pa e de la amilia Teg a X1 “E is a”, con una disminuci´on de
la ecuencia de la CPU y disponiendo solamen e de la mi ad de n´ucleos CUDA que
los modelos u ilizados en la N idia Shield TV [N id] o la Nin endo Swi ch [Nin]. Es a
amilia ue la p ime a de N idia que se dise˜n´o pensando en disposi i os po ´a iles,
adem´as de se la p ime a a qui ec u a que incluy´o cie o sopo e pa a ope aciones
en pun o lo an e de 16 bi s. En algunas si uaciones, como en el caso de que se a e
de la misma ope aci´on, dos ope aciones en FP16 se pueden empaque a jun as a
ejecuci´on sob e un ´unico n´ucleo CUDA de 32 bi s (Figu a 4.1) [HS]. Es o ´ul imo lo
u iliza emos de ca a a la acele aci´on de la in e encia de nues as edes neu onales.
Figu a 4.1: Ejecuci´on sob e un n´ucleo CUDA de 32 bi s de dos ope aciones del
mismo ipo en FP16.
4.2. Op imizado es: ONNXRun ime y Tenso RT
Como hemos comen ado en la secci´on 3.3, an o la de inici´on de nues a ed
neu onal como su en enamien o los hemos ealizado u ilizando la lib e ´ıa Ke as so-
b e Tenso Flow. Ve emos aho a que la in e encia empleando es as lib e ´ıas se puede
acele a eno memen e sob e o as pla a o mas. En es a secci´on es udia emos las dos
que hemos u ilizado: el o ma o de ep esen aci´on de modelos ONNX (Open Neu-
al Ne wo k Exchange) [ONN] y su op imizado ONNXRun ime [Mic] y Tenso RT
[N ie], la lib e ´ıa de N idia pa a la op imizaci´on de la in e encia sob e sus a je as
g ´a icas (Figu a 4.2).
26
Figu a 4.2: Flujo de abajo pa a la acele aci´on de la in e encia.
ONNX es un o ma o lib e de ep esen aci´on de modelos de ap endizaje au-
om´a ico que de ine un conjun o de ope ado es y un o ma o de a chi o no malizado.
De es a o ma se ob iene una ep esen aci´on es ´anda que pe mi e la in e conexi´on
en e una g an a iedad de lib e ´ıas de IA, he amien as, mo o es de ejecuci´on y
compilado es. Posibili a el desa ollo de los modelos median e lib e ´ıas como Ke as,
Ca e, MATLAB, PyTo ch o Tenso Flow y su pos e io despliegue en en o nos de
ejecuci´on dise˜nados pa a acele a la in e encia sob e un ha dwa e espec´ı ico.
ONNXRun ime es un mo o de in e encia de al o endimien o que pe mi e op-
imiza la ejecuci´on de modelos de machine lea ning ap o echando de o ma m´as
e icien e las capacidades de cada ha dwa e. El modelo ONNX lo con ie e a una
ep esen aci´on in e na en memo ia p incipal y le aplica una se ie ans o maciones,
como po ejemplo la di isi´on del modelo en una se ie de pa es pa a que cada una se
ejecu e sob e un en o no de ejecuci´on o acele ado di e en e (CPU, nG aph, CUDA,
Tenso RT...).
ONNX ambi´en nos si e como ep esen aci´on in e media a pa i de Ke as pa a
u iliza op imizado es sob e ha dwa e m´as espec´ı icos, como puede se Tenso RT
pa a las a je as g ´a icas de N idia. U iliza Tenso RT de o ma di ec a en ez de
indi ec amen e a pa i de ONNXRun ime nos pe mi e aplica m´as y mejo es op imi-
zaciones adap adas espec´ı icamen e al ha dwa e inal. Es o se debe a que el paso del
modelo en o ma o ONNX a Tenso RT se ealiza sob e es e ha dwa e, disponiendo
de odos los pa ´ame os del sis ema de ini i o. Sin emba go, es as ans o maciones
se ´an a cos a de una disminuci´on muy le e en la p ecisi´on ob enida.
Las op imizaciones que ealiza Tenso RT de ca a a educi el iempo necesa io
pa a la in e encia son las siguien es:
Disminui el ama˜no en memo ia de los pesos pa a maximiza el ancho de
banda, a expensas de educi m´ınimamen e la p ecisi´on del modelo. De es a
27
o ma, se puede pasa de n´ume os en coma lo an e de 32 bi s a 16 bi s o
incluso a en e os de 8 bi s median e ans o maciones y ajus es adicionales.
Fusiona capas del modelo pa a op imiza el uso de la memo ia de la GPU y el
ancho de banda. Donde sea posible, ans o ma en un ´unico nodo una po ci´on
m´as compleja del modelo inicial.
Adap a los algo i mos y da os usados en la ejecuci´on de las capas del modelo
a la GPU obje i o.
Redis ibui los da os pa a minimiza la can idad de huecos en memo ia.
Pa aleliza la ejecuci´on de o ma que se u ilice de o ma e icien e oda la GPU.
4.3. De ecci´on del able o
Como ya hemos is o en el cap´ı ulo 2, la ase de de ecci´on del able o se compone
de dis in os m´odulos que se ejecu an de o ma i e a i a has a ob ene la posici´on
inal. Pa a en ende mejo el cos e compu acional de odo ese p oceso, analizamos
a ias ejecuciones del c´odigo con la he amien a de an´alisis de endimien o (p o ile )
que p opo ciona Py hon po de ec o.
Los p ime os pasos as decidi nos po basa la de ecci´on del able o en es e
m´e odo han sido:
Adap a el c´odigo a las e siones ac uales del lenguaje y de las lib e ´ıas u ili-
zadas, sob e odo el paso de Py hon 2 a Py hon 3, OpenCV 2 a 4 y Tenso Flow
1 a 2.
Re ac o iza el p oyec o pa a que enga mayo cla idad y pode inclui lo m´as
acilmen e en nues o amewo k.
Adecua odo el c´odigo a la gu´ıa de es ilo de Py hon PEP8 [RWC01].
Una ez ob enido un ma co uncional, pasamos a hace un p ime an´alisis del
endimien o del c´odigo u ilizando el p o ile de Py hon. Es a he amien a nos p o-
po ciona una se ie de es ad´ıs icas y nos desc ibe cu´an as eces y du an e cu´an o
iempo se ha ejecu ado cada unci´on del c´odigo. En pa icula , po cada unci´on nos
indica el n´ume o eces que se ha llamado y el iempo o al y po llamada que ha
a dado, dis inguiendo en e inclui o no el iempo que hayan empleado sus sub un-
ciones en ejecu a se. Es o nos pe mi i ´a dedica es ue zo a op imiza las zonas del
c´odigo que nos ayan a p opo ciona una mayo disminuci´on del iempo.
Las ejecuciones pa a analiza el endimien o de la de ecci´on de able o las ealiza-
mos sob e nues a pla a o ma inal, la N idia Je son Nano. Las im´agenes de p ueba
son el conjun o de 10 o os que u ilizan los au o es de [CLW17] pa a ob ene sus
28
esul ados. Es as son im´agenes de si uaciones muy a iadas, que con ienen o os ob-
je os que o man l´ıneas ec as adicionales adem´as del able o y que ienen somb as,
dis o siones y uido.
Los iempos mos ados aqu´ı son desde an es de lee las im´agenes de en ada
has a despu´es de esc ibi la imagen de ec ada de cada able o ( e Figu a 2.1). En
pa icula , es e no incluye la ob enci´on de las casillas indi iduales. Pa a un an´alisis
comple o de los iempos inales e el cap´ı ulo 5.
4.3.1. P ime an´alisis: Op imizaci´on median e ONNX
En la ejecuci´on del c´odigo en es a ase ob enemos que se a da una media de
16,01 segundos en p ocesa cada uno de los 10 able os de p ueba. Es e iempo lo
ob enemos u ilizando la lib e ´ıa imei y ejecu ando 5 eces el conjun o comple o de
able os. Los siguien es da os desg anados ienen dados po el p o ile , que conlle a
un lige o sob ecos e, po lo que los exp esamos como po cen ajes del iempo o al
pa a abs ae nos de es a di e encia.
Inicialmen e, el 38,1 % del iempo se emplea en la ase de iden i icaci´on de la
posici´on del able o (CPS) 2.1.3, el 37,4 % en la ase de b´usqueda de pun os de la
cuad ´ıcula (LAPS) 2.1.2 y el 18 % en la ase de de ecci´on de l´ıneas ec as (SLID)
2.1.1. De aqu´ı, obse amos que m´as de es cua as pa es del iempo de b´usqueda
de pun os de la cuad ´ıcula se emplea en la in e encia de la ed neu onal, desa ollada
po [CLW17], u ilizada pa a e mina de decidi los pun os que no il a el de ec o
geom´e ico ( ´ease el Algo i mo 2.3). Po lo an o, un buen pun o de pa ida pa a
op imiza el c´odigo se ´ıa acele a es a ed neu onal.
Pa a ello, p ime o ecupe amos del p oyec o o iginal la es uc u a del modelo
y los pesos en enados pa a de ec a los pun os que o man pa e de la cuad ´ıcula
del able o. Pos e io men e, ans o mamos el modelo a o ma o ONNX pa a pode
educi el iempo necesa io pa a su ejecuci´on median e ONNXRun ime, como hemos
is o en la secci´on 4.2. De es a mane a, haciendo unos cambios m´ınimos en el c´odigo,
pod emos ap o echa un modelo p e iamen e en enado op imiz´andolo de o ma casi
anspa en e.
T as op imiza es a pa e del p og ama, hacemos una nue a p ueba de endi-
mien o y comp obamos que aho a se a da una media de 10,33 segundos en p ocesa
cada uno de los 10 able os de p ueba. As´ı, cen ´andonos en mejo a las unciones
en las que se in ie e una mayo can idad de iempo, conseguimos un speedup de
1,55.
4.3.2. Segundo an´alisis: Reducci´on del sob ecos e de NumPy
Una ez op imizada la ejecuci´on de la ed neu onal en la ase LAPS as el p ime
an´alisis, ol emos a e alua el endimien o del c´odigo pa a e po d´onde podemos
segui mejo ando. En es e segundo an´alisis, ap oximadamen e el 41,4 % del iempo
29

se emplea en la iden i icaci´on de la posici´on del able o, el 28,6 % en la de ecci´on de
l´ıneas ec as y el 21,8 % en la b´usqueda de pun os de la cuad ´ıcula ( eco demos que
es o an es ocupaba el 37,4 % del iempo).
Llegado a es e pun o, nos so p ende que casi la e ce a pa e del iempo o al se
emplea en el c´alculo de un p oduc o ec o ial u ilizando la lib e ´ıa NumPy [Oli06].
Es a ope aci´on o ma pa e de una peque˜na unci´on u ilizada an o po la iden i i-
caci´on de la posici´on del able o como po la de ecci´on de l´ıneas ec as. El c´alculo
es simplemen e
k(y−x)×(x−z)k,
donde obse amos que x, y yzson ec o es de dos componen es. Sabiendo es o,
podemos ans o ma el mismo c´alculo a o a o ma equi alen e y mucho m´as sencilla
sin necesidad de hace llamadas a la lib e ´ıa NumPy. Las llamadas a lib e ´ıas, al
in oduci peque˜nos sob ecos es po su amplio espec o de posibles usos, acaban
siendo menos e icien es.
El c´alculo an e io puede simpli ica se como
|(y1−x1)(x2−z2)−(y2−x2)(x1−z1)|,
donde hemos deno ado x= (x1, x2), y = (y1, y2) y z= (z1, z2). Es a ope aci´on
puede hace se di ec amen e sin necesidad de u iliza lib e ´ıas ex e nas. Tambi´en
hemos e i ado el c´alculo de la no ma del ec o esul an e del p oduc o ec o ial
in oduciendo simplemen e un alo absolu o.
Hay que no a que es a ope aci´on acaba ealiz´andose m´as de 25000 eces po
able o de ec ado. Po lo an o, in en amos e si se puede educi su uso de alguna
mane a. Reo denando la o ma de calcula si una l´ınea es ´a ce ca del bo de de la
cuad ´ıcula ( ´ease el Algo i mo 2.4), e i amos llamadas a es a ope aci´on cuyos esul-
ados a eces no e an necesa ios. As´ı, conseguimos educi casi un 20 % el n´ume o
de in ocaciones a es a unci´on.
T as es os cambios hacemos una nue a p ueba de endimien o y comp obamos
que aho a se a da una media de 5,55 segundos en p ocesa cada uno de los 10
able os de p ueba, consiguiendo un speedup de 1,86 sob e la op imizaci´on an e io .
4.3.3. Te ce an´alisis: Reducci´on del sob ecos e de Ben ley-
O mann
Despu´es de obse a c´omo las llamadas a lib e ´ıas pueden supone un cos e
compu acional mayo de lo necesa io si no es ´an jus i icadas, ol emos a analiza el
c´odigo po si hubiese alguna o a si uaci´on simila . En el e ce an´alisis, ap oxima-
damen e el 40,2 % del iempo se emplea en la b´usqueda de pun os de la cuad ´ıcula,
el 32,3 % en la iden i icaci´on de la posici´on del able o y el 20,6 % en la de ecci´on de
l´ıneas ec as.
Aqu´ı, des aca el hecho de que una unci´on dedicada al c´alculo de las in e sec-
ciones de un conjun o de l´ıneas median e el algo i mo de Ben ley-O mann ocupa
30
casi el 39 % del iempo o al. Vimos al p incipio del Algo i mo 2.3 que es e m´e odo
de ba ido se emplea pa a ob ene odos los pun os candida os a o ma pa e de la
cuad ´ıcula del able o. Sin emba go, aqu´ı emos que adem´as de pa a ese caso, am-
bi´en se es ´a u ilizando pa a calcula la in e secci´on de cada pa de l´ıneas e icales
y ho izon ales candida as a se el ma co de la cuad ´ıcula 6 ×6 del able o ( un-
ci´on polysco e del Algo i mo 2.4). Es e segundo uso supone el 56,5 % del iempo
empleado en es e c´alculo.
El algo i mo de Ben ley-O mann pe mi e calcula las in e secciones de un con-
jun o de l´ıneas de o ma m´as e icien e, O((n+k) log n), que la i ial, O(n2), donde
nes el n´ume o de l´ıneas y kel n´ume o de in e secciones. Pa a consegui es o se
a˜nade un sob ecos e que no compensa pa a conjun os peque˜nos de l´ıneas, en nues-
o segundo caso son solo 4 l´ıneas.
Sol en amos es a si uaci´on calculando di ec amen e las 6 posibles in e secciones
de 2 l´ıneas de en e el conjun o de 4. Es o consis e b´asicamen e en el c´alculo de
de e minan es de o den 2 y ope aciones elemen ales, que en nues o caso, al se un
conjun o peque˜no, no supone ninguna ine iciencia p ´ac ica. De es a o ma educimos
el iempo en p ocesa cada uno de los 10 able os de p ueba a una media de 4,22
segundos po able o, consiguiendo un speedup de 1,32 sob e la op imizaci´on an e io .
4.4. Clasi icaci´on de las piezas
En las secciones 3.3 y3.4 hemos de allado el p oceso de clasi icaci´on de las piezas
del able o u ilizando una ed neu onal p o unda cons uida median e Ke as. Una
ez es ablecido el p oceso a a ´es del cual podemos comple a la digi alizaci´on del
able o, es amos en si uaci´on de escoge qu´e modelo u iliza emos pa a la in e encia
y c´omo acele a emos su ejecuci´on.
E ec ua emos las p uebas sob e 5 im´agenes con able os de ajed ez que con ienen
piezas de dis in o ipo al u ilizado en el conjun o de da os de en enamien o. De
es a o ma, pod emos comp oba lo obus o que es cada modelo an e cambios en
el ipo de las piezas. Cada able o iene en e 21 y 32 piezas en posiciones di e sas
ex a´ıdas de pa idas eales. A di e encia del esquema que mos amos inicialmen e
en las Figu as 1.1 y1.2, las o os pa a es as p uebas las hemos omado desde un
plano ceni al. Adap ´andonos as´ı a las si uaciones que hemos comen ado en la secci´on
2.2 al ob ene las casillas indi iduales del able o (Figu a 4.3). Como p opond emos
en el cap´ı ulo 6, en el caso de dispone de un da ase con el que eco a las casillas
u ilizando el m´e odo is o en el apa ado 2.2.1, s´ı que pasa ´ıamos a oma las o os
desde un la e al.
Los alo es pa a la p ecisi´on los oma emos como el po cen aje de casillas p edi-
chas co ec amen e po nues o p og ama. Es o no coincide exac amen e con lo que
se ´ıa el alo Top-1 del modelo, ya que adem´as enemos en cuen a el conocimien o
sob e el dominio que hemos de allado en la secci´on 3.4.
31
Figu a 4.3: Una de las im´agenes de p ueba pa a la clasi icaci´on de las piezas. Tomada
en el XXXVII To neo de Ajed ez Pueblo Nue o 60’+30”.
4.4.1. Elecci´on del modelo
Adelan ´abamos en la secci´on 3.3 los modelos que hemos escogido pa a la cla-
si icaci´on. Una ez en enados sob e el da ase de piezas de ajed ez, enemos que
hace una compa aci´on en e las p ecisiones ob enidas y el iempo necesa io pa a la
in e encia. Pa a ello, en una p ime a ap oximaci´on ejecu amos la in e encia sob e la
Je son Nano u ilizando los modelos ob enidos di ec amen e de Ke as y ob enemos
los esul ados de la Tabla 4.1.
Xcep ion DenseNe 201 NASNe Mobile MobileNe V2
Tes 1 95 % 18,73s 94 % 28,95s 94 % 11,81s 98 % 5,85s
Tes 2 94 % 18,73s 95 % 28,98s 92 % 12,01s 89 % 5,81s
Tes 3 95 % 18,73s 94 % 28,88s 91 % 11,73s 92 % 5,88s
Tes 4 91 % 18,72s 91 % 28,96s 91 % 11,68s 91 % 5,85s
Tes 5 97 % 18,72s 88 % 29,03s 98 % 11,89s 92 % 5,90s
Media 94 % 18,73s 92 % 28,96s 93 % 11,82s 92 % 5,86s
Tabla 4.1: P ecisi´on y iempo ob enido sob e la Je son Nano pa a cada uno de los
modelos iniciales ejecu ando la in e encia median e Ke as.
De es os p ime os esul ados podemos conclui que los cua o modelos son lo
su icien emen e complejos como pa a ap ende las ca ac e ´ıs icas que p opo ciona
la imagen de una casilla, ya que p opo cionan alo es simila es de p ecisi´on. De ellos,
el m´as ´apido es el que iene un meno n´ume o de pa ´ame os, es deci , MobileNe V2.
32
Compa ando, MobileNe V2 iene unos 3,6 millones de pa ´ame os en e a los 5,4
millones de NasNe Mobile, los 20,3 millones de DenseNe 201 o los 23 millones de
Xcep ion.
Viendo es os esul ados nos p egun amos si con modelos m´as sencillos, cuya
in e encia debe ´ıa se m´as ´apida, pod ´ıamos ob ene una p ecisi´on simila . As´ı,
decidimos en ena ambi´en una ed AlexNe y o a SqueezeNe - 1.1. Adem´as de
es as dos edes, la p opia MobileNe V2 con iene un pa ´ame o αque con ola el
ancho de la ed. Con α= 1, el n´ume o de il os en cada capa es el alo po de ec o
que p opo cionan los au o es del modelo. Con α > 1 se aumen a y con 0 < α < 1
se disminuye p opo cionalmen e el n´ume o de il os en cada capa. As´ı, incluimos
en las p uebas la p opia ed MobileNe V2 con α= 0,5 y α= 0,35, alo es pa a los
cuales Ke as p opo ciona pesos sob e ImageNe pa a inicializa el en enamien o.
MobileNe V2 MobileNe V2 AlexNe SqueezeNe - 1.1
α= 0,5α= 0,35
Tes 1 95 % 3,10s 89 % 3,02s 81 % −97 % 1,27s
Tes 2 91 % 3,17s 75 % 3,05s 61 % −86 % 1,28s
Tes 3 94 % 3,09s 83 % 3,02s 81 % −92 % 1,28s
Tes 4 88 % 3,08s 83 % 3,02s 75 % −84 % 1,29s
Tes 5 91 % 3,12s 89 % 3,04s 73 % −94 % 1,28s
Media 92 % 3,11s 84 % 3,03s 74 % −91 % 1,28s
Tabla 4.2: P ecisi´on y iempo ob enido sob e la Je son Nano pa a cada uno de los
modelos m´as sencillos ejecu ando la in e encia median e Ke as.
En la Tabla 4.2 podemos obse a los esul ados de es a segunda ba e ´ıa de p ue-
bas. Comp obamos que MobileNe V2 man iene la p ecisi´on con α= 0,5, educiendo
el iempo empleado en la in e encia a casi la mi ad que con α= 1. El o o modelo
que consigue una p ecisi´on supe ando el 90 % es SqueezeNe - 1.1, que adem´as es el
m´as ´apido de odos los candida os al ejecu a se di ec amen e median e Ke as sob e
la Je son Nano. La p ecisi´on de MobileNe V2 con α= 0,35 es no ablemen e in e io
a la a ian e con α= 0,5 sin consegui apenas mejo as en el iempo.
El modelo que peo es esul ados ob iene es AlexNe . En es e caso, al igual que con
SqueezeNe - 1.1, hemos ealizado la implemen aci´on a pa i de cada capa bas´ando-
nos en o os modelos que no es ´an incluidos o icialmen e en la lib e ´ıa de Ke as. Sin
emba go, al con a io que con el es o de modelos, no hay disponibles pesos sob e
ImageNe pa a la implemen aci´on que hemos ealizado de AlexNe . Es os han sido
los mejo es esul ados que hemos ob enido as a ios en enamien os. Es e hecho
ha podido se un ac o a la ho a de explica po qu´e la p ecisi´on es in e io al es o
cuando en eo ´ıa es e modelo se compo a como SqueezeNe - 1.1 sob e ImageNe .
Adem´as, ha sido demasiado pesado en memo ia pa a ejecu a se de es a mane a sob e
la Je son Nano (los esul ados de la Tabla 4.2 son los ob enidos en nues o PC, de
ah´ı que no incluyamos alo es pa a los iempos). Pod emos hace un mejo an´alisis
33
an o, educimos el n´ume o de modelos a conside a de 8 a 4 y, dependiendo de
nues as necesidades, pod ´ıamos op a po una de las siguien es edes: SqueezeNe -
1.1, MobileNe V2 (α= 0,5), NASNe Mobile o Xcep ion. N´o ese que la ejecuci´on
de NASNe Mobile es sob e ONNXRun ime.
Figu a 5.1: P ecisi´on ob enida po cada modelo en unci´on del iempo necesa io pa a
la in e encia de un able o sob e la Je son Nano median e Tenso RT en un ba ch
de 64 im´agenes, sal o NASNe Mobile, cuyo mejo iempo es sob e ONNXRun ime.
Omi imos AlexNe po ob ene una p ecisi´on mucho meno .
5.3. Digi alizaci´on o al
La comple a digi alizaci´on de un able o de ajed ez comp ende desde que el sis-
ema de ec a que hay una nue a imagen a p ocesa has a que e mina de p ocesa la
y p oduce una cadena en no aci´on FEN. En las secciones an e io es hemos es udia-
do en de alle los esul ados que hemos ob enido pa a la de ecci´on del able o en la
imagen inicial y la clasi icaci´on de las piezas una ez sepa adas las casillas indi i-
duales. Adem´as de es as dos acciones, que suponen la p ac ica o alidad del iempo
de ejecuci´on, exis en o as es ope aciones que hay que comple a pa a e mina
odo el p oceso.
En p ime luga , una ez de ec ado el able o de ajed ez debemos sepa a las
casillas indi iduales (secci´on 2.2). Es o supone unos 80 milisegundos sob e la Je son
Nano. Adem´as, despu´es de ob ene los ec o es de p obabilidades de la ed que es-
40

emos u ilizando, hay que in e i cu´al es la con igu aci´on de piezas (secci´on 3.4) y
inalmen e ans o ma es a in o maci´on a la no aci´on FEN (secci´on 3.1). La suma
del iempo necesa io pa a ejecu a es as dos ope aciones es in e io a los 10 milise-
gundos. Po an o, adicionalmen e a los iempos de los p ocesos que hemos es udiado
en p o undidad, debemos a˜nadi algo menos de 100 milisegundos pa a comple a la
digi alizaci´on.
Resumimos odos los iempos que hemos ob enido en la Tabla 5.4. Aqu´ı podemos
e de o ma m´as cla a que exis e una a iable impo an e a la ho a de desplega el
sis ema, qu´e ed u iliza pa a la clasi icaci´on de las piezas. Es o depende ´a del uso
inal del p og ama y, como e emos en el cap´ı ulo de conclusiones y abajo u u o,
de las necesidades y mejo as que se puedan implemen a .
Tes 1 Tes 2 Tes 3 Tes 4 Tes 5
De ecci´on able o 4,21s 3,30s 4,28s 3,69s 3,35s
Sepa a casillas
indi iduales 0,08s
Ob ene ec o es
de p obabilidades
SqueezeNe - 1.1 0,46s
MobileNe V2 (α= 0,5) 0,60s
NASNe Mobile 3,42s
Xcep ion 5,61s
In e i piezas +
No aci´on FEN 0,01s
To al
SqueezeNe - 1.1 4,76s 3,85s 4,83s 4,24s 3,90s
MobileNe V2 (α= 0,5) 4,90s 3,99s 4,97s 4,28s 4,04s
NASNe Mobile 7,72s 6,81s 7,79s 7,20s 6,86s
Xcep ion 9,91s 9,00s 9,98s 9,39s 9,05s
Tabla 5.4: Resumen de iempos o ales sob e la Je son Nano po able o de p ueba
pa a cada uno de los modelos que o man el en e de Pa e o.
Al es udia los iempos que emplea nues o p og ama en ejecu a cada una de
es as ases obse amos que, si op amos po las edes m´as peque˜nas pa a la clasi ica-
ci´on de las piezas, la inmensa mayo ´ıa del iempo anscu e en la ase de de ecci´on
del able o. En si uaciones en las que sepamos que el able o y la c´ama a an a es a
inm´o iles, podemos ap o echa pa a no ecalcula su posici´on cada ez. As´ı, simple-
men e enemos que man ene las coo denadas de las esquinas que hemos calculado
an e io men e, comp oba que el able o sigue en el mismo si io y pasa a sepa a
las casillas di ec amen e.
Siguiendo la idea in oducida en el apa ado 2.1.2, hemos implemen ado un al-
go i mo que nos pe mi e comp oba de una o ma ´apida si el able o sigue en la
misma posici´on. Pa a ello, u ilizamos el de ec o geom´e ico y la ed neu onal is os
al busca los pun os de la cuad ´ıcula. Si las 49 esquinas del cuad ado cen al 6 ×6
41
del able o siguen en su si io, pod emos a i ma que la in o maci´on que en´ıamos
sigue siendo co ec a. Al con a las esquinas que s´ı o man pa e de la cuad ´ıcula
end emos que oma un ma gen de ole ancia, ya que hay pun os que pueden es a
ocluidos po alguna pieza. De o ma expe imen al hemos comp obado que ace ando
20 de los 49 pun os que comp obamos es su icien e pa a a i ma que el able o sigue
en el mismo si io (Algo i mo 5.1).
Algo i mo 5.1: Comp obaci´on de la posici´on del able o.
En ada: Imagen que con iene un able o.
Esquinas candida as a segui o mando pa e del cuad ado
cen al 6 ×6 del able o.
Salida: Si el able o sigue en la misma posici´on.
1esquinas co ec as ←0;
2pa a cada pun o ∈esquinas hace
3ma iz ←p ep ocesa ( ecindad(imagen,pun o));
4es pun o cuad icula ←de ec o geome ico(ma iz);
5si es pun o cuad icula en onces
6esquinas co ec as ←esquinas co ec as + 1;
7en o o caso
8es pun o cuad icula ← ed neu onal(ma iz);
9si es pun o cuad icula en onces
10 esquinas co ec as ←esquinas co ec as + 1;
11 in
12 // Si no pe enece a la cuad ´ıcula, pasamos a la siguien e
13 in
14 in
15 de ol e esquinas co ec as ≥ ole ancia (= 20)
La ejecuci´on de es e algo i mo sob e la Je son Nano a da unos 150 milisegun-
dos po able o. Luego en caso de de ol e un esul ado posi i o conseguimos una
educci´on eno me en el iempo o al. En la Tabla 5.5 esumimos los iempos cuando
es a comp obaci´on de uel e cie o.
Como podemos obse a , es a p edicci´on educi ´ıa el iempo o al necesa io pa a
digi aliza nue as posiciones a menos de un segundo. Adem´as, con es e iempo se
pod ´ıa a˜nadi un mues eo pe i´odico de im´agenes pa a cap u a posibles jugadas
in e medias. Se pod ´ıan e i a de es a o ma los casos en los que haya, po ejemplo,
una mano apando pa e del able o.
Es e peque˜no sob ecos e que hab ´ıa que a˜nadi en caso de que la comp obaci´on
de uel a also se e al amen e compensado. En la Tabla 5.4 hemos is o que el a-
ble o que se de ec a m´as ´apido a da 3,30 segundos, luego con que la comp obaci´on
de ol ie a cie o en 1 de cada 14 ocasiones, se e ´ıan amo izadas es as llamadas.
42
Table o inm´o il
Comp obaci´on
able o 0,15s
Sepa a casillas
indi iduales 0,08s
Ob ene ec o es
de p obabilidades
SqueezeNe - 1.1 0,46s
MobileNe V2 (α= 0,5) 0,60s
NASNe Mobile 3,42s
Xcep ion 5,61s
In e i piezas +
No aci´on FEN 0,01s
To al
SqueezeNe - 1.1 0,70s
MobileNe V2 (α= 0,5) 0,84s
NASNe Mobile 3,66s
Xcep ion 5,85s
Tabla 5.5: Resumen de iempos o ales pa a cada uno de los modelos que o man
el en e de Pa e o sob e la Je son Nano cuando la comp obaci´on de la posici´on del
able o de uel e cie o.
43
Cap´ı ulo 6
Conclusiones y abajo u u o
La isi´on a i icial es un campo que es ´a omando una g an ele ancia en muchas
si uaciones. El acceso de la sociedad a disposi i os capaces de in e ac ua con el
mundo que les odea ha supues o la au oma izaci´on de a eas muy di e sas, bien
sea median e c´alculos en sis emas empo ados o u ilizando el pode de c´ompu o de
po en es se ido es alojados en la nube. En el ´ambi o del ajed ez, uno de los p ime os
juegos pa a los que se desa oll´o un algo i mo de in eligencia a i icial, ambi´en se
puede aplica es e campo a la au oma izaci´on de la digi alizaci´on de las pa idas. En
es e abajo hemos explo ado una de las opciones que mejo es esul ados p opo ciona
en la ac ualidad y hemos c eado un p og ama que es capaz de segui el i mo de una
pa ida de ajed ez sob e un sis ema empo ado.
Como hemos podido obse a en los esul ados inales (Tabla 5.4), el iempo
o al u ilizando an o SqueezeNe - 1.1 como MobileNe V2(α= 0,5) se man iene
po debajo de los 5 segundos pa a odos los able os de p ueba sob e la Je son
Nano. Es o es alcanzando una p ecisi´on de 91 y 92 % espec i amen e a la ho a
de clasi ica las piezas. M´as a´un, si el able o pe manece inm´o il, es os iempos se
educen has a los 0,70 y 0,84 segundos espec i amen e.
El iempo que nos ma camos como obje i o inicialmen e ue on 5 segundos po
jugada. Po lo an o, despu´es de pa i de un iempo o al que ondaba en e los
25 y 45 segundos po able o, du aci´on que no hac´ıa ac ible su uso p ´ac ico, he-
mos podido alcanza una me a que pe mi i ´ıa su despliegue en si uaciones eales.
Todo ello ealizando los c´alculos ´ın eg amen e en un sis ema empo ado sin nece-
sidad de conec i idad con ninguna ed. El c´odigo comple o del p og ama que he-
mos desa ollado se encuen a de o ma p´ublica en nues o eposi o io de Gi Hub:
h ps://gi hub.com/da idmallasen/Li eChess2FEN.
En enando las dis in as edes neu onales con olucionales pa a la clasi icaci´on de
las piezas nos hemos encon ado con una ba e a a la ho a de mejo a la p ecisi´on.
Los modelos m´as sencillos han sido capaces de ap ende p ´ac icamen e oda la in-
o maci´on disponible en el da ase que hemos podido ecopila , y el hecho de oma
modelos m´as complejos no ha p opo cionado casi bene icio (Tabla 4.1). Teniendo en
cuen a es o, conside amos que pa e de es e p oblema se soluciona ´ıa in oduciendo
m´as in o maci´on en el da ase , po ejemplo median e el nue o m´e odo de sepa aci´on
de casillas que hemos p opues o (apa ado 2.2.1). As´ı e i a ´ıamos los casos en los
que solo se e la base de la pieza, si uaci´on en la que ni siquie a un humano es capaz
de dis ingui la.
En el caso de que mejo ando el da ase se ob u ie an esul ados m´as p ecisos
con un modelo que equie a un mayo es ue zo de c´ompu o, la disponibilidad de
44
n´ucleos enso iales pa a el c´alculo de ope aciones en FP16 se ´ıa una mejo a c ´ı ica.
Una e oluci´on de la Je son Nano, que iene el mismo ac o de o ma, es la Je son
Xa ie NX [N ic]. Ac ualmen e, es e m´odulo onda los 400$, unas 4 eces m´as que
la Je son Nano, aunque p e isiblemen e con la ecien e salida de la a qui ec u a
Ampe e hab ´a una educci´on de p ecios o nue os modelos con p ecio in e io .
La Je son Xa ie NX iene una GPU con una a qui ec u a Vol a que apo a 384
n´ucleos CUDA, 48 n´ucleos enso iales y 2 n´ucleos NVDLA (NVidia Deep Lea ning
Accele a o ), en e a los 128 n´ucleos CUDA de la Je son Nano que hemos empleado
noso os. Adem´as, dispone de una CPU hexa-co e y 8 GB de RAM, an e los cua o
n´ucleos y 4 GB de nues a pla a o ma. Todo ello hace que sea capaz de alcanza 6
TFLOPS en FP16, unas 12 eces m´as de lo que disponemos ac ualmen e. Adem´as,
a di e encia de la Je son Nano, pe mi e la ejecuci´on de ope aciones en en e os de
8 bi s, a una az´on de 21 TOPS. Es o ´ul imo se pod ´ıa ap o echa ans o man-
do los modelos y calib ando los angos de los pesos median e las capacidades que
p opo ciona Tenso RT.
El hecho de dispone de m´as n´ucleos de CPU ha ´ıa ac ible la pa alelizaci´on de
algunas secciones del c´odigo de la de ecci´on del able o. Po ejemplo, se pod ´ıan
calcula pa alelamen e en di e en es p ocesos las dis in as m´asca as CLAHE en los
pasos has a la ob enci´on de los segmen os, como hemos is o en el Algo i mo 2.2.
Es o ha supues o una mejo a de un 10 % en el iempo o al sob e una CPU In el Co e
i7-4770K con 4 n´ucleos con hype h eading, u ilizando la clase P ocessPoolExecu o
de Py hon. Sin emba go, al hace la p ueba sob e la Je son Nano los iempos se han
man enido cons an es.
En el apa ado 3.4.1 hemos in oducido un algo i mo que pe mi e in e i las
piezas que se mue en en un able o a pa i de dos im´agenes consecu i as. En el caso
de conoce con ce eza la con igu aci´on inicial de las piezas, po ejemplo digi alizando
una pa ida desde el comienzo, pod emos conoce de o ma p ecisa el n´ume o y ipo
de piezas que hay en cada momen o sob e el able o. Es a in o maci´on se pod ´ıa
inclui en el Algo i mo 3.1 pa a a ina m´as la unci´on alcanzado max.
En ocasiones, sob e odo en pa idas in an iles, alguno de los jugado es ealiza un
mo imien o ilegal. Teniendo la ce eza del ipo de pieza que ealiza el mo imien o,
po ejemplo po im´agenes de las acciones an e io es, se pod ´ıa ad e i de es as
si uaciones. Es o se i ´ıa an o como in o maci´on adicional pa a el usua io, como
pa a co egi malas p edicciones que pod ´ıan da se a a´ız de es as jugadas il´ıci as.
Adem´as, en odos los casos en los que sabemos que una pieza ha pe maneci-
do quie a, podemos u iliza los ec o es de p obabilidades que hemos ob enido en
im´agenes an e io es pa a aumen a nues o conocimien o. Po ejemplo, pod ´ıamos
oma la media de es as p obabilidades en las o os en las que no se ha mo ido. De
es a mane a mejo a ´ıamos la in e encia en si uaciones en las que an es hab´ıa una
pieza ocluyendo pa e de la casilla que es amos conside ando.
45

Cap´ı ulo 7
In oduc ion (English)
The ecogni ion o chess pieces and chessboa ds is a compu e ision p oblem
ha has no ye been sol ed e icien ly. Howe e , i s solu ion is c ucial o many
expe ienced playe s who wan o compe e agains chess engines and specialized p o-
g ams, bu who also p e e o make decisions using a physical chessboa d. I is also
impo an o chess ou namen o ganize s who wan o b oadcas he games online
o o ama eu playe s who wan o sha e hei games wi h iends. These digi izing
asks a e usually pe o med by humans o wi h he help o specialized chessboa ds
and pieces.
In o de o digi ize a game au oma ically, i is necessa y o be able o ecogni-
ze bo h he chessboa d and a e wa ds he layou o he pieces. In li e games, in
addi ion o p ecision, i is c i ical o minimize he ime equi ed o pe o m such
ecogni ion, since he mo es can happen e y quickly. This is he case o he game
modes known as “Bli z” and “Bulle ”, in which each playe has be ween 1 and 5
minu es o play he en i e game. This is also ue in classic games when he e is
li le ime le .
7.1. Rela ed wo k
Specialized boa ds ha physically de ec he pieces a e a ha dwa e solu ion o
au oma ic chess digi iza ion. Recen examples cu en ly used in majo ou namen s
can be ound in [Squ] o [DGTa]. Howe e , hese boa ds a e expensi e and di icul
o deploy in many a eas. As an example, a se o DGT chessboa d and pieces (b and
used in o icial ou namen s) cos s be ween e500 and e1000 [DGTb].
O he al e na i es a e hose p o ided by obo s ha mo e he pieces on a boa d,
such as [Ma +11] o mo e ecen ly [CW19]. These obo s a e based on posi ioning a
zeni h came a o e he boa d and de ec ing he di e en ials be ween one mo emen
and he nex . A d awback o his is ha i is necessa y o s a om a known ini ial
layou . A boa d wi h a gene ic layou could no be digi ized his way. In addi ion,
e o s should be aken in o accoun , because hey could add up in each new play.
The solu ions o e ed by compu e ision a e an al e na i e o conside , since
hey p o ide cheape and inc easingly accu a e sys ems, as well as being a majo
echnological challenge. Fo compa ison, he pla o m we will be using o in e ence,
an N idia Je son Nano, cos s a ound e110 [N ib] and does no jus s ick o one
unc ion, i could be eused o ano he ask.
These compu e ision p ocedu es a e based on combining and adap ing ans-
46
o ma ions and de ec o s al eady known and used in o he ields, such as he Ha is
co ne de ec o and he Hough ans o m [EA10]. Many o he me hods o en assu-
me big simpli ica ions, such as de e mining he exac posi ion o he came a, using
boa ds speci ically designed wi h ma ke s o aid in co ne de ec ion, o di ec ly h-
ough use in e ac ion [Din16]. Howe e , some gene ic solu ions ha o e come hese
es ic ions al eady exis .
Fo example, he e a e me hods ha allow us o classi y occu ences o a ious
objec s in a bi a y places using con olu ional neu al ne wo ks (CNNs) [Gao+17],
bu hey do no ha e he p ecision equi ed o ob ain hei exac posi ion. The
au ho s o [Ben+16] desc ibe a me hod o objec de ec ion ha also uses CNNs
ained h ough weak supe ision. Tha is, i is enough o ha e labeled images o
he objec s in o de o ain he ne wo k, wi hou he need o also p o ide he exac
posi ion o he objec in each aining image. The p oblem wi h his app oach is
ha i akes many i e a ions o p ecisely loca e an objec , which does no make i
e y p ac ical in si ua ions ha equi e eal- ime esponses.
The au ho s o [CLW17] p opose a me hod o chessboa d de ec ion ha is obus
agains ligh condi ions and he angle om which he images a e aken. In addi ion,
i wo ks wi h mos s yles o boa ds and i o e comes many o he weaknesses ha
we ha e been discussing. I is an i e a i e p ocess in which he posi ion o he
boa d is e ined in se e al phases. The au ho s ge 99,5 % accu acy in de ec ing he
in e sec ions o he cen e boa d g id and ind he ull posi ion o he chessboa d
accu a ely 95 % o he ime.
Rega ding piece classi ica ion once he boa d has been loca ed, in [Din16] a
me hod is p oposed ha uses a suppo ec o machine (SVM). This is ained
on he ea u es ex ac ed by SIFT [Low04], hus achie ing 85 % accu acy when
classi ying he pieces. In [CLW17] au ho s claim o achie e 95 % accu acy classi ying
chess pieces using a con olu ional neu al ne wo k (CNN), which hey enhance by
clus e ing simila pieces, aking in o accoun hei heigh and a ea, and using a
game engine o ob ain he p obabili y o pa icula layou s. The code o hese
enhancemen s has no been eleased, so we we e unable o analyze his pa icula
app oach.
7.2. Objec i es and wo k plan
The p ocessing o each ame is s ill oo slow in o de o hos li e b oadcas s.
The e o e, accele a ing his compu a ion is a e y impo an challenge. Ou inal
objec i e is o build a unc ional amewo k ha is capable o execu ing he en i-
e p ocess o digi izing a chess game pho o in eal- ime, making all he necessa y
calcula ions on specialized ha dwa e.
To accomplish his, we ha e made a se ies o changes o a me hod al eady im-
plemen ed ha de ec s he chessboa d. We ha e e ac o ed he code and modi ied
some modules o include new possibili ies (see o example sec ion 2.2.1 o boa d
47
posi ion checking in sec ion 5.3). In addi ion, we ha e op imized he code based on
pe o mance analysis ools and we ha e accele a ed i s execu ion on ou ha dwa e
(sec ion 4.3). To comple e he amewo k, we ha e buil a con olu ional neu al ne -
wo k o classi y he ob ained pieces and we ha e d as ically educed he necessa y
in e ence ime in he inal sys em (sec ion 4.4).
We ha e ca ied his ou ha ing in mind i s use in ama eu games o in ou na-
men s, aking he pho os om he side o he boa d each ime a playe p esses he
clock (Figu e 1.1). Howe e , some imes playe s o ge o p ess he clock. In hese
cases, pe iodic sampling based on he p ocessing speed o an image would be neces-
sa y o y o cap u e all he mo es. We show a schema ic o he came a posi ion in
Figu e 1.2.
48
Cap´ı ulo 8
Conclusions and u u e wo k
Compu e ision is a ield ha is acqui ing g ea ele ance in many si ua ions.
Uni e sal access o de ices capable o in e ac ing wi h he wo ld a ound hem has
mean he au oma ion o e y di e se asks, ei he h ough embedded sys ems o
using he compu ing powe o se e s hos ed in he cloud. In chess, one o he i s
games o which an a i icial in elligence algo i hm was de eloped, compu e ision
can also be applied o au oma e he digi iza ion o games. In his wo k we ha e
explo ed one o he op ions ha cu en ly p o ide he bes esul s and we ha e
c ea ed a p og am ha can keep up wi h a chess game on an embedded sys em.
As we ha e seen in he inal esul s (Table 5.4), he o al ime using bo h
SqueezeNe - 1.1 and MobileNe V2(α= 0.5) emains below 5 seconds o all es
boa ds on he Je son Nano. Achie ing an accu acy o 91 and 92 % espec i ely
when classi ying he chess pieces. Fu he mo e, i he boa d emains s a ic, hese
imes a e educed o 0.70 and 0.84 seconds espec i ely.
Ini ially, he ime we se as ou goal was 5 seconds pe boa d. The e o e, s a ing
om a o al ime be ween 25 and 45 seconds, a cos ha did no make i s p ac ical
use easible, we ha e been able o each a a ge ha would allow i s deploymen in
p ac ical scena ios. Mo eo e , he calcula ions a e pe o med en i ely on an embed-
ded sys em wi hou he need o connec i i y o any ne wo k. The comple e sou ce
code o he amewo k ha we ha e de eloped is publicly a ailable in ou Gi Hub
eposi o y: h ps://gi hub.com/da idmallasen/Li eChess2FEN.
Whils aining he di e en con olu ional neu al ne wo ks, we ha e ound a
ba ie when i comes o imp o ing p ecision o piece classi ica ion. The simples
models ha e been able o lea n p ac ically all he in o ma ion a ailable in he da ase
ha we ha e been able o collec , and aining mo e complex models has p o ided
almos no bene i (Table 4.1). Wi h his in mind, we belie e ha pa o his p oblem
would be sol ed by in oducing mo e in o ma ion in o he da ase , o example by
means o he new me hod o squa e sepa a ion ha we ha e p oposed (sec ion
2.2.1). This way we would a oid he cases in which only he base o he piece is
seen, a si ua ion in which no e en a human is able o dis inguish i .
I mo e accu a e esul s we e ob ained by imp o ing he da ase wi h a model
ha equi es a g ea e compu a ional e o , he a ailabili y o enso co es o cal-
cula ing ope a ions in FP16 would be a c i ical imp o emen . An e olu ion o he
Je son Nano, which has he same o m ac o , is he Je son Xa ie NX [N ic]. Cu-
en ly, his module cos s a ound $400, abou 4 imes mo e han he Je son Nano,
al hough wi h he ecen elease o he Ampe e a chi ec u e, a educ ion in p ices
o new models o a lowe p ice a e expec ed.
49