En la programación de juegos, ¿cómo puedo probar si una heurística utilizada es consistente o no?

Question

He pensado en algunos heuristics para un juego de tres en raya (mayores dimensiones). ¿Cómo puedo verificar cuáles de ellos son realmente consistente?

¿Qué significa consistencia de todos modos?

Answer 1

EDITADO: Esta respuesta confunde la admisibilidad y la coherencia. Lo he corregido para referirme a la admisibilidad, pero la pregunta original era sobre la coherencia, y esta respuesta no responde completamente a la pregunta.

Puede hacerlo analíticamente, distinguiendo todos los casos diferentes y por lo tanto probando que su heurística es de hecho admisible.

Para la búsqueda informada, una heurística es admisible con un problema de búsqueda (por ejemplo, la búsqueda de la mejor movimiento en un juego) si y sólo si se subestima la 'distancia' a un estado adecuado.

EJEMPLO: Busque la ruta más corta a una ciudad de destino a través de una red de carreteras entre ciudades. Aquí, uno podría usar la distancia Eucideana como heurística: la longitud de una línea recta hacia la meta siempre es más corta o igual de larga que la mejor manera posible.

Se requiere la admisibilidad de algoritmos como A*, que luego lo ponen en cuarentena para que sea óptimo (es decir, encontrarán la mejor "ruta" para un objetivo si existe).

Yo recomendaría buscar el tema en un AI textbook.

Answer 2

Las heurísticas producen algún tipo de valor de costo para un estado determinado. La consistencia en este contexto significa que la estimación de un estado más el costo de pasar al siguiente estado es menor o igual que la estimación para ese nuevo estado. Si esto no fuera cierto, implicaría que, si la heurística era precisa, la transición de un estado al siguiente podría generar un costo negativo, que normalmente es imposible o incorrecto.

Esto es intuitivo para probar cuando se trata de pathfinding, ya que se espera que cada paso del camino tome algo de tiempo, por lo tanto la estimación en el paso 1 debe ser menor que la estimación en cualquier paso 2. Probablemente sea un poco más complejo para tic-tac-toe, ya que probablemente deba decidir arbitrariamente qué constituye un "costo" en su sistema. Si su heurística puede subir o bajar como resultado de jugar un movimiento, ej. porque codifica buenos movimientos con números positivos y movimientos negativos con números negativos, entonces su heurística no puede ser consistente.

Sin embargo, la falta de una heurística consistente no siempre es un problema. Es posible que no tenga garantizado que llegue a una solución óptima sin una, pero aún puede acelerar la búsqueda en comparación con una búsqueda de estado de fuerza bruta.