Codenames but Math

This set of thoughts is inspired by a conversation in which I was asked to mansplain something, and they chose Codenames, and in the explanation I realised two things:

1. Mansplaining feels very good, and one should really fight the drug of mansplanations.

2. Codenames is actually a very interesting game from a purely abstract perspective.

The Rules of Codenames

Codenames is a really interesting game. Morally, it is a game where one side of each team constructs a word puzzle for the other side to solve.  The actual rules are as follows:

Start by taking the word cards and making a 5x5 grid of them on a playing surface. Then split the group into a red team and a blue team, and each team into n codeguessers and one codegiver. The two codegivers (one from each team) now look at a secret clue card. This card proportionally represents the 5x5 grid of cards on the playing surface, with some cards colored red, some blue, some beige, and one card colored black. The red cards are one team's cards, the blue are another team's, the beige are neither, and if the black card is chosen, the team that chose it automatically loses. The goal is for the codeguessers to tap each of the words of their colors before the other team. 

The codegivers have to say a single word and a number, k. Then their team tries to use the word to guess words on the 5x5 grid from the clue, and confirm their guesses by tapping said card. They can continue up until they make a mistake or have tapped k+1 correct word cards; if k=0, they can guess as much as they desire. The team that goes first has 9 clue words to find, and the one that goes second has eight clue cards to find.

Morally, you can see how the cluegivers are creating a word puzzle for the clueguessers to solve. This word problem has a couple of standard variants.

The Standard Strategies

1. The Star Puzzle:

This is the most common puzzle that we can consider. For this game, you choose a word whose closest k words on the table are of your color. Here, close is defined by a culturally defined metric on words. There are various weaker star puzzle strategies, e.g.,  choosing a word whose closest k+r words are not of the opponent's color, or even riskier by choosing a word whose closest k+r words do not include the black card. When  r=0, this is the strong star puzzle strategy. So we can define a (k,r)-star clue as a word whose closest k+r connecting words contain k words in your color and no words in the opponent's color, and a weak (k,r)-star clue as a word whose closest k+r connecting words contain k words in your color and not the black card.

2.  The Avoid-At-All-Costs puzzle:

The avoid-at-all-costs puzzle is only implemented when the codeguessers are adamant that they want to guess a given word, but the codegiver knows that if they tap that word, then they will surely lose the game. To do so, the codegiver chooses a word incredibly close to the bad word and chooses k=0. 

Less Standard Strategies

These are just some strategies that I have seen used, but they are by no means an exhaustive list. These are not given in the rules as an explicit example of how to play the game.

     3. The Anti-Star puzzle:

For the anti-star puzzle, we provide a clue word, but choose k=0, so that the clue-guessers know that the given word is maximally far away from some unknown k' words of our color.

4. The Path puzzle:

For the path puzzle, the codegiver gives a clue that connects to one word of their color very strongly. However, the direction from the clue to the given word creates a path connecting to k-1 other words of that color.  

Cheating strategies

There are plenty of strategies that are obvious moral cheats; for instance, using snowman to connect snow and man is against the rules for the simple reason that the link between these words is as strings as opposed to the atoms of language. A less known but obvious cheat is given by mathematical intuition. 

5. The mathematical cheat:

Create a reasonably good reversible mapping from the space of words (as strings) to the set of secret clue cards (2^25). The cluegiver provides the word corresponding to their secret clue card, and the team reverses said algorithm. Hint: organic compound names are likely the easiest single words in the English language for which a proficient, mathematically inclined chemist, or vice versa, can provide such a mapping and reverse-engineer such a mapping. Though it will probably not be any fun.

Mathematically Extending Codenames

I expect that the mathematicians amongst you have already noticed that we will likely put a weighted graph structure on the words in the English language, making the (k,r)-star and antistar strategies literally about the existence of a vertex whose star of k+r nearest adjacent vertices, restricted to the given 25 words, has the above structure. In doing so, we can see that we will have the following two mathematical extensions:

The Graph Theoretic Extension:

Here we will replace the English language with an edge-colored, edge-weighted graph. Where the coloring on the edges encodes the context for the similarity between the words, and the weighting encodes the full contextual distance between these words. e.g., Italy connects very closely to boot through the context of a well-known saying/association, while Italy and sock, while also being the same shape, are more connected through the nearest neighbor of boot being connected to both. The first through a saying and the second through a utility; secondarily, one may associate them purely for the shape without the cultural context association with boot. 

We can now mathematically extend the game of Codenames. Given a weighted edge-colored graph G and a subset of vertices H=H_blue U H_red U H_beige U H_black, find a vertex g in G that is not in H and a number k. Such that another player could connect k elements in H_blue, without loss of generality, to g before connecting to r elements not in H_blue. Then the above strategies correspond to finding either a colored star from the edge given by the nearest element in H to g, or an uncolored star, or an antistar (which in this context means that we consider the subset of edge colors corresponding to `opposites` for weights, e.g., fire and ice are very very near in this strategy, but oxygen and tank are not). 

To deal with the annoyance that the cheating strategy is still viable (as the graph is effectively finite), consider the following extension. 

The Continuous Extension:

Here we take the graph of English with all its contexts and consider instead a continuous space for which the graph of English acts as a sample. Edge context then defines the local structure of this space, providing a quasi-tangent space at each point. The game of Codenames is now defined as: given a topological space with a metric, X, with local structure at a point g given by some algebraic structure O_{X,g}, if some discrete set of G points were sampled from it, and further a second subset of points H=H_blue U H_red U H_beige U H_black were sampled from G, we can construct the graph given above using local structure to weigh the edges corresponding to the paths connecting any two points in G and play the above game. More simply, can you choose a point in G such that another player can connect k elements in H_blue (without loss of generality) before connecting r points in H not in H_blue? 

The beautiful part of this game is that the path strategy is now simply choosing a point g in G such that the local structures connecting g to its nearest point in H, H_g, define a subspace containing k points in H_blue and r points outside of H_blue. A clue is better than or equal to another in this strategy if it connects more or the same number of blue points k'>= k and fewer or equal number of bad points r'<=r. If we imagine that this local structure is a tangent space of a Lie Group, L, the strategy becomes about the construction of a 1-parameter family, e.g., a literal path that connects these points. 

More generally, we should expect a less definable structure on X, leading to multiple geodesic paths between the two points and further bifurcation on integral curves.  

Conclusions

The really interesting conclusion here is that if there is a magical space X which all of language is a sample of, then we should try to better understand it to beat our friends in Codenames (without any finite element cheating scandals). Also, I should read more about dynamical systems on smoothish topological spaces to see where one can find bifurcations of one-dimensional families.