Estoy estudiando IA. Mi maestro nos dio el código fuente de un juego de ajedrez y nos pidió que lo mejoraramos. Mi ejercicio es mejorar la implementación del algoritmo alfa / beta en ese juego. El programador ya usa tablas de transposición, MTD (f) con memoria alfa / beta + (MTD (f) es el mejor algoritmo que conozco hasta ahora). Entonces, ¿hay algún algoritmo mejor para mejorar la búsqueda alfa-beta o una buena manera de implementar MTD (f) en la codificación de un juego?
Contestaré en general, luego más específicamente. Primero, en mi experiencia cuando un profesor pregunta, ¿hay una mejor manera? Inmediatamente voy al libro y busco cosas que el autor señaló como fallas del algoritmo en cuestión. Segundo, miro las optimizaciones que me han ayudado en el pasado.
Para un algoritmo de búsqueda de árbol como alfa-beta, consideraría agregar una heurística que reduzca el número de búsquedas o haga que primero busque en ubicaciones más probables.
Asignaría pesos a los caminos que se pueden tomar en el árbol en función de resultados anteriores. Si un camino ha resultado en una puntuación más alta en el pasado, probablemente sea un buen camino para tomar nuevamente. En resumen, agregue heurística a los caminos y elija seguirlos para que el algoritmo pueda terminar antes.
Tenga en cuenta que realmente no recuerdo mucho sobre el algoritmo específico, solo que es un árbol y el enfoque ingenuo no implica esta heurística.
No mencionaste la poda de movimiento nulo o las reducciones de movimiento tardío. Son bastante fáciles de implementar y son aún más eficaces para reducir el tamaño de búsqueda que la poda alfa-beta. Las extensiones de búsqueda también son importantes para mitigar el efecto horizonte; La búsqueda de reposo en particular es un componente muy importante para una IA de ajedrez.
fuente
Examine el orden de movimiento y la búsqueda de variación de principios
fuente