Poda alfa-beta

La poda alfa beta es una técnica de búsqueda que reduce el número de nodos evaluados en un árbol de juego por el algoritmo Minimax. Se trata de una técnica muy utilizada en programas de juegos entre adversarios como el ajedrez, el tres en raya o el Go.

Entre los pioneros en el uso de esta técnica encontramos a Arthur Samuel, D.J Edwards y T.P. Hart,^[1]​ Alan Kotok,^[2]​ Alexander Brudno,^[3]​ Donald Knuth y Ronald W. Moore^[4]​

El problema de la búsqueda 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 eliminar partes grandes del árbol, aplicándolo a un árbol Minimax estándar, de forma que se devuelva el mismo movimiento que devolvería este, gracias a que la poda de dichas ramas no influye en la decisión final.

1. ↑ Richards, D.J. and Hart, T.P. (4 de diciembre de 1961 to 28 October 1963). «The Alpha-Beta Heuristic (AIM-030)». Massachusetts Institute of Technology. Consultado el 21 de diciembre de 2006. 
2. ↑ Kotok, Alan (XHTML 3 December 2004). «MIT Artificial Intelligence Memo 41». Consultado el 1 de julio de 2006. 
3. ↑ Marsland, T.A. (mayo de 1987). «Computer Chess Methods (PDF) from Encyclopedia of Artificial Intelligence. S. Shapiro (editor)» (PDF). J. Wiley & Sons. pp. 159-171. Archivado desde el original el 30 de octubre de 2008. Consultado el 21 de diciembre de 2006. 
4. ↑ Knuth, D. E., and Moore, R. W. (1975). «An Analysis of Alpha-Beta Pruning». Artificial Intelligence Vol. 6, No. 4: 293-326.