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,
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.