Juego sin adversario

Métodos Utilizados en Juegos Sin Adversario
Para algoritmos de juegos unipersonales (por ejemplo los puzzles o el solitario) suelen utilizarse los algoritmos más comunes de búsquedaheurística, aunque realmente las soluciones a un juego unipersonal pueden encontrarse con cualquier algoritmo de fuerza bruta sin heurística alguna, siempre y cuando se disponga del tiempo y memorianecesarios.
De entre los algoritmos de búsqueda heurística, suele utilizarse o bien el algoritmo A*, que se describe en esta sección, o bien el algoritmo IDA* (según los recursos del computador). Elalgoritmo A* (Hart, 1968) implementa una búsqueda primero el mejor (best-first). En otras palabras, se basa en intentar encontrar todos los movimientos necesarios para llegar del estado inicial alestado final, usando preferiblemente aquellos movimientos que sean más favorables.
Así, entre otras cosas, se puede lograr minimizar los pasos de la solución, o el tiempo de cálculo.
Paraconocer qué movimiento es mejor se utiliza una función de evaluación estática formada descompuesta como:
f = g + h
Donde “f” será el valor numérico del movimiento estudiado, la función “g” es unafunción del coste de llegar del estado inicial al estado actual, y la función “h” es una estimación del coste de llegar desde el estado actual al estado final o objetivo. Lógicamente, “h” es unaestimación porque no conocemos a priori el camino exacto hacia la solución. El algoritmo A*, simplificado y con sintaxis imprecisa, viene a ser el siguiente:
Algoritmo A*Estados_pendientes.insertar(Estado_inicial);
Actual = Estados_pendientes.primero();
Mientras(no_es_final(Actual) y (no Estados_pendientes.vacio)) hacer
Estados_pendientes.borrar_primero();Estados_ya_estudiados.insertar(Actual);
Sig_movimientos = generar_sucesores(Actual);
Sig_movimientos = eliminar_repetidos(Sig_movimientos,
Estados_ya_estudiados,
Estados_pendientes);...