(:addthis:)

Dynalab, the dynamic labyrinth

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)

Environment

Project Darkstar by Sun
Croquet / Cobalt
- DualMaze by Dave Faught (daf)
Second Life
- Second Life Maze Builder by Scott (still limited to 2D mazes though)

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 ask_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)
			while (!path_exist(mazes[i].maze,get_position(mazes[i].maze),new_position=ask_position()))
				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

Potential resources for strategies

"reversed" shortest path problematic and publications in Operations Resarch
Non-Myopic Active Learning: A Reinforcement Learning Approach by Pascal Poupart, University of Waterloo, Google, March 2009
in a broader sense Theory of Mind

Inspiration

dynamic labyrinth p396 of The Diamond Age

References

publication history on Eleusis by Martin Gardner
Cube the movie
Dataflow Programming

Page last modified on August 20, 2010, at 09:29 AM