Magic Labyrinth – generating fair (or unfair) game boards

Magic Labyrinth is a cool game suitable for young children where players must navigate a maze to reach a goal, with the complication that the walls of the maze are NOT apparent until you run into them, forcing you to return to your start position.¹

Up to 4 players start from the corners of a 6 by 6 board. For each round of the game, the objective is to be the first to reach a randomly selected goal tile – in the picture below, the goal has a sword icon, which refers to a tile near the red token.

The tokens can be moved moved non-diagonally to reach the goal tile. The trick is that underneath the board is a maze consisting of walls that the players can’t see, but which will become evident if they try to move their token across a wall. Each token has a magnet that holds up a metal ball, which will be dislodged by the walls.

Back in 2018, we visited some friends with young kids and played Magic Labyrinth with them. The instructions come with two example mazes – an easier one with 19 walls and a harder one with 24 walls.

With only two example mazes, I thought it’d be interesting to code a tool to generate additional mazes, and to make sure they were relatively fair, regardless of which corner you started in. At the time, I was taking an online Python course, so it gave me an excuse to practice coding in Python. I also analyzed how fair the default example maze was.

Goal

• randomly generate board mazes
• analyze relative fairness, between each of the 4 corner starting positions

Plan

• function parameters: what size board (x by y) and how many walls to place
  • default board has 24 internal walls on a 6x6 board
• randomly place internal walls
• confirm that all squares are reachable (recursive connectivity search)
  • if any squares not reachable, restart
• test each valid goal square
  • all squares are potentially valid goal squares, except for the corner squares and the 2 tiles immediately adjacent
  • so for a 6x6 board, there are a total of 24 possible goal squares
  • for each corner starting position (4), determine the shortest path from each corner to each possible goal (recursive depth-first search)
• compare mean distance to all possible goals from each corner
  • if the mean shortest paths are relatively similar, consider it a fair board layout

Results

• to place 24 internal walls on a 6x6 board, it actually can take a lot of attempts to create a board with all positions reachable
• some boards are REALLY unfair to some corners

Some examples of generated boards

A pretty fair one:

    Generating 6 by 6 board with 24 walls
    Required 514 attempts
     _ _ _ _ _ _ 
    | |_  |    _|
    |_ _    |  _|
    |  _  |_   _|
    |_|  _  |_| |
    | |  _|  _ _|
    |_ _|_ _ _ _|
    
    Average # of steps to goals from (0, 0) = 6.67
    Average # of steps to goals from (0, 5) = 7.58
    Average # of steps to goals from (5, 0) = 6.25
    Average # of steps to goals from (5, 5) = 8.0
    Maximum difference of average distances = 1.75

Another very fair one:

    Generating 6 by 6 board with 24 walls
    Required 717 attempts
     _ _ _ _ _ _ 
    |_ _  |_   _|
    |_ _ _      |
    | | |_  |_| |
    |  _|  _   _|
    |    _|    _|
    |_|_|_ _|_ _|
    
    Average # of steps to goal from (0, 0) = 8.0
    Average # of steps to goal from (0, 5) = 7.17
    Average # of steps to goal from (5, 0) = 6.5
    Average # of steps to goal from (5, 5) = 6.92
    Maximum difference of average distances = 1.5

A pretty unfair one (stinks to start in the upper left hand corner; lower left hand corner is great):

    Generating 6 by 6 board with 24 walls
    Required 86 attempts
     _ _ _ _ _ _ 
    |_ _  | |_  |
    | |  _|    _|
    |  _  |_| | |
    |_  |_|_   _|
    |  _|  _    |
    |_ _ _ _ _|_|
    
    Average # of steps to goal from (0, 0) = 14.25
    Average # of steps to goal from (0, 5) = 7.0
    Average # of steps to goal from (5, 0) = 9.58
    Average # of steps to goal from (5, 5) = 8.58
    Maximum difference of average distances = 7.25

Analysis of the default board (with 24 walls)

²

It turns out that the default board with 24 walls isn’t very fair. I manually generated the board that we played on. You can see that starting out in the bottom right hand corner on average takes 2 more steps to reach the goal.

     _ _ _ _ _ _ 
    | |_  |_  | |
    |    _| |   |
    |_|_     _|_|
    |_   _|  _ _|
    | |  _  |   |
    |_ _|_ _ _|_|
    
    Average # of steps to goals from (0, 0) = 6.83
    Average # of steps to goals from (0, 5) = 6.92
    Average # of steps to goals from (5, 0) = 6.33
    Average # of steps to goals from (5, 5) = 8.83
    Maximum difference of average distances = 2.5

How many walls can be placed on a 6 x 6 board?

It also turns out that for a 6x6 board, 24 is close to the maximum number of internal walls you can place and still reach all positions.

• in 100,000 attempts, trying to place 26 internal walls FAILED to generate a connected graph
• trying to place 25 walls can work, but it can take a lot of attempts.

Here’s a really fair 25 wall board. It’s pretty unusual to see such an ‘fair’ board.

    Generating 6 by 6 board with 25 walls
    Required 1777 attempts
     _ _ _ _ _ _ 
    |  _  |  _| |
    | |_ _  |_  |
    |_ _ _|  _  |
    |    _  | |_|
    | |_| |_ _  |
    |_ _ _ _ _|_|
    
    Average # of steps to goal from (0, 0) = 7.5
    Average # of steps to goal from (0, 5) = 7.83
    Average # of steps to goal from (5, 0) = 7.58
    Average # of steps to goal from (5, 5) = 8.25
    Maximum difference of average distances = 0.75

Python code

Here’s the code used to generate and analyze the boards. I wrote this 6 years ago, and don’t really use Python, so I barely remember how it works…

class Square(object):
    '''
    Define object that represents a square on the board
    '''
    def __init__(self, name, neighbors):
        self.name = name
        self.neighbors = neighbors # array of names of reachable adjacent Nodes

def empty_board(num_x, num_y):
    '''
    Return empty board with all neighbors reachable
    '''
    board = {} # key is tuple of x,y coordinates, contains a Node object
    for x in range(num_x):
        for y in range(num_y):
            name = (x,y)
            neighbors = []
            if x != 0: # Add West, unless on left column
                neighbors.append((x - 1, y))
            if x != num_x - 1: # Add East, unless on right column
                neighbors.append((x + 1, y))
            if y != 0: # Add North, unless on top row
                neighbors.append((x, y - 1))
            if y != num_y - 1: # Add South, unless on bottom row
                neighbors.append((x, y + 1))
            board[name] = Square(name, neighbors) # create new node with associated neighbors
    return(board)

def check_connectivity(graph, connected, name):
    '''
    Recursive function to collect set of connected nodes
    - 'connected' is recursively extended to include set of node names that are connected
    '''
    connected.add(name) # add current node to set
    for neighbor in graph[name].neighbors: # iterate over current node's neighbors
        if neighbor not in connected: # avoid infinite recursion, already visited
            check_connectivity(graph, connected, neighbor) # visit the neighbor

def all_connected(board, num_x, num_y):
    '''
    Check connectivity
    - uses check_connectivity()
    - returns True if all connected
    '''
    connected = set() # initialize empty set of reached node names
    check_connectivity(board, connected, (0,0)) # start from node (0,0)
    return(len(connected) == (num_x * num_y))

def add_wall(board, square1, square2):
    '''
    Add a wall (i.e., remove connections) in 'board' between square1 and square2, bidirectionally
    - alternatively, if don't want to 'try / except': if square2 in board[square1].neighbors
    '''
    success = True
    try:
        board[square1].neighbors.remove(square2)
    except: # print(square1, 'is not connected to', square2)
        success = False
    try:
        board[square2].neighbors.remove(square1)
    except: # print(square2, 'is not connected to', square1)
        success = False
    return success

def DFS(graph, start, end, path, shortest):
    '''
    Depth-first search, accessed via shortestPath function
    - returns entire path, or None if no path found
    - len(path) - 1 would equal number of steps needed
    '''
    path = path + [start]
    if start == end:
        return path
    for node in graph[start].neighbors:
        if node not in path: # avoid cycles
            if shortest == None or len(path) < len(shortest):
                newPath = DFS(graph, node, end, path, shortest)
                if newPath != None:
                    shortest = newPath
    return shortest

def shortestPath(graph, start, end):
    '''
    Uses DFS() to return shortest path (or None)
    '''
    return DFS(graph, start, end, [], None)

def print_board(board, num_x, num_y):
    '''
    Prints out a board (needs a monospace font)
    - for each row (y), prints the NS walls and the lower EW walls
    - [ ] should group board / num_x / num_y all into an object
    '''
    # First generate the wall at the north edge of the board
    s = ' '
    for x in range(num_x):
        s += '_ '
    print(s)
    
    # Then generate each row, including the southern walls of each square
    for y in range(num_y):
        s = '|'
        for x in range(num_x):
            if (x, y + 1) in board[(x, y)].neighbors:
                s += ' '
            else:
                s += '_'
            if (x + 1, y) in board[(x, y)].neighbors:
                s += ' '
            else:
                s += '|'
        print(s)

def generate_board(num_wall = 24, num_x = 6, num_y = 6, max_attempts = 10000):
#     num_wall = 24 # number of internal walls to place; 26 on a 6x6 seems near impossible
#     num_x = 6     # width of board
#     num_y = 6     # height of board
#     max_attempts = 10000
    from random import randint

    attempts = 0
    while attempts < max_attempts:
        attempts += 1
        board = empty_board(num_x, num_y)
        for i in range(num_wall):
            while True:
                x = randint(0, num_x - 1)
                y = randint(0, num_y - 1)
                square1 = (x, y)

                direction = randint(0, 3)
                if direction == 0:
                    square2 = (x - 1, y)
                elif direction == 1:
                    square2 = (x + 1, y)
                elif direction == 2:
                    square2 = (x, y - 1)
                elif direction == 3:
                    square2 = (x, y + 1)
                else:
                    print('*** ERROR ***')

                if add_wall(board, square1, square2) == True: # successfully added wall
                    break

        if all_connected(board, num_x, num_y) == True:
            return(board, num_wall, num_x, num_y, attempts)
        
    return(None, num_wall, num_x, num_y, attempts)

Setting up parameters and running the code:

(board, num_wall, num_x, num_y, attempts) = generate_board(num_wall = 24, num_x = 6, num_y = 6, max_attempts = 10000)
corners = [(0, 0), (0, num_y - 1), (num_x - 1, 0), (num_x -1, num_y - 1)]
invalid_goals = corners + [ (0,1), (1,0), (0, num_y - 2), (1, num_y - 1), (0, num_x - 2), (1, num_x - 1), (num_x - 1, num_y - 2), (num_x - 2, num_y - 1) ]

print('Generating', num_x, 'by', num_y, 'board with', num_wall, 'walls')

if board is not None:
    print('Required', attempts, 'attempts')
    print_board(board, 6, 6)
    print()

    # Set as goal every possible square EXCEPT those adjacent to corners
    # - determine mean shortest distances from each corner
    total_distance = {}
    for corner in corners:
        total_distance[corner] = 0

    for x in range(num_x):
        for y in range(num_y):
            goal = (x,y)
            if goal not in invalid_goals:
                for start in corners:
                    total_distance[start] += len(shortestPath(board, start, goal)) - 1

    for start in corners:
        print('Average # of steps to goal from', start, '=', round(total_distance[start] / (num_x * num_y - 12), 2))
        
    ave_distances = [round(total_distance[start] / (num_x * num_y - 12), 2) for start in corners]
    print('Maximum difference of average distances =', max(ave_distances) - min(ave_distances))

else:
    print('Failed to generate board in', attempts, 'attempts')

Quick hack to manually create and analyze the 24-wall default board:

# Test default board

print('Default board')

num_x = 6
num_y = 6
corners = [(0, 0), (0, num_y - 1), (num_x - 1, 0), (num_x -1, num_y - 1)]
invalid_goals = corners + [ (0,1), (1,0), (0, num_y - 2), (1, num_y - 1), (0, num_x - 2), (1, num_x - 1), (num_x - 1, num_y - 2), (num_x - 2, num_y - 1) ]

board = empty_board(num_x, num_y)

add_wall(board, (0,0), (1,0))
add_wall(board, (2,0), (3,0))
add_wall(board, (4,0), (5,0))
add_wall(board, (2,1), (3,1))
add_wall(board, (3,1), (4,1))
add_wall(board, (0,2), (1,2))
add_wall(board, (4,2), (5,2))
add_wall(board, (2,3), (3,3))
add_wall(board, (0,4), (1,4))
add_wall(board, (3,4), (4,4))
add_wall(board, (1,5), (2,5))
add_wall(board, (4,5), (5,5))

add_wall(board, (0,2), (0,3))
add_wall(board, (0,3), (0,4))
add_wall(board, (1,0), (1,1))
add_wall(board, (1,2), (1,3))
add_wall(board, (2,1), (2,2))
add_wall(board, (2,3), (2,4))
add_wall(board, (2,4), (2,5))
add_wall(board, (3,0), (3,1))
add_wall(board, (4,2), (4,3))
add_wall(board, (4,3), (4,4))
add_wall(board, (5,2), (5,3))
add_wall(board, (5,3), (5,4))

print_board(board, 6, 6)
print()

# Set as goal every possible square EXCEPT those adjacent to corners
# - determine mean shortest distances from each corner
total_distance = {}
for corner in corners:
    total_distance[corner] = 0

for x in range(num_x):
    for y in range(num_y):
        goal = (x,y)
        if goal not in invalid_goals:
            for start in corners:
                total_distance[start] += len(shortestPath(board, start, goal)) - 1

for start in corners:
    print('Average # of steps to goals from', start, '=', round(total_distance[start] / (num_x * num_y - 12), 2))

ave_distances = [round(total_distance[start] / (num_x * num_y - 12), 2) for start in corners]
print('Maximum difference of average distances =', max(ave_distances) - min(ave_distances))

Footnotes

1. Most images are from the Amazon product page

2. From the Magic Labyrinth game instructions