Algoritmo de Dios
[2] Se refiere a cualquier algoritmo que produzca una solución con la menor cantidad de movimientos posibles, siendo la idea que solo un ser omnisciente conocería un paso óptimo de cualquier configuración dada.
Este recuento se conoce como el número de Dios,[4] o, más formalmente, el valor minimax.
Para su generalización el n- rompecabezas, el problema de encontrar una solución óptima es NP-hard.
[9] Por lo tanto, se desconoce si existe un algoritmo de Dios práctico para este problema, pero parece poco probable.
[12] Por tanto, 20 es un límite superior marcado en la longitud de las soluciones óptimas.
El matemático David Singmaster había "conjeturado precipitadamente" que este número era 20 en 1980.
[13] Sin embargo, algunos juegos bien conocidos con un conjunto muy limitado de reglas y movimientos simples y bien definidos nunca han tenido el algoritmo de Dios para una estrategia ganadora determinada.
Algunos ejemplos son los juegos de mesa ajedrez y go.
[14] Ambos juegos tienen un número de posiciones que aumenta rápidamente con cada movimiento.
Si bien se han construido computadoras de ajedrez que son capaces de vencer incluso a los mejores jugadores humanos, no calculan el juego hasta el final.
[19] Los algoritmos de evaluación son propensos a cometer errores elementales[20] por lo que incluso para una mirada limitada hacia el futuro con el objetivo limitado a encontrar la posición interina más fuerte, un algoritmo de Dios no ha sido posible para el go.
Por otro lado, las damas, con similitudes superficiales con el ajedrez, han sido sospechadas durante mucho tiempo de ser "jugadas" por sus expertos practicantes.
