Efecto horizonte

El efecto horizonte , también conocido como el problema del horizonte , es un problema en inteligencia artificial en el que, en muchos juegos, el número de estados o posiciones posibles es inmenso y las computadoras solo pueden explorar de manera factible una pequeña parte de ellos, generalmente unas pocas jugadas más abajo en el árbol de juego . Por lo tanto, para una computadora que solo explora un número fijo de jugadas, existe la posibilidad de que realice una mala jugada a largo plazo. Las desventajas de la jugada no son "visibles" porque la computadora no explora hasta la profundidad en la que su función de evaluación revela la verdadera evaluación de la línea. La analogía es como observar a distancia en una esfera como la Tierra, pero con una amenaza bajo el horizonte y, por lo tanto, invisible.

Al evaluar un árbol de juego extenso mediante técnicas como minimax con poda alfa-beta , la profundidad de búsqueda se limita por razones de viabilidad. Sin embargo, evaluar un árbol parcial puede dar un resultado engañoso. Cuando se produce un cambio significativo justo más allá del horizonte de búsqueda, el sistema computacional se ve afectado por el efecto horizonte.

En 1973, Hans Berliner denominó a este fenómeno, que él y otros investigadores habían observado, el «Efecto Horizonte». ^{[ 1 ]} Dividió el efecto en dos: el Efecto Horizonte Negativo «que da como resultado la creación de distracciones que retrasan ineficazmente una consecuencia inevitable o hacen que una inalcanzable parezca alcanzable». En cuanto al Efecto Horizonte Positivo, «en gran medida ignorado», «el programa se aferra demasiado pronto a una consecuencia que puede imponerse a un oponente con calma, frecuentemente de una forma más eficaz».

El efecto horizonte puede mitigarse en cierta medida mediante la búsqueda de quiescencia . Esta técnica extiende el esfuerzo y el tiempo dedicados a buscar estados del tablero que quedan en posiciones volátiles y asigna menos esfuerzo a estados del tablero más fáciles de evaluar. Por ejemplo, "puntuar" el valor de una posición de ajedrez a menudo implica un recuento de valor material , pero este recuento es engañoso si hay piezas colgantes o un jaque mate inminente. Un estado del tablero después de que la dama blanca haya capturado un caballo negro protegido parecería ventajoso para las blancas según el recuento material ingenuo, ya que ahora tienen un caballo de ventaja, pero probablemente sea desastroso, ya que la dama será capturada en el intercambio una jugada después. Una búsqueda de quiescencia puede indicarle a un algoritmo de búsqueda que juegue las capturas y los jaques antes de puntuar los nodos hoja con posiciones volátiles.

En ajedrez , supongamos una situación en la que la computadora solo busca en el árbol de juego hasta seis jugadas y, a partir de la posición actual, determina que la dama se pierde en la sexta jugada; y supongamos que hay una jugada en la profundidad de búsqueda en la que puede sacrificar una torre, y la pérdida de la dama se pospone hasta la octava jugada. Esta es, por supuesto, una jugada peor que sacrificar la dama, ya que conlleva la pérdida tanto de la dama como de la torre. Sin embargo, como la pérdida de la dama se pospuso más allá del horizonte de búsqueda, no se descubre ni se evalúa. Perder la torre parece ser mejor que perder la dama, por lo que el sacrificio se devuelve como la mejor opción, mientras que retrasar el sacrificio de la dama, de hecho, ha debilitado aún más la posición de la computadora. Como otro ejemplo, mientras que algunos jaques perpetuos desencadenan rápidamente un empate por repetición triple, otros pueden implicar que una dama persiga a un rey por todo el tablero, variando la posición cada vez, lo que significa que el empate forzado real podría ocurrir muchas jugadas más adelante. Si no se realiza una búsqueda de quiescencia que ejecute las comprobaciones, es posible que la IA no detecte la posibilidad y que el motor cometa el error de convertir una posición ganadora en una de empate.

En Go , el efecto horizonte es una preocupación importante para escribir una IA capaz de jugar incluso a nivel principiante, y parte de la razón por la que la búsqueda alfa-beta fue un enfoque débil para el Go computacional en comparación con los enfoques posteriores de aprendizaje automático y reconocimiento de patrones. Es muy común que ciertas piedras estén "muertas" pero requieran muchos movimientos para capturarlas si se disputan. El efecto horizonte puede hacer que un algoritmo ingenuo evalúe incorrectamente la situación y crea que las piedras se pueden salvar calculando una jugada que aparentemente mantiene vivas las piedras condenadas hasta el movimiento en el que se detiene el árbol de búsqueda. Si bien la muerte del grupo puede retrasarse, no se puede evitar, y disputar esto solo permitirá que se capturen más piedras. Un ejemplo clásico que aprenden los principiantes son las escaleras de Go , pero la misma idea general ocurre incluso en situaciones que no son estrictamente escaleras. ^{[ 2 ]}

• Niebla de guerra
• Tácticas antiinformáticas
• Búsqueda de árboles en Montecarlo

• Russell, Stuart J.; Norvig , Peter (2003), Inteligencia artificial: un enfoque moderno (2.ª  ed.), Upper Saddle River, Nueva Jersey: Prentice Hall, pág.  174, ISBN 0-13-790395-2

• Efecto Horizonte en la Wiki de Programación de Ajedrez (CPW)