domingo, marzo 31

Inteligencia Artificial en el Go: límite 4 piedras

El Go es un juego de estrategia milenario con unas reglas sencillas pero una estrategia muy compleja. Es particularmente popular en Asia (su origen es chino) donde cuenta con millones de jugadores amateurs y miles de profesionales que compiten en torneos patrocinados por grandes empresas.



Una de las particularidades del juego es que tiene un árbol de probabilidades enorme, superior al ajedrez. Eso hace que no haya programas informáticos capaces de jugar a un alto nivel.
Una empresa taiwanesa llegó a ofrecer en los años 90 una gran recompensa económica a la persona capaz de desarrollar un programa que venciera a un jugador de Go profesional.

En los últimos años el desarrollo de la inteligencia artificial ha avanzado bastante. Para la programación del Go se emplean algoritmos como el de Montecarlo, el de Bouzy 5/21 o el algoritmo de Benson. El tema es profundo y complejo. Si quieres más información puedes empezar buscando aquí.

Límite: 4 piedras

Según informa la página Go Game Guru, recientemente se ha podido ver un gran avance en la programación del juego de Go. En un intervalo de un año, dos programas informáticos han logrado vencer a dos jugadores profesionales con 4 piedras de handicap. Esto quiere decir que el jugador profesional, empezó con 4 movimientos de desventaja sobre el tablero. Parece una gran desventaja pero sólo un jugador realmente fuerte podría ganar a uno de esos profesionales con 4 piedras de handicap.

Zen vs. Takemiya Masaki

Zen y el japonés Takemiya Masaki. Takemiya, de 62 años, es un famoso jugador profesional de Go famoso por su estilo llamado "cósmico" y por sus aperturas muy personales.

Takemiya Masaki (9 dan pro)
El 17 de marzo de 2012 se enfrentaron el programa
Zen es un software programado por un japonés llamado Yoji Ojima que ha ganado diversos premios y olimpiadas de computadoras. En el año 2012 fue el software ganador del UEC Computer Go.

En la primera partida, se le dieron 5 piedras de handicap a Zen, que venció por 11 puntos (un diferencia algo ajustada). Se jugó una segunda partida con 4 piedras de handicap y para sorpresa de todos, Zen volvió a ganar esta vez por 20 puntos. El comportamiento de Zen fue muy avanzado, sentenciando especialmente bien su posición durante el transcurso de la partida, ya que aceptaba algunas pérdidas locales a cambio de otras ventajas, que quizás muchos humanos no harían.



Aquí está la segunda partida entre Zen y Takemiya:

(;GM[1]FF[4]CA[UTF-8]AP[CGoban:3]ST[2] RU[Japanese]SZ[19]HA[4]KM[0.00]TM[1800]OT[1x60 byo-yomi] PW[Takemiya Masaki]PB[Zen]WR[9p]BR[5d]DT[2012-03-17]EV[6th E&C Symposium]RO[Game 2]PC[Japan]WT[Human]BT[Computer]SO[http://gogameguru.com/]AB[dd][pd][dp][pp]RE[B+20.00]PL[W]MULTIGOGM[1] ;W[cn]WL[1800] ;B[fp]BL[1778] ;W[ch]WL[1789] ;B[pj]BL[1755] ;W[fc]WL[1778] ;B[fd]BL[1737] ;W[gd]WL[1772] ;B[fe]BL[1720] ;W[eb]WL[1756] ;B[he]BL[1700] ;W[ge]WL[1743] ;B[gf]BL[1682] ;W[hd]WL[1729] ;B[fg]BL[1663] ;W[ef]WL[1717] ;B[ff]BL[1645] ;W[id]WL[1708] ;B[di]BL[1627] ;W[cj]WL[1697] ;B[ci]BL[1610] ;W[bi]WL[1690] ;B[bh]BL[1591] ;W[bg]WL[1682] ;B[bj]BL[1574] ;W[ah]WL[1678] ;B[ck]BL[1556] ;W[eh]WL[1642] ;B[dh]BL[1538] ;W[eg]WL[1601] ;B[dg]BL[1520] ;W[df]WL[1594] ;B[gi]BL[1503] ;W[fi]WL[1568] ;B[gj]BL[1483] ;W[gh]WL[1531] ;B[fh]BL[1465] ;W[ei]WL[1525] ;B[dj]BL[1447] ;W[ek]WL[1489] ;B[dm]BL[1427] ;W[hh]WL[1477] ;B[cf]BL[1408] ;W[ce]WL[1448] ;B[cg]BL[1390] ;W[de]WL[1441] ;B[ii]BL[1373] ;W[ih]WL[1431] ;B[ji]BL[1352] ;W[jh]WL[1414] ;B[kh]BL[1334] ;W[kg]WL[1399] ;B[lg]BL[1317] ;W[hi]WL[1372] ;B[hj]BL[1299] ;W[ki]WL[1352] ;B[lh]BL[1281] ;W[ij]WL[1347] ;B[jj]BL[1264] ;W[ik]WL[1342] ;B[fl]BL[1247] ;W[kk]WL[1249] ;B[kj]BL[1230] ;W[lj]WL[1245] ;B[li]BL[1212] ;W[jk]WL[1237] ;B[ki]BL[1195] ;W[jf]WL[1233] ;B[hl]BL[1177] ;W[jm]WL[1205] ;B[mj]BL[1158] ;W[lk]WL[1175] ;B[jo]BL[1140] ;W[lo]WL[1163] ;B[kn]BL[1122] ;W[mk]WL[1124] ;B[nj]BL[1104] ;W[ln]WL[1117] ;B[kq]BL[1084] ;W[lq]WL[1107] ;B[lr]BL[1066] ;W[mq]WL[1099] ;B[nl]BL[1048] ;W[nn]WL[1059] ;B[on]BL[1025] ;W[oo]WL[1049] ;B[pn]BL[1002] ;W[kp]WL[1020] ;B[bf]BL[984] ;W[jp]WL[975] ;B[cd]BL[966] ;W[ed]WL[803] ;B[be]BL[949] ;W[ee]WL[739] ;B[qq]BL[932] ;W[qf]WL[711] ;B[qe]BL[913] ;W[pf]WL[703] ;B[oe]BL[895] ;W[qh]WL[490] ;B[qi]BL[877] ;W[pe]WL[467] ;B[qd]BL[860] ;W[od]WL[462] ;B[oc]BL[842] ;W[nd]WL[456] ;B[nc]BL[825] ;W[ne]WL[434] ;B[of]BL[808] ;W[ri]WL[358] ;B[ph]BL[790] ;W[pg]WL[348] ;B[rh]BL[773] ;W[nf]WL[260] ;B[rf]BL[755] ;W[og]WL[251] ;B[qg]BL[738] ;W[cq]WL[225] ;B[cp]BL[720] ;W[bp]WL[220] ;B[bo]BL[703] ;W[bq]WL[210] ;B[co]BL[686] ;W[er]WL[205] ;B[kf]BL[665] ;W[ld]WL[180] ;B[jg]BL[648] ;W[if]WL[170] ;B[lb]BL[629] ;W[nh]WL[161] ;B[ni]BL[609] ;W[fk]WL[140] ;B[ho]BL[589] ;W[gq]WL[126] ;B[gl]BL[568] ;W[gp]WL[29] ;B[go]BL[551] ;W[fq]WL[24] ;B[dq]BL[532] ;W[dr]WL[18] ;B[ml]BL[513] ;W[nk]WL[28]OW[1] ;B[ok]BL[495] ;W[ll]WL[28]OW[1] ;B[ig]BL[475] ;W[hg]WL[28]OW[1] ;B[kg]BL[457] ;W[ie]WL[28]OW[1] ;B[le]BL[437] ;W[kd]WL[28]OW[1] ;B[mc]BL[418] ;W[md]WL[28]OW[1] ;B[or]BL[398] ;W[nr]WL[28]OW[1] ;B[dc]BL[379] ;W[cb]WL[28]OW[1] ;B[ec]BL[357] ;W[db]WL[28]OW[1] ;B[bc]BL[340] ;W[el]WL[28]OW[1] ;B[em]BL[322] ;W[om]WL[28]OW[1] ;B[ol]BL[301] ;W[pm]WL[28]OW[1] ;B[qn]BL[283] ;W[nm]WL[28]OW[1] ;B[np]BL[266] ;W[no]WL[28]OW[1] ;B[nq]BL[248] ;W[mr]WL[28]OW[1] ;B[ql]BL[230] ;W[kb]WL[28]OW[1] ;B[ka]BL[209] ;W[ja]WL[28]OW[1] ;B[la]BL[189] ;W[jb]WL[28]OW[1] ;B[ip]BL[171] ;W[iq]WL[28]OW[1] ;B[ns]BL[153] ;W[ms]WL[28]OW[1] ;B[mp]BL[134] ;W[lp]WL[28]OW[1] ;B[dl]BL[112] ;W[hf]WL[28]OW[1] ;B[jn]BL[94] ;W[km]WL[28]OW[1] ;B[ej]BL[77] ;W[fj]WL[28]OW[1] ;B[mm]BL[57] ;W[lm]WL[28]OW[1] ;B[gk]BL[37] ;W[gg]WL[28]OW[1] ;B[os]BL[20] ;W[ep]WL[28]OW[1] ;B[fo]BL[0] ;W[eo]WL[28]OW[1] ;B[bn]BL[28]OB[1] ;W[eq]WL[28]OW[1] ;B[qm]BL[28]OB[1] ;W[dn]WL[28]OW[1] ;B[cm]BL[28]OB[1] ;W[hp]WL[28]OW[1] ;B[en]BL[28]OB[1] ;W[lc]WL[28]OW[1] ;B[mb]BL[28]OB[1] ;W[im]WL[28]OW[1] ;B[hm]BL[28]OB[1] ;W[do]WL[28]OW[1] ;B[ao]BL[28]OB[1] ;W[bb]WL[28]OW[1] ;B[ab]BL[28]OB[1] ;W[oh]WL[28]OW[1] ;B[oi]BL[28]OB[1] ;W[in]WL[28]OW[1] ;B[io]BL[28]OB[1] ;W[hn]WL[28]OW[1] ;B[gn]BL[28]OB[1] ;W[ke]WL[28]OW[1] ;B[mg]BL[28]OB[1] ;W[pl]WL[28]OW[1] ;B[pk]BL[28]OB[1] ;W[op]WL[28]OW[1] ;B[oq]BL[28]OB[1] ;W[po]WL[28]OW[1] ;B[qo]BL[28]OB[1] ;W[bm]WL[28]OW[1] ;B[bl]BL[28]OB[1] ;W[am]WL[28]OW[1] ;B[al]BL[28]OB[1] ;W[ap]WL[28]OW[1] ;B[an]BL[28]OB[1] ;W[cc]WL[28]OW[1] ;B[bd]BL[28]OB[1] ;W[il]WL[28]OW[1] ;B[dk]BL[28]OB[1] ;W[ba]WL[28]OW[1] ;B[mn]BL[28]OB[1] ;W[mo]WL[28]OW[1] ;B[pb]BL[28]OB[1] ;W[mf]WL[28]OW[1] ;B[lf]BL[28]OB[1] ;W[ng]WL[28]OW[1] ;B[mh]BL[28]OB[1] ;W[me]WL[28]OW[1] ;B[mi]BL[28]OB[1] ;W[hk]WL[28]OW[1] ;B[fm]BL[28]OB[1] ;W[aa]WL[28]OW[1] ;B[ac]BL[28]OB[1] ;W[ko]WL[28]OW[1]C[http://gogameguru.com/]) ://gogameguru.com/])

Crazy Stone vs. Ishida Yoshio

El 20 de marzo de 2013, justo un año después, se enfrentan el programa Crazy Stone y el japonés Ishida Yoshio. Ishida, paradojicamente apodado "La computadora" gracias a su habilidad para contar, es un pro de 64 años que consiguió ser profesional con tan sólo 15 años. Fue especialmente fuerte en la década de los 70 cuando consiguió ganar de manera consecutiva 5 títulos Honinbo.

El programa Crazy Stone, recién proclamado campeón en la 6ª Computer Go UEC Cup, está programado por Rèmi Coulom, un profesor universitario especializado en inteligencia artificial aplicada a juegos.

Rèmi Coulom (izq.) coloca las piedras según su programa Crazy Go ante Ishida  Yoshio (der.)

Ishida se maravilló ante la tranquilidad y flexibilidad de movimientos de Crazy Go. Al final de la partida, el programa hizo varios movimientos "por seguridad" sabiendo que iba ganando y que le restaron puntos. Al final la computadora ganó por 2,5 puntos.

La partida entre Crazy Go e Ishida Yoshio:

(;GM[1]FF[4]SZ[19]AP[SmartGo:2.8.3.0]CA[UTF-8] GN[Crazy-Stone-vs-Ishida-Yoshio-20130320] PW[Ishida Yoshi]WR[9d] PB[Crazy Stone] EV[6th Computer Go UEC Cup]RO[Denseisen] DT[2013-03-20] PC[University of Electro-Communications, Tokyo] HA[4] KM[0.5] RE[B+2.5] RU[Japanese]BT[64 cores] TM[1800.0]OT[30s] SO[http://gogameguru.com/] AB[dp][pd][dd][pp] PL[W];W[cn];B[fq];W[ci];B[cg];W[bp];B[jd];W[qf];B[nd];W[pj];B[qn];W[hq];B[cq] ;W[bq];B[dn];W[dm];B[en];W[cm];B[jq];W[ho];B[hr];W[dc];B[ec];W[eb];B[ed] ;W[db];B[fb];W[cd];B[ce];W[bd];B[di];W[cj];B[gc];W[of];B[mf];W[qc];B[qd] ;W[rd];B[pc];W[rb];B[qb];W[rc];B[jo];W[dh];B[bb];W[cb];B[be];W[bc];B[im] ;W[gr];B[gq];W[ir];B[iq];W[hs];B[hp];W[jr];B[lq];W[ip];B[hr];W[kq];B[hq] ;W[kp];B[lr];W[kr];B[ln];W[kn];B[ko];W[lp];B[nq];W[np];B[lo];W[mo];B[mq] ;W[mp];B[oq];W[nm];B[jp];W[ql];B[rl];W[rk];B[pl];W[qk];B[on];W[oo];B[po] ;W[mm];B[ok];W[ol];B[ch];W[ei];B[dj];W[ej];B[dk];W[ek];B[pm];W[pk];B[eh] ;W[dg];B[eg];W[df];B[ef];W[ck];B[de];W[dl];B[kg];W[mi];B[om];W[nl];B[ki] ;W[hi];B[mj];W[lj];B[li];W[mk];B[mh];W[nj];B[pg];W[pf];B[nh];W[pb];B[ob] ;W[qa];B[hg];W[rm];B[rp];W[gm];B[mb];W[oa];B[oi];W[oj];B[na];W[fo];B[io] ;W[gg];B[gh];W[hh];B[ig];W[fh];B[gf];W[gi];B[cf];W[dr];B[cr];W[fr];B[eq] ;W[er];B[eo];W[jh];B[co];W[bo];B[fm];W[jg];B[jf];W[kh];B[lg];W[ff];B[ih] ;W[ji];B[ii];W[jj];B[gl];W[hf];B[if];W[ge];B[ab];W[ac];B[di];W[hl];B[hm] ;W[ie];B[je];W[fl];B[gk];W[rn];B[ro];W[lh];B[pi];W[qi];B[qh];W[ij];B[rg] ;W[rf];B[il];W[hk];B[gn];W[ri];B[og];W[ne];B[me];W[oc];B[pa];W[id];B[qb] ;W[ic];B[ra];W[rh];B[jc];W[br];B[ib];W[hb];B[jb];W[hc];B[gd];W[qg];B[bi] ;W[bj];B[ah];W[cs];B[nf];W[oe];B[od];W[kl];B[op];W[no];B[ni];W[kj];B[ae] ;W[ba];B[qe];W[re];B[lm];W[cp];B[dq];W[fe];B[qq];W[km];B[ks];W[qm];B[ll] ;W[ha];B[lk];W[kk];B[ik];W[hj];B[fk];W[fa];B[el];W[em];B[fl];W[dj];B[dh] ;W[gb];B[fc];W[ph];B[aj];W[ak];B[bh];W[ia];B[ja];W[jn] C[http://gogameguru.com/];B[hd];W[he];B[sn];W[sm];B[so];W[js];B[ls];W[in] ;B[hn];W[do];B[ad];W[aa];B[co];W[ng];B[mg];W[do];B[fj];W[fn];B[co];W[nn] ;B[pn];W[do];B[ep];W[qh];B[ea];W[da];B[oh];W[co];B[ai];W[sb];B[fg];W[fi] ;B[go];W[sa];B[qa];W[gj];B[fp])


Ambas partidas se jugaron con un tiempo de 30 minutos por jugador, un tiempo bastante rápido para lo acostumbrado por los profesionales. Seria interesante también enfrentamientos computadora-humano al mejor de 5, de forma que los profesionales puedan adaptar su juego a la forma de jugar de la computadora en sucesivas partidas.

¿Estamos cerca de conseguir programas que superen a un profesional del Go o es un objetivo inalcanzable?

Fuentes: http://gogameguru.com/crazy-stone-computer-go-ishida-yoshio-4-stones/
http://gogameguru.com/zen-computer-go-program-beats-takemiya-masaki-4-stones/