Bug Game - Revision history

RobinCodes: /* Growth Rate */ Fixed small typo

2025-11-02T18:59:10Z

Growth Rate: Fixed small typo

← Older revision		Revision as of 18:59, 2 November 2025
Line 15:		Line 15:

	== Growth Rate ==		== 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 (<math>2^{HW-2}</math>) mazes in each domain, ~~therefor~~ all can be searched and scored in finite time.		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 (<math>2^{HW-2}</math>) mazes in each domain, therefore all can be searched and scored in finite time.

	Furthermore, there is a known upper bound <math>Bug(H,W) \le 4^{HW}</math> first discovered by Daniel Yuan on 11 Sep 2025 ([https://discord.com/channels/960643023006490684/1362008236118511758/1415874391199449088] and [https://discord.com/channels/960643023006490684/1362008236118511758/1416144180039651401]) and further described by Shawn Ligocki ([https://discord.com/channels/960643023006490684/1362008236118511758/1416158428287602752]). 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 <math>v(a)</math> is the final visit count for a tile ''a'' and <math>deg(a)</math> is the degree (number of adjacent tiles), then for any two adjacent tiles ''a,b''		Furthermore, there is a known upper bound <math>Bug(H,W) \le 4^{HW}</math> first discovered by Daniel Yuan on 11 Sep 2025 ([https://discord.com/channels/960643023006490684/1362008236118511758/1415874391199449088] and [https://discord.com/channels/960643023006490684/1362008236118511758/1416144180039651401]) and further described by Shawn Ligocki ([https://discord.com/channels/960643023006490684/1362008236118511758/1416158428287602752]). 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 <math>v(a)</math> is the final visit count for a tile ''a'' and <math>deg(a)</math> is the degree (number of adjacent tiles), then for any two adjacent tiles ''a,b''

Polygon: Added category:functions

2025-11-02T18:53:56Z

Added category:functions

← Older revision		Revision as of 18:53, 2 November 2025
Line 137:		Line 137:
	* Original Game website: https://buglab.ru/		* Original Game website: https://buglab.ru/
	* Known Exact Values of Bug(H,W): [https://docs.google.com/spreadsheets/d/1eTaddIAiXGR--RvFbQfnwjXHVWMpPxDuOFKbgQ1XCoI/edit?usp=sharing Spreadsheet]		* Known Exact Values of Bug(H,W): [https://docs.google.com/spreadsheets/d/1eTaddIAiXGR--RvFbQfnwjXHVWMpPxDuOFKbgQ1XCoI/edit?usp=sharing Spreadsheet]

			[[Category:Functions]]

Isokate: Added source for Bug(7,7) = 218. (Feel free to change the text of the citation)

2025-10-03T18:51:08Z

Added source for Bug(7,7) = 218. (Feel free to change the text of the citation)

← Older revision		Revision as of 18:51, 3 October 2025
Line 77:		Line 77:
	</pre>		</pre>

	Bug(7,7) = 218		Bug(7,7) = 218 ([https://katelyndoucette.com/articles/bugs-mazes-and-bradys-algorithm Source])
	<pre>		<pre>
	#########		#########

Sligocki: /* Square Domains */ Add source for 8x8

2025-10-03T18:01:17Z

Square Domains: Add source for 8x8

← Older revision		Revision as of 18:01, 3 October 2025
Line 90:		Line 90:
	</pre>		</pre>

	Bug(8,8) = 506		Bug(8,8) = 506 ([https://discord.com/channels/960643023006490684/1362008236118511758/1423502208422510716 Discord Link])
	<pre>		<pre>
	##########		##########

Texanbytrade at 03:13, 3 October 2025

2025-10-03T03:13:26Z

← Older revision		Revision as of 03:13, 3 October 2025
Line 88:		Line 88:
	#..#-..F#		#..#-..F#
	#########		#########
			</pre>

	Bug(8,8) = 506		Bug(8,8) = 506

Texanbytrade: /* Square Domains */

2025-10-03T03:13:02Z

Square Domains

← Older revision		Revision as of 03:13, 3 October 2025
Line 88:		Line 88:
	#..#-..F#		#..#-..F#
	#########		#########
	~~</pre>~~Bug(8,8) = 506<pre>
			Bug(8,8) = 506
			<pre>
	##########		##########
	#S.#.....#		#S.#.....#

Texanbytrade: /* Square Domains */ added (8,8) to known champion list https://discord.com/channels/960643023006490684/1362008236118511758/1423502208422510716

2025-10-03T03:10:29Z

Square Domains: added (8,8) to known champion list https://discord.com/channels/960643023006490684/1362008236118511758/1423502208422510716

← Older revision		Revision as of 03:10, 3 October 2025
Line 88:		Line 88:
	#..#-..F#		#..#-..F#
	#########		#########
	</pre>		</pre>Bug(8,8) = 506<pre>

	~~== 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 [https://discord.com/channels/960643023006490684/1362008236118511758/1420062369429852160])~~
	<pre>
	##########		##########
	#S.#.....#		#S.#.....#
Line 106:		Line 100:
	##########		##########
	</pre>		</pre>

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

	Bug(19,29) ≥ 11,160,428 (Daniel Yuan 12 Sep 2025 [https://discord.com/channels/960643023006490684/1362008236118511758/1416241487452049469])		Bug(19,29) ≥ 11,160,428 (Daniel Yuan 12 Sep 2025 [https://discord.com/channels/960643023006490684/1362008236118511758/1416241487452049469])

Sligocki: Add Bug Game maze image

2025-10-01T18:55:41Z

Add Bug Game maze image

← Older revision		Revision as of 18:55, 1 October 2025
Line 1:		Line 1:
			[[File:Bug Game Example.png\|thumb\|An example of a Bug Game maze]]
	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/		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/

Sligocki: Created page with "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 == T..."

2025-09-30T17:11:56Z

Created page with "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 == T..."

New page

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 [https://buglab.ru/index.asp?main=avtors authors]) at "Нортландия" (Nortlandiya) summer school. It was shared as a CodeForce [https://codeforces.com/blog/entry/115144 competition on 16 Apr 2023]. It was introduced to the [[bbchallenge]] community by @savask on 11 Sep 2025 ([https://discord.com/channels/960643023006490684/1362008236118511758/1415723582989930679 Discord]).

== Rules ==
A maze is a rectangular grid of tiles. The top left corner tile is the bug starting position (<code>S</code>)) and the bottom right corner is the destination (<code>F</code>)). All other tiles may be set to either wall (<code>#</code>) or empty (<code>.</code>). 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 (<math>2^{HW-2}</math>) mazes in each domain, therefor all can be searched and scored in finite time.

Furthermore, there is a known upper bound <math>Bug(H,W) \le 4^{HW}</math> first discovered by Daniel Yuan on 11 Sep 2025 ([https://discord.com/channels/960643023006490684/1362008236118511758/1415874391199449088] and [https://discord.com/channels/960643023006490684/1362008236118511758/1416144180039651401]) and further described by Shawn Ligocki ([https://discord.com/channels/960643023006490684/1362008236118511758/1416158428287602752]). 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 <math>v(a)</math> is the final visit count for a tile ''a'' and <math>deg(a)</math> is the degree (number of adjacent tiles), then for any two adjacent tiles ''a,b''

<math display="block">v(a) \ge \left\lfloor \frac{v(b)}{deg(b)} \right\rfloor</math>

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

== 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 (<code>-</code>) 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
<pre>
####
#S-#
#.F#
####
</pre>

Bug(3,3) = 8
<pre>
#####
#S..#
#.#.#
#.#F#
#####
</pre>

Bug(4,4) = 20
<pre>
######
#S...#
#..###
#....#
#..#F#
######
</pre>

Bug(5,5) = 42
<pre>
#######
#S...##
#.....#
#.....#
#.#.###
#.#..F#
#######
</pre>

Bug(6,6) = 96
<pre>
########
#S.....#
#.###.##
#.#...##
#.#....#
#..#.###
#..#..F#
########
</pre>

Bug(7,7) = 218
<pre>
#########
#S.###..#
#......##
#.#.##..#
#..#...##
#..#....#
#...#.###
#..#-..F#
#########
</pre>

== 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 [https://discord.com/channels/960643023006490684/1362008236118511758/1420062369429852160])
<pre>
##########
#S.#.....#
#.#..##.##
#.#.##..##
#....##..#
#.#.#...##
#..##....#
#....#.###
#....#..F#
##########
</pre>

Bug(19,29) ≥ 11,160,428 (Daniel Yuan 12 Sep 2025 [https://discord.com/channels/960643023006490684/1362008236118511758/1416241487452049469])
<pre>
###############################
#S##.##.....#..#.##.....#....##
#.....##...#......#.#..##.##.##
#..#.#...#.#..##..#.##.##.#...#
#.....#.#...#.#...#..#.##.##.##
#..#.#...#.#...#.##.##.#...#.##
#..#.##.#...#.##.#...#.##.##.##
#.#...#..#.#..##..#.##.##.##.##
#..#.#...#.#...#.##.##.##.#...#
#.#...#.#...#.#...#.#...#.##.##
#..#.#...#.#...#.#..##.##..#.##
#.#..#..##.##.##..#.#...#.##..#
#..#..#.#...#.#..##.##.##.##.##
#..#.#...#.##..#.##.##.#..##.##
#.#...#.#...#.##.##.##.##.#..##
#..##...#..#..#...#.##.#..##..#
#...#..#.#.##.##.##.##.#.#...##
#..#.##.#...#..#.#...#.#.#....#
#.#......#....#...#.##.#.##.###
#...#....#....#.....##...##..F#
###############################
</pre>

Note: the [https://buglab.ru/index.asp?main=rating 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.

== See Also ==
* Original Game website: https://buglab.ru/
* Known Exact Values of Bug(H,W): [https://docs.google.com/spreadsheets/d/1eTaddIAiXGR--RvFbQfnwjXHVWMpPxDuOFKbgQ1XCoI/edit?usp=sharing Spreadsheet]