# Bachelor thesis assignments

Below you find a number of examples of potential assignments for a bachelor thesis. In general there are far more assignments than can be listed here. It is always more fruitful to do a bachelor thesis assignment that matches your interests. Therefore, I invite you to discuss your particular desires with me. If you have an idea about a topic yourself, I am very open to discuss this.

### Are there winning strategies for Quoridor?

A relatively recently formulated game is Quoridor. There are two to four players, where each must reach the opposite of the board. All players alternatingly have a turn in which they either can move their pawn, or put a barrier on the board. When putting a barrier on the board, no player may be blocked from reaching the opposite side. The question is whether we can determine on small boards, whether for a two player game the first player has a winning strategy. For this purpose we need to make a model of the game, and verify the modal formula which says that the first player has a winning strategy.

### Find an optimal solving recipe for Rubick's 2x2 cube.

Using mCRL2 it is possible to model Rubick's cubes. For the 2x2 cube, the statespace is sufficiently small to be generated completely, and hence it is straightforward to calculate using mCRL2 the optimal sequence of turns required to solve the this cube. An intriguing question is whether an optimal or near optimal recipe can be devised to solve the puzzle, given that the complete state space is known. An initial investigation reveals that the 'standard' approach to solve cubes is not particularly optimal. Doing the upper corners last requires almost as many turns as are required to solve any 2x2 Rubick's cube.

### Implementing a fast graph positioning algorithm.

The tool ltsgraph in the mcrl2 toolset is used to visualize directed graphs. It uses a simple spring-attraction algorithm to position edges and vertices. Its complexity is quadratic per contraction step of the algorithm and For large graphs the algorithm is far too slow. The assignment is to find and implement a faster algorithm to poaition the states.

### Translate CIF to mCRL2.

At the department of mechanical engineering the specification language CIF is used. This language cannot do evaluation of properties. The toolset mcrl2 toolset can provide verifications. There is a translator from CIF to mCRL2, but it is not optimal if there are many parallel processes. In this assignment it is requested to make a better translator. This assignment is together with dr.ir. Michel Reniers at the department of Mechanical Engineering.

If you visit me to discuss potential bachelor thesis assignments, I appreciate if you can bring a list of attended courses.