Constructing an evil maze against random exploration

Question

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.

Answer 1

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.

Answer 2

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!

Answer 3

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!

Answer 4

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)

Answer 5

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.

Answer 6

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                                                             |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

Answer 7

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                                                             |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

Answer 8

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.