Submission #9975: stochastique's NES Shanghai in 00:48.620

Shanghai, a Mahjong Solitaire game for the Famicom, presents a classic puzzle. The original objective is to match and remove all 144 tiles without getting stuck. In this TAS, my goal was to clear the board as quickly as possible to reveal the iconic dragon at the end, which meant minimizing cursor travel.

I was surprised to find only one Mahjong Solitaire game on tasvideos.org as I thought it would be a great game to optimize. The existing Shanghai TAS, for the DS, utilized a stylus, demanding a significantly different optimization approach than this NES project.

- Complete the board as fast as possible

Bizhawk Version 2.9.1

I developed a Python-based brute-force solver specifically designed for this type of problem. At its core, the program employs a heuristic search, akin to an A* algorithm, to navigate the vast landscape of possible moves. This algorithm continuously builds an expanding database of game states, prioritizing and exploring those with the lowest frame counts until a complete solution is discovered. To prevent the search from getting trapped in seemingly promising but ultimately dead-end paths, I incorporated variations such as sorting by step count and introducing random choices.

To complement that core solver, I created a complementary pre-solver script. This script utilizes a backtracking algorithm to systematically identify and catalog all strategically impossible tile pairs that inevitably lead to an unsolvable board. This pre-processing step significantly reduced the search space and accelerated the overall optimization process.

Initially, I applied this solver to Shanghai on the Game Boy, but the unpredictable lag frames after tile removal made the program pretty useless. I then searched other versions of Shanghai where my code could be readily adapted and settled on the NES (or Famicom, given it's a Japan-only release).

At the end, I ran this program for multiple days and got an impressive solution. During the adaptation of the solution to the TAS, I managed to shave off a few extra frames by moving the cursor on the exact frame a tile pair is validated.

My initial attempt at optimizing this problem involved linear programming, drawing inspiration from the Miller–Tucker–Zemlin formulation of the Traveling Salesman Problem. This approach proved effective for boards with fewer than 50 tiles, but it failed to produce any solution for the full 144-tile layout.

- Since board layouts are randomized, an easier board might exist. There's a trade-off between waiting in the main menu for an optimal board and a faster clear time. My optimization primarily focused on the first available board, though I did briefly explore the second and third (which appeared 1 and 2 frames later) without finding a better outcome. - Given more computational time, I think a better solution could be found for this layout. - Future optimizations could consider that the cursor can be moved during the tile validation frames, potentially saving additional time.

Taken from this Shanghai Game Boy longplay: See all different end screens https://www.youtube.com/watch?v=moC5KM2aqQ8

I dedicate this TAS to my Grandma, who really loved playing Mahjong Solitaire. She's the one who taught me how to play when I was younger and I have fond memories of playing solitaire types of games with her. Unfortunately, her failing eyesight has left her nearly blind, preventing her from playing. Merci mamie!

https://github.com/guiguilegui/ShanghaiNes

nymx: Claiming for judging.

nymx: First off, I chose to judge this because I have been interested in the Super Nintendo version and have been reviewing a solution for over a year. Second, you BOTed it...which I get excited about. My opinion on this run? It's fast, certainly faster than what a human can do; however, I don't know if it is the fastest version possible. Why? You didn't delay the "start" to experiment with different RNG layouts (seeds). At this point, I don't care...we have a good solid run that will be highly competitive for future attempts. I like this kind of work and I applaud your effort. Congratulations!

Accepting to Standard.

despoa: Processing...