THIS IS HISTORY! Check fabien.benetou.fr for news.

Seedea, scalable creativity

Xye, consultancy for serious creators

Information

CoEvolution > Oimp > Dynalab

Dynalab, the dynamic labyrinth

Team
Initiator : Fabien

Goal

Find the algorithm behind walls re-disposition rather than a classical absolute path to escape the labyrinth before your opponent!

Competition

each player start into each other labyrinth and see who is the first to get out

Rules

• wall change only after each player step (not based on reflexes)
• at least 1 possible path always available (impossible to entirely block a player, as opposed to Go)
• wall changing strategy is designed before the game starts (no live change)

Constraints

to spice up the game

• initial configuration (number of "wall" already set)
• per step time limit
• pre-game algo time limit
• per step + pre-game algo time limit
• no help allowed (mapping, simulations, MAS, ...)

Complexity

to make it entertaining for newcomers as well as hardcore gamers

• size
• dimensions
• number of "wall" that can be changed per step
• ability to use a memory of the path the adversary player took

Realization

• 1 matrice per player
• each turn you are able to apply a transformation to your own (moving) and let your pre-written algorithm on the other (changing the walls)

Proposed solution

to update in order to reflect the change ob being able to escape only after the NEXT transformation

```mazes[number_of_players]
maze[size^dimension],initiation_function,transformation_function

bool path_exist(maze,position,position)
bool exit_path_exist(maze)
bool player_exited(maze)
maze initiate_maze(maze,initiation_function)
maze transform_maze(maze,transformation_function)
maze move_player(maze,new_position)
position get_position(maze)
null display_maze(maze)

for(i=0,number_of_players,i++)
if (i+1 >= number_of_players) j=0 else j=i
mazes[i].maze = initiate_maze(mazes[i].maze,mazes[j].initiation_function)
if (!exit_path_exist(mazes[i].maze)) exit "player J lost, no path available"

while (1)
for(i=0,number_of_players,i++)
if (i+1 >= number_of_players) j=0 else j=i
display_maze(mazes[i].maze)
display_maze(mazes[i].maze)
move_player(mazes[i].maze,new_position)
if ( player_exited(mazes[i].maze) ) exit "player I won"
mazes[i].maze = transform_maze(mazes[i].maze,mazes[j].transformation_function)
if (!exit_path_exist(mazes[i].maze)) exit "player J lost, no path available"
```

Examples of initiation_function

maze[3^2], start=0,0 arrival=2,2

```	S11
011
00A
```

PS : using "block" for walls is easier but it can "crush" the player, thus when the user is "crushed" he is just "bumped" at the closest point of a path (which can be lucky or unlucky, eventually using probabilities to position oneself according to the guess transformation should be part of the strategy). That seems strange but it's precisely the specificity of the dynamic aspect that doesn't appear in classical labyrinths.

Examples of transformation_function

without using : position_of_player, number_of_iterations, random, set_wall_off, set_wall_on, ...

only possible primitives : switch_wall, fill_holes

```	for(i,j) in maze
switch_wall
```

would give

```	S11    S00
011 -> 100
00A    11A
```