Reducciones de última hora

La reducción de movimientos tardíos (abreviada como LMR) es una mejora no específica del juego para el algoritmo alfa-beta y sus otras variantes que intenta examinar un árbol de búsqueda de juego de manera más eficiente "podando" nodos malos. Se basa en la suposición de que un buen orden de movimientos específico del juego hace que un programa busque los movimientos más probables (buenos) al principio. Si se va a producir un corte en una búsqueda, los primeros movimientos son los que tienen más probabilidades de provocarlo. En juegos como el ajedrez , la mayoría de los programas buscan primero capturas ganadoras y " movimientos asesinos ". La reducción de movimientos tardíos disminuirá la profundidad de búsqueda para los movimientos buscados más tarde en un nodo dado. Esta heurística permite que el programa busque más profundamente a lo largo de las líneas críticas y juegue mejor. ^{[ 1 ]}

La mayoría de los programas (o motores) de ajedrez suelen analizar en profundidad los primeros uno o dos movimientos . Si la puntuación de los primeros movimientos es inferior a alfa, se considera que el movimiento es malo. Sin embargo, si la puntuación es superior a alfa, la búsqueda reducida no aporta información, por lo que será necesario realizar una búsqueda completa (conocida como búsqueda de fallo por debajo del valor mínimo).

Esta reducción de la búsqueda puede generar un espacio de búsqueda distinto al del método alfa-beta puro, lo que puede dar lugar a resultados diferentes. Es fundamental seleccionar cuidadosamente los criterios de reducción, ya que de lo contrario la búsqueda podría pasar por alto amenazas importantes.

Las reducciones de movimientos tardíos se basan en la idea de que cuanto más arriba esté un movimiento en una lista ordenada, mejor es la probabilidad de que sea. ^{[ 2 ]} Cuando un motor evalúa un nodo , utiliza heurísticas para ordenar los movimientos de manera que las líneas más prometedoras, como las capturas o las sugeridas por la heurística del asesino , se busquen primero. ^{[ 1 ]} Si estos movimientos no producen un corte, se considera que los movimientos posteriores tienen cada vez más probabilidades de ser peores; como resultado, el algoritmo busca estos movimientos "tardíos" a una profundidad menor de la prevista originalmente. ^{[ 3 ]}

• NNUE : una red neuronal que se utiliza para evaluar movimientos (o calcular la "puntuación" aproximada de un movimiento).
• Stockfish (ajedrez) : un popular motor de ajedrez potente que utiliza NNUE como su función de evaluación .
• YaneuraOu : un motor de ajedrez shogi que implementó por primera vez NNUE.

• Introducción a las reducciones por movimientos tardíos