427 meneos
 

Cómo piensa un programa de ajedrez

Un genial articulo que nos habla un poco de inteligencia artificial, algoritmo MiniMax y más. Dentro de la complejidad del tema, lo explica de una manera muy sencilla a modo divulgativo.
etiquetas: ajedrez, funcion, programa
usuarios: 213   anónimos: 214   negativos: 2  
40comentarios mnm karma: 610
Comentarios destacados:         
#1   Este tipo de cosas me hubieran venido de perlas antes de dejar la carrera de Ingenieria Informática..sniff...XD
votos: 4    karma: 24
#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 ;)
votos: 2    karma: 23
#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 :-D
votos: 2    karma: 22
#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 :-P
votos: 0    karma: 7
#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.)
votos: 0    karma: 6
#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…   » ver todo el comentario
votos: 3    karma: 34
#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.
votos: 1    karma: 15
#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.
votos: 0    karma: 8
#21   #1 Pues algo de esto se ve en Analisis y Diseño de Algoritmos (ADA para los amigos xD ) 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 xD ) para elegir... y entonces varían las jugadas.

Un saludo!
votos: 3    karma: 30
#2   Meneo al canto porque me ha parecido muy interesante, la verdad no tenía ni idea de como funcionaban.
votos: 0    karma: 6
#3   Soy el autor del post. Muchísimas gracias a Abeel por enviarlo y a vosotros por menearlo, pero sobre todo a todos por leerlo.

Por supuesto podeis preguntarme cualquier duda o darme cualquier sugerencia.
votos: 33    karma: 272
#4   #3 De nada, algo divulgativo siempre vale la pena divulgar (ole la redundancia)
votos: 0    karma: 9
#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.
votos: 4    karma: 45
#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.
votos: 0    karma: 8
#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.
votos: 0    karma: 6
#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.
votos: 0    karma: 9
#32   #31 Gracias. Menearía tu respuesta :-D
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.
votos: 0    karma: 8
#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 :-D

(web del mismo, con programasde los diferentes capítulos y tal: mitpress.mit.edu/books/FLAOH/cbnhtml/)
votos: 0    karma: 6
#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.
votos: 0    karma: 8
#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).
votos: 0    karma: 6
#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!.
votos: 0    karma: 6
#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...
votos: 1    karma: 13
#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.
votos: 0    karma: 7
#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…   » ver todo el comentario
votos: 7    karma: 70
#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.
votos: 1    karma: 17
#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 xD
votos: 0    karma: 9
#8   por cierto, para cuándo el primer comentario de "Anatoliiiii" ?
votos: 1    karma: 16
#10   Bueno, pensar, pensar...
Mas bien simula pensar.
Como el 90% de la gente, ahora que pienso :-P.
votos: 6    karma: 70
#14   Mis mas sinceras felicitaciones al autor del artículo. Creo que no se puede explicar mejor para un neófito como yo.
votos: 0    karma: 7
#15   Gran aporte, felicidades al autor.
votos: 0    karma: 8
#22   Siempre me había preguntado eso, incluso pensé en programar yo uno en C xD
votos: 0    karma: 7
#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.
votos: 1    karma: 15
#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…   » ver todo el comentario
votos: 3    karma: 30
#28   Me veo obligado, por lo menos, a jugar :-D
votos: 0    karma: 8
#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 :-P

A lo que iba: ¡¡¡Excelente Post!!! Muy bien explicado, absolutamente correcto…   » ver todo el comentario
votos: 2    karma: 24
#30   siii! a mi también me ha gustado.
Bien explicado.
votos: 0    karma: 6
#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.
votos: 0    karma: 6
#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.
votos: 0    karma: 8
#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…   » ver todo el comentario
votos: 1    karma: 18
comentarios cerrados

menéame