depth first search

In a previous post I mentioned that de Bruijn graphs are a useful way to model fixed memory agent strategies. I decided to code up a version of de Bruijn graphs using Python + NetworkX to show how this representation might be useful. You can find the source here. If we use de Bruijn graphs, we can replace the dynamic programming approach of the original paper with an application of Dijkstra’s algorithm to find the shortest (weighted) path.

The resulting running time if given this representation is actually less than the running time of the algorithm presented in the paper, but the cost of generating the representation from the original normal form game is quadradic in the number of available agent actions.

•