ALFA – BETA

Fecha: 16  Enero 2015

La clase de la fecha Enero 16 del 15 fue muy intuitiva e interesante, el docente planteo que debíamos hacer un pequeño resumen de  búsquedas entre adversarios  y plantear nuestras  ideas en una diapositiva para compartir información en clases entre compañeros.

Una pequeña introducción al algoritmo que se documentara a continuación es que es la evolución de un método que recorría todo un árbol de juego o árbol binario, este algoritmo se llama min Max.

.

MARCO TEÓRICO

DEFINICIÓN

alfa-beta es un algoritmo de búsqueda que busca reducir el número de nodos que se evalúan por el algoritmo minimax en su árbol de búsqueda. Se trata de un algoritmo de búsqueda de confrontación de uso común para la máquina de juego de juegos de dos jugadores (Tic-tac-toe, Ajedrez, Go, etc.). Deja de evaluar completamente un movimiento cuando se haya encontrado al menos una posibilidad de que demuestra el paso a ser peor que un movimiento ya examinada. Estos movimientos no tienen que ser evaluados más. Cuando se aplica a un árbol min max estándar, devuelve el mismo movimiento como min – max haría, pero ciruelas distancia ramas que no es posible influir en la decisión final. (Russel & Norvig. 2010)

Allen Newell y Herbert A. Simon, que utiliza lo que John McCarthy llama una «aproximación” (McCarthy.2006) en 1958 escribió que «parece que se ha reinventado varias veces» alfa-beta.( Newell & Herbert. 1976)Arthur Samuel tuvo una primera versión y Richards , Hart, Levine y / o Edwards encontraron alfa-beta de forma independiente en los Estados Unidos. (Edwards & Hart. 1963)McCarthy propusieron ideas similares durante la Conferencia de Dartmouth en 1956 y sugirió a un grupo de sus estudiantes, incluyendo Alan Kotok en el MIT en 1961 (Kotok.2014).

Al igual que el procedimiento minimax es un proceso en profundidad, existe el problema de que el número de estados del juego que tiene que examinar es exponencial en el número de movimientos.

Desafortunadamente, no podemos eliminar el exponente, pero en realidad se puede reducir a la mitad. El dispositivo es capaz de calcular la decisión minimax correcta sin tener en cuenta todos los nodos en el árbol de juego. Es decir, mejorar su eficiencia mediante el uso de técnicas de poda, en los que las soluciones parciales claramente peor que las soluciones conocidas pueden ser inmediatamente abandonada. Hay, por tanto, considerar una gran parte del árbol.

Cuando se aplica a un árbol minimax estándar, devuelve el mismo movimiento que el regreso minimax, para podar las ramas que no tienen una posible influencia en la decisión final.

Considerando de nuevo el juego trivial de la Figura 19 como ejemplo de las etapas del cálculo de la decisión de la alfa-beta para el árbol de juego.

La primera hoja B tiene valor 3. En consecuencia, B, que es un nodo Min tiene un valor máximo de 3. La segunda hoja 12 en B tiene un valor, MIN evitar que este movimiento, por lo que B se encuentra todavía en la mayoría de 3. La tercera hoja en B tiene un valor 8, por lo que el valor de B es exactamente 3. Ahora, podemos deducir que el valor de la raíz es por lo menos 3, ya que MAX tiene una opción de valor 3 en la raíz,

CONCLUSIÓN

Poda alfa-beta es un algoritmo que limita la profundidad de búsqueda en juego no estocástico donde se conocen las reglas y se dominan las acciones. La compresión de este algoritmo de búsqueda avanzada lleva a un nivel de compresión alto en cuanto a las matemáticas respectas si deseas aplicarlo debes saberles. La clase fue muy didacta en el aspecto de compartir información entre los compañeros de manera espontánea.

REFERENCIAS

Russel,. S; Norvig, P .2010. Artificial Intelligence: A Modern Approach (3 ed.). Prentice Hall. ISBN 978-0-13-604259-4.

McCarthy, J 2006. «Human Level AI Is Harder Than It Seemed in 1955». Retrieved 2006-12-1

Newell, A & Herbert A. 1976.  «Computer Science as Empirical Inquiry: Symbols and Search» (PDF). Communications of the ACM 19 (3). Retrieved 2006-12-21.

Edwards, D & Hart, T. 1963. «The Alpha–beta Heuristic (AIM-030)». Massachusetts Institute of Technology. Retrieved 2006-12-21.

Kotok, A.  2004. «MIT Artificial Intelligence Memo 41». Retrieved 2006-07-01.

Marsland, T. 1987.  «Computer Chess Methods (PDF) from Encyclopedia of Artificial Intelligence. S. Shapiro (editor)» (PDF). J. Wiley & Sons. pp. 159–171. Retrieved2006-12-21.