Submission Text Full Submission Page
The process of making this TAS was probably more interesting than the movie itself. I've been interested in using optimization algorithms for the purpose of helping to route TASes. This is probably the most mundane example possible of that but it's got me thinking about using a similar approach for more complex gameplay.
You can move up/down/left/right or diagonally every other frame & the optimal solution is the one that visits the fewest unnecessary tiles (tiles you've already chiseled or tiles that aren't part of the solution). If all of the tiles in the puzzle are connected in a way that you can solve the puzzle just by visiting each of them once & no other tiles that is clearly an optimal solution (aka a Hamiltonian path).
To verify that all solutions are optimal I converted all the puzzles to a distance matrix which allows the puzzles to be treated as instances of the Traveling Salesman Problem. The Concorde solver ( http://www.math.uwaterloo.ca/tsp/concorde.html ) is a highly efficient TSP solver that quickly verified the fewest number of steps for all puzzles. I also wrote some extra code to convert solutions directly to controller input so they could simply be pasted into TAStudio to speed up the process.
Some notes:
  • 2 frames after each level starts there is a single frame where the game allows you to move early (but not chisel). For any level where you start off moving (i.e. if the nearest tile of the solution is more than 1 block away from the start) you save some frames moving here.
  • Every 30 frames (when the timer ticks down) the game will drop input so I have to periodically delay some of my input by a frame to account for this.
  • Some levels are laggy (1 lag of frame every time I chisel) for reasons I'm not entirely sure of.
  • Time Trial mode (the final mode unlocked) gives you a random puzzle from the Time Trial level set and notes the final completion time on the ranking board. Since all levels share the same leaderboard & individual level completion isn't tracked here I chose to "complete" this mode just by finishing the first level it gives me and registering the name "TAS".
Possible improvements:
  • Regarding the input that is dropped, it seems that sometimes if the frame on which the timer ticks down isn't being used to chisel a tile (i.e. if you are just moving) then input doesn't get dropped and you don't have to wait a frame. So it might be possible to save some frames by finding solutions that have the same # of moves but where the order of moves is slightly changed so that any frames on which you aren't chiseling land on one of these 60 frame intervals. This would save only a tiny amount of frames throughout the entire run though.
  • I'm not sure how the random puzzle selection for Time Trial mode works (it is not simply a matter of delaying frames) but it might be possible to manipulate a slightly faster puzzle than the one I used (Koopa Troopas).
Edit: Will resubmit fixed version
feos: Judging...

Show more

Hide
1 2
Posted: 7/20/2020 10:46 PM
Quote
RetroEdit
Any
Editor, Reviewer, Player (169)
Joined: 8/8/2019
Posts: 152
Arcade TAS of 2023
This is the screen that appears after completing the Stars level collection: The phrasing "You have solved every puzzle" suggests this is the end of the main game. It isn't credits, but it's pretty expressive. I disagree that completing all 64 unique Time Trial puzzles is required for publication because "all unique content" needs to be played. Instead, I think this screen is sufficient to show completing all 192 standard levels is an endpoint. My draft movie above also ends input early on the premise that reaching this screen is completion. However, there are screens afterwards explaining that Time Trial mode is now unlocked. I will note the screens go on to describe time trial as "the ultimate PICROSS challenge", but I will still maintain that it's fundamentally a side-mode that's not needed for completion. Side note: "How to play" isn't really content either, it's just an explanation of how to play and a brief demo, but it can be skipped after entering by pressing start. In my opinion, it should not count towards completion either.
Posted: 7/20/2020 11:38 PM
Quote
qqwref
Player (138)
Joined: 8/27/2004
Posts: 165
It feels wrong to me to require completing all puzzles in Time Trial, since from the perspective of a player without memory watch, the mode simply gives you a new puzzle every time, and stores your best overall time. The game doesn't appear to look or act differently if all puzzles are completed, and as far as I can tell, will simply keep giving you puzzles you've already done. One could theoretically consider every Time Trial puzzle "unique content", but that argument could then be brought over to other games as well which generate puzzles randomly. If some logic game generates a random puzzle using a PRNG, it may only have, say, 65536 possible puzzles; should a TAS solve every single one? The fact that Mario's Picross has hard-coded "random" puzzles is just an implementation detail. On a wider level, the "unique content" rule should probably be clarified to say it's for games whose main mode has "infinite" looping levels. There are many games where a huge number of slightly different paths are possible, such as Undertale where there are 93 different endings and a "True 100%" speedrun that saw all of them took 27 hours - I don't think we should argue that a 100% run of the game must do that, simply because some slightly different content is available at each branch.
Posted: 7/21/2020 12:59 AM
Quote
CasualPokePlayer
Emulator Coder, Judge, Experienced player (729)
Joined: 2/26/2020
Posts: 783
Location: California
Arcade TAS of 2023 TASer of 2021 Gameboy TASer of 2021 Rookie of 2020 Gameboy TASer of 2020 Lucky TAS of 2020
Went ahead and dumped the "list" of Time Trials the player will get: 
0C 2A 1C 13 26 1F 01 37 14 27 3B 1E 06 2C 18 3A
0D 38 19 2B 23 3F 1D 20 0B 31 36 08 29 25 24 02
3C 30 10 39 12 21 0F 17 1B 28 2F 05 00 3D 32 22
1A 35 15 03 0A 16 3E 09 2E 34 07 11 0E 04 33 2D
There appears to be no duplicates in this "list" and as I've corrected on my original post, this list is re-randomized upon entering Time Trial 64 times (don't ask how I got 133 lol). So in essence the game will go through each unique puzzle before it re-randomizes the list. (again of course, the game does not care if all are completed, giving up goes to the next puzzle on the list)
Posted: 7/21/2020 6:17 AM
Quote
ThunderAxe31
Any
Editor, Reviewer, Skilled player (1359)
Joined: 9/12/2016
Posts: 1646
Location: Italy
Arcade TAS of 2023 Homebrew TAS of 2023 PSX TASer of 2022 Gameboy TASer of 2017
RetroEdit wrote:
This is the screen that appears after completing the Stars level collection: The phrasing "You have solved every puzzle" suggests this is the end of the main game. It isn't credits, but it's pretty expressive. I disagree that completing all 64 unique Time Trial puzzles is required for publication because "all unique content" needs to be played. Instead, I think this screen is sufficient to show completing all 192 standard levels is an endpoint.
I agree that this is the completion point for fastest-completion, as it objectively counts as the ending of the game, but an author may still add the additional Time Trial puzzles and would be considered applicable for Vault as full-completion.
CasualPokePlayer wrote:
(again of course, the game does not care if all are completed, giving up goes to the next puzzle on the list)
The game may not be keeping track of the puzzles completed, but we can.
my personal page - my YouTube channel - my GitHub - my Discord: thunderaxe31 <Masterjun> if you look at the "NES" in a weird angle, it actually clearly says "GBA"
Posted: 7/23/2020 4:43 PM
(Edited: 7/23/2020 5:37 PM)
Quote
RetroEdit
Any
Editor, Reviewer, Player (169)
Joined: 8/8/2019
Posts: 152
Arcade TAS of 2023
ThunderAxe31 wrote:
RetroEdit wrote:
This is the screen that appears after completing the Stars level collection: The phrasing "You have solved every puzzle" suggests this is the end of the main game. It isn't credits, but it's pretty expressive. I disagree that completing all 64 unique Time Trial puzzles is required for publication because "all unique content" needs to be played. Instead, I think this screen is sufficient to show completing all 192 standard levels is an endpoint.
I agree that this is the completion point for fastest-completion, as it objectively counts as the ending of the game, but an author may still add the additional Time Trial puzzles and would be considered applicable for Vault as full-completion.
This presents an interesting conundrum for all movies thus far that I have just realized after some testing. You don't have to play the Easy levels at all to reach this screen. Only all the Kinoko levels to unlock the Star levels, and then all the Star levels to reach the screen. Under this metric, the current movies could be considered severely suboptimal in the pursuit of reaching the fastest completion goal. EDIT: Here's a movie that skips the Easy levels and goes straight through Kinoko levels and then Star levels to the completion screen: Picross-Scripting-SkipEasy.bk2 EDIT II: My original interpretation seems a bit wrong. The game delineates between "EASY PICROSS" and "PICROSS". That screen refers specifically to the PICROSS level set, which includes the Kinoko levels and the Star levels.
Posted: 7/23/2020 5:31 PM
Quote
RetroEdit
Any
Editor, Reviewer, Player (169)
Joined: 8/8/2019
Posts: 152
Arcade TAS of 2023
CasualPokePlayer brought up that this screen appears after beating the easy levels (if you don't reset to get to the next level set faster): I think this is a good point: the game clearly delineates between "EASY PICROSS" and "PICROSS". I think they should be considered separate branches for this game, since they have different content. And to be clear, this is not a trivial game. Firstly, the optimal solutions had to be calculated for each layout, which Jigwally has nicely done in this movie. Secondly, the difference in level lag between soft-resetting and hard-resetting suggests the possibility of significant lag reduction with more research, leading to more deep meta-optimization. As for full completion... ThunderAxe's definition sounds reasonable enough. I think it's important to keep in mind that not all games have SaveRAM anyway, so artificially restricting the completion of certain puzzles just because completion flags don't show up in the save file seems a bit of a weak argument. On the other hand, you could take a more relative approach and reject it on the basis of completing puzzles in Time Trial without individual acknowledgement being less meaningful than the explicit tracking in the other part of the game. But it's still unique content either way, and would probably present different challenges to the TASer in addition to those presented by the other modes.
Posted: 7/24/2020 2:18 PM
Quote
feos
Site Admin, Skilled player (1254)
Joined: 4/17/2010
Posts: 11478
Location: Lake Char­gogg­a­gogg­man­chaugg­a­gogg­chau­bun­a­gung­a­maugg
NES TAS of 2011
For a game like this, we prefer all modes in one movie over having a branch for each mode, but separate modes are also acceptable. Completing all puzzles that are there can count as full completion, and it looks like that would indeed include all modes, making individual branches superseded by that.
Warning: When making decisions, I try to collect as much data as possible before actually deciding. I try to abstract away and see the principles behind real world events and people's opinions. I try to generalize them and turn into something clear and reusable. I hate depending on unpredictable and having to make lottery guesses. Any problem can be solved by systems thinking and acting.
Posted: 7/25/2020 3:06 PM
Quote
RetroEdit
Any
Editor, Reviewer, Player (169)
Joined: 8/8/2019
Posts: 152
Arcade TAS of 2023
I don't think this movie should be accepted in its current form. There are a variety of reasons for this, but the main one is that it's been demonstrated to suboptimal in some rather significant ways, regardless of how you look at it.
    1. Using SGB mode. I don't personally care too much about the extra time here, but a frame purist would say it's unnecessary time for the purposes of comparison, and I assume this movie is going to be accepted as a Vault movie. 2. Slow hint-cancelling. Every hint-cancel in the submission loses 30-frames by pressing B instead of R then A. 3. Level mistakes. Holding A at the start of many levels saves one frame by chiseling the top left square followed by immediately moving to an adjacent square (normally, a blank frame is required between inputs). Also, my analysis revealed that the Star 6B level accidentally had some extraneous inputs added that wasted time. This can even be seen in the encode if you watch it at 25% speed, where you can see a square is chiseled, erased, then re-chiseled. 4. If completing all the Time Trial levels would obsolete this movie anyway, maybe we might as well do that now if it wouldn't take too much time. Optimal solutions would need to be found for the additional 64 levels, but I'm already working on a program to do so. I think this is less important than the other 3. Another submission can be made later.
Overall, I think the original movie is a good foundation for a site publication, but it just has a few issues. I would urge Jigwally to request a delay if he's interested in waiting for me to finish my version, which would be co-authored with him, since I'm probably going to be using his solutions for the most part. ---- EDIT: Here is the fastest movie file I've gotten so far. It addresses all of the above issues except for #4: User movie #64941625601488011. This movie goes through EASY PICROSS and PICROSS, ending input early before the PICROSS completion screen is guaranteed to appear, which already seems to be confirmed as a reasonable endpoint. If Jigwally is willing, it can replace the submission, and I'd be more comfortable with the submission being accepted. I'm kind of wondering if completing all 64 time trial puzzles should be in a separate submission anyway, since the validity of that being considered full completion is more contentious. It will take some time to add those new puzzle solutions and create a new movie file, so this movie being accepted in the interrim wouldn't necessarily pose a problem, even if does end up ultimately being obsoleted by a "more complete" movie later.
Posted: 7/25/2020 8:14 PM
Quote
TASVideosGrue
They/Them
Joined: 10/1/2008
Posts: 2785
Location: The dark corners of the TASVideos server
om, nom, nom... blech, salty!
1 2