ML Engineer teaches graph algorithms with Dungeons & Dragons – The New Stack
Thus began a learning adventurein which Dungeons & Dragons the role-playing game is deployed to present “a first intuitive understanding of common graph algorithms”, explained the software engineer Mohammad Athar. Athar is currently a Principal Machine Learning Engineer at TackleAI.
“Among my many interests, I really think graphics are good,” Athar told the audience.
Athar also enjoys serving as the narrator – or “Dungeon Master” – for Dungeons & Dragons games. Athar found a way to combine the two interests into one speech at this year’s conference PyCon 2022 – the annual Python conference funded by the non-profit Python Software Foundation
Before it was over, Athar had taken the audience through a whirlwind tour showing all the major graphics algorithms.
The beers are raw
Like many Dungeons & Dragons games, Athar’s conversation begins in a tavern. “And you want to get a lager because beers are gross.” But unfortunately, there are multiple paths through the tavern – and sometimes the routes between tables are blocked by tavern patrons. Then Athar points out that your routes through the tavern “naturally turn into a graph” if you think of each intersection as one of the nodes in a graph.
And it lets you use your first algorithm – the standard graph traversal pattern known as depth-first search.
Athar fancifully billed it as “a nice, simple recursive algorithm that’s, you know, quick to implement, easy to use, yadda-yadda.”
Specifically, it moves as far as it can on each path, then backtracks to try the next available path, until one of them reaches the desired end point. And the example of getting lager in a tavern shows that the algorithm is broadly applicable in common situations – providing an easy-to-grasp and intuitive example of when it could be used.
But could there be a quest about to begin?
“As you’re ordering your beer, a little street urchin comes up to you and asks for your help…” Athar told the audience. Apparently there’s something disturbing behind the locked sewer grate – and the kid tells you to get the key from Alice or Bob.
“It’s a weird town – everyone’s names are listed alphabetically,” Athar noted. Alice sends you back to Carmen and Dev, while Ellen receives a recommendation from Bob…and the hunt for the key begins to unfold in a multi-directional mess.
Algorithms to the rescue — but this time it’s the algorithm known as deep search. (That is, take one step on each available path before exploring deeper.)
Its biggest advantage? You can collect its data as you go (without needing to know how deep it will eventually go.) This algorithm allows you to avoid the extra research that would have been involved in exploring all possible paths to its end.
This will greatly speed up your search for the key to this sewer…
Athar returns to sing their praises at the end of the conversation. “If you don’t come away with any other algorithm today, check out deep search first. It’s really useful. You can use it for a lot of different things.
At this point, Athar staged a realization that he was running out of time, then simply blurted out a much shorter summary: “Guys, deep search is awesome. Do it.”
Then continues to tell the D&D adventure…
The sea urchin surprises you by knowing a shorter way to the end of the sewer – thanks to “a wizard named Dijkstra”. The audience laughs, knowing what is to follow: an introduction to Dijkstra’s algorithm
Although a width-oriented algorithm can guarantee the fewest number of Connectionsit’s not always what you want, Athar pointed out.
Sometimes many short distance connections can combine into a shorter overall path than another path with fewer but longer connections. This is where Dijkstra’s algorithm saves the day, effectively calculating the distance of every possible path.
Armed with this efficiency-guaranteed algorithm, your magical quest continues, and somehow you reach the end of the sewer, Athar explained. “And then you walk into the villain’s lair and you make Batman noises.”
In addition to explaining common algorithms, the lecture had obvious applications for its audience of Python programmers. Athar started the talk by reminding the audience that there are many ways to represent graphs using Python data structures.
Just for an example, there’s the common data structure of a matrix, which Athar later defined as “really just a table of numbers”.
Each node in the graph gets a row in this table for the number of connections from that node to all other nodes. Each node also gets its own columns.
Reading the columns can be seen as an alternative view that does not count connections “from” a node but connections “to” a node. And they will often be the same, unless the connections in your graph are sometimes one-way.
Another way to represent graphs in Python is to list all pairs of connected nodes.
Athar also suggested the Python data structure called a dictionary – known in other languages as an associative array – where looking up a “key” provides its corresponding/associated values.
For a graph, the key can be the node itself, the associated values being a list of all the nodes it connects to.
Athar even shows a way to do this using object oriented programming – with node objects. And of course Python also has a library to simplify this – the NetworkX package.
But with all these technical details, Athar maintained a lively and understated model throughout the presentation. At one point, Athar noted that an important part of the algorithms is tracking graph nodes that have already been visited: “So when Carmen finally tells you to go see Bob, you’re like, ‘Ha, I I’ve already taken care of that!” Don’t even trip, man.
And soon our quest had reached its dramatic finale. At the end of the sewer. It turns out that you have discovered a henchman, carrying messages to members of a nefarious network.
Athar then shows how you can graph recipient relationships and then easily find actionable patterns. For example, you can scan the chart for “points of articulation– essentially a single point of failure, where its removal splits the graph into two unconnected parts. You can also try counting the number of connections to each node…
But one of those techniques leads you to the main villain, “So you go in there and make more Batman noises,” Athar told the audience, adding, “And you get a big bag of money.”
This leads to the final problem – how to distribute all the cash you’ve looted from the villain’s lair.
And of course, this is a problem that can be solved using yet another algorithm…