An extension of self avoiding walks on lattices to self avoiding walks on queen graphs is explored, and a new criterion for termination is defined in terms of partitioning the graph by visited vertices, rather than just deleting visited vertices, inspired by the board game Trike, invented by Alek Erickson. An algorithm is developed for generating these walks as stochastic processes, as well as realizing them as multiway graphs. Further directions for this study are mentioned, including a development of a fully fledged Trike algorithm that optimizes Trike play according to winning conditions imposed on the multiway structure.
Construction of Generalized Queen Graphs from Embedded Lattices
Construction of Generalized Queen Graphs from Embedded Lattices
Lattices and walks on lattices are an extensively studied topic in graph theory. One might imagine extending the “abilities” of the walker on the lattice from only being able to make one step at a time to being able to make as many steps as it desires in one direction, and seeing what the resulting combinatorial properties of this walk are. Since these walkers are allowed to move like chess queens on some generalized chess board, represented by a lattice endowed with a particular embedding, we will refer here to these kinds of graphs as “generalized queen graphs.” Mathematically, for a board lattice B, we consider its corresponding queen graph Q(B). Let us first examine the simplest kind of board lattice we can possibly construct, the 1 dimensional path lattice. What does it’s corresponding queen graph look like?
In[]:=
{GridGraph[{1,5}],Queen[Round/@GraphEmbedding[GridGraph[{1,5}]],{{1,0}}]}
Out[]=
,
That is, Q(Pn) for a path graph of length n yields the complete graph on n nodes, Kn, otherwise known as the n-1 simplex. Why is that? Well, each node can move to every other, since there is only one direction the queen can possibly move, so the queen graph is completely connected. The next thing we can do is look at queen graphs on two dimensional lattice grid graphs. Note that this is not yet the tried and true chess board lattice quite yet, because in chess, the diagonals are also connected. Technically, you might object and say that this graph is actually the rook graph. Here, however, we are just going to use the term “queen” nominally to mean connecting all possible directions or lines of sight, and the possible lines of sight that can be drawn are dependent on the underlying lattice structure itself.
In[]:=
{GridGraph[{5,5}],Queen[Round/@GraphEmbedding[GridGraph[{5,5}]],{{1,0},{0,1}}]}
Out[]=
,
As you can see, it starts to get complicated pretty quickly. However, it is easier to see what is going on by constructing the queen graph row by row.
In[]:=
{GridGraph[{2,5}],Queen[Round/@GraphEmbedding[GridGraph[{2,5}]],{{0,1},{1,0}}]}
Out[]=
,
In[]:=
{GridGraph[{3,5}],Queen[Round/@GraphEmbedding[GridGraph[{3,5}]],{{0,1},{1,0}}]}
Out[]=
,
Hopefully, it is now easier to see what this construction is doing. For an m by n board, we have m rows of length n, so we have a set of m complete graphs on n nodes, and for each pair of row graphs, each of their corresponding nodes have an edge between them bijectively, so we end up with these prism-like constructs where the “faces” of the prism are complete graphs. Mathematically speaking, we are taking a graph Cartesian product of complete graphs.
Stochastic Evolution of Random Self Avoiding Walks on Queen Graphs
Stochastic Evolution of Random Self Avoiding Walks on Queen Graphs
Aside from the interesting properties that queen graphs have on their own, we can also define some interesting processes happening on them. Among the more obvious of these processes to define are terminating walks, i.e., walks along which choices are constrained such that eventually they terminate. One of the first of these terminating criteria we might imagine defining is that the queen is not allowed to revisit a vertex already visited, i.e. the self avoiding walk. First of all, to get an idea of how the complexity of this thing grows, consider the number of possible self avoiding walks on the simplest possible board, the path graph of length n. The queen graph of this board, as discussed above, is a complete graph on the n nodes of the path. How many possible self avoiding walks are there on this graph? Well since the graph is completely connected and thus every node can visit every other node, we can simply make a self avoiding walk by permuting the nodes in any order we want. Thus, the state space of the self avoiding queen walks in a single row is n! This gives you some idea of the scale at which the state space is growing, row by row. It is a more difficult combinatorics problem to find the number of possible self avoiding queen walks on larger boards, I will address this at a later time. For now, let’s get a visualization for the evolution of the process.
In[]:=
board=Round/@GraphEmbedding[GridGraph[{5,5}]];basis={{1,0},{0,1}};graph=Queen[board,basis];SAWEvolution=RandomWalk[{graph,{1,1}},SelfAvoidAssociation[board,basis]];
Here is what the time evolution of the queen graph looks like. As the queen traverses the graph and the choices are constrained, visited vertices are deleted and the graph devolves in complexity.
In[]:=
ListAnimate[Table[Graphics[{Point/@board,Disk[#,1/5]&/@Last/@Take[SAWEvolution,n]}],{n,1,Length[SAWEvolution],1}]]
Out[]=
In[]:=
ListAnimate[Table[HighlightGraph[First[SAWEvolution[[n]]],Last[SAWEvolution[[n]]]],{n,1,Length[SAWEvolution],1}]]
Out[]=
You can see that eventually, at the end of this evolution, there remains some disconnected node that the queen lands on that is effectively a point of no return. Let's look at another constraining rule. Instead of restricting the graph by deleting vertices, let’s imagine partitioning the lines of sight by visited vertices. So, not only are vertices deleted, but some number of edges also get deleted by this partitioning process, corresponding to the fact that the queen is not allowed to “jump over” visited vertices, as well as not being able to revisit. Here is how to visualize what is going on.
In[]:=
trikeEvolution=RandomWalk[{graph,{1,1}},TrikeAssociation[board,basis]];
In[]:=
ListAnimate[Table[Graphics[{Point/@board,Disk[#,1/5]&/@Last/@Take[trikeEvolution,n]}],{n,1,Length[trikeEvolution],1}]]
Out[]=
Realizing the Walks as Multiway Systems
Realizing the Walks as Multiway Systems
The Game of Trike
The Game of Trike
Conclusion and Plans for Future Work
Conclusion and Plans for Future Work
Keywords
Keywords
◼
Self avoiding walk
◼
Queen graph
◼
Partition
◼
Multiway graph
◼
Trike
◼
Clique
Acknowledgment
Acknowledgment
Thanks to my mentor Brad Klee, for stimulating discussion and competitive gameplay. Additionally, thanks to the support from my team and the friends I have made here.
References
References