Heuristica
Páginas: 11 (2634 palabras)
Publicado: 2 de octubre de 2012
Diseño de funciones heuristicas para problemas:
Geometricos:
La fuente unica del camino más corto, basado en la conexion, tiene muchas caracteristicas geograficas espaciales obvias. Diseñando el modelo espacial de datos de la conexion y analisando las caracteristicas geometricas de la tendencia espacial de la ruta, formamos una funcion espacial restringida, la cual puede reducir el costo debusqueda, el camino mas corto en la conexion. La funcion espacial restringida es usada en el algoritmo heurisitico como un tipo de funcion heuristica. Con esta funcion el algoritmo heuristico espacial restringido es diseñado y descrito. Resultados experimentales muestran que: el costo de el algoritmo heuristico espacial restringido es cercano al algoritmo heuristico A*, pero eso puede obtener lasolucion optima de el camino mas corto en tiempo real por un algoritmo iterativo.
El juego de ajedrez:
Un programa de ajedrez típico contiene tres elementos: descripción del tablero, árbol de corte y búsqueda y evaluación de la posición.
← a) Datos de interés.
Al inicio de un juego de ajedrez cada lado tiene 20 movimientos posibles de modo que hay unas 400 posiciones posiblesdiferentes después de los primeros intercambios. El número de movimientos posibles para cada jugador es de aproximadamente 50 en el medio juego.
Como se dijo el factor de ramificación (b) para el juego de ajedrez es de 35 la profundidad del árbol (d) es de 100.
← b) Función de evaluación.
La forma que toma la función de evaluación estadística para este juego es:
E(p) = a*B + b*R+ c*M + d*C + e*P + f*A
El parámetro B es el balance material existente en la posición, para ello se usan los valores: peón = 1, caballo = alfil = 3, torre = 5, reina = 10. Por eso si max tiene ventaja de un alfil y min de un peón se tendría B = +3 –1 = +2.
R: La seguridad relativa del rey. El coeficiente b puede variar durante el juego, volviéndose 0 cuando las piezas principales hansido sacadas del juego y el rey ayuda el ataque protegiendo sus propias piezas.
M: La movilidad de las piezas, medida por la cantidad de casillas para las cuales cada pieza puede moverse: este número será pesado por un factor dependiendo del tipo de la pieza.
C: Control del centro. El coeficiente d toma un valor alto en el medio juego.
P: Estructura de peones. La contribución positivala dan los peones protegidos, avanzados y pasados de max y de los aislados y desprotegidos de min.
A: Esta es una medida de las posibilidades relativas para atacar, tomando en cuenta las piezas avanzadas más allá de la cuarta fila, torres sobre filas o columnas abiertas, posibles jaques, etc.
← c) Método de búsqueda.
Los preferidos son variantes del algoritmo (-( limitado aprofundidad. El modelo general para todos los programas de ajedrez es el siguiente. Una búsqueda exhaustiva a todo lo ancho a unas pocas capas de profundidad. A profundidades más grandes se usa alguna forma de búsqueda selectiva, típicamente movimientos poco prometedores se ignoran.
Damas Inglesas
Algunos juegos como las damas o el ajedrez, por tener información completa de inicio
son idóneospara la búsqueda de caminos en un sistema complejo, pudiendo después
aplicar lo descubierto a otros campos de la computación o de la ciencia en general.
El primer juego que se intento computarizar y para el que se desarrolló un programa fue
precisamente el juego de las damas. Posteriormente otros juegos fueron tratados en este
aspecto, llegando al momento actual en que es el ajedrez el másestudiado y al que
mayores esfuerzos se dedican en pos de la consecución del jugador perfecto, como
sucedió con los programas Deep Blue y actualmente, 3DFritz.
Las técnicas y algoritmos que se usan para todos estos juegos son básicamente los
mismos, cambiando solo alguna particularidad del juego tratado, como la generación de
jugadas, etc. Por todo ello, los algoritmos que se detallarán a...
Geometricos:
La fuente unica del camino más corto, basado en la conexion, tiene muchas caracteristicas geograficas espaciales obvias. Diseñando el modelo espacial de datos de la conexion y analisando las caracteristicas geometricas de la tendencia espacial de la ruta, formamos una funcion espacial restringida, la cual puede reducir el costo debusqueda, el camino mas corto en la conexion. La funcion espacial restringida es usada en el algoritmo heurisitico como un tipo de funcion heuristica. Con esta funcion el algoritmo heuristico espacial restringido es diseñado y descrito. Resultados experimentales muestran que: el costo de el algoritmo heuristico espacial restringido es cercano al algoritmo heuristico A*, pero eso puede obtener lasolucion optima de el camino mas corto en tiempo real por un algoritmo iterativo.
El juego de ajedrez:
Un programa de ajedrez típico contiene tres elementos: descripción del tablero, árbol de corte y búsqueda y evaluación de la posición.
← a) Datos de interés.
Al inicio de un juego de ajedrez cada lado tiene 20 movimientos posibles de modo que hay unas 400 posiciones posiblesdiferentes después de los primeros intercambios. El número de movimientos posibles para cada jugador es de aproximadamente 50 en el medio juego.
Como se dijo el factor de ramificación (b) para el juego de ajedrez es de 35 la profundidad del árbol (d) es de 100.
← b) Función de evaluación.
La forma que toma la función de evaluación estadística para este juego es:
E(p) = a*B + b*R+ c*M + d*C + e*P + f*A
El parámetro B es el balance material existente en la posición, para ello se usan los valores: peón = 1, caballo = alfil = 3, torre = 5, reina = 10. Por eso si max tiene ventaja de un alfil y min de un peón se tendría B = +3 –1 = +2.
R: La seguridad relativa del rey. El coeficiente b puede variar durante el juego, volviéndose 0 cuando las piezas principales hansido sacadas del juego y el rey ayuda el ataque protegiendo sus propias piezas.
M: La movilidad de las piezas, medida por la cantidad de casillas para las cuales cada pieza puede moverse: este número será pesado por un factor dependiendo del tipo de la pieza.
C: Control del centro. El coeficiente d toma un valor alto en el medio juego.
P: Estructura de peones. La contribución positivala dan los peones protegidos, avanzados y pasados de max y de los aislados y desprotegidos de min.
A: Esta es una medida de las posibilidades relativas para atacar, tomando en cuenta las piezas avanzadas más allá de la cuarta fila, torres sobre filas o columnas abiertas, posibles jaques, etc.
← c) Método de búsqueda.
Los preferidos son variantes del algoritmo (-( limitado aprofundidad. El modelo general para todos los programas de ajedrez es el siguiente. Una búsqueda exhaustiva a todo lo ancho a unas pocas capas de profundidad. A profundidades más grandes se usa alguna forma de búsqueda selectiva, típicamente movimientos poco prometedores se ignoran.
Damas Inglesas
Algunos juegos como las damas o el ajedrez, por tener información completa de inicio
son idóneospara la búsqueda de caminos en un sistema complejo, pudiendo después
aplicar lo descubierto a otros campos de la computación o de la ciencia en general.
El primer juego que se intento computarizar y para el que se desarrolló un programa fue
precisamente el juego de las damas. Posteriormente otros juegos fueron tratados en este
aspecto, llegando al momento actual en que es el ajedrez el másestudiado y al que
mayores esfuerzos se dedican en pos de la consecución del jugador perfecto, como
sucedió con los programas Deep Blue y actualmente, 3DFritz.
Las técnicas y algoritmos que se usan para todos estos juegos son básicamente los
mismos, cambiando solo alguna particularidad del juego tratado, como la generación de
jugadas, etc. Por todo ello, los algoritmos que se detallarán a...
Leer documento completo
Regístrate para leer el documento completo.