#9081: TaoTao's SNES Same Game "maximum score" in 02:07.47

Game objectives

Emulator used: BizHawk 2.9.1 (BSNESv115+ core)
Aims for maximum score
Manipulates luck

This run achieves the (probably) maximum scores for SNES "Same Game (J)".

Here are the scores for each difficulties:

Easy: 844
Medium: 2229
Hard: 8987

Note: from a speedrun perspective, it is faster to reset the game immediately after a score is saved. But, this prevents the game from displaying the achieved score. So, I decided not to use a reset.

About the game

SameGame is a tile-matching puzzle game. This game was originally created as "ChainShot!" by Morisuke, and it has been ported to various platforms.

In this game, you can erase connected pieces of the same kind at once. In many versions, when you erase n pieces, you will get O(n^2) points. Additionally, if you erase all the pieces, you will get some bonus points.

The SNES version has three modes:

SameGame: "score attack" mode.
TumeGame: "problem" mode. (this term comes from "Tume Shogi" (Shogi problems))
UraGame: player-vs-player mode, involving some luck.

"SameGame" mode has three difficulties, "Easy", "Medium", and "Hard". Each difficulty has a different board size:

Easy: 8x6
Medium: 10x8
Hard: 15x12

In "SameGame" mode, you will get (n-1)^2 points when you erase n pieces. Additionally, if you erase all the pieces, you will get a bonus determined by each difficulties:

Easy: 200
Medium: 500
Hard: 1000

Comments

I analyzed the RNG, and wrote a solver to achieve the maximum scores:

The search space of this game is a DAG (Directed Acyclic Graph), so you can apply dynamic programming (managing the upper bound of score for each board with some hash table). I solved "Easy" and "Medium" with this method.

For "Hard", the search space is somewhat large, so I solved it with beam search. But there are few boards that runs out the beam width, so I think it's unlikely that there are better solutions than this one.

In this game, you can easily estimate the upper bound of score for a board by assuming you can erase all piece of the same kind at once (unless the count of the piece kind is 1). This is very useful for pruning nodes, especially in "Easy" and "Medium".

About the RNG

The RNG depends on the elements below:

16-bit internal state (shift register, but actually the highest bit is meaningless)
NMI counter
mainloop counter (converted to 0 to 4, and works like a subtle entropy term)
(CPU cycles)

In the board generation process, the RNG generates pieces based on the internal state, the NMI counter, and the mainloop counter. And, the internal state will be updated based on the previous internal state and the NMI counter.

But, a NMI occurs while the board generation process, so the NMI counter is incremented once during the process. From my observation, a NMI usually will occur just after 40 pieces are generated.

And, there is a restriction for the board generation. If there are too many pieces of the same kind, the board will be regenerated. (the count of the same kind must be less than (board square count) / 2)

It is not so difficult to manipulate the RNG. You can regenerate a board by pressing Select or opening the menu by pressing L/R (you can also manipulate the mainloop counter slightly by opening the menu). And, when you regenerate a board, you can obtain 2^8 different RNG states by manipulating the NMI counter. So, you will be able to obtain a desired RNG state by regenerating a few boards (I used a quick-and dirty search until depth 2).

Memory map

RAM:

addr	type	description
$7F0046	u8	mainloop counter
$7F0467	u16le	board square count
$7F0469	u16le[5]	counts of each piece kind
$7F0F52	u8	NMI counter
$7F0F53	u16le	RNG internal state
$7F2000	u8[]	buffer for board generation

ROM:

addr	type	description
$809AD2	code	board generation routine
$809DD9	code	checks the restriction for the board generation
$80A8A1	code	RNG helper (generate a piece from a random number and the mainloop counter)
$80D6BA	code	generates a random number within specified range
$80D6D1	code	RNG core

Possible improvements

There might be more boards which I haven't checked:

If you can manipulate the NMI timing during the board generation process, more different boards will become available.
When the board is regenerated by the restriction mentioned above, it seems that a NMI occurs at a different timing. I haven't investigated this case so deeply, but I haven't found a better solution taking advantage of this.

Darkman425: The game that I, for some reason, hear referred more often to as Sega Swirl. Anyways, claiming for judging.

Darkman425: I see a lot of work was done in understanding how the board is generated and how to maximize the score with regards to how board generation is done. The search algorithms and the provided code to find the maximum score for a given board also helped with maximizing the score for given boards. The final result of all this shows very clearly with the incredible amount of points gained overall. Nice work figuring this out!

Accepting to Standard.