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