Cómo piensa un programa de ajedrez

#1   Este tipo de cosas me hubieran venido de perlas antes de dejar la carrera de Ingenieria Informática..sniff...XD

#2   Meneo al canto porque me ha parecido muy interesante, la verdad no tenía ni idea de como funcionaban.

#4   #3 De nada, algo divulgativo siempre vale la pena divulgar (ole la redundancia)

#5   Yo hice inteligencia artificial en la uni. Que pena que el enfoque que le dieron no era lo suficientemente bueno, porque el tema es muy interesante. Más flipante me pareció la resolución de problemas más complejos utilizando Hill climbing y otros algoritmos. Un ajedrez es bastante básico, pero imaginaros la de información y posibilidades que puede manejar un bot en un juego de acción.

#1 Ánimos crack, siempre puedes volver al lado oscuro con nosotros

#6   He probado en el Chess de Ubuntu a configurar CPU para ambos jugadores. Creía que serían deterministas, es decir, que las partidas serían iguales pero no, unas veces ganan blancas y otras negras...

#7   #3 Calcula los meneos y las visitas, a ver si se corresponden; y nos lo dices...
Por otro lado quiero felicitarte no solo por el artículo, sino por explicarlo de tal manera que un analfabeto de la matemática como un servidor se ha enterado. Poca gente es capaz de explicar ciencia así. Meneo.

#8   por cierto, para cuándo el primer comentario de "Anatoliiiii" ?

#9   #5 Los juegos de acción no entrañan dificultad alguna.

Se trata de machacar continuamente el botón de disparo, el de saltar y el de ir hacia adelante

#10   Bueno, pensar, pensar...
Mas bien simula pensar.
Como el 90% de la gente, ahora que pienso :-P.

#11   #7 Por ahora van más visitas que meneos, pero nunca sabré si todos leen el artículo
Muchas gracias, la verdad es que no tenía muy claro si el lenguaje era suficientemente claro, espero que, como decís, sí lo haya sido.

#12   Un articulo de puta madre. Muchas gracias por hacernos un poco más listos a los que lo hemos leido.
#6 Muy bien hecho. Es una de las cosas que hace alguien con mucha curiosidad.. jeje.

#13   #9 Bueno... hay juegos en los que el enemigo te escucha, se esconde, hace fuego de cobertura... no es tan fácil implementarlo como jugarlo

#14   Mis mas sinceras felicitaciones al autor del artículo. Creo que no se puede explicar mejor para un neófito como yo.

#15   Gran aporte, felicidades al autor.

#16   #5 Personalmente no definiría el ajedrez como algo "básico".

Genial artículo, muy bien explicado y muy interesante. Siempre había tenido la curiosidad de saber como funcionan esas cosas. (Y que el tipo que lo explique hable de la tostadora valiente da muchos puntos a su explicación.)

#17   #3 Ya te vale, has ignorado por completo la poda alfa-beta. Ahora todo el mundo pensará que es necesario examinar todas las posibles ramificaciones... .
Buen artículo.

#18   #17 si insistes, puedo escribir otro que hable de las posibles variaciones: negamax, negascout, poda alfa-beta... Y lo digo en serio
#16 opino como tú, yo tampoco llamaría al ajedrez algo "básico". Está claro que crear un algoritmo que mueva las piezas es muy sencillo: sólo tiene que conocer las reglas. Pero hacer que sea el mejor es harto más difícil. Larga vida a la tostadora valiente.

Gracias a todos por las felicitaciones.

Por cierto, a modo de sondeo. Yo también quiero aprender con mi blog, así que últimamente pregunto a mis amigos sobre temas que les interesen para investigar sobre ellos y publicar algo. Así que si alguno tenéis una idea, podéis decírmela y si me interesa el tema lo agregaré a mi lista personal de artículos pendientes

#19   #18 Te animo a que expliques la versión mejorada con poda alfa-beta u otros algoritmos, ya que puede estar muy interesante. Me recordarán aquellas horas de programación de IAs en la uni, y mucha gente aprenderá cosas interesantes.

#20   #19 tomo nota. Podrás verlo dentro de un tiempo, el próximo que publique (que espero que sea pronto) será de teoría de juegos.

#21   #1 Pues algo de esto se ve en Analisis y Diseño de Algoritmos (ADA para los amigos ) en la técnica de backtracking.

#6 Hombre, no sé como lo habrán implementado, pero si en el árbol de decisión, el algoritmo para una profundidad 'x' obtiene 10 nodos hijo con la misma máxima puntuación (osease, no sabe cual de todos los posibles movimientos llevan a la victoria entre esos 10 supuestos mejores) pues es bastante probable que en ese caso el algoritmo decida usar el azar (la función random vaya ) para elegir... y entonces varían las jugadas.

Un saludo!

#22   Siempre me había preguntado eso, incluso pensé en programar yo uno en C

#23   Muchas gracias por la noticia.

Para aquellos que tengan interés por el asunto, creo que esta página es interesante

www.tckerrigan.com/Chess/TSCP

Se trata de un progrma de ajedrez pensado para aquellos que quieran aprender a programar estos cacharros. El código está bastante comentado y se supone que es bastante sencillo.

Aprovecho para pregntar al autor y demás si conocen de recursos en la red para aprender a sacar un programita e estos.

#24   Muy buen artículo, temás básicos en el mundo de la IA, pero muy bien explicado.

El ajedrez ha sido originalmente el problema a resolver por la IA, y ya ha sido resuelto sobradamente (IAs ganando a los mejores jugadores del mundo). Esto se ha conseguido mezclando heurísticas buenas con potencia de cálculo. Ahora el próximo problema a resolver es el Go, el cual a pesar de tener una reglas más simples que el ajedrez, es computacionalmente mucho más complejo que el ajedrez (pero que muchísimo mas). Os dejo un par de enlaces de la wikipedia a los que tengais curiosidad, e invito al autor a hablar sobre él

en.wikipedia.org/wiki/Go_(game) <- ¿Qué es el Go?
en.wikipedia.org/wiki/Go_and_mathematics <- Complejidad matemática del Go
en.wikipedia.org/wiki/Computer_Go <- Porqué el Go es tan complicado para una IA

#6 Eso se debe que aunque son deterministas, hay muchos puntos que dos o tres jugadas tienen el mismo valor. En ese caso se elige una al azar para darle más dinamismo a las partidas y que no sean siempre iguales.

#25   #23 Pipulo, en los enlaces del final del post tienes algunos, te recomiendo:
profeblog.es/blog/alfredo/2009/07/28/ajedrez-paso-10-nace-la-inteligen

#24 Programé hace poco una IA para el Othello (similar al Reversi). Si lo que dices del Go! es cierto, no voy a poder evitar enfrascarme en la programación de una IA para él. Si lo llevo a cabo lo dejaré ver por dCiencia.

#26   char*l="ustvrtsuqqqqqqqqyyyyyyyy}{|~z|{}"
" 76Lsabcddcba .pknbrq PKNBRQ ?A6J57IKJT576,+-48HLSU";
#define F getchar()&z
#define v X(0,0,0,21,
#define Z while(
#define _ ;if(
#define P return--G,y^=8,
B,i,y,u,b,I[411],*G=I,x=10,z=15,M=1e4;X(w,c,h,e,S,s){int t,o,L,E,d,O=e,N=-M*M,K
=78-h<<x,p,g,n,m,A,q,r,C,J,a=y?-x:x;y^=8;G++;d=w||s&&s>=h&&v 0,0)>M;do{_ o=I[
p=O]){q=o&z^y _ q<7){A=q--&2?8:4;C=o-9&z?q["& .$ "]:42;do{r=I[p+=C[l]-64]_!w|p
==w){g=q|p+a-S?0:I+S !r&(q|A<3||g)||(r+1&z^y)>9&&q|A>2){ m=!(r-2&7))P G[1]=O,
K;J=n=o&z;E=I[p-a]&z;t=q|E-7?n:(n+=2,6^y);Z n<=t){L=r?l[r&7]*9-189-h-q:0 _ s)L
+=(1-q?l[p/x+5]-l[O/x+5]+l[p%x+6]*-~!q-l[O%x+6]+o/16*8:!!m*9)+(q?0:!(I[p-1]^n)+
!(I[p+1]^n)+l[n&7]*9-386+!!g*99+(A<2))+!(E^y^9)_ s>h||1<s&s==h&&L>z|d){p[I]=n,O
[I]=m?*g=*m,m=0:g?g=0:0;L-=X(s>h|d?0:p,L-N,h+1,G[1],J=q|A>1?0:p,s)_!(h||s-1|B
O|in|p-b|L<-M))P y^=8,u=J;J=q-1|A<7||m||!s|d|r|o<z||v 0,0)>M;O[I]=o;p[I]=r;m?
m=*g,*g=0:g?g=9^y:0;}_ L>N){*G=O _ h&&c-L<0)P L;N=L _!h&s>1)i=n,B=O,b=p;}n+=J
||(g=I+p,m=p<O?g-3:g+2,*m<z|I[p+=p-O]|m[p<O?1:-1]);}}}}Z!r&q>2||(p=O,q|A>2|o>z&
!r&&++C*--A));}}}Z++O>98?O=20:e-O);P N+M*M&&N>-K+1924|d?N:0;}main(){Z++B<121)*G
++=B/x%x<2|B%x<2?7:B/x&4?0:*l++&31;Z B=19){Z B++<99)putchar(B%x?l[B[I]|16]:x)_
x-(B=F)){i=I[B+=(x-F)*x]&z;b=F;b+=(x-F)*x;Z x-(G=F))i=G^8^y;}else v u,5);v u,
1);}}

Este nanochess es de Oscar Toledo. Es una familia mejicana que debe ser un poco secta... pero el programa parece ser que juega y es el más pequeño que hay, que yo sepa.

PS.- nanochess.110mb.com/chess3_es.html

#27   #25 Como dato, la complejidad de un arbol de juego de ajedrez es de logaritmo en base 10 de 123, mientras que la del go es de logaritmo en base 10 de 360. En dos turnos de cada jugador (4 turnos en total) hay 16702719120 posibles movimientos, y una partida media dura 200-300 movimientos.

Es un tablero de 19x19 donde puedes poner legalmente en cualquier punto, y además cuando te comes grupos de piedras, puedes volver a poner ahi. Es tremendamente sutil, y hay ciertas cosas que no se pueden valorar numéricamente (¿territorio o influencia?)

Es un juego magnífico

#28   Me veo obligado, por lo menos, a jugar

#29   #3 Estoy interesado en como podria crear un enfoque heurístico para el reconocimiento de patrones en las cadenas de texto (como evaluaria google por ejemplo). ¿Conoces de algun documento que me puedas recomendar?, gracias. Por cierto me considero un mercernario del codigo, mi nivel de algoritmia es practicamente 0.

#30   siii! a mi también me ha gustado.
Bien explicado.

#31   #28 El Go se basa en reconocimiento de patrones, que es lo peor para un ordenador, de ahí el problema... Según tengo entendido (pero hace un par de años, ya no recuerdo):

Un ordenador puede vencer (o más bien empatar) a un experto en 3 en raya
Un ordenador puede vencer a un experto en ajedrez, aunque no a un gran maestro
Un ordenador no puede vencer a un principiante del Go

Son como las tres leyes

A lo que iba: ¡¡¡Excelente Post!!! Muy bien explicado, absolutamente correcto (hay veces que para hacer un trabajo divulgativo se olvidan los detalles y se cometen pequeñas incorrecciones... ¡pero no es tu caso! Has logrado hacerlo siento exquisitamente preciso), y bien redactado. Pó Dió, ¡haz más!

En cuanto a temas interesantes... anda que no hay. Por ejemplo de IA, es sencillo explicar algoritmos genéticos, algoritmos de partículas (eg. optimización con hormigas), aprendizaje por refuerzo, planificación (eg. STRIPS), clasificación (cualquier puede entender el ID3 )

Si hablas de optimización, por cierto, puedes tratar de hablar de tipos de problemas (P, NP, co-NP) que siempre mola. Y luego otros temas clásicos son los de complejidad: Atractores extraños (Lorentz), teoría del caos en general (Logistic), fractales (Julia), etc. Y muchos más, ¡tienes tanto donde elegir!

Cosas que ni creo que se pudieran tratar de divulgar así como así serían las redes neuronas (ni el perceptrón simple, la gente tiene sus problemas para imaginar hiperplanos, normalmente), tampoco visión artificial (yo mismo no recuerdo nada ya :P), etc.

PD: Si haces algo de algoritmos genéticos, please, habla y mete el video de Karl Sims: www.archive.org/details/sims_evolved_virtual_creatures_1994

PPD: ¿Ves qué ladrillo me ha quedado? Eso te pasa por preguntar temas Jeje, sorry, es que me he emocionado.

#32   #31 Gracias. Menearía tu respuesta
Lo de teoría del caos lo había pensado, a ver si me saco un libro de la biblioteca de la etsiit. Apunto todo lo que me has dicho, inclusive lo de las redes neuronales, que es un tema que me interesa bastante. A ver si puede hacerse algo entendible.

#29 La verdad es que ahora mismo no se me ocurre ningún documento. Si no encuentras nada en internet, que a veces pasa, tienes que tirar a lo clásico: libros.

#33   #32 Si quieres un libro divulgativo sobre complejidad, éste es, sin duda, "Computational Beauty of Nature". Aunque no sé si soy objetivo, yo personalmente ADORO ese libro

(web del mismo, con programasde los diferentes capítulos y tal: mitpress.mit.edu/books/FLAOH/cbnhtml/)

#35   #33 El que saque será un libro formal, no divulgativo. Pero apunto ese título que me has dicho.

#34 Exacto, y lo digo justo al comienzo del artículo... También hay otra forma de decir las cosas.

#36   En realidad el ajedrez no ha sido resuelto computacionalmente puesto que los ordenadores siguen sin ser capaces de crear planes, pero su visión a largo término dada la potencia de cálculo les permite ganar a los mejores jugadores.
Mucho más complejo por tanto sería hacer un programa que entendiese el ajedrez, pero entiendo que hay pocos alicientes para hacerlo dados los resultados obtenidos con métodos más simples.

#37   Yo voto irrelevante, porque no es nada nuevo... y el que no lo sabía de antes, sería porque el tema no le interesaba demasiado. Yo esto lo he visto cientos de veces.

#38   Para los interesados en el juego y en la IA, un caso muy interesante es el del Backgammon. A pesar de ser un juego de una sencillez increíble, (más o menos como el parchís, con dados pero con más estrategia), hacer un programa que juegue a un nivel principiante es sencillo,... pero hacer uno que juegue a nivel decente y capaz de derrotar a un buen jugador se resistía. Al menos utilizando algoritmos tradicionales con evaluación de posiciones, cálculo de estadísticas en función de las posibilidades del dado, etc.

El enfoque adecuado ha sido el de redes neuronales y tablas hash precomputadas para dinamitar los finales...

Un programa muy bueno, opensource para los curiosos y con un nivel de juego campeonato es Gnubg www.gnubg.org/index.php?itemid=16 Muy intersante. Además el BG es divertido, creo yo...

#39   #3 Me ha parecido un post muy interesante. Me ha recordado a mi práctica de Inteligencia Artificial. Tenía que implementar las damas con una poda alfa-beta en Clips... ¡Que tiempos aquellos!.

#40   #35 Hombre, es el libro que usé en la asignatura "Complejidad Computacional", de la carrera de Ingeniería Informática. Puedo garantizar que es mejor que comenzar con las matemáticas duras desde el principio (más tarde estudié fractales en un Máster en Matemática Computacional, y las matemáticas son duras y sobretodo abstractas).