Dead Channel

Definición: Entenderemos como juegos de tablero todos lo juegos que normalmente podemos encontrar en una juguetería bajo el cartel de “juegos de mesa” o “juegos en familia”. Son juegos de varios jugadores, por turnos, basados en mayor o menor medida en la inteligencia o habilidad de los jugadores y en el azar. Dado que la mecánica es prácticamente la misma, podemos incluir aquí los juegos de estrategia por turnos, como Worms, Incubation o Panzer General.

Jugabilidad:

Los juegos de tablero basan su éxito en la competición y en la interacción humana. Por tanto el jugador siempre disfrutará mucho más si puede estar en contacto directo o en comunicación con los demás jugadores. En algunos casos podemos disfrutar del reto intelectual jugando contra el ordenador, esto ocurre mucho más con algunos juegos de estrategia por turnos (ajedrez, Civilization, go, risk).

A la hora de implementarlos, los objetivos y la forma de conseguirlos suelen ser muy claros (conseguir todos los trozos del pastel de colores, matar al rey, comerse todas las damas del contrario…) Los gráficos no tienen que ser nada del otro mundo, el sonido no es más que un extra en muchos casos, así que si no eres un artista pero si un programador con ganas de currar, elige uno y manos a la obra.

Lo bueno de este tipo de juegos es que su tiempo de vida es potencialmente infinito, ya que, con muy pocos recursos, cada partida será distinta (sobre todo en multijugador) y el jugador/es puede estar toda la vida jugándolo sin aburrirse.

Sigue leyendo:

Dificultades técnicas:

A la hora de implementar un juego de estrategia por turnos nos enfrentaremos a dos problemas principales:
- Implementar el modo multijugador.
- Para el modo de un jugador necesitamos programar una IA, dependiendo del juego esta puede ser un duro trabajo.

Veamos estos dos puntos algo más en profundidad:

- Modo multijugador: Al ser un modo de juego por turnos podemos jugar o bien todos en el mismo ordenador (nos ahorramos el cliente servidor, pero limitamos el juego) o bien en distintos ordenadores. Para este último caso no necesitamos tiempo real, sincronía, ni nada de eso. El juego funcionará con intercambio de mensajes de forma asíncrona y un pequeño control por si se pierde o se retrasan mensajes. Para esto lo más cómodo es implementar una interface cliente-servidor con sockets:

- El servidor crea la partida y espera los clientes.
- Cada cliente se conecta al servidor mediante su IP y el socket elegido.
- En cada turno el servidor cede el control a un cliente y manda la orden de bloquear la interface a todos los demás. El jugador que tiene el turno hará el(/los) movimientos que crea necesario y cuando su turno termine se enviará un paquete al servidor con los cambios producidos.
- El servidor enviará los cambios a los demás jugadores y cederá el turno al siguiente.

Este sería el esquema básico, por supuesto los paquetes deben tener una estructura interna, se pueden implementar funciones para controlar la correctitud de los movimientos en el servidor además de en los clientes, así como que todos los jugadores tienen el mismo estado de juego en pantalla…

Si pensamos en el ajedrez todo se verá muy sencillo: Juegan blancas, mueve una ficha, mandamos la información al server que a su vez la manda al otro jugador y cambia el turno. Con más jugadores y sistemas más complicados tendremos que manejar más información, pero el esquema básico no varía.

- Implementación de una IA:

Este es un tema bastante más extenso y complejo, así que lo acotaré un poco para hoy, voy a repasar un poco los elementos a tener en cuenta y las herramientas de IA que podrían servirnos y luego voy a hablar un poco de como programar la IA en un grupo concreto de estos juegos.

Dependiendo del tipo de juego la IA y las posibles técnicas a aplica varían en gran medida, podemos tener que controlar muchos aspectos o mecánicas del juego: planificación a largo plazo, tácticas de juego, jugadas comunes, reconocimiento de patrones, gestión de recursos, diplomacia, etc. Las técnicas para atacar estos problemas también pueden ser variadas:

• Estrategia o conjunto de movimientos preestablecidos a corto plazo (como salidas importantes en ajedrez, o como organizar los 3 primeros minutos de Starcraft, que todos sabemos que siempre es igual :P)
• Diagrama de estados para definir la actitud de la IA (agresiva, defensiva, diplomática, dependiendo de la situación en la que se encuentre con respecto a los demás, en Civilization eran tan nobles….)
• Sistema de conocimiento o sistema experto: este diseño se basa en crear una gran base de datos de acción-respuesta, es decir, conocimientos sobre el juego en concreto y cómo responder a cada situación. Básicamente tratamos de meter toda la información y las reglas que un jugador experto consideraría en cada momento. No sé de ningún ejemplo de esto, pero seguro que esto se ha aplicado en mayor o menor medida en más de un juego.
• Árbol de decisiones y funciones heurísticas de valoración de las ramas. De este es del que hablaré ahora después.
• Utilización de Redes Neuronales o Algoritmia evolutiva. Este es el campo más experimental de la IA, debemos tener claro que de verdad puede ser útil y que el entrenamiento debe realizarse a priori, para añadir a la IA del juego una red o un individuo ya evolucionado. Estas técnicas se utilizan sobre todo en optimización y clustering.

Normalmente no utilizaremos una sola de éstas técnicas, sino varias, para cada una en distintos aspectos o distintas fases de juego, o incluso técnicas mixtas (un arbol de decisión que utiliza una base de conocimiento para ajustar la heurística es lo que usan programas como DeepBlue).

Vamos a centrarnos en el caso de los juegos más sencillos, y además la técnica más útil, o que más aplicaciones tiene: Los árboles de decisión son árboles N-arios en los que cada rama será un posible movimiento (movimientos posibles son aquellos que cumplen todas las reglas, esto debe ser controlado mediante código, claro está) en la siguiente jugada. Se utilizan sobre todo en los juegos bipersonales de suma cero (lo que yo pierdo lo gana el otro). Y en cada nivel del árbol mueve un jugador. Por ejemplo: el juego de las tres en raya.

- De la raíz del árbol partirán 3 ramas: mover a la esquina, mover al centro, mover a un lateral.
- Ahora cada nodo de los obtenidos será la raíz para los posibles movimientos del otro jugador. Así hasta completar todas las posibilidades o alcanzar un nivel máximo o límite de exploración, escogido de forma arbitraria.
- Si hemos alcanzado el final del juego en las hojas del árbol tendremos el resultado y por tanto podremos valorar con 1 las ramas en las que ganamos, con 0 en las que empatamos y con -1 en las que perdemos y elegir en consecuencia. Pero normalmente esto no es posible por limitaciones de espacio y tiempo, con lo que tendremos que inventarnos una función heurística (heurística quiere decir arbitraria y basada en conocimientos humanos) que nos diga cómo de buena es cada hoja. Cada nodo raíz será tan bueno como el peor de sus hojas si es un nodo en el que movemos nosotros (porque suponemos que el contrario moverá bien) y la mejor si mueve el contrario (el también tratará de conseguir lo mejor) Y así ya tenemos una valoración de todo el árbol, con lo que podremos escoger la rama más favorable.

((!) Si en cada movimiento puede intervenir el azar, deberemos ponderar cada rama con la probabilidad de que sea escogida)

Esto, que así explicado no sé si habrá quedado muy claro, es el algoritmo MiniMax. (Luego vendrán los links ;)) Este árbol puede generarse en amplitud, como yo lo he explicado, o en profundidad, en cuyo caso expandimos las ramas de una en una hasta el final, para luego seguir con la siguiente. Esta forma de expandir el árbol consigue que cuando vamos a por la segunda rama ya tenemos los valores de la primera calculados, si los valores de la segunda parece que serán peores (necesitamos otra heurística: la función de estimación, que nos estima el máximo y el mínimo que podremos conseguir con ese movimiento, sin saber los siguientes) podemos no expandir esa rama y pasar a la siguiente. Este procedimiento se conoce como ramificación y poda, o poda alfa-beta. Con unas adecuadas funciones heurísticas, y unos cuantos niveles de anticipación (niveles hasta llegar al limite de exploración) este algoritmo puede obtener muy buenos resultados para la mayoría de juegos de dos jugadores, sin azar y suma cero (excluyendo el go), lo que es más de lo que parece ;P

La técnica de ramificación y poda también puede utilizarse en otros muchos casos, sobre todo de optimización y exploración de soluciones, y es una técnica ampliamente extendida en diseño de algoritmos.

No me extiendo más, para ruegos y preguntas podéis comentar, tanto en el foro de Stratos (AQUÍ) como en el blog. Espero vuestros comentarios y opinión, así como matizaciones, correcciones o ampliaciones. Y ahora algunos enlaces con más información para el que quiera ampliar:

En la wikipedia: (enlazo los artículos ingleses porque son más completos y traen los algoritmos, quien quiera puede cambiar a español sin esfuerzo)
Algoritmo Minimax.
Ramificación y poda (Branch and bound)
Implementación de juegos de ajedrez.

Comunidad de IA en videojuegos, en classic games tenéis una gran cantidad de juegos de tablero.
IAchess4k, un ejemplo de juego de ajedrez en 4k, con tres niveles de IA, se puede ver como el programador ha usado un algoritmo minimax con mayor nivel límite para cada nivel de de dificultad (en el nivel 3 os esperan tiempos de decisión bastante largos).