PODA ALFA-BETA

INTRODUCCIÓN

Poda alfa-beta surgió como mejora del algoritmo minimax. Este algoritmo es capaz de reducir significativamente el número de nodos evaluados en un árbol de juegos y es una técnica muy usada en juegos entre adversarios como por ejemplo: el ajedrez, tres en raya y otros.

DESARROLLO

¿QUÉ ES PODA ALFA-BETA?

El poda alfa-beta es una mejora del algoritmo minimax, y se puede calcular una decisión mínima correcta y es posible aplicarlo a arboles de cualquier profundidad. Emplea la búsqueda primero en profundidad para considerar los nodos que se encuentran a lo largo del camino.

Existen dos jugadores en:

·         Maximizador

·         Minimizador

Y existen dos valores que son:

·         Alfa

·         Beta

Estos valores ayudan en la búsqueda, lo que mejora la búsqueda y mejorando la velocidad sin que se pierda la información

CARACTERÍSTICAS DE LA PODA ALFA-BETA

·         Omite la expansión de nodos donde los valores no son los mejores.

·         La búsqueda se para en algún nivel y se realizan evaluaciones heurísticas.

·         Si el valor del nodo MAX es decir alfa, es menor que el más alto hasta este momento, entonces omitir nodo.

·         Si el valor nodo MIN es decir, beta es mayor que el nodo más bajo hasta el momento, entonces omitir  nodo.

·         El algoritmo alfa-beta permite una búsqueda más completa.

·         En este algoritmo solo importa el orden y no los valores exactos.

·         Poda alfa-beta nos lleva al resultado final.

·         Alfa-beta es una mejora del algoritmo Minimax que evita revisar aquellos nodos donde la información no es útil en la jugada.

La búsqueda se realiza en profundidad y avanza de forma ordenada y usa la información para podar las ramas.

ESTRUCTURAS DE DATOS

Dos variables que se deben ser recordadas durante la búsqueda:

·         Alfa: limite inferior encontrando hasta ese momento.

·         Beta: limite superior.

·         En los niveles maximizantes MAX, se usa beta para podar.

·         En los niveles MIN, se usa alfa para podar.

·         Alfa-beta es muy usado para busqueda en árboles de juegos.

CONCLUSIÓN

Poda alfa beta es una mejora del algoritmo minimax que evita recorrer todos los nodos del árbol lo cual mejora la velocidad y no se pierde la información. El poda alfa-beta usa dos valores para obtener sus propósitos: alfa y beta.

BIBLIOGRAFÍA

López, B. 2009. Poda Alfa-Beta. (En línea). ME. Consultado, 20 de NOV. 2015. Formato PDF. Disponible en: http://www.itnuevolaredo.edu.mx/takeyas/

Solano, R. 2008. Poda Alfa-Beta. (En línea). EC. Consultado, 20 de nov. 2015. Formato PDF. Disponible en: http://es.slideshare.net/rfsolano/ poda-alfa-beta

Russell S. y P. Norvig Inteligencia Artificial: Un enfoque moderno. 2 ed. España. Pearson. p 188-191.

BÚSQUEDA ENTRE ADVERSARIOS-JUEGOS

INTRODUCCIÓN

Los juegos son entornos donde se desenvuelven dos agentes, cada agente debe considerar las acciones del otro agente que se desenvuelven en entornos competitivos donde los agentes siempre están en conflictos, solo puede haber un ganador y el otro indiscutiblemente será el perdedor, esto da lugar a la búsqueda entre adversarios más conocido como juegos.

DESARROLLO

JUEGOS

La teoría de los juegos es una rama de la economía porque ve un entorno multiagente como un juego donde cada acción realizada genera un impacto significativo.

Los juegos son una clase especializada a la que los teóricos de juegos la llamaban juegos de suma cero, de dos jugadores, etc.

Los primeros juegos fueron: el ajedrez, tres en raya. En todo juego si un jugador de gana el otro pierde, por esta razón los agentes producen una situación de adversarios.

Los juegos ocupan las facultades mentales de la gente, en ocasiones en un grado muy elevado, pero los investigadores indican que la naturaleza de los juegos los hacen un tema interesante.

Jugar juegos fue una de las primeras tareas de la inteligencia artificial, poco después de que las computadoras se hicieran programables. Los juegos son parecidos a la vida real en cierto modo, por ejemplo: en un juego se requiere de la capacidad de tomar decisiones cuando se debe calcular una solución óptima y castigan la ineficiencia   

DECISIONES ÓPTIMAS EN JUEGOS

Puede definirse como una clase de problemas de búsqueda con los siguientes componentes:

·         El estado inicial.

·         Una función sucesor devuelve una lista de movimientos pares o estados.

·         El test terminal determina cuando termina el juego.

·         Una función utilidad.

e   Ejemplo:

CONCLUSIÓN

Los juegos fueron uno de los primeros objetivos de la I.A, tiene la capacidad de ocupar la mentalidad de algunas personas en niveles excesivos lo que no es bien visto. Un juego está conformado por dos agentes donde uno de ellos es el ganador y el otro debe ser el perdedor.

BIBLIOGRAFÍA

Ceccaroni, L. 2008. Búsqueda entre adversarios. (En línea). ES. Consultado,  13 de nov. 2015. Formato PDF. Disponible en: http://www.cs.upc.edu/~luigi/II

Pérez, G. 2011. Búsqueda entre adversarios. (En línea). ES. Consultado,  13 de nov. 2015. Formato PDF. Disponible en: http://es.slideshare.net/gvnyps/

Russell S. y P. Norvig Inteligencia Artificial: Un enfoque moderno. 2 ed. España. Pearson. p 181-182.

AGENTES DE BÚSQUEDA ONLINE Y AMBIENTES DESCONOCIDOS

INTRODUCCIÓN

La busqueda online es una idea necesaria para un problema de explaración. La busqueda online es una idea necesaria para un problema de explaración.

Estos agentes observan el entorno de trabajo y hace un cambio en donde va a trabajar. Un agentes de este tipo es una buena idea para dominios estocasticos.

Los agentes de búsqueda online escogen la major ruta para llegar al objetivo con solo saber los acontecimientos que realmente suceden.

                                                         DESARROLLO            

Un agente de búsqueda online es una buena idea en dominios, es una idea incluso mejor que los dominios estocásticos. Esta búsqueda es una idea necesaria para un problema de exploración donde los estados y las acciones son desconocidos por el agente, y como el agente está en estado de ignorancia debe usar sus acciones como experimentos para determinar que hace después y luego se empieza a intercalar el cálculo y la acción.

AGENTES DE BÚSQUEDA ONLINE

Luego de una acción el agente online recibe una percepción al conocer el estado que ha alcanzado y a partir de esta información puede crear o aumentar su mapa del entorno, dicho mapa se usa para decidir dónde ir después.

El algoritmo online puede expandir sólo el nodo que ocupa físicamente. Para evitar viajar a través de todo el árbol para expandir el siguiente nodo es mejor expandir los nodos en orden local. La búsqueda primero en profundidad tiene exactamente dicha propiedad porque el siguiente nodo a expandir es hijo del nodo anteriormente expandido.

OBJETIVO DEL AGENTE

·         Alcanzar el estado objetivo.

·         Minimizar el coste.

INTERCALACIÓN PLANIFICACIÓN-ACCIÓN

Luego de cada acción el agente online recibe una percepción al decir que el estado se ha alcanzado. Dicha información aumenta el mapa de entorno, y luego ese mismo mapa se usa para decidir hacia dónde ir.

La búsqueda online es necesaria en problemas de exploración. Los estados deben expandirse teniendo en cuenta la posición física que la búsqueda en profundidad.

Búsqueda online: intercala el cálculo y la acción:

·         Tomar una acción.

·         Observar el entorno.

·         Calcular la siguiente acción.

Usos de la búsqueda online:

·         Problemas de exploración donde el agente desconoce los estados y las acciones

Un problema de búsqueda online puede ser resuelta solo por un agente que ejecute acciones más que por un proceso computacional

CONCLUSIÓN

Los agentes de búsqueda online trabajan en ambientes desconocidos, ellos deben explorar para aprender y con lo aprendido arma un mapa y decide que hacer luego de llegar a una meta. Son parecidos a los bebes que exploran el mundo para conocerlo.

BIBLIOGRAFÍA

Russell S. y P. Norvig Inteligencia Artificial: Un enfoque moderno. 2 ed. España. Pearson. p 138-142.

Mora, M. 2014. Agentes de búsqueda online y ambientes desconocidos. (En línea). ES. Consultado,  12 de oct. 2015. Formato PDF. Disponible en: http://inteligenciartificialmariana.blogspot.com/