GROOVE

What is more fun then comparing your tool to other’s? AGTIVE 2007 – The third International Workshop and Symposium on Applications of Graph Transformation with Industrial Relevance – has opened a Graph Transformation Tools Contest. We decided to join this contest with our GROOVE toolkit.

We have chosen to do two out of the three presented case studies: the Ludo game and the Sierpinsky triangles. While solving these problems we stumbled on some minor issues in the tools, which have been dealt with and included in this version of the tool (to be used as any nightly build of the tool).

Ludo
In this case study the goal was to model the Ludo game. We focussed on allowing for different strategies per player. Also, the die-roll has been kept non-deterministic (every time a die is rolled there are 6 possible choices to continue). For simulation we use the barbed exploration strategy, that randomly chooses one of the available paths until a final state (where no more transitions are possible) is found. When a loop is encountered the strategy will follow known paths until an unexplored branching is encountered where it will continue. The grammar representing the game contains 16 rules: 9 rules to model the game-rules, 3 extra rules (that override, whith priority, general game rules) for player-strategies and 4 rules to identify the winner in the generated state space. Simulation creates a statespace that varies from 1400 to 5000 states, where the path to the final state contains about 50% of the states, the other states are unexplored die-rolls. Ludo Grammar

Sierpinsky Triangles
This case study focusses on performance. The sierpinsky triangle is a phase-wise simulation, where every phase’s size grows by a factor of 3, as does the size of the state. A performance analysis has been done on the duration of completing the simulation up to a certain phase. The number of possible matches in the beginning of every phase also grows with a factor 3. Hence, we use a linear exploration strategy here, which applies the first match of a rule found until a final state has been reached. The grammar contains two rules. One for transforming a triangle into three triangles (which can be applied until all triangles have been split), and one that jumps to the next phase. We managed to complete phase 12 after some optimizations in GROOVE. Sierpinsky Grammar