Bug Game

The Bug Game is an optimization game in which players design a 2d maze that a bug will be slowest to solve. The bug follows a relatively simple algorithm which preferentially visits locations less visited which is guaranteed to always eventually find a way to the destination (if such a path exists), but by exploiting the details of the tie-breaking logic, some mazes can trap the bug for a long time. You can play online at https://buglab.ru/

History

The Bug Game was invented by a group of Russian students and their teacher (see authors) at "Нортландия" (Nortlandiya) summer school. It was shared as a CodeForce competition on 16 Apr 2023. It was introduced to the bbchallenge community by @savask on 11 Sep 2025 (Discord).

Rules

A maze is a rectangular grid of tiles. The top left corner tile is the bug starting position (S)) and the bottom right corner is the destination (F)). All other tiles may be set to either wall (#) or empty (.). The maze has implicit walls around the outside of this rectangle. The domain (or rectangular grid size) is specified as HxW (height by width), the original buglab and CodeForce challenges are for the 19x29 domain.

For a given maze, the bug is placed on the start position (facing up) and repeatedly makes a step until it reaches the destination. At each stem, the bug will move to the orthogonally adjacent empty tile which has been visited least. If there is a tie then the bug will tie break among those least visited options by first preferring to continue to go straight ahead and second preferring directions in the order Down, Right, Up, Left.

The score of a maze is the number of steps needed for the bug to reach the destination. Bug(H,W) is the maximum score across all HxW mazes. The champion mazes (for a given domain) are the collection of mazes which score this maximum value.

A helpful abstraction is to think about a maze as an undirected graph/network with each tile as a node and adjacent tiles connected by edges.

Growth Rate

Bug(H,W) is a computable function. For every maze, if there is a path to the destination, the bug will eventually succeed in finite time. It is also computable to detect that there exists a path to the destination (this is a graph connectivity problem). And finally there are finitely many ( $2^{HW-2}$ ) mazes in each domain, therefor all can be searched and scored in finite time.

Furthermore, there is a known upper bound $Bug(H,W)\leq 4^{HW}$ first discovered by Daniel Yuan on 11 Sep 2025 ([1] and [2]) and further described by Shawn Ligocki ([3]). The crux of the argument is that there is a limit to how different the visit counts of any two adjacent tiles can be. Specifically, if $v(a)$ is the final visit count for a tile a and $deg(a)$ is the degree (number of adjacent tiles), then for any two adjacent tiles a,b

v(a)\geq \left\lfloor {\frac {v(b)}{deg(b)}}\right\rfloor

In a rectangular grid, $deg(b)\leq 4$ and so we have approximately $v(b)\leq 4v(a)$ (due to the floor function, the exact relationship is slightly weaker like $v(b)+1<=4(v(a)+1))$ ). Then you can calculate maximum visit counts for all tiles/nodes and sum them up, this can never by greater than $4^{HW}$ .

Known Champions

This is a list of some known values for Bug function and an example champion (there may be other champions tied for first place not listed). In the mazes below (-) indicates that this tile may be either wall or empty, it does not matter because the bug never visits that tile.

Square Domains

Bug(2,2) = 2

####
#S-#
#.F#
####

Bug(3,3) = 8

#####
#S..#
#.#.#
#.#F#
#####

Bug(4,4) = 20

######
#S...#
#..###
#....#
#..#F#
######

Bug(5,5) = 42

#######
#S...##
#.....#
#.....#
#.#.###
#.#..F#
#######

Bug(6,6) = 96

########
#S.....#
#.###.##
#.#...##
#.#....#
#..#.###
#..#..F#
########

Bug(7,7) = 218

#########
#S.###..#
#......##
#.#.##..#
#..#...##
#..#....#
#...#.###
#..#-..F#
#########

Current Champions

These are some best known mazes (and scores) for domains that have not been exhaustively solved yet.

Bug(8,8) ≥ 506 (Katelyn Doucette 23 Sep 2025 [4])

##########
#S.#.....#
#.#..##.##
#.#.##..##
#....##..#
#.#.#...##
#..##....#
#....#.###
#....#..F#
##########

Bug(19,29) ≥ 11,160,428 (Daniel Yuan 12 Sep 2025 [5])

###############################
#S##.##.....#..#.##.....#....##
#.....##...#......#.#..##.##.##
#..#.#...#.#..##..#.##.##.#...#
#.....#.#...#.#...#..#.##.##.##
#..#.#...#.#...#.##.##.#...#.##
#..#.##.#...#.##.#...#.##.##.##
#.#...#..#.#..##..#.##.##.##.##
#..#.#...#.#...#.##.##.##.#...#
#.#...#.#...#.#...#.#...#.##.##
#..#.#...#.#...#.#..##.##..#.##
#.#..#..##.##.##..#.#...#.##..#
#..#..#.#...#.#..##.##.##.##.##
#..#.#...#.##..#.##.##.#..##.##
#.#...#.#...#.##.##.##.##.#..##
#..##...#..#..#...#.##.#..##..#
#...#..#.#.##.##.##.##.#.#...##
#..#.##.#...#..#.#...#.#.#....#
#.#......#....#...#.##.#.##.###
#...#....#....#.....##...##..F#
###############################

Note: the BugLab Ratings page lists the current 19x29 champion at score 100,353,979,636 (as of 30 Sep 2025). But the actual maze is a secret.