In my last devlog, I mentioned that collecting player logs is a step towards implementing automatic hints. In this devlog, I’ll share how I make this work in LFP.

Background

A few years ago, I had the awesome opportunity to do a project with Dr. Tiffany Barnes and her graduate students at NC State where I learned a lot about educational technology. They have made a really cool logic tutor called Deep Thought which uses logs from previous users to automatically generate hints. I was instantly impressed and wanted to try making something similar someday.

From how I understand it, this is an alternative to state-space searches where a system tries to reach a goal state by doing a brute-force search through the state space graph to find the goal state.

In some scenarios, the state space graph is really really big; to deal with this, you might use monte carlo methods or heuristic functions to help make the search computationally feasible. For logic puzzles, where there are many possible possible paths to reach a goal state, we might want to try other methods. 

State Space Graphs

A graph is a structure consisting of nodes and edges. Each edge connects two nodes. A directed graph is a graph where each edge has a direction, so there’s a “from” node the edge comes from and a “to” node the edge goes to.

A state space graph is a graph where each node represents a state and each edge represents some action or change from one state to another. Because going from state A to state B does not involve the same action or change as going from state B to state A, state space graphs are directed graphs.  

Imagining a “state” as the node in a graph can be hard to imagine. Terry Cavanagh, a dev for Dicey Dungeon, wrote a great article explaining this way better than I can.

LFP Levels as a State Space Graph

Let’s imagine we have a state space graph of some level. There’s an initial state and a goal state that the player wants to reach. Each edge represents some action the player does to “move” between states, such as moving a token, inserting a token, undoing, etc.

We know which node a player is “located” at by their current state. If the current state is “equal” to the state of some node, then the player is “located” at that node. At the start, the player is “at” the initial state node.

When a player does an action such as editing a token, they “move” to a new state from that action. The example shows the player "moving" after they do an "edit" action.

Generating Hints with a State Space Graph

How does this help generate hints? If we have a state space graph for the current level with a goal state, and if the player is “at” one of the nodes on that graph, then we can we can use any graph search algorithm like Dijkstra or A* to find a path to the goal state.

The path from some state to a goal state represents the sequence of moves used to reach the goal from the current state. Whichever is the first move on that path would be the hint for the player leading them towards the goal.

Looking back at the state space graph, let’s say the player deleted a token at the start, bringing them off the preferred path.

If the player requested a hint, the it would recommend the “undo” action because that action leads them on a path towards the goal state.

Constructing a State Space Graph with Logs

How do we actually create a state space graph? We can reconstruct a state space graph of a level using log messages if every log gives both the state of the game and the action (moving a token, inserting a token, undoing, etc.) which brought you to that state.

Imagine we have some game logs from players. Each log records the state and the action which was done to “move” into that state, except for the initial state where there are no previous actions.

Using this, we can make a state space graph for each player by making a node for every state and an edge between two nodes if the log before one node precedes the log for another node.

Given many state space graphs for a level, we can represent all the actions every player has done for that level in one giant state space graph by combining these graphs together.

This combined graph is what’s used for generating automatic hints.

Limitations

There are some limitations to using historical game logs for generating state space graphs for automatic hints.

First, if a player is on a state that no player has ever been on before, then the system can’t generate any hints because it can’t find where the player is “at” on the state space graph.

Second, this approach only works if there’s enough data. Without any data, no hints can be generated. This is known as the cold start problem.

Finally, building the entire state space graph for every level could be wasting time because we could be constructing large parts of the graph that a player might never visit.

Conclusion

Despite these limitations, I’m very happy that I got to try implementing this feature. While I admit this might not be the best possible option for enabling hints in LFP, it was the one I was most interested in trying. I hope you learned something new and I encourage you to do more research if you thought it was interesting.