# Constructing an evil maze against random exploration

RollerCoaster Tycoon 2's maze is the inspiration for this question. Credit to Marcel Vos for thoroughly breaking the classic RCT2 AI. The pathfinding AI in this question is the AI in the latest version of OpenRCT2 at the time of writing, which was updated in response to that video.

Suppose a guest enters a $$\w \times h\$$ grid maze with the following strategy in mind:

After every step I pick a random valid direction except backwards, unless I have no other choice but to go back.

We are evil and wish to construct the maze that takes the most amount of time on average to solve using the above strategy.

This is a code-challenge. The winner is the answer that contains a $$\100 \times 100\$$ maze with the greatest mean solve time using the above strategy. In the case of a tie the earlier poster wins.

A $$\w \times h\$$ maze is a $$\w \times h\$$ grid of square tiles. It has two designated start tiles along the border, connected either horizontally or vertically, and similarly two designated exit squares, along the border, connected either horizontally or vertically. Between each tile there may or may not be a wall (with the exception of the two start and two end tiles, they must be directly connected to their partner). There is always a border of walls around the grid.

The guest enters with a 50/50% chance on either start tile, facing away from the other tile. Then the guest starts exploring the maze one step at a time. At the start of a step the guest looks to its left, forward and right (relative to its current direction) and checks for walls. It chooses a random new direction with uniform chance from the unobstructed directions. If and only if all other directions are obstructed it chooses to go backwards instead.

The guest wanders around as such until it reaches one of the two exit squares, which will cause the guest to immediately exit. The average number of steps it takes for this to happen is your score, the bigger the better. If the start and exit are not connected your maze is invalid and has no score.

To accurately score mazes I wrote a judge program in Python that uses Markov chains to compute your score mathematically. It requires Python 3, numpy, scipy and imageio to run (an optional dependency for a speedup is scikit-umfpack). In addition, the judge contains functions to output an image of your maze, as well as a compressed representation of your maze. Please familiarize yourself with the judge program before starting this challenge.

Please include (a link to) a $$\100\times 100\$$ compressed maze as generated by the judge program in your answer. Your answer will be scored based on this. An answer without a concrete, specific solution maze is invalid.

• I think that the time can never be exponential in the graph size? (I can't prove this, but I can't find any exponential solution either) Aug 6, 2020 at 13:54
• Are you sure the start and end tiles are drawn correctly? I have line maze.set_exit(0, maze.height-1, 0, maze.height-2) which calculates correctly apparently but draws with axes flipped?
– qwr
Aug 6, 2020 at 20:38
• Note that pillow images are usually row-major order, meaning indexing is done img[y,x].
– qwr
Aug 6, 2020 at 21:11
• The mazes could be made really evil with one-way gates.
– qwr
Aug 7, 2020 at 2:00
– orlp
Aug 7, 2020 at 2:30

# No dead ends near the entrance, 21,477,560 21,485,005

Try it online!

Yay, 21 million. The giant horizontal segments up to row 19 are also removed, so about 20% of the entire grid is just an open space.

Also, as the "real maze" starts at the leftmost column, moving the entrance to the top right gives a slight bump to the score. (Thanks to @Neil)

# Previous version, 20,211,703

Try it online!

Yes, 20 million. It's actually good to remove some dead ends and add some open spaces near the entrance, but it stops being good as it gets sufficiently far away from it.

This is a derivation from width-3 dead end maze by removing some h-walls (it's called h-walls in the code, but it is a vertical segment in the image):

• The h-walls from row 1 to row 22 (inclusive) are entirely removed.
• The h-walls from row 23 to row 40 (inclusive) are reduced by half, keeping the odd indices.
• Moving the start to 99, 0, 99, 1 bumps your score up a bit more.
– Neil
Aug 7, 2020 at 9:06

# Tridents, score 21,947,177 21,951,598

UEsDBBQAAAAIAAAAIQAL/+yrSgAAAIgAAAAJABQAYXJyXzAubnB5AQAQAIgAAAAAAAAASgAAAAAAAACb7BfqGxDJyFDGUK2eklqcXKRupaBuk2mirqOgnpZfVFKUmBefX5SSChJ3S8wpTgWKF2ckFqQC+RpGOpo6CrUKFACuFAYGBhAGAFBLAwQUAAAACAAAACEAlmPInE8AAACQAAAACQAUAGFycl8xLm5weQEAEACQAAAAAAAAAE8AAAAAAAAAm+wX6hsQychQxlCtnpJanFykbqWgbpNpoq6joJ6WX1RSlJgXn1+UkgoSd0vMKU4FihdnJBakAvkaRjoKRpo6CrUKZAOuZAYGhiQgToZiAFBLAwQUAAAACAAAACEAX1d180sAAACQAAAACQAUAGFycl8yLm5weQEAEACQAAAAAAAAAEsAAAAAAAAAm+wX6hsQychQxlCtnpJanFykbqWgbpNpoq6joJ6WX1RSlJgXn1+UkgoSd0vMKU4FihdnJBakAvkaRjoKRpo6CrUKZAMuBihghNIAUEsDBBQAAAAIAAAAIQCi1p2qngAAACwnAAAJABQAYXJyXzMubnB5AQAQACwnAAAAAAAAngAAAAAAAADt2jEKAkEMheFM6ynSRWGK3XI9gJ1iY2EloztiIa7MLDbqKbywuydYcLD7QwjkEfgukM9mt97unTzkaW3Mp2RLtdexNq927lKfwu3QpTaO+SpccxzyfAn3OOzzpvFaV9XC61t/q5mIcyJlc6rceFfUGBgYGBgYGBgYGBgYGBgYGBgYGBgYGBgYGBgYGBgYGBgYGBgYGP8zpPCVbNr4AlBLAwQUAAAACAAAACEAXL51PqgAAAAsJwAACQAUAGFycl80Lm5weQEAEAAsJwAAAAAAAKgAAAAAAAAA7dohDgIxEIXhqeUUdQNJxa5cDoCDYBAoUtgSBGFJSzDAKbgwW4GFDTWI/7V5Scd8re9zsZov10auctM2pF3UqdX7tlZndd/FS/SnTRfbkOczf0yhn6eDP4f+PK6rytmmmTj7sL9lJGIkp6S/xORlSnoQUrohICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICD+kij7f2UGvULeNynpT3kBUEsBAhQAFAAAAAgAAAAhAAv/7KtKAAAAiAAAAAkAAAAAAAAAAAAAAIABAAAAAGFycl8wLm5weVBLAQIUABQAAAAIAAAAIQCWY8icTwAAAJAAAAAJAAAAAAAAAAAAAACAAYUAAABhcnJfMS5ucHlQSwECFAAUAAAACAAAACEAX1d180sAAACQAAAACQAAAAAAAAAAAAAAgAEPAQAAYXJyXzIubnB5UEsBAhQAFAAAAAgAAAAhAKLWnaqeAAAALCcAAAkAAAAAAAAAAAAAAIABlQEAAGFycl8zLm5weVBLAQIUABQAAAAIAAAAIQBcvnU+qAAAACwnAAAJAAAAAAAAAAAAAACAAW4CAABhcnJfNC5ucHlQSwUGAAAAAAUABQATAQAAUQMAAAAA


Based on @Bubbler's answer, but some tinkering about with a wall finding algorithm led me to tweak the layout slightly:

Edit: Slightly improved my score by changing the exit orientation, which allowed me to use the trident shape there too. For some reason (I'm not ruling out human error) not only did @isaacg's "tricky routing" not affect the score for this layout but also my "trident exit" doesn't seem to affect the score for his layout...

I actually wrote a script where I could parametrise the number of long horizontal lines, how many of them had teeth, how many of them had gappy teeth, and how many of the ends had prongs, and this was the best I could come up with (also my wall finder couldn't find a way of improving it). Try it online!

• "Note that due to a display issue the start and exit display horizontally but they are actually both vertical." I've fixed this bug already, please download the latest version of the judge :)
– orlp
Aug 8, 2020 at 0:10
• @orlp I'm not sure how much difference it makes to my wall finder, but I think I'll stick to unrounded scores for its algorithm for now.
– Neil
Aug 8, 2020 at 16:33
• Turning that sideways looks about as good as the nonsense I had at the end. Aug 15, 2020 at 16:03
• @isaacg Indeed, I had already tried the extra side version, and the score came out equal to yours to with an accuracy of <1e-10.
– Neil
Aug 15, 2020 at 16:11

# Two sides of mazes, score 21987725

UEsDBBQAAAAIAAAAIQChBYC8SQAAAJAAAAAJAAAAYXJyXzAubnB5m+wX6hsQychQxlCtnpJanFykbqWgbpNpoa6joJ6WX1RSlJgXn1+UkgoSd0vMKU4FihdnJBakAvkaRjqaOgq1ChQArhQGCIDRAFBLAwQUAAAACAAAACEAkzeCEkwAAACgAAAACQAAAGFycl8xLm5weZvsF+obEMnIUMZQrZ6SWpxcpG6loG6TaaGuo6Cell9UUpSYF59flJIKEndLzClOBYoXZyQWpAL5GkY6CkaaOgq1CmQDLgYcgBFKAwBQSwMEFAAAAAgAAAAhAJBqs1pOAAAAoAAAAAkAAABhcnJfMi5ucHmb7BfqGxDJyFDGUK2eklqcXKRupaBuk2mhrqOgnpZfVFKUmBefX5SSChJ3S8wpTgWKF2ckFqQC+RpGOgpGmjoKtQpkA65kBghAp5OgNABQSwMEFAAAAAgAAAAhAEghScnMAAAALCcAAAkAAABhcnJfMy5ucHnt2jEOgjAUgOF29RTdqgkDjHgAN42Lg5NBqXEwaopxUU/hhQVP8F4xhOF/IS+hy5eSf+Sz2izXW2se5unr0Byinzv/2hc+c/54jfdYXXbXWIfufFGdm9CeN6fqFtr3aVlmrsjzWebeLm0mJnnsb0l2H8MKHwwMDAwMDAwMDAwMDAwMDAwMDAwMjP8byTPAPVRGH0Vs9PhaY7pHukBXGoWupAJdaRS6kgp0pVHoSirQlUahK6lAVxqFrqQCXWmUsXRlBrhHt5IF8U9k9gtQSwMEFAAAAAgAAAAhACNNXj3ZAAAALCcAAAkAAABhcnJfNC5ucHnt2rEKwjAUheFk9SmyRaFDO9YHcFNcHJyk2oiDWEnFRX0KX9g6uGq5gXKRP4RAu3w9J3fsc7GaL9fWXM3N16HdRT91/r4tfOb8vomXWJ02TazD+/2sOrahe98eqnPonsdFnmeuLCeZezjZGhnpsr3PBMJa2+tMIPpuCAgICAgICAgICAgICAgICAgICAiIb1u4dKUQx9BF/MV1D0AwUXqKEmdQRTBReooSZ1BFMFF6ihJnUEUwUXqKEmdQRTBReooSZ1BF/MNEJTQ1RFH9/r9KuW7z+cIfpzUvUEsBAhQDFAAAAAgAAAAhAKEFgLxJAAAAkAAAAAkAAAAAAAAAAAAAAIABAAAAAGFycl8wLm5weVBLAQIUAxQAAAAIAAAAIQCTN4ISTAAAAKAAAAAJAAAAAAAAAAAAAACAAXAAAABhcnJfMS5ucHlQSwECFAMUAAAACAAAACEAkGqzWk4AAACgAAAACQAAAAAAAAAAAAAAgAHjAAAAYXJyXzIubnB5UEsBAhQDFAAAAAgAAAAhAEghScnMAAAALCcAAAkAAAAAAAAAAAAAAIABWAEAAGFycl8zLm5weVBLAQIUAxQAAAAIAAAAIQAjTV492QAAACwnAAAJAAAAAAAAAAAAAACAAUsCAABhcnJfNC5ucHlQSwUGAAAAAAUABQATAQAASwMAAAAA


Based on @Neil's trident design, but I added an extra side of mazes, and also did some tricky routing right at the end to improve the score a bit more.

It turned out to be optimal to have the blank region be a perfect square, which I didn't expect, due to the asymmetry of the maze region. The blank region is 58x58, and there are 14 rows of maze on each side.

I really wanted to get to 22 million, but I had to stop just short. I tried lots of designs that didn't improve anything, like making the blank region nonrectangular, or making the design symmetrical across the main axis. None of that helped.

Try it online!

• The symmetry doesn't affect the score much. The board can be considered as an undirected graph (with each cell a node and two cells have an edge iff they're adjacent and not separated with a wall), and two boards with the same graph has the same score. Aug 10, 2020 at 2:32
• I double-checked and you can also alternate each pair of paths between horizontal and vertical (which is visually slightly more pleasing) for the same score.
– Neil
Aug 13, 2020 at 9:27
• I just noticed that the area of our blank regions is similar (mine is 3400 and yours is 3364).
– Neil
Aug 13, 2020 at 9:30
• The "tricky routing" makes a whole world of difference; with my original routing the score is only 21983310 and I can beat that using a row of 2-way branches and 11 rows of 3-way branches, then 16 rows of 3-way branches in the opposite axis, scoring 21985758.
– Neil
Aug 14, 2020 at 10:25
• I also tried extending the "tricky routing" along the length of the row, but it turns out that this makes no difference to the score at all.
– Neil
Aug 14, 2020 at 10:57

# Even more dead ends, 16,555,009.5

UEsDBBQAAAAIAAAAIQChBYC8SQAAAJAAAAAJABQAYXJyXzAubnB5AQAQAJAAAAAAAAAASQAAAAAAAACb7BfqGxDJyFDGUK2eklqcXKRupaBuk2mhrqOgnpZfVFKUmBefX5SSChJ3S8wpTgWKF2ckFqQC+RpGOpo6CrUKFACuFAYIgNEAUEsDBBQAAAAIAAAAIQCcpkBwTAAAAKAAAAAJABQAYXJyXzEubnB5AQAQAKAAAAAAAAAATAAAAAAAAACb7BfqGxDJyFDGUK2eklqcXKRupaBuk2mhrqOgnpZfVFKUmBefX5SSChJ3S8wpTgWKF2ckFqQC+RpGOgpGmjoKtQpkAy4GNMCIxgcAUEsDBBQAAAAIAAAAIQAsPfLMTwAAAKAAAAAJABQAYXJyXzIubnB5AQAQAKAAAAAAAAAATwAAAAAAAACb7BfqGxDJyFDGUK2eklqcXKRupaBuk2mhrqOgnpZfVFKUmBefX5SSChJ3S8wpTgWKF2ckFqQC+RpGOgpGmjoKtQpkAy4GKEhmQAVJUBoAUEsDBBQAAAAIAAAAIQAYEnl9jgAAACwnAAAJABQAYXJyXzMubnB5AQAQACwnAAAAAAAAjgAAAAAAAADtzbENwjAUhGG7ZYrXPZBcxGUYIB0oDUUqZIgRRUSQHaUBpsjCmBWQqPhP19w137I/7NrOmtk8tI/5nHQr+jx5daKXMU0p3I5j6uPnb8KQY/nzNdxj2eu6duKrauPkJd9lZaz9eTEwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDD+23gDUEsDBBQAAAAIAAAAIQBg04Z/fgAAACwnAAAJABQAYXJyXzQubnB5AQAQACwnAAAAAAAAfgAAAAAAAADt2jEKwkAQheFJ6ymmG4UtkjIewE6xsbAKG7NiIUZ2g43JKbxwkisEAhb/42PgvTPM73Q5nq+ZfORrTUi3aHu1vi7Mqd3b2EX/qtrYhHk/+GcK054e/h2mvi3y3GlZ7pwOuiwbyWTOqhcAAAAAAAAAAAAAAAAA8M/W/iITGQFQSwECFAMUAAAACAAAACEAoQWAvEkAAACQAAAACQAAAAAAAAAAAAAAgAEAAAAAYXJyXzAubnB5UEsBAhQDFAAAAAgAAAAhAJymQHBMAAAAoAAAAAkAAAAAAAAAAAAAAIABhAAAAGFycl8xLm5weVBLAQIUAxQAAAAIAAAAIQAsPfLMTwAAAKAAAAAJAAAAAAAAAAAAAACAAQsBAABhcnJfMi5ucHlQSwECFAMUAAAACAAAACEAGBJ5fY4AAAAsJwAACQAAAAAAAAAAAAAAgAGVAQAAYXJyXzMubnB5UEsBAhQDFAAAAAgAAAAhAGDThn9+AAAALCcAAAkAAAAAAAAAAAAAAIABXgIAAGFycl80Lm5weVBLBQYAAAAABQAFABMBAAAXAwAAAAA=


The guests now have 3 choices per intersection for most intersections, however there are only about 2/3 as many intersections. Of 34 corridors, the first and last corridors have 98 two-way branches, and 32 corridors have 2 two-way branches and 98 three-way branches. (I didn't count carefully)

• As a hint towards further progress, believe it or not but this outscores your answer by around 2%.
– orlp
Aug 7, 2020 at 4:53

# Empty maze, score 51113

UEsDBBQAAAAIAAAAIQChBYC8SQAAAJAAAAAJAAAAYXJyXzAubnB5m+wX6hsQychQxlCtnpJanFykbqWgbpNpoa6joJ6WX1RSlJgXn1+UkgoSd0vMKU4FihdnJBakAvkaRjqaOgq1ChQArhQGCIDRAFBLAwQUAAAACAAAACEAkzeCEkwAAACgAAAACQAAAGFycl8xLm5weZvsF+obEMnIUMZQrZ6SWpxcpG6loG6TaaGuo6Cell9UUpSYF59flJIKEndLzClOBYoXZyQWpAL5GkY6CkaaOgq1CmQDLgYcgBFKAwBQSwMEFAAAAAgAAAAhAJBqs1pOAAAAoAAAAAkAAABhcnJfMi5ucHmb7BfqGxDJyFDGUK2eklqcXKRupaBuk2mhrqOgnpZfVFKUmBefX5SSChJ3S8wpTgWKF2ckFqQC+RpGOgpGmjoKtQpkA65kBghAp5OgNABQSwMEFAAAAAgAAAAhAPN9K5lvAAAALCcAAAkAAABhcnJfMy5ucHntyDEOgkAUANGl5RS/+5JsASUewE5CY0FFVlliYYTsEhr1FFwYuIIJ3bxuZqlu17pJzGw+2vn4CHoW/d4LtaL9EKbg3u0QOr//i3tFv/34dKPf+lSWVoo8z6z85D+pAQAAAAAAAAAAAAAAAADgYCtQSwMEFAAAAAgAAAAhACFK7HxvAAAALCcAAAkAAABhcnJfNC5ucHntyDEOgkAUANGl5RS/+5JsASUewE5CY0FFVlliYYTsEhr1FFwYuIIJ3bxuZqlu17pJzGw+2vn4CHoW/d4LtaL9EKbg3u0QOr//i3tFv/34dKPf+lTkuZWyzKz85D+pAQAAAAAAAAAAAAAAAADgYCtQSwECFAMUAAAACAAAACEAoQWAvEkAAACQAAAACQAAAAAAAAAAAAAAgAEAAAAAYXJyXzAubnB5UEsBAhQDFAAAAAgAAAAhAJM3ghJMAAAAoAAAAAkAAAAAAAAAAAAAAIABcAAAAGFycl8xLm5weVBLAQIUAxQAAAAIAAAAIQCQarNaTgAAAKAAAAAJAAAAAAAAAAAAAACAAeMAAABhcnJfMi5ucHlQSwECFAMUAAAACAAAACEA830rmW8AAAAsJwAACQAAAAAAAAAAAAAAgAFYAQAAYXJyXzMubnB5UEsBAhQDFAAAAAgAAAAhACFK7HxvAAAALCcAAAkAAAAAAAAAAAAAAIAB7gEAAGFycl80Lm5weVBLBQYAAAAABQAFABMBAACEAgAAAAA=


Try it online! Just to get the ball rolling.

# Zigzag path, score 12,582,074

UEsDBBQAAAAIAAAAIQChBYC8SQAAAJAAAAAJAAAAYXJyXzAubnB5m+wX6hsQychQxlCtnpJanFykbqWgbpNpoa6joJ6WX1RSlJgXn1+UkgoSd0vMKU4FihdnJBakAvkaRjqaOgq1ChQArhQGCIDRAFBLAwQUAAAACAAAACEAkzeCEkwAAACgAAAACQAAAGFycl8xLm5weZvsF+obEMnIUMZQrZ6SWpxcpG6loG6TaaGuo6Cell9UUpSYF59flJIKEndLzClOBYoXZyQWpAL5GkY6CkaaOgq1CmQDLgYcgBFKAwBQSwMEFAAAAAgAAAAhAJVYfYFPAAAAoAAAAAkAAABhcnJfMi5ucHmb7BfqGxDJyFDGUK2eklqcXKRupaBuk2mhrqOgnpZfVFKUmBefX5SSChJ3S8wpTgWKF2ckFqQC+RpGOgpGmjoKtQpkAy4GKEhiQAXJUBoAUEsDBBQAAAAIAAAAIQDzfSuZbwAAACwnAAAJAAAAYXJyXzMubnB57cgxDoJAFADRpeUUv/uSbAElHsBOQmNBRVZZYmGE7BIa9RRcGLiCCd28bmapbte6ScxsPtr5+Ah6Fv3eC7Wi/RCm4N7tEDq//4t7Rb/9+HSj3/pUllaKPM+s/OQ/qQEAAAAAAAAAAAAAAAAA4GArUEsDBBQAAAAIAAAAIQAos+JrlgAAACwnAAAJAAAAYXJyXzQubnB57doxDsIwDIVhZ+UU3gxShnYsB2ADsTAwobQNYkAUJYgFegouTHuFStl+Wx7eW74L+Hc47Y9nJ2/5WB9zl2yr9m1r82rXIb1SeFyG1Me534V7jlOfb+EZp7yuq8pr02y8jrpsVuJESp8rvhAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBDLieJvZPIHUEsBAhQDFAAAAAgAAAAhAKEFgLxJAAAAkAAAAAkAAAAAAAAAAAAAAIABAAAAAGFycl8wLm5weVBLAQIUAxQAAAAIAAAAIQCTN4ISTAAAAKAAAAAJAAAAAAAAAAAAAACAAXAAAABhcnJfMS5ucHlQSwECFAMUAAAACAAAACEAlVh9gU8AAACgAAAACQAAAAAAAAAAAAAAgAHjAAAAYXJyXzIubnB5UEsBAhQDFAAAAAgAAAAhAPN9K5lvAAAALCcAAAkAAAAAAAAAAAAAAIABWQEAAGFycl8zLm5weVBLAQIUAxQAAAAIAAAAIQAos+JrlgAAACwnAAAJAAAAAAAAAAAAAACAAe8BAABhcnJfNC5ucHlQSwUGAAAAAAUABQATAQAArAIAAAAA


Try it online! Creates a giant zigzag, something like this but larger:

+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| S                                                             |
+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +
| S                                                             |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+   +
|                                                               |
+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +
|                                                               |
+   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|                                                               |
+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +
|                                                               |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+   +
|                                                               |
+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +
|                                                               |
+   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|                                                               |
+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +
|                                                               |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+   +
|                                                               |
+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +
|                                                               |
+   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|                                                               |
+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +
|                                                               |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+   +
| E                                                             |
+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +
| E                                                             |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+


# Slightly fewer dead ends, score 16,663,349

UEsDBBQAAAAIAAAAIQChBYC8SQAAAJAAAAAJAAAAYXJyXzAubnB5m+wX6hsQychQxlCtnpJanFykbqWgbpNpoa6joJ6WX1RSlJgXn1+UkgoSd0vMKU4FihdnJBakAvkaRjqaOgq1ChQArhQGCIDRAFBLAwQUAAAACAAAACEAkzeCEkwAAACgAAAACQAAAGFycl8xLm5weZvsF+obEMnIUMZQrZ6SWpxcpG6loG6TaaGuo6Cell9UUpSYF59flJIKEndLzClOBYoXZyQWpAL5GkY6CkaaOgq1CmQDLgYcgBFKAwBQSwMEFAAAAAgAAAAhAJVYfYFPAAAAoAAAAAkAAABhcnJfMi5ucHmb7BfqGxDJyFDGUK2eklqcXKRupaBuk2mhrqOgnpZfVFKUmBefX5SSChJ3S8wpTgWKF2ckFqQC+RpGOgpGmjoKtQpkAy4GKEhiQAXJUBoAUEsDBBQAAAAIAAAAIQAhaJ1vdQAAACwnAAAJAAAAYXJyXzMubnB57cgxDoJAFEXRoXUVv/uaTAElLsBOY0NBRQYZY2HEzBgaYBVsGNgCBbG491TvTbfiei8T05leGx8fQc+iQ52pFX224Rfcp2pD49f/4t7RL398ua9f9jHPrWRperIyyrYOZocSAAAAAAAAAAAAAAAAAMDf2qMZUEsDBBQAAAAIAAAAIQAos+JrlgAAACwnAAAJAAAAYXJyXzQubnB57doxDsIwDIVhZ+UU3gxShnYsB2ADsTAwobQNYkAUJYgFegouTHuFStl+Wx7eW74L+Hc47Y9nJ2/5WB9zl2yr9m1r82rXIb1SeFyG1Me534V7jlOfb+EZp7yuq8pr02y8jrpsVuJESp8rvhAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBDLieJvZPIHUEsBAhQDFAAAAAgAAAAhAKEFgLxJAAAAkAAAAAkAAAAAAAAAAAAAAIABAAAAAGFycl8wLm5weVBLAQIUAxQAAAAIAAAAIQCTN4ISTAAAAKAAAAAJAAAAAAAAAAAAAACAAXAAAABhcnJfMS5ucHlQSwECFAMUAAAACAAAACEAlVh9gU8AAACgAAAACQAAAAAAAAAAAAAAgAHjAAAAYXJyXzIubnB5UEsBAhQDFAAAAAgAAAAhACFonW91AAAALCcAAAkAAAAAAAAAAAAAAIABWQEAAGFycl8zLm5weVBLAQIUAxQAAAAIAAAAIQAos+JrlgAAACwnAAAJAAAAAAAAAAAAAACAAfUBAABhcnJfNC5ucHlQSwUGAAAAAAUABQATAQAAsgIAAAAA


Try it online! Based on the original dead end guest trap as posted by @qwr, but removing some of the dead ends like this manages to increase the score:

+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| S     |   |   |   |   |   |   |   |   |   |   |   |   |       |
+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +
| S                                                             |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+   +
|       |   |   |   |   |   |   |   |   |   |   |   |   |       |
+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +
|                                                               |
+   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|       |   |   |   |   |   |   |   |   |   |   |   |   |       |
+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +
|                                                               |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+   +
|       |   |   |   |   |   |   |   |   |   |   |   |   |       |
+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +
|                                                               |
+   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|       |   |   |   |   |   |   |   |   |   |   |   |   |       |
+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +
|                                                               |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+   +
|       |   |   |   |   |   |   |   |   |   |   |   |   |       |
+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +
|                                                               |
+   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|       |   |   |   |   |   |   |   |   |   |   |   |   |       |
+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +
|                                                               |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+   +
| E     |   |   |   |   |   |   |   |   |   |   |   |   |       |
+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +
| E                                                             |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+


# The original dead end guest trap, 16,505,047.166666668

UEsDBBQAAAAIAAAAIQChBYC8SQAAAJAAAAAJABQAYXJyXzAubnB5AQAQAJAAAAAAAAAASQAAAAAAAACb7BfqGxDJyFDGUK2eklqcXKRupaBuk2mhrqOgnpZfVFKUmBefX5SSChJ3S8wpTgWKF2ckFqQC+RpGOpo6CrUKFACuFAYIgNEAUEsDBBQAAAAIAAAAIQCTN4ISTAAAAKAAAAAJABQAYXJyXzEubnB5AQAQAKAAAAAAAAAATAAAAAAAAACb7BfqGxDJyFDGUK2eklqcXKRupaBuk2mhrqOgnpZfVFKUmBefX5SSChJ3S8wpTgWKF2ckFqQC+RpGOgpGmjoKtQpkAy4GHIARSgMAUEsDBBQAAAAIAAAAIQAsPfLMTwAAAKAAAAAJABQAYXJyXzIubnB5AQAQAKAAAAAAAAAATwAAAAAAAACb7BfqGxDJyFDGUK2eklqcXKRupaBuk2mhrqOgnpZfVFKUmBefX5SSChJ3S8wpTgWKF2ckFqQC+RpGOgpGmjoKtQpkAy4GKEhmQAVJUBoAUEsDBBQAAAAIAAAAIQCiugFzcQAAACwnAAAJABQAYXJyXzMubnB5AQAQACwnAAAAAAAAcQAAAAAAAADtyDEOgkAURdGhdRW/+5hMASUugA5jY2FlRhlDQcDMEBphFWwY3AIJ3X2nene53qvbIzGj+Wnt4zvoRXR65WpFP30Yguuefaj9v5eujX7rsXFfv/20KKzkWXa2Msu+nUwCAAAAAAAAAAAAAAAAAMCxVlBLAwQUAAAACAAAACEAKLPia5YAAAAsJwAACQAUAGFycl80Lm5weQEAEAAsJwAAAAAAAJYAAAAAAAAA7doxDsIwDIVhZ+UU3gxShnYsB2ADsTAwobQNYkAUJYgFegouTHuFStl+Wx7eW74L+Hc47Y9nJ2/5WB9zl2yr9m1r82rXIb1SeFyG1Me534V7jlOfb+EZp7yuq8pr02y8jrpsVuJESp8rvhAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBDLieJvZPIHUEsBAhQDFAAAAAgAAAAhAKEFgLxJAAAAkAAAAAkAAAAAAAAAAAAAAIABAAAAAGFycl8wLm5weVBLAQIUAxQAAAAIAAAAIQCTN4ISTAAAAKAAAAAJAAAAAAAAAAAAAACAAYQAAABhcnJfMS5ucHlQSwECFAMUAAAACAAAACEALD3yzE8AAACgAAAACQAAAAAAAAAAAAAAgAELAQAAYXJyXzIubnB5UEsBAhQDFAAAAAgAAAAhAKK6AXNxAAAALCcAAAkAAAAAAAAAAAAAAIABlQEAAGFycl8zLm5weVBLAQIUAxQAAAAIAAAAIQAos+JrlgAAACwnAAAJAAAAAAAAAAAAAACAAUECAABhcnJfNC5ucHlQSwUGAAAAAAUABQATAQAAEgMAAAAA


The original design in Marcel Vos's video. 50 corridors, each with 99 intersections, gives 4950 two-way branches (maybe off by one or two) for guests to choose between.