ıllı Internet y Tecnologías de la Información (2018)

internet, Hosting, dominios, seo, antivirus, banco de imágenes, páginas web, tiendas online

[Enciclopedia Online Gratuita] Diccionario de Internet y Tecnologías de la Información y la Comunicación (TIC):

ıllı Poda alfa-beta : que es, definición y significado, descargar videos y fotos.

videos internet

salud  ıllı Poda alfa-beta : que es, definición y significado, descargar videos y fotos.  


paraisodigitalEjemplo de poda alfa-beta.

La poda alfa beta es una técnica de busca que reduce el número de nodos evaluados en un árbol de juego por el algoritmo Minimax. Se trata de una técnica muy usada en programas de juegos entre contrincantes como el ajedrez, el 3 en raya o bien el Go.


Entre los vanguardistas en el empleo de esta técnica hallamos a Arthur Samuel, D.J Edwards y T.P. Hart,? Alan Kotok,? Alexander Brudno,? Donald Knuth y Ronald W. Moore?


El inconveniente de la busca Minimax es que el número de estados a explorar es exponencial al número de movimientos. Partiendo de este hecho, la técnica de poda alfa-beta trata de quitar partes grandes del árbol, aplicándolo a un árbol Minimax estándar, de manera que se devuelva exactamente el mismo movimiento que devolvería este, merced a que la poda de dichas ramas no influye en la resolución final.


La busca minimax es primero en profundidad, por este motivo en cualquier instante solo se deben estimar los nodos durante un camino en el árbol.


La poda alfa-beta toma dicho nombre de la utilización de 2 factores que describen los límites sobre los valores cara atrás que aparecen durante cada camino.



  • a es el valor de la opción mejor hasta el instante a lo largo del camino para MAX, esto implicará por ende la elección del valor más alto
  • ß es el valor de la opción mejor hasta el instante a lo largo del camino para MIN, esto implicará en consecuencia la elección del valor más bajo.

Esta busca alfa-beta va actualizando el valor de los factores conforme se recorre el árbol. El procedimiento efectuará la poda de las ramas sobrantes cuando el valor actual que se está examinando sea peor que el valor actual de a o bien ß para MAX o bien MIN, respectivamente.


El desarrollo del algoritmo en pseudocódigo va a ser el siguiente:

función alfa-beta(nodo //en nuestro caso el tablero, profundidad, a, ß, jugador) si nodo es un nodo terminal o bien profundidad = 0 devolver el valor heurístico del nodo si jugador1 para cada hijo de nodo a := max(a, alfa-beta(hijo, profundidad-1, a, ß, jugador2)) si ß=a romper (* poda ß *)devolver a si nopara cada hijo de nodo ß := min(ß, alfa-beta(hijo, profundidad-1, a, ß, jugador1)) si ß=a romper (* poda a *)devolver ß
(* Llamada inicial *)alfa-beta(origen, profundidad, -infinito, +infinito, jugador_deseado)

Ejemplo de poda alfa-beta

La figura muestra un caso de la poda alfa-beta. Cada nivel representa la jugada de los jugadores MAX y MIN, que deberán delimitar un valor a o bien ß respectivamente.

A continuación se presenta un caso de aplicación del algoritmo para el árbol de la figura. En ella los nodos podados al aplicar el algoritmo se presentan sombreados en gris.


Comenzamos primero con la busca en profundidad. El padre de los nodos hoja más a la izquierda, etiquetados con cinco y seis respectivamente, va a deber elegir un valor ß tratándose de un nivel MIN, esto implica que va a deber seleccionar el valor mínimo entre dichos nodos, esto es cinco.


Siguiendo el desarrollo, se expandirán el resto de sucesores del padre. En un caso así se expande el camino que conduce a los nodos hoja siete y, buscando un valor ß menor, el nodo etiquetado con cuatro. Ahora el valor momentáneo de ß en ese nivel es cuatro (el mínimo entre siete y cuatro). Esto implica que ahora en el nivel superior, el padre del nodo que etiquetamos previamente con ß igual a cinco, y de este ß igual a cuatro momentáneo, debe decidir el mejor valor, (el más alto al encontrarse en un nivel MAX), si prosiguiéramos expandiendo hijos del nodo MIN padre de siete y cuatro, solo podríamos lograr valores menores a cuatro, lo que proseguiría implicando una elección de la jugada izquierda en el nivel MAX, en consecuencia, podemos podar el resto de hijos, tal como se muestra en la figura.


El resto del desarrollo del árbol se proseguiría usando los criterios mentados de antemano.


La eficiencia de la poda alfabeta depende del orden en el que se examinan los sucesores, o sea, el algoritmo se comportará de forma más eficaz si examinamos primero los sucesores que seguramente van a ser los mejores.


Si esto pudiese hacerse, implicaría que alfa-beta solo debería examinar O(bd/2)undefined en vez de los O(bd)undefined de Minimax. Esto implica que el factor de ramificación eficiente va a ser de bundefined en vez de bundefined. En otras palabras, alfa-beta podría mirar cara delante más o menos un par de veces más que Minimax en exactamente la misma cantidad de tiempo.


Si se recurre a una ordenación azarosa en vez de primero el mejor en los sucesores, el número aproximado de nodos examinados sería de O(b3d/4)undefined para un valor moderado de bundefined. En ajedrez se puede efectuar una función de ordenación fácil teniendo presente primero atrapas de fichas, después amenazas, movimientos cara delante y finalmente movimientos cara detrás, esto lograría más o menos un factor de 2 del resultado O(bd/2)undefined del mejor caso. La incorporación de esquemas activos para ordenar movimientos, basados en experiencia podrían acercarse al máximo teorético.?


  ELIGE TU TEMA DE INTERÉS: 


autoayuda.es   Internet y Tecnologias 

Está aquí: Inicio > [ INTERNET ] > ıllı Poda alfa-beta : que es, definición y significado, descargar videos y fotos.

Las cookies nos permiten ofrecer nuestros servicios. Al utilizar nuestros servicios, aceptas el uso que hacemos de las cookies. Ver políticas