Creando Tak en Rust — Parte 1

Este artículo es el primero de una serie de ellos acerca del proyecto “Creando Tak en Rust”. En él, se presenta el proyecto general y se detalla el proceso de desarrollo del simulador inicial de Tak en forma de una herramienta de terminal.

El proyecto creado se puede encontrar en el siguiente enlace de GitHub.

¿Qué es el Tak?

El Tak es un juego de mesa que tiene su origen en la novela de Patrick Rothfuss, El temor de un hombre sabio. Este juego fue traído a la realidad por el gran James Ernest en colaboración con el autor y consiste en un juego de mesa abstracto para dos jugadores en el que el objetivo principal es crear un camino que conecte dos lados opuestos del tablero.

Imagen 1: Un tablero de Tak y sus piezas

El tablero está formado por casillas distribuidas en forma cuadrada. El tamaño es variable pero los más habituales suelen ser de 5x5 o 6x6 casillas. De hecho, como se puede ver en la imagen anterior, la comunidad suele crear tableros que presentan los 2 tamaños a la vez.

Un jugador en su turno, puede hacer dos tipos de acciones: Colocar una pieza en una casilla libre del tablero o Mover una pieza ya existente.

En Tak, las piezas se llaman “piedras” y me parecen de lo más elegante del juego. Estas están diseñadas para poder jugarse en distintas posiciones, de manera que al jugar una piedra tumbada es un “camino” y si por el contrario se juega de pie, es una “pared”. Esta característica hace que las piedras sean apilables entre sí, añadiendo una tercera dimensión al juego. Sin embargo, el tercer tipo de piedra, la “piedra angular”, no permite que se le apilen otras piedras encima.

Imagen 2: Tablero de Tak con las piezas sobre él

Reglas

Una vez explicados los componentes podemos proceder a explicar las reglas de manera superficial. Para una explicación más extensa de las reglas se puede visitar el siguiente enlace.

Lo primero que debemos tener en cuenta es que en Tak, no se puede colocar una piedra directamente sobre una casilla ya ocupada. Sin embargo, sí se puede mover una piedra ya presente en el tablero en una de las 4 direcciones ortogonales (Norte, Sur, Este y Oeste) incluso apilándola encima de otras en base a las siguientes reglas:

• Si en la casilla objetivo hay un camino como piedra superior, se puede apilar cualquier piedra encima.
• Si en la casilla objetivo hay una pared como piedra superior, solo se puede apilar una piedra angular encima. No importa de que jugador sea cada piedra y la pared se tumbará convirtiéndose en un camino.
• No se puede apilar nada encima de una piedra angular.

Como en una casilla puede haber varias piedras apiladas, la piedra superior determina el jugador que controla esa casilla. Este jugador puede realizar un movimiento con cualquier numero de piedras de la pila siempre y cuando no mueva más piedras que la longitud del lado del tablero. Por ejemplo, si se juega en un tablero de 5x5, los jugadores podrán mover como mucho 5 piedras al mismo tiempo.

Además, si un jugador decide mover una pila de piedras, una vez decide la dirección del movimiento, puede moverse tantas casillas como quiera siempre y cuando vaya soltando la piedra más baja de la pila en cada casilla. A continuación un par de ejemplos.

Imagen 3: Movimiento multi-casilla válido visto lateralmente

En la imagen anterior se puede observar como, con 4 piedras se puede hacer un movimiento de 4 casillas soltando la más baja en cada una. El movimiento puede ir en una dirección ortogonal tantas casillas como se quiera por lo que se podría parar antes. Cabe descacar que en un movimiento de varias casillas, cada colocación de piedras debe ser legal. La siguiente imagen muestra un movimiento de varias casillas ilegal.

Imagen 4: Movimiento multi-casilla inválido visto lateralmente

En la imagen anterior, el movimiento es ilegal porque al dejar la penúltima piedra, que es un camino, este iría encima de una pared y no es posible. Este movimiento solo sería posible si la piedra que cayese encima de una pared fuese una piedra angular, como se puede ver a continuación.

Imagen 5: Movimiento multi-casilla válido con una piedra angular sobre una pared

El movimiento anterior aprovecha las piedras inferiores para conseguir llegar a posicionar la piedra angular sobre una pared, “rompiéndola” así y convirtiéndola en un camino.

Finalmente, el juego se termina al cumplir una de 3 condiciones:

• Un jugador hace un camino que conecte dos lados opuestos del tablero
• Un jugador se queda sin piedras que colocar
• En un momento dado no hay espacios libres donde colocar piedras en el tablero

Dependiendo de como termine la partida, el ganador se determina de una u otra forma. Para empezar, si un jugador construyó un camino que conecta dos lados opuestos del tablero gana. Esta conexión solo tiene en cuenta casillas ortogonalmente adyacentes en las que la piedra superior es un camino o una piedra angular, las paredes cortan un camino sin importar su dueño. En caso de que no haya un camino válido, el ganador es el jugador que controla el mayor número de casillas sin contar las que tienen paredes. Finalmente, si un jugador, con un mismo movimiento crea un camino ganador para él y su oponente, el ganador será quien hizo el movimiento.

Ah! Casi se me olvida! en un juego cortés de Tak, cuando un jugador está a un movimiento de hacer un camino ganador, debe avisar al oponente diciendo “Tak”.

Motivación del proyecto

Como siempre en mis artículos, me gusta resaltar las razones o motivos que me llevan a escoger un proyecto. En este caso, yo estaba aprendiendo Rust a través de un curso de Udemy y me pareció muy buen lenguaje de programación (Probablemente mi nuevo favorito). En la misma época, un amigo me mandó un video de @ModernRogue acerca del Tak y me gustó tanto que pensé, “Que buena pinta tiene este juego! Me gustaría analizarlo más en profundidad”. Mi cabeza unió ambas cosas y de ahí nació este proyecto.

Después de madurarlo durante unos días, definí una serie de objetivos básicos y empecé a trabajar:

• Aprender Rust: Casi mi objetivo principal era afianzar mis conocimientos en Rust llevando a cabo un proyecto propio. No existe mejor manera de aprender.
• Obtener un Tak digital: La clave estaba no solo en crear una herramienta que permitiese jugar al Tak entre jugadores sino en también crear una IA contra la que jugar, ya que no encontré nada por el estilo actualmente.
• Analizar las mecánicas: Soportando jugadores de IA, ponerlos a jugar con distintas estrategias entre ellos no sería demasiado complicado y me podría ayudar a obtener algunas estadísticas acerca de qué técnicas resultan mejores en este juego.

Como el alcance de este proyecto puede ser todo lo grande que se quiera, he decidido dividirlo en varios artículos a lo largo del desarrollo. De esta forma será más sencillo de explicar y me parece que cada uno quedará menos denso. Así, en cada artículo explicaré las nuevas metas que he fijado para esa iteración, las lecciones que he aprendido durante el desarrollo y los puntos más destacables.

Me gustaría destacar que, por paradójico que suene, todavía no he jugado ni una sola partida al Tak. Tengo muchas ganas, sin duda, pero este proyecto atrapó mi atención tanto que todavía no he tenido tiempo a probarlo. Lo que si he descubierto es que, en la comunidad de Tak, muchos aficionados se crean sus propios tableros de distintos materiales por lo que me gusta pensar que yo estoy haciendo lo mismo, la diferencia es que yo no lo estoy construyendo en formato físico (todavía).

Desarrollo del Simulador

Esta es la primera fase del desarrollo de este proyecto. Por ello, este artículo se centrará en la creación de la herramienta básica. El producto final de esta iteración será una herramienta en terminal que:

• Permite el juego en local entre dos jugadores
• Implementa una IA completamente aleatoria
• Permite a un jugador jugar contra la IA
• Permite simular una partida entre dos IAs

Arquitectura General

Imagen 6: Diagrama de clases y paquetes del proyecto en su fase actual

En la imagen anterior se presenta el diagrama general de clases y paquetes del proyecto. Aunque este diagrama no es exhaustivo para no complicarlo demasiado, en él se puede ver que existen diversos paquetes (“crates” en Rust) y como interactúan entre ellos. A continuación se detalla cada parte.

Tak Errors

Este paquete se encarga de la gestión de errores de todo el proyecto. En su estado actual contiene básicamente un Enum con los distintos tipos de error que se pueden dar durante la ejecución del programa y sus mensajes asociados. Es utilizado a lo largo de todo el proyecto.

CLI

Este paquete se encarga de todo lo relacionado con la entrada/salida por terminal. La clase CLI está implementada siguiendo un patrón Singleton de manera en que exista siempre una sola instancia en todo el proyecto y brinda funcionalidades como obtener entradas del usuario y mostrar mensajes en la terminal como el estado actual del tablero. Su utilidad principal es agrupar todas estas operaciones en un solo sitio para un mejor mantenimiento.

Adicionalmente, existe el Enum CLICommand que traduce y estandariza las entradas introducidas por el usuario de manera que sean más deterministas y sencillas de manejar.

Game

Este paquete gestiona las partidas en sí. La clase principal es Game y su utilidad se centra en crear la partida deseada y los componentes necesarios para llevarla a cabo. Se comporta como una especie de controlador ya que gestiona los turnos y llama a las otras clases en cada situación. Tiene dos métodos principales que serían el de play_turn() y get_game_result(). La idea es llamar estos métodos desde fuera de manera que, después de jugar cada turno con play_turn() , se compruebe el estado de la partida con get_game_result().

Aparte de la clase Game, existen GameMode y GameResult que son Enums auxiliares para gestionar el tipo de partida y sus resultados.

Board

Este paquete gestiona todo lo relacionado con el tablero y las piedras en el Tak. Su clase principal es Board y su utilidad es crear un tablero con todas las casillas necesarias de acuerdo con las dimensiones deseadas. Además implementa métodos para colocar y mover piedras en el tablero.

Cada casilla del tablero se encuentra representada por la clase Tile, que contiene una pila de posibles piedras. Estas últimas, a su vez, están representadas por el Enum Stone y guardan información acerca del dueño de cada una.

Finalmente, las clases relacionadas con el movimiento en el tablero son Direction y Movement. La primera consiste en un Enum que simplemente define las 4 direcciones posibles. La segunda define cualquier tipo de movimiento en el tablero, tanto colocación como movimiento de piedras.

Player

Este paquete gestiona todo lo relacionado con los jugadores. Su clase principal es PlayerManager y su utilidad es crear a los jugadores según el tipo de partida que se va a jugar. Como ya se mencionó anteriormente, hay 3 tipos de partida distintos: Jugador contra Jugador, Jugador contra IA e IA contra IA.

La clase Player contiene toda la información referente a un jugador como su Id en la partida (Jugador 1 o 2), su numero actual de piedras, etc. Además, si un jugador es IA, tiene un algoritmo asociado que utilizará para tomar decisiones en cada momento. En caso contrario, si un jugador es humano, en lugar de utilizar un algoritmo de IA se utiliza el paquete CLI para que el jugador decida su acción a través de la terminal.

Con respecto a los algoritmos de IA, están recogidos en un sub-paquete del paquete Player llamado AI. Este contiene una interfaz (Trait en Rust) que los algoritmos concretos deben implementar. La función de esta interfaz es generate_move() y, como se adelanto antes, sirve para generar un movimiento. Dentro de este paquete, cada algoritmo proporciona un objeto estático al que llamar. Actualmente el único implementado es RandomAI que simplemente obtiene la lista de movimientos posibles en un momento dado y selecciona uno al azar.

Main

La clase principal del proyecto se encarga de interpretar los argumentos de línea de comandos para luego comenzar una partida con las opciones escogidas. Una vez creada la partida, entra en un bucle en el que se van jugando turnos hasta que la partida termina.

Retos y Fortalezas en Rust

Como ya se mencionó anteriormente, uno de los objetivos era aprender Rust, por eso este proyecto está implementado con ese lenguaje de programación. Al ser el primer proyecto de un tamaño decente que he llevado a cabo en Rust, se han encontrado muchos retos y algunas genialidades de este lenguaje que me gustaría compartir.

Ownership y Referencias

La característica más diferenciativa de Rust es su sistema de ownership. Todo valor tiene un solo dueño (una variable). Las variables tienen un alcance definido y, una vez ese alcance termina se libera la memoria, de esta forma no es necesario contar con un recolector de basura como en el caso de Java.

let string1 = String::from("Hello");    //Variable string1 owns the String Value "Hello"
let string2 = string1;      //Ownership of value "Hello" moves from variable string1 to string2

println!("{}", string1);     //This is not valid since string1 doesn't own any value
//At the end of string2's scope, "Hello" value gets dropped and memory is released

En el ejemplo de código anterior, se puede observar cómo cada valor puede tener un solo dueño. Cuando se hace la asignación string2 = string1; el dueño del valor pasa a ser string2 y por lo tanto, no se puede seguir usando string1 ya que no es dueño de ningún valor. Esto se conoce como un move en Rust. Al terminar el trozo de código, string1 no tiene ningún valor asociado pero string2 sí por lo que, al terminarse su alcance, se libera la memoria correspondiente.

Esta característica aplica a todo Rust. Incluso al pasar un valor como argumento a una función, el dueño de ese valor cambia por lo que, al terminar la función, la memoria asociada se libera y ya no puede ser utilizado fuera de la función. Esto tiene muchas ventajas como evitar accesos a memoria inválidos o la verificación en tiempo de compilación. Sin embargo, cambia de manera significativa la forma de programar y de estructurar el código. De hecho, si fuese el único mecanismo de Rust para gestionar la memoria, sería un gran limitante para el lenguaje, pero para eso están las Referencias.

El concepto de Referencias y Préstamos en Rust puede parecer bastante similar a otros lenguajes como C pero tiene sus particularidades. Lo que permiten las referencias es acceder a un valor sin ser su dueño. Estas pueden ser Mutables o Inmutables en función de si pueden modificar el valor o solo leerlo. Rust permite tener, a la vez, cualquier número de referencias inmutables o solo una mutable. Estas reglas de préstamo ayudarían, entre otras cosas, a que no existan condiciones de carrera crítica. Por ejemplo:

let mut string1 = String::from("Hello");
let s1 = &string1;  //Inmutable reference to string1
let s2 = &mut string1;  //Mutable reference to string1. Not allowed

s2.trim();  //Modify string1 through reference
println!("{}",s1);  //Try to print string1 through reference

El ejemplo anterior muestra un código que Rust no compilaría debido a tener referencias mutables e inmutables a la vez. Sin embargo, sirve para ejemplificar por qué esta situación no sería deseable. Suponiendo que este código se ejecutase en paralelo, al haber una referencia mutable y una inmutable se pueden dar casos de carreras críticas. Por ejemplo, si la inmutable intenta imprimir el valor mientras la mutable la modifica.

En el proyecto, esto supuso una limitación ya que, como se puede observar en el diagrama de clases expuesto anteriormente, la instancia de la clase Board debe estar presente para varias clases. La clase Game la necesita para leer y modificar el tablero mientras que la clase PlayerManager la necesita para que los jugadores puedan ver el estado del tablero en cada momento.

Para solucionar esta situación de la manera más sencilla posible se hizo uso de las clases Rc y RefCell. Estas clases permiten flexibilizar el sistema de Ownership y Referencias de la siguiente forma:

La clase Rc (Reference Counting) lleva un contador interno para saber cuantas referencias existen a un valor. Libera el valor cuando este contador llega a cero, como si se tratase de un recolector de basura simple y para un valor específico. Esta clase se suele utilizar en escenarios en que varias partes del código necesitan acceder al mismo dato y no es posible saber en tiempo de compilación cual será la última en utilizarlo. Sin embargo, este préstamo solo puede ser inmutable.

La clase RefCell permite el préstamo mutable en tiempo de ejecución en lugar de hacerlo durante la compilación. Esto significa que se rompen las reglas estáticas de Rust pero se verifica en tiempo de ejecución que no haya violaciones y, en caso de haberlas, se termina el programa con un error. Se suele utilizar en combinación con Rc de manera que este último permite compartir el RefCell y el RefCell permite modificar el valor incluso con múltiples referencias.

use std::rc::Rc;
use std::cell::RefCell;

let dato = Rc::new(RefCell::new(42));

let ref1 = Rc::clone(&dato);
let ref2 = Rc::clone(&dato);

*ref1.borrow_mut() += 10; // Modify through ref1
println!("Valor: {}", *ref2.borrow()); // Print through ref2

Cabe destacar que todo esto solo funciona en programas de un solo hilo. Probablemente era posible una solución sin recurrir a estas clases mediante la especificación de lifetimes. Sin embargo, como siempre hay espacio de mejora, se implementó primero de esta forma teniendo en mente la posibilidad de cambiarla en caso de que fuese demasiado costosa computacionalmente.

Enums, Options y Results

Durante el aprendizaje de Rust, se han descubierto algunas clases que son de gran utilidad y que presentan muchas facilidades y soluciones a problemas de programación habituales. Se trata de clases básicas pero precisamente debido a eso, son todavía más útiles ya que se pueden aplicar a un sinfín de casos.

La primera de estas clases son los Enum. Los Enum no tienen ningún misterio, existen de una forma u otra en casi todos los lenguajes de programación y solucionan un problema habitual, tener una lista fija de posibles valores de manera más o menos auto-explicativa. La razón que diferencia a los Enums de Rust del resto de lenguajes es su posibilidad de llevar datos asociados. Esto les aporta todavía más versatilidad pudiendo guardar en conjunto, no solo la variante de valor dentro de la lista sino también valores asociados de distintos tipos. El tipo de datos asociados a un Enum puede ser distinto para cada una de sus variantes.

enum CLICommand {
    Place(usize, usize, Stone), // Row, Column, Stone
    Move(usize, usize, usize, usize, Direction),    // Row, Column, Num Stones, Num Tiles, Direction
    Board,
    Stones,
    Quit,
    Help,
}

Como se puede observar en el ejemplo anterior, el Enum CLICommand tiene 6 variantes distintas. Dentro de estas, solo las dos primeras cuentan con valores asociados, el resto directamente no tienen. Las que tienen valores asociados, ademas, pueden tener tantos como quieran y de cualquier tipo. En este caso, los comandos Place y Move necesitan información asociada como las coordenadas donde se realiza el movimiento, la piedra que se va a colocar o la dirección en la que se va a mover.

Otra clase que presenta una versatilidad muy interesante es la de Option. Esta clase permite manejar la presencia o ausencia de valor. Esta es una necesidad que se detecta en muchos lenguajes de programación pero ninguno parece abordar el problema directamente. Por ejemplo, en C, para tener una variable que pueda tener un valor o no, se crea un puntero que, si apunta a una dirección de memoria válida se considera con valor y si no apunta a ninguna, se considera sin valor o con valor nulo. Claro que mediante este proceso, se tienen punteros sin valor asociado que pueden traer problemas como accesos a memoria inválidos.

Los Option de Rust no dejan de ser un Enum que cuenta con dos variantes: Some y None. La variante None representa la ausencia de valor y, por lo tanto, no tiene ningún valor asociado. La variante Some, en cambio, representa la presencia de un valor y debido a esto sí tiene un valor asociado. Esto presenta una versatilidad y comodidad increíbles en el uso de funciones, tanto para especificar argumentos opcionales como para devolver valores que no tienen por qué estar ahí.

fn controlled_by(&self) -> Option<&PlayerId> {
    let top_stone = self.stack.peek();
    match top_stone {
        None => None,
        Some(stone) => Some(stone.get_owner())
    }
}

En el ejemplo anterior se puede observar un método perteneciente a la clase Tile. Este método permite comprobar quien, en ese momento de la partida, controla una casilla dada. Recordemos que una casilla estaba controlada por el jugador que fuese dueño de la piedra superior en la pila de esa casilla. Se pueden dar tres escenarios diferentes:

• Que la piedra superior sea del jugador 1
• Que la piedra superior sea del jugador 2
• Que no haya piedras en la casilla

Los Option son perfectos para este caso. La variante None se utilizaría para cuando no hay piedras en la casilla ya que esta no está controlada por ningún jugador. La variante Some tendría el tipo de dato asociado PlayerId e indicaría qué jugador controla esa casilla.

Finalmente, la clase Result permite devolver el resultado de una función que pueda fallar. Para esto también se podría utilizar la variante None de un Option, aunque en el ejemplo presentado anteriormente para los Options, el uso de estos está mucho mejor justificado. Usar un Result presenta algunas ventajas.

Result , también está basado en un Enum con dos variantes Ok y Err. La variante Ok se puede utilizar para cuando una función termina con éxito y devuelve un valor. Por supuesto, el valor asociado a la variante Ok es el resultado real de la función. La variante Err, se utiliza para cuando una función termina en error y lo devuelve. El valor asociado es un error y esto permite concretar qué pasó durante la llamada a la función.

fn new(size: usize) -> Result<Self,TakError>{
    if size < 4 || size > 8 {
        return Err(TakError::InvalidBoardSize);
    }

    let empty_tile = Tile::new();
    Ok(
        Board {
            tiles: vec![empty_tile; size*size],
            rows: size,
            cols: size,
        }
    )
}

La función anterior es el constructor de la clase Board. Este crea un nuevo tablero con el tamaño deseado pero en Tak, los tableros oficiales son de entre 4 y 8 casillas por lado. Por ello, si se especifica una medida fuera de esos valores, la función devuelve la variante Err de Result teniendo, como valor asociado, el error concreto que ha sucedido (InvalidBoardSize). En caso de poder crear el tablero correctamente, devuelve la variante Ok de Result con una instancia de la clase Board como valor asociado.

Este mecanismo tiene muchas ventajas ya que permite devolver un valor a la vez que el estado de ejecución de la función. Además, si la función falla, esta indica por qué y tanto en la propia declaración de una función como en el tipo de dato que devuelve, se puede ver que puede fallar y qué tipo de errores puede devolver. Esto se suele utilizar incluso para funciones que no devolverían un valor y simplemente pueden fallar; en caso de fallo devolverían el error y en caso de que todo vaya bien, devolverían la variante Ok con una tupla vacía (también llamada unit).

Tests Unitarios

Ciertas clases del proyecto, como Board y Game, tienen una lógica intrincada y que puede resultar compleja. Por ello, para verificar que la implementación fuese correcta, se añadieron al código una serie de tests unitarios que verifican cada función.

La forma que tiene Rust de gestionar los test unitarios me parece bastante elegante. Simplemente, en el mismo fichero donde hay un módulo, se crea otro llamado tests anotado con #[cfg(test)] encima del mismo. Dentro de este, cada función puede ser un test anotandola con #[test] en la línea superior a la cabecera de la función.

Estos tests se tienen en cuenta para la compilación de manera separada. De esta forma, al ejecutar cargo run no se compilan pero al ejecutar cargo test si. Además, el último comando permite especificar qué clase se quiere probar o, en caso de no especificar nada, probar el proyecto en su totalidad.

#[test]
fn board_creation() {
    //Check invalid input parameters
    assert!(Board::new(0).is_err());
    assert!(Board::new(3).is_err());
    assert!(Board::new(9).is_err());

    //Check board size 4
    let board = Board::new(4);
    assert!(board.is_ok());
    let board = board.unwrap();
    assert_eq!(board.tiles.len(), 16);
    assert_eq!(board.rows, 4);
    assert_eq!(board.cols, 4);

    //Check board size 7
    let board = Board::new(7);
    assert!(board.is_ok());
    let board = board.unwrap();
    assert_eq!(board.tiles.len(), 49);
    assert_eq!(board.rows, 7);
    assert_eq!(board.cols, 7);

    //Check board size 8
    let board = Board::new(8);
    assert!(board.is_ok());
    let board = board.unwrap();
    assert_eq!(board.tiles.len(), 64);
    assert_eq!(board.rows, 8);
    assert_eq!(board.cols, 8);
}

En el código anterior se puede ver la función de test unitarios correspondiente con el método creación de la clase Board visto anteriormente. En él, se pueden ver las macros assert y assert_eq que se corresponden con las funciones habituales de test unitarios en cualquier lenguaje de programación. Estas aseguran que un resultado sea true o que dos resultados sean iguales respectivamente.

Crates Externas Utilizadas

Rust base incluye una gran cantidad de funcionalidades y es muy completo. Sin embargo, para simplificar el desarrollo se ha utilizado una crate (o módulo) que permite gestionar de manera sencilla los argumentos por línea de comandos.

Esta crate se llama Clap (Command Line Argument Parser) y es muy intuitiva a la hora de parsear y manejar argumentos en línea de comandos. Puede utilizarse como un patrón Builder o, como se utilizó en este caso, de manera declarativa utilizando #[derive].

#[derive(Parser, Debug)]
struct Args {
    // Board size
    #[clap(short, long, default_value = "5", value_parser = Self::validate_board_size)]
    board_size: usize,

    // Game mode
    #[clap(short, long, value_enum, default_value_t = GameMode::PVP)]
    game_mode: GameMode,

    // AI difficulty level (if applicable)
    #[clap(long, value_enum, default_value_t = AILevel::Random)]
    ai_level_1: AILevel,

    #[clap(long, value_enum, default_value_t = AILevel::Random)]
    ai_level_2: AILevel,
}

impl Args {
    fn validate_board_size(size: &str) -> Result<usize, String> {
        match size.parse::<usize>() {
            Ok(n) if n >= 4 && n <= 8 => Ok(n),
            _ => Err("Board size must be between 4 and 8".to_string()),
        }
    }
}

El código anterior está incluido en el fichero main. Este contiene un struct que deriva el trait Parser de la crate Clap. Dentro de este struct se define cada argumento posible con su tipo y, en la línea superior a cada uno, se indican ciertos parámetros dentro de #[clap()] que permiten personalizar cada uno de ellos. Por ejemplo, short hace que el argumento se pueda especificar mediante su primera letra. En el caso de board_size, esto significaría que se puede especificar con la opción -b por línea de comandos. La opción long, permite especificar el argumento en su forma alargada, siguiendo el ejemplo anterior, el argumento sería --board_size. Como se puede observar, también existen diversas opciones como valores por defecto, funciones concretas para interpretar argumentos o utilizar Enums especiales como tipo de datos.

En cualquier caso, esta crate sin duda permite acelerar el desarrollo enormemente y ahorra tener que lidiar manualmente con la gestión de los argumentos en línea de comandos.

Algoritmos

Además de los retos que se presentan al utilizar un lenguaje de programación nuevo, existen retos que se presentan en todos los proyectos. Esta fase del proyecto no ha presentado muchos que no estuviesen relacionados con Rust. Sin embargo, alguno si que hay.

Cálculo de Caminos

Para saber si un jugador ha ganado la partida, es necesario que el simulador analice el estado del tablero tras cada turno. Durante este análisis se deben evaluar las distintas condiciones que desembocan en el final de la partida como que no queden casillas libres donde colocar piedras, que algún jugador se haya quedado sin piedras en su reserva o que algún jugador haya conectado dos lados opuestos del tablero con un camino. En este apartado se va a hablar más en profundidad de la última condición.

El análisis de caminos consiste en buscar sobre el tablero con el fin de detectar un camino compuesto por piedras de camino o piedra angular en el tope de la pila de cada casilla. Por supuesto, para que un camino sea válido tiene que haber una adyacencia ortogonal entre las casillas y estas deben estar controladas por el mismo jugador.

La tarea de encontrar caminos es un problema habitual en programación y uno de los enfoques que se le puede dar a este algoritmo es el recursivo. Un algoritmo recursivo es aquel que, para completar su función y devolver un resultado, se llama a sí mismo una o más veces. En este caso, el algoritmo de búsqueda de caminos sigue este mismo enfoque aplicado a casillas como veremos a continuación.

Imagen 7: Representación del algoritmo de búsqueda de caminos

La función de cálculo de caminos es una función no recursiva que se encarga de invocar al algoritmo recursivo desde distintas casillas del tablero. Esto se hace con las casillas del lado Oeste del tablero (primera columna) para buscar caminos que conecten con el Este (última columna) así como también de Norte a Sur (de la primera a la última fila). De hecho, esto es lo que pasa en las 3 primeras fases de la imagen anterior.

De esa forma, el algoritmo recursivo parte de una casilla y una dirección de análisis. Durante su ejecución, se llama a si misma para las 3 casillas adyacentes en la dirección deseada (es decir, si se analiza de Oeste a Este, se llamará en las adyacentes del Norte, del Sur y del Este). El algoritmo se detiene al llegar al lado opuesto del tablero.

El algoritmo base por si mismo puede llegar a resultar muy redundante y, si los tableros escalaran infinitamente, este implicaría una carga computacional bastante elevada. Por suerte, existen distintos mecanismos que pueden suponer una mejor guía del algoritmo y por tanto una mejora general en su rendimiento.

• Dueños de casilla: Esta técnica de “poda” consiste en que si una casilla está vacía o pertenece a un jugador distinto al dueño de la casilla original donde comenzó el análisis, se corta el algoritmo por esa rama.
• Casillas exploradas: Como una casilla solo puede pertenecer a un dueño y por tanto a un camino (En una misma dirección del análisis), una vez explorada no hay por qué volver a analizar un camino que pase por ella ya que todas las casillas conectadas ya han sido analizadas a su vez. Por ello, al algoritmo se le pasa una lista mutable de elementos en la que se van añadiendo las coordenadas de cada casilla explorada. De esta manera, si una casilla ya se encuentra en esa lista, también se corta el algoritmo.
• Un solo ganador: Como solo puede ganar un jugador, el análisis puede parar en el momento en que se encuentre el primer camino válido. Esto podría ahorrar muchos recursos.

Estas mejoras se implementaron en el algoritmo dando muy buenos resultados. Sin embargo, al revisar las normas del Tak, se descubrió que era posible que, con un solo movimiento, se formasen dos caminos de distintos jugadores a la vez. En este caso, el jugador ganador sería aquel que ha hecho el movimiento y por tanto, implica que la mejora de “Un solo ganador” no es aplicable, ya que es necesario explorar todos los caminos existentes en el tablero.

Este cambio implicó bastantes modificaciones en las funciones ya que pasaron de devolver un solo camino válido o ninguno (Un Option) a tener que devolver todos. Se exploraron varios enfoques pero, al final, se optó por devolver una tupla de booleanos que indican si existen caminos ganadores para cada jugador. De esta manera se puede mantener separada la lógica del algoritmo, que pertenece a la clase Board, de la lógica de turnos perteneciente a la clase Game ya que como ya se explicó, el ganador en caso de que haya dos caminos válidos, es el que hizo el movimiento, es decir, aquel cuyo turno acaba de pasar.

IA Random

Como esta fase de desarrollo incluía toda la creación del simulador de Rust, la parte del desarrollo de IAs contra las que jugar se vio algo mermada. Sin embargo, sí se implementó la IA más básica de todas, la aleatoria. Esta IA implementa un algoritmo muy sencillo: Obtiene absolutamente todos los movimientos posibles para ese jugador en el momento actual y después escoge uno al azar.

La primera parte será común a todas, cualquier algoritmo de IA necesitará saber qué movimientos puede hacer para tomar una decisión. La diferencia es que el resto de IAs probablemente implementarán algún tipo de algoritmo (que posiblemente será distinto para cada una de ellas) para evaluar cada movimiento y ponderarlos de cara a escoger su mejor acción. Visto desde ese punto de vista, la estrategia de IA implementada hace algo similar pero asignando el mismo valor a todos los movimientos, de manera que al final, cualquier elección es igual de buena y “tira un dado”.

Como es de esperar, esta IA depende mucho de los movimientos posibles en cada momento. Por ello, lo más probable es que al principio realice muchas colocaciones de piedra ya que, en un tablero vacío, la mayoría de acciones posibles son esas. Además a esto se le suma que cada colocación puede ser de 3 tipos de piedras (Caminos, Paredes o Piedras Angulares), por lo que hay que multiplicar estas posibilidades por 3. Según avance la partida y haya más piedras sobre el tablero, estas se podrán mover y cada piedra, por lo general, se podrá mover en cuatro direcciones, por lo que es más probable que en fases más tardías, esta IA realice más movimientos que colocaciones.

Conclusiones

Esta fase del proyecto estuvo centrada en la creación del simulador y la arquitectura de este. La idea es que esto sirva como base de construcción para las futuras iteraciones por lo que era fundamental que el alcance estuviese bien definido y que no fuese demasiado ambicioso para poder llevarlo a cabo de manera satisfactoria.

Imagen 8: Tablero y movimiento de un jugador desde la terminal

En la imagen anterior se puede observar el simulador en funcionamiento. Concretamente, el comando P (Place) coloca un camino (P de Path) en la fila 1, columna A. Para ver los comandos disponibles se puede utilizar el comando H.

Imagen 9: Lista de comandos posibles permitidos por el simulador desde la terminal

En la imagen anterior se muestra el mensaje de ayuda con los distintos comandos y sus parámetros. Por ejemplo, para ver las reservas de piedras de los jugadores se puede utilizar S.

Imagen 10: Movimientos realizado por dos jugadores en una partida jugador contra jugador

La imagen anterior muestra como el jugador 1 coloca una piedra al lado de una del jugador 2 y este último, en su turno, mueve su piedra a encima de la de su oponente controlando así la casilla 1B.

La sensación general después de haber utilizado Rust es muy positiva. Reconozco que es un lenguaje de programación que cambia bastante el paradigma convencional y presenta ciertos retos al ser tan estricto pero sin duda entra en la categoría de lenguajes de programación que me gustan, ya que prefiero los compilados a los interpretados. Con respecto al compilador, es el mejor que he visto nunca. Es cierto que construir código adecuado para el compilador es un proceso largo pero este te guía muy bien, casi siempre te presenta alternativas para cada error en tu código.

Lo más satisfactorio es que, aunque el proceso de arreglar errores de compilación y solventar warnings pueda resultar tedioso, sin duda compensa ya que la mayor parte del tiempo, una vez pasada la fase de compilación, el código funciona y rara vez da fallos. Otros lenguajes compilados como C suelen dar algún error en tiempo de ejecución y lenguajes interpretados como Python o Javascript pueden contener errores importantes que se mantienen indetectables hasta que el código es ejecutado. Rust es mucho más seguro en ese aspecto y creo que en general, acorta el tiempo de depuración enormemente.

Planes para la siguiente fase

De cara a la siguiente fase de este proyecto, el objetivo principal será implementar algoritmos de IA. Tener la IA Random está bien pero realmente no es oponente para nadie y creo que es un tema que puede dar mucho de sí. Sin duda mi intención es comenzar por algoritmos más tradicionales y que sigan una serie de reglas pero no descarto utilizar técnicas avanzadas como entrenar modelos, algoritmos genéticos, etc.

En cualquier caso, muchas gracias por leer hasta aquí. Nos vemos en la siguiente parte y espero que os haya gustado, tanto el artículo como Tak.

¡Hasta la próxima!