Google
 

martes, octubre 17, 2006

I.A. Básica

La forma más básica de usar la inteligencia artificial en un juego se convierte en algo tan sencillo como probar todas las posibilidades y escoger la que te lleve al premio gordo. Es fácil de efectuar con una lista. Hay tres algoritmos básicos que te pueden ayudar:
- Breadth First
- Depth First
- A*
La diferencia entre esos algoritmos es mínima, únicamente cambia la posición en la que añadimos y quitamos cosas de la lista. El pseudo-código estándar podria ser así:
hacer
estado_actual = quitar_estado_de_la_lista
si estado_actual contiene la solucíon entonces final_de_juego
array_de_estados_hijos = expandir(estado_actual)
añadir_a_la_lista(array_de_estados_hijos)
mientras no_acabe_el_juego
La diferencia entre los diferentes algoritmos es:
- Breadth First: los elementos se añaden siempre en una cara de la lista y se quitan de la cara opuesta.

- Depth First: los elementos se añaden y se quitan de la misma cara de la lista.

- A*: los elementos se añaden a cualquier cara de la lista pero se eliminan primero los mejor puntuados según una función heurística (podríamos puntuar, por ejemplo, los que estén más cerca del objetivo). Reduce enormemente el número de elementos pero a base de usar un algoritmo más lento.

10 comentarios:

samsaga2 dijo...

Pues no es que des mucho ejemplo. ¿Donde esta el problema?

selinux dijo...

Estas cosas llevan más trabajo que lo que propones, pero como idea está bien. Realmente, para juegos sencillos puede funcionar, lo que planteas parece un autómata programable de estados finitos. Eso no es una inteligencia artificial, pero es perfecto para hacer un tres en raya o un ajedrez.

Actualmente no hay juegos que aprendan del jugador, por lo que no tenemos inteligencia artificial, tenemos tontos que calculan muy rápido, y que son mejores o peores según la cantidad de información que tengan.

Personalmente pienso que opinar y hacer el ridículo siempre es mejor que denunciar y no aportar nada nuevo al tema, todavía más si ni siquiera la persona se digna a identificarse.

Juanmi dijo...

Tal vez Samsagaz no esté haciendo el ridículo, (y digo tal vez porque con tan poca informacion es dificil saber lo que querias decir realmente). Pero creo que se está refiriendo a los distintos métodos de atacar un árbol de decisión. Es decir, un arbol en el que los hijos de cada nodo son las distintas decisiones que podemos tomar en el siguiente paso... En ese caso los dos primeros serían recorridos de fuerza bruta en profundidad y anchura y el último es el algoritmo MINIMAX.(Cosa que parece asi pues se suele denominar tb A*)

Pero si que estoy con el Troll reventador en que deberías haber informado algo mejor, un psot así solo sirve para el que ya se lo sabe y por tanto no lo necesita...

samsaga2 dijo...

Algunos de los algoritmos de IA como minimax o los que comentaba no son mas que diferentes formas de recorrer un grafo.

Esto solo era una introduccion, ya tengo el codigo preparado para ampliarlo.

samsaga2 dijo...

A ver señor Yayo que parece que no nos acabamos de entender.

¿Me estas diciendo que los grafos no se han usado nunca en la vida o que es una jilipollez aprender a usarlos habiendo cosas mas interesantes como algoritmos genéticos, redes neuronales o máquinas de estado?

Si es la primera opción te diré que algoritmos como minimax, que esta íntimamente ligado a BFS, es algo que se ha estado usando durante años en cosas como juegos de ajedrez (bueno, las variantes del minimax mejor dicho).

Si en cambio te refieres a la segunda creo que es más correcto saber algo sobre los inicios de la IA que meterse a programar un sistema experto.

Por otra parte no negaré que he racaneado bastante en la explicación pero es que hasta anoche no pude hacer un pequeño ejemplo en C++ con el BFS para poder explayarme un poco más en el funcionamiento del algoritmo.

Argail dijo...

Vaya, parece que ahora uno no puede escribir en su blog sin que lo apedreen ^^uuu. En mi opinión como novato, es una introduccion al fin y al cabo, normalmente lo que se pretende es dejar las cosas un poco en el aire para luego profundizar en cada uno de los puntos que se mencionan.
Muy interesante el primer plato, seguire la serie, que el tema es interesante.

Yayo dijo...

Hola, soy el yayo der verdad, mirad que aparece la foto y el perfil de blogger. Esos comentarios son de algún hijodeputa que se intenta hacer pasar por mí. Si descubro quien es le partiré la cara con mucho gusto.

Seguro que es castellano, seguro.

Perdona por el perjuicio que te pueden haber causado mis camaradas. Espero que borres sus comentarios y dejes este.

Lo siento mucho. Algún día me lo pagarán.

Yayo dijo...

Otra nota, para saber cuales son las verdaderas hay que entrar en la página de añadir comentarios al post y ver los que aparecen con perfil.

samsaga2 dijo...

Por petición del Yayo autentico he borrado los comentarios (trolles) anteriores.

Yayo dijo...

Es que soy cretino pero no tanto como para ir a insultar a los demás sin razón ninguna, hombre.

Muchas gracias ;)