I love playing board games. I love machine learning. I love Rust. So why not combine them and do something really fun? So I ran a word vector analogy query and I got back:

machine learning + board games - Rust = Codenames 

So let's implement Codenames in Rust. It's a simple game. There are two teams, each having one Spymaster and several field operatives. There is a shared 5x5 board, which represents a map to the field operatives, which are hidden. Each spot on the map has a word on it. The spymasters must give clues to the operatives so that they can find the enemy operatives and take them out. A more detailed description and pictures can be found in my previous post.

In this post, we will implement a simple model for the game, using dummy agents. In a future post, we will implement some smarter agents, with word vectors.

Modeling the map

First, let's start modeling the map. Each cell on the map can be a red agent, a blue agent, an assassin (black) or a neutral character (gray). There is one word on each cell and we need to track if the cell has been overturned or not. All this will go in a file called map.rs:

#[derive(Debug, Copy, Clone, PartialEq)]
pub enum State {
    Gray,
    Red,
    Blue,
    Black
}

#[derive(Debug)]
pub struct Cell<'a> {
    pub color: State,
    pub word: &'a str,
    pub revealed: bool
}

Cells have a lifetime parameter which is needed for the word field. Using the 'a lifetime parameter we tell the compiler that the str in that field will live at least as long as the cell that contains it.

While the derived Debug provides a way to print out the debug version of both the State and the Cell, when printing out in the CLI the actual game we'll want to customize what we print out. For this, we will have to implement the  Display trait, which is then used by formatters to create a string representation. For states, we will print only the first letters, for cells we will print the state if the cell has been overturned (so it's visible) and its word otherwise.

use core::fmt;
use crate::map::State::{Gray, Red, Blue, Black};

impl fmt::Display for State {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        let char = match self {
            Gray => 'N',
            Red => 'R',
            Blue => 'B',
            Black => 'X'
        };
        write!(f, "{}", char)
    }
}

impl fmt::Display for Cell<'_> {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        if self.revealed {
            f.pad(&format!("{}", self.color))
        } else {
            f.pad(self.word)
        }
    }
}

Now let's make a struct for the map. The map will have just a vector for the cells. We also want to provide a constructor, which in Rust is by convention called new, which takes a list of words, chooses 25 words randomly, and assigns each cell a color. Initially, all cells will have revealed flag set to false.

use rand::prelude::*;

pub struct Map<'a> {
    cells: Vec<Cell<'a>>
}

impl Map<'_> {
    pub fn new<'a>(words: &[&'a str]) -> Map<'a> {
        let mut colors = vec![Gray; 7];
        colors.append(&mut vec![Red; 9]);
        colors.append(&mut vec![Blue; 8]);
        colors.push(Black);

        let mut rng = thread_rng();
        colors.shuffle(&mut rng);
        let words: Vec<&&str> = words.into_iter().choose_multiple(&mut rng, 25);

        let mut cells = Vec::with_capacity(25);
        for i in 0..25 {
            cells.push(Cell { color: colors[i], word: words[i], revealed: false });
        }
        Map{cells}
    }
}

We have to have a lifetime even for map, because the cells need it. For the constructor, because we have two input lifetimes, we have to explicitly specify to which one is the output lifetime related: to the words, because the map will contain some of them.

For all the random stuff we use the Rand module. We import everything from it and then we instantiate a thread_rng. I find the name a bit misleading, because it has nothing to do with threads per se, it's just that it's not thread safe. Our program doesn't use threads, so we don't care about that. The Rand module then provides a trait for slices which we can use to shuffle the color list and to choose the 25 random words.

Let's also add a Display implementation, which will just show each cell, using the Display for Cell. To make sure things show up nicely in a grid, we calculate the longest word first and then we pad all the words to that size.

impl fmt::Display for Map<'_> {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        let max_len = self.cells.iter().map(|x| x.word.len()).max().unwrap();
        for i in 0..5 {
            for j in 0..5 {
                write!(f, "{:width$} ", self.cells[i*5+j], width=max_len)?;
            }
            write!(f, "\n")?;
        }
        Ok(())
    }
}

The formatter knows to use the Display for Cell, so it will show words for unrevealed cells and colors for revealed cells.

Let's put everything together and test it out. Let's write a simple main.rs:

mod map;

use crate::map::{Color, Cell, Map};


fn main() {
    let words = vec!["RAY", "REVOLUTION", "RING", "ROBIN", "ROBOT", "ROCK",
"ROME", "ROOT", "ROSE", "ROULETTE", "ROUND", "ROW", "RULER", "SATELLITE", "SATURN",
"SCALE", "SCHOOL", "SCIENTIST", "SCORPION", "SCREEN", "SCUBA DIVER", "SEAL",
"SERVER", "SHADOW", "SHAKESPEARE", "SHARK", "SHIP", "SHOE", "SHOP", "SHOT", "SINK"];
    let map = Map::new(words);
    println!("{}", map);
}

I hard coded there a list of words for now, we'll get rid of that soon. For now, this should output something similar to the following:

RAY         SHOT        RING        ROBIN       ROBOT       
ROCK        ROME        ROOT        SHARK       ROULETTE    
ROUND       ROW         RULER       SATELLITE   SATURN      
SCALE       SCHOOL      SCIENTIST   SCORPION    SHOE        
SCUBA DIVER SEAL        SERVER      SHADOW      SHAKESPEARE 

Everything is nicely aligned.

The player agents

We have a map. Now let's start implementing the players. There will be two player types: a spymaster and a field operative. The spymaster has to give hints based on the map and the field operative has to guess words, based on the hint. In Codenames hints consist of a word (a single word) and a number, which is the number of words on the board that are related to the hint word. This goes into a players.rs file.

use crate::map::Map;

#[derive(Debug)]
pub struct Hint {
    word: String,
    count: usize,
}

pub trait Spymaster {
    fn give_hint(&mut self, map: &Map) -> Hint;
}

pub trait FieldOperatives {
    fn choose_words<'a>(&mut self, hint: &Hint, words: &[&'a str]) -> Vec<&'a str>;
}

The Hint word is a String and not a &str because in some cases we might have to return owned hints and not borrowed ones (such as when reading from the CLI).

Both the Spymaster and the FieldOperative must borrow self mutably, because they might need to change some state internally (such as a random number generator) to give their corresponding answers.

For now, we will implement two kinds of players: a random player, that outputs random clues and chooses words at random and a human player, that reads from the outputs from the keyboard.

use rand::prelude::*;

pub struct RandomSpyMaster<'a> {
    rng: ThreadRng,
    clues: &'a [&'a str]
}

pub struct RandomFieldOperatives {
    rng: ThreadRng,
}

impl RandomSpyMaster {
    pub fn new() -> RandomSpyMaster {
        let rng = thread_rng();
        RandomSpyMaster{rng}
    }
}

impl RandomFieldOperatives {
    pub fn new() -> RandomFieldOperatives {
        let rng = thread_rng();
        RandomFieldOperatives{rng}
    }
}

The random field operative has only a random number generator, while the spymaster also has a list of words from which it can choose clues.

impl Spymaster for RandomSpyMaster<'_> {
    fn give_hint(&mut self, _map: &Map) -> Hint {
        let word = (*self.clues.choose(&mut self.rng).unwrap()).to_string();
        let count = self.rng.gen_range(1, 5);
        Hint { word, count }
    }
}

impl FieldOperative for RandomFieldOperative {
    fn  choose_words<'a>(&mut self, hint: &Hint, words: &[&'a str]) -> Vec<&'a str> {
        let nr_found_words = self.rng.gen_range(1, hint.count+1) as usize;
        words.choose_multiple(&mut self.rng, nr_found_words).copied().collect()
    }
}

We do a dereferencing when getting the word in the spymaster, because Clippy says it's faster that way.

Let's test them out, by adding them in our main function:

    let mut sp = RandomSpyMaster::new(&words);
    let mut fo = RandomFieldOperative::new();

    let hint = sp.give_hint(&map);
    println!("{:?}", &hint);
    println!("{:?}", fo.choose_words(&hint, &words));

And we will have as output:

Hint { word: "SHIP", count: 4 }
["ROSE", "SERVER", "SHIP"]

It ain't much, but it's random work. Let's implement the CLI players, which are even simpler:

pub struct HumanCliSpymaster {}

pub struct HumanCliFieldOperative {}

They don't have any fields or internal state, because everything comes from the brain of the player.

The spymaster player should give the hint in the following format: 2 rust. If we can't parse it, we'll ask them to give the input again.

impl Spymaster for HumanCliSpymaster {
    fn give_hint(&mut self, map: &Map) -> Hint {
        println!("Give a hint for this map in count, word format: \n{} ", map);
        loop {
            let mut input = String::new();
            io::stdin().read_line(&mut input).unwrap();
            let results = input.split_ascii_whitespace().collect::<Vec<&str>>();
            match results[0].parse::<usize>() {
                Ok(count) => return Hint { count, word: results[0].to_string() },
                Err(_e) => println!("Give hint in count, word format!"),
            };
        }
    }
}

When reading from stdin, we apply unwrap. I can't even really imagine under what conditions that read might fail or what you could even do in that case, so I think it's fine.

The field operative has to give a list of as many words as the clue said, each on separate line. All the words they give must be from the words on the map.

impl FieldOperative for HumanCliFieldOperative {
   fn choose_words<'a>(&mut self, hint: &Hint, words: &[&'a str]) -> Vec<&'a str> {
       let mut chosen_words = vec![];
       println!("Choose {} words from {:?}", hint.count, words);
       let mut counts = hint.count;
       while counts > 0 {
           let mut input = String::new();
           io::stdin().read_line(&mut input).unwrap();
           if input.trim() == "" {
               return chosen_words;
           }
           match words.iter().position(|&x| {
               x.to_lowercase() == input.trim()
           }) {
               Some(c) => {
                   chosen_words.push(words[c]);
                   counts -= 1;
               },
               None => println!("Choose a word from the given list")
           }
       }
       chosen_words
   }
}

If the player submits a blank line, we return only the list of words we have found so far, even if they are fewer than what hint said, because they probably are out of ideas. If the player submits a word that is not on the map, we ask again.

To find the index of an item, the Rust idiom is to do vector.iter().position(|x| x == my_value), which returns an Option. I find it too verbose. Why isn't there a convenience indexOf method that directly tests for equality? I'm sure this is a very common use case.

The game logic

Now, let's put all of this together and make our game logic, in a file called game.rs. First we define a function that will do all the player interaction: getting hints and choosing words.

pub fn get_actions(spymaster: &mut dyn Spymaster, field_op: &mut dyn FieldOperative, map: &Map) -> Vec<String>{
    let hint = spymaster.give_hint(map);
    field_op.choose_words(&hint, &map.remaining_words()).iter().map(|&x| x.to_string()).collect()
}

The dyn keyword is necessary to make it explicit that we are using a trait object, which has some performance implications.

Next, we need to check the results. What happened in the last turn? If the player chose the Black cell, instant game over, they lost. If the player chose one of their own field operatives or a neutral one, their round is over and the remaining guesses are discarded.

fn opposite_player(color: Color) -> Color {
    match color {
        Color::Red => Color::Blue,
        Color::Blue => Color::Red,
        _ => panic!("Impossible player type!")
    }
}

pub fn check_if_lost(current_player: Color, guesses: &[String], map: &mut Map) -> bool {
    for word in guesses {
        let color = map.reveal_cell(word);
        if color == Color::Black {
            return true;
        }
        if color != opposite_player(current_player) {
            return false;
        }
    }
    false
}

We have also added a helper function to get the color of the other player. Now we need to reveal the cells in Map.

impl Map<'_> {
    pub fn reveal_cell(&mut self, word: &str) -> Color {
        let cell = self.cells.iter_mut().find(|x| x.word == word).unwrap();
        cell.revealed = true;
        cell.color
    }
}

To reveal a cell, we simply iterate over all the cells until we find the one where the word matches. We know the word comes from the cells, so it's safe to unwrap. We set the revealed bit to true and then we return the color of the cell, because that's all we need.

And now let's loop until the game is over.

pub fn game(red_spymaster: &mut dyn Spymaster, red_field_op: &mut dyn FieldOperative,
            blue_spymaster: &mut dyn Spymaster, blue_field_op: &mut dyn FieldOperative,
            map: &mut Map) -> Color {
    let mut current_color = Color::Red;
    loop {
        println!("The turn of player {}", current_color);
        let guesses;
        if current_color == Color::Red {
            guesses = get_actions(red_spymaster, red_field_op, &map);
        } else {
            guesses = get_actions(blue_spymaster, blue_field_op, &map);
        };
        println!("{:?}", &guesses);
        if check_if_lost(Color::Blue, &guesses, map) {
            return opposite_player(current_color);
        }
        println!("The map is now: {}", map);
        if map.is_over() {
            return current_color;
        }
        current_color = opposite_player(current_color);
    }
}

If the player lost (because they found the Black cell), we return the other player as the winner. If the game is over, we return the current player as the winner. Otherwise, we swap colors and it's the turn of the other player.

When is the game over? When there are no more cells belonging to red or blue that are unturned. To count the number of cells of a certain color that are unturned, we simply iterate over all of them and filter out the ones that have been revealed and the ones that are another color:

impl Map<'_> {
    pub fn is_over(&self) -> bool {
        if self.unturned_cells_of_color(Red) == 0 {
            return true
        }
        if self.unturned_cells_of_color(Blue) == 0 {
            return true
        }
        return false
    }

    fn unturned_cells_of_color(&self, color: Color) -> usize {
        self.cells.iter().filter(|x| !x.revealed)
                         .filter(|x| x.color == color).count()
    }
}

Our main function becomes as follows:

use crate::map::{Color, Cell, Map};
use crate::players::{RandomFieldOperative, RandomSpyMaster, Spymaster, FieldOperative, HumanCliSpymaster, HumanCliFieldOperative};
use crate::game::game;
use std::fs::File;
use std::io::Read;

fn main() {
    let mut file = File::open("resources/wordlist").unwrap();
    let mut contents = String::new();
    file.read_to_string(&mut contents).unwrap();
    let words = contents.lines().collect::<Vec<&str>>();
    
    let mut map = Map::new(&words);

    let result = game(&mut RandomSpyMaster::new(&words), &mut RandomFieldOperative::new(),
           &mut RandomSpyMaster::new(&words), &mut RandomFieldOperative::new(), &mut map);

    println!("The winner is {}", result)
}

I've also moved the list of words to an external file, so that they are not hardcoded in the binary. You can find a list of all the words in the official game with a quick DuckDuckGo search :D

If you want, you can try to put a HumanCliSpymaster or a HumanCliFieldOperative and see if you can beat the random player. It's quite easy :)

The whole code put together can be seen on GitHub (on the blog branch).

Now, we've got the basic skeleton for our Rust implementation for Codenames. Next time, we will get to the fun part: creating a smart agent that actually knows how to give hints and how to make guesses, using word vectors.

I’m publishing this as part of 100 Days To Offload - Day 22.