En esta página se tratan los aspectos lógicos y computacionales
de este tipo de juegos con especial hincapié en el juego de Damas.
Se tocan temas como el de la inteligencia artificial aplicada en este entorno,
algoritmos más usuales, etc.
Desde los principios de la computación el ser humano ha pretendido imitar su propio pensamiento, elucubrando que algunas de sus funciones podrían ser imitadas por las maquinas al igual que los aviones imitan el vuelo de las aves.
En muchos casos se ha llegado más lejos, surgiendo incluso teorías psicológicas que toman como modelo el computador para encontrar analogías con la mente humano, comparando procesos e intentando sistematizar éstos.
Los juegos-ciencia, por tener información completa de inicio (llamados de suma cero) son idoneos para la busqueda de caminos en un sistema complejo, pudiendo despues aplicar lo descubierto a otros campos de la computación o de la ciencia en general.
El primer juego que se intento computerizar y para el que se desarrollo un programa fue precisamente el juego de Damas. Posteriormente otros juegos fueron tratados en este aspecto, llegando al momento actual en que es el ajedrez el mas estudiado y al que mayores esfuerzos se dedican en pos de la consecución del jugador perfecto.
Los avances en algoritmica para el juego, busquedas, evaluaciones, etc..., unido al incremento progresivo de la potencia de las maquinas harán practicamente imposible que un ser humano juegue mejor a cualquier juego-ciencia que una maquina, a lo más tardar el año 2010.
Pero , ¿ como juegan estos programas ?, ¿ como indagan en la busqueda de la jugada adecuada ?. A estas y otras preguntas procuraremos contestar aquí, dando una explicación a grandes rasgos de cómo ésto es posible.
Las tecnicas y algoritmos que se usan para todos los juegos-ciencia son basicamente los mismos, cambiando solo alguna particularidad del juego tratado, como la generación de jugadas,etc. Por todo ello, lo aquí comentado es válido para las damas, el ajedrez, go, etc.
Existen dos modos o estrategias basicos de atacar este problema :
1) Estrategia A o de fuerza bruta
2) Estrategia B o selectiva.
En la Estrategia A se procura ver todo lo que pueda hacer cualquier jugador y todas las contestaciones posibles del contrario, asi hasta que la explosión combinatoria, el limite de jugadas o de tiempo hagan finalizar esta exploración, que contestará con el mejor resultado encontrado hasta ese momento.
La Estrategia B no mira todas las jugadas posibles, sino que selecciona por determinados criterios algunas de ellas y asi prosigue hasta el final de la exploración, que se habrá determinado por motivos parecidos al anterior caso.
La Estrategia A tiene el inconveniente de que en esta clase de juegos es tal la cantidad de jugadas posibles, que la explosión combinatoria hace imposible ver a muchas jugadas vista, mientras que la segunda estrategia tiene el inconveniente de poder eliminar algunas de las continuaciones, que posteriormente pudiesen ser buenas.
Hasta el momento ninguna estrategia ha demostrado una superioridad clara sobre la otra y en general los programas suelen ser de uno de estos tipos, aunque existen algunos con mezcla de estas dos visiones del juego.
Para empezar a planear um programa de este tipo se debe tener muy en cuenta todas las características con que queremos dotarlo, pues las modificaciones profundas y sobre la marcha no suelen dar buenos resultados.
A grandes rasgos se deben proceder a construir algoritmos para :
Cuando se vuelve un movimiento se va a un ply (media jugada) anterior y por lo tanto al turno del contrario; en estos momentos de debe comparar el valor mejor que tiene hasta esos momentos con el valor que le devuelve la última busqueda, aceptando el mejor de los dos.
Como ya se ha señalado, la generación de movimientos es distinta para cada juego, debiendo adaptarse a sus caracteristicas particulares; como curiosidad decir que los movimientos del juego de Damas son de los más difíciles de generar mediante un algoritmo; practicamente solo ésto es un ejercicio de programación de primer nivel; se han dado casos de programadores que han estado meses intentando generar estos movimientos.
En comparación de esto, el generar los movimientos posibles del ajedrez en una posición cualquiera es una labor verdaderamente muy sencilla; lo mas dificil del ajedrez es la evaluación correcta de posiciones y la cantidad de excepciones que tiene dicho juego a la hora de considerar una posición.
La única regla general para hacer la programación de la generación de movimientos es la comprensión adecuada de las reglas y el no desfallecer en la labor. Es normal que ni siquiera viendo el código escrito por otro programador en cualquier lenguaje, podamos descifrar el como ha hecho la generación.
El principio minimax implica el que en una posición dada y una vez valorados sus nodos o ramas posibles, elijamos la mas conveniente a nuestros intereses o de mayor puntuación, desechando las otras. Si asumimos que para un jugador la puntuación mejor es positiva y para el oponente la negativa, tendremos que uno elegirá como mejor la puntuación maxima y el otro la mínima, de donde procede el nombre de minimax.
La poda alfa-beta es una mejora al método minimax, que nos indica que si en una posición hemos encontrado una jugada mejor que la que el contrario ya tiene en un ply anterior como mejor, podemos dejar de investigar todas estas ramas, pues por muy buena que encontremos una jugada, el contrario no la aceptará al llegar al ply en que es optativa suya, con lo que perderíamos el tiempo en estas búsquedas. Este método puede reducir a la décima parte el número de posiciones que es necesario ver en cualquier búsqueda.
Las tablas de transposición es otra mejora a los métodos de búsqueda, que consiste en crear tablas o posiciones de memoria, en las que es posible introducir unos datos a los que se accede por medio de una clave con la que se identifica a cada tablero. Estos datos nos dirian la valoración de esa posición si ya la hubiesemos visto antes, con lo que no seria necesario efectuar otra vez la busqueda. El peligro de estas tablas son las colisiones o claves repetidas. Para su solución se aplican variados métodos que se indicarán en otra ocasión.
La evaluación de posiciones también es particular de cada juego y de ella depende mucho la calidad del resultado final. No se conocen todas las claves de una posición, pero desde luego para las damas es necesario contar el material, la calidad de éste, el dominio del centro, las estructuras de peones y los peones pasados o las posibilidades de éstos.
Existe un peligro en la evaluación estatica de una posición en el juego de Damas, pues al igual que el ajedrez tiene muchas excepciones y una posición que parece muy buena puede tener una combinación del contrario que gane el juego o que le deje en mejor situación; esto ocurre con mucha frecuencia.
Debemos tambien decidir entre indagar en profundidad o en anchura. En la primera vemos hasta el limite de plys señalados y volvemos hacia atras la búsqueda hasta una jugada no realizada, lo que se ejecuta hasta el final del campo de exploración.
La busqueda en anchura ver ply a ply todas las jugadas posibles, evaluándolas y no pasando al siguiente ply hasta que no ha encontrado la mejor en el anterior.
Aunque pueda parecer que esta segunda opción pueda calcular muchas veces la misma posición, en la realidad tiene tiempos de busqueda parecidos a la primera, por la colocación de las jugadas en cada ply y el recurso de hacer "primero la mejor".
La búsqueda en anchura es seguida por la mayoria de los programas de juego, pues también es idonea para el juego a tiempo determinado, tras el cual se finaliza la busqueda y se da como buena la mejor encontrada hasta el momento.
La búsqueda en profundidad es mas rapida si podemos encontrar las mejores opciones en los primeros lugares de busqueda, pues de lo contrario puede dar tiempos largos.
Para mejorar el juego y el tiempo de reflexión de un programa
se pueden introducir aperturas con el fin jugar las mejores de manera inmediata
y no perder tiempo en ellas y finales, para que si la evaluación
llega a ver que está en un final conocido, aplique el valor de este
final a la posición y termine la busqueda.