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).
Some levels are laggy (1 lag of frame every time I chisel) for reasons I'm not entirely sure of.
I'm going to take a wild guess that this is mostly because you did this on the SGB instead of the GB/C, which just booting the game up I can tell the SGB is has much more lag than the GB/C.
Joined: 10/12/2011
Posts: 6449
Location: The land down under.
Complaint: The TAS uses SGB. You should've TASed this in GBA mode.
In terms of load differences playing in not SGB has the advantage.
I believe the input can be ported across so I'll see if it can help save anything.
TAS is well made so got no complaints on that front from what I've seen so far, just the type of system used.
Edit: Due to hand you'll reach a point of lag hell and something needs to be done about that.
Estimate is about 10,000 15,000 - 20,000 frames to be saved from switching to SGB to the handheld.
This is a straight switch file which retains the solutions but doesn't adjust anything.
AND SHOULDN'T BE REPLACING THIS SUBMISSION FILE. (since it will desync at hand)
I am currently working with CasualPokePlayer to get ahead of these desync issues.
Edit 2: I wrote the wrong estimate number. Adjusted.
WebNations/Sabih wrote:
+fsvgm777 never censoring anything.
Disables Comments and Ratings for the YouTube account.Something better for yourself and also others.
IMO the game looks noticeably better on SGB than on GBC. Even if the movie file ends up being converted to the GBA mode, I think it's worth it to do the encode with the SGB movie file.
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).
I decided to look into it and discovered the following:
* The game will make a random list of indexes of the different puzzles you will do in time trial.
* This list is generated on initializing the save data.
* Save data is initialized before you can do any inputs.
* What data was in the save before hand will affect the resulting puzzle (Bizhawk FF's it so it's consistent, but console would have to flash the save on).
* What data is in WRAM on bootup (ie uninitialized memory) will affect the resulting puzzle. Sameboy appears to just put 00 for uninitialized WRAM, and Gambatte appears to FF it (which results in different puzzles).
* Can't do anything to influence the random list you get. You get what you get.
* You could give up on the time trial then redo it to get a different puzzle (ie the next one on the list), but again that different puzzle will be set and the time it takes to do this makes it not worth it.
* Any chance at console verifying time trial is essentially fucked (since uninitialized WRAM on console is overall non-deterministic, might be possible to do some witchcraft to console sync but lol gl on that).
I would like to point out that a nonogram is technically a paper & pencil game. As such, the Vault eligibility of this submission, which is exclusively about solving nonograms, is questionable.
The issue here is that the current wording in the Movie Rules refers to "board games" instead of "tabletop games". This may require a revision for consistency.
Fixed version
http://tasvideos.org/userfiles/info/64703570145989235
Notes:
- Switching from SGB didn't completely eliminate the laggy levels, just caused them to happen on different levels
- Time Trial puzzle got changed as a result of input changes
Wow, incredible how fast you managed to finish the rest of the game 0.0 It's definitely a yes for entertainig from me, as I really enjoy this game casually, and watching this TAS is just mindblowing and really fun haha.
Like Fortranm, I also favor the SGB movie, just because it's visually way more appealing to me. Although I guess one could argue wether colors are SO important for a game, which main focus lies on arranging black and white squares on a grid... (but I still feel like it changes the overall atmosphere quite a lot.)
Now on to the next topic, pointed out by SmashManiac:
I would like to point out that a nonogram is technically a paper & pencil game. As such, the Vault eligibility of this submission, which is exclusively about solving nonograms, is questionable.
I guess this is a very reasonable and valid claim and well, I also kinda agree with you. However, I just want to mention, that there are accepted TASes of f. e. Minesweeper, Polarium and Rubics World, which more or less fall in the same cathegory as this game (1P, puzzle, no action).
Joined: 1/24/2018
Posts: 308
Location: Stafford, NY
KiwiCracker wrote:
However, I just want to mention, that there are accepted TASes of f. e. Minesweeper, Polarium and Rubics World, which more or less fall in the same cathegory as this game (1P, puzzle, no action).
Problem: All of those submissions are older ones, and I believe were submitted and accepted before the rules regarding such games for Vault eligibility were set in their current form. Someone (ideally, a judge different from the one that handled the original submission) would have to determine whether those games would be acceptable under the current ruleset before referencing them as an argument for accepting this submission.
c-square wrote:
Yes, standard runs are needed and very appreciated here too
Dylon Stejakoski wrote:
Me and the boys starting over our games of choice for the infinityieth time in a row because of just-found optimizations
^ Why I don't have any submissions despite being on the forums for years now...
However, I just want to mention, that there are accepted TASes of f. e. Minesweeper, Polarium and Rubics World, which more or less fall in the same cathegory as this game (1P, puzzle, no action).
Problem: All of those submissions are older ones, and I believe were submitted and accepted before the rules regarding such games for Vault eligibility were set in their current form. Someone (ideally, a judge different from the one that handled the original submission) would have to determine whether those games would be acceptable under the current ruleset before referencing them as an argument for accepting this submission.
Yep, I guess you're right, the newest one of these dates back to 2014.
I would like to point out that a nonogram is technically a paper & pencil game. As such, the Vault eligibility of this submission, which is exclusively about solving nonograms, is questionable.
The issue here is that the current wording in the Movie Rules refers to "board games" instead of "tabletop games". This may require a revision for consistency.
While this could, indeed, be classified as a "tabletop game" because it's based on a paper & pencil puzzle, there still exists potential for optimization in a picross game; namely, what order the black squares are filled in.
This presents a "routing" challenge as the fastest sequence of filing the black squares is not immediately or trivially identifiable even when the answer to the puzzle itself is previously known. Different TASers may find different routes that could yield the same time, but there are surely some solution sequences that are faster than others. This presents not only a TASing challenge, but also potential for improvement.
I see this as an acceptable game (though I haven't watched this specific submission so I can't comment as to it's optimization or acceptability).
Creating a TAS for this type of puzzle is no less of a TASing challenge than any other puzzle based game (i.e. Tetris Attack's Puzzle Mode) just because it is derived from a puzzle that can also be done on paper.
It seems to me that the routing challenge argument also applies to video game adaptations of board games, game show games and educational games, which aren't currently eligible for Vault. I'm not sure why those are not currently considered "serious" games.
For example, it doesn't really make sense to me that a single-player card game would be accepted (like [3113] NES Solitaire by TheRealThingy in 00:37.82), but not a multiplayer card game (like #6684: dekutony's GBC Uno "Fastest Uno" in 01:01.01).
I don't mind either way. All I'm saying is that there appears to be an inconsistency in the way Vault eligibility is being considered right now, but I could be missing something. Personally, I would accept anything with a clear end goal to Vault, but that's just my opinion.
Newest version:
http://tasvideos.org/userfiles/info/64785263837932039
Spikestuff pointed out to me that you can do a soft reset to the title at two points (between Easy/Kinoko Picross and between Star Picross/Time Trial) because reloading the save is faster than going through the text message. However when I tried doing this, I had to readjust input for a bunch of new laggy levels, and in fact there were so many laggy levels that I ended up losing time vs my non-reset version. So for now I have only added the single reset right before Time Trial mode.
I still don't know exactly what causes certain levels to be laggy. Nothing obvious like delaying frames at different points seems to make a difference.
Newest version:
Spikestuff pointed out to me that you can do a soft reset to the title at two points (between Easy/Kinoko Picross and between Star Picross/Time Trial) because reloading the save is faster than going through the text message. However when I tried doing this, I had to readjust input for a bunch of new laggy levels, and in fact there were so many laggy levels that I ended up losing time vs my non-reset version. So for now I have only added the single reset right before Time Trial mode..
So would a hard reset on Easy/Kinoko save time or does lag screw that over too? iirc there was less lag with a hard reset for over a soft reset, but I didn't look into it that much.
You were right, doing a hard reset there instead reduces a lot of the lag.
Edit: I accidentally introduced some additional frames while adjusting some of the levels for lag, I went through and fixed them: http://tasvideos.org/userfiles/info/64810349029646615
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".
Is the puzzle selected indeed random? Did you test if it was possible to manipulate RNG to yield a shorter puzzle for this mode?
EDIT: Are the Time Trial puzzles repeats of other puzzles in the game? If not, wouldn't all the Time Trial puzzles need completed to consider the game truly completed?
EDIT 2:
This page shows 64 puzzles are possible in Time Trial Mode. Scanning though them, there are unique puzzles in this mode compared to other modes in the game. Thus, I'd argue that all these unique puzzles also need solved to consider the game 'beaten' even if their order is randomized.
I would argue the time trial puzzle(s) doesn't count towards full competition at all. It's just a single record; it doesn't keep track of each individual puzzle out of the 64 possible puzzles that was done.
This is in contrast to the clear way the other 192 puzzles are treated, each having an individual checkbox among other indicators showing each puzzle is complete.
I would argue the time trial puzzle(s) doesn't count towards full competition at all. It's just a single record; it doesn't keep track of each individual puzzle out of the 64 possible puzzles that was done.
This is in contrast to the clear way the other 192 puzzles are treated, each having an individual checkbox among other indicators showing each puzzle is complete.
With that perspective, we could potentially have a 2nd branch of this game:
This submission would be the any% branch.
A version that completes all the unique content would be a 100%/Full Completion branch.
My personal perspective: Given that this game (as presented) has no "end credits" with which to mark the end-point of game-play, the only other definitive end-of-game moment is to exhaust all unique content. The fact that the game uses the same high score (low time?) table for all the Time Trial puzzles is a moot point. The game, in my opinion, is incomplete.
I do not have enough experience with this game to know if there are credits offered after all the Time Trial puzzles are exhausted.
Something else to consider for a "full completion" run would be the "How to play" mode. If it's simply directions, then it may not be necessary. However, if there's any solving on the player's part that occurs in that mode, it could also likely be required for Full Completion.
EDIT: There is a potential consideration regarding if the game tracks completion of the Time Trial puzzles:
If all 64 unique TT puzzles must be completed before any are repeated, then it's likely tracked internally even if there's no indicator to the player that it's tracked.
EDIT 2: I just tested....after entering your name for the TT puzzle in this submission, the game continues directly on to the next puzzle. It doesn't go back to a menu of any type. Oops. It continues if you hit A, it goes back to a menu if you hit B. My mistake.
EDIT: There is a potential consideration regarding if the game tracks completion of the Time Trial puzzles:
If all 64 unique TT puzzles must be completed before any are repeated, then it's likely tracked internally even if there's no indicator to the player that it's tracked.
From my poking around, it seems like it does not track puzzles completed. The internal counter just goes up every time you go into the Time Trial puzzle. The game does not care if you actually complete the puzzle or not. ie if you give up right away, it will give you the next puzzle on the list when you go back to the time trial (and it will not re-randomize the list until you enter Time Trial 134 times EDIT: this is wrong, it's 64 times).
Also just want to say (again), the "randomization" relies solely on what should be (what should be) non-deterministic data, both uninitialized SRAM and WRAM are used to create the "random" list (cough cough DK94 cough cough). Since Gambatte just FF's the entirety of uninitialized RAM, you will end up with a constant list 100% of the time. The fact that Sameboy got a different puzzle is simply because it does not have the same behavior regarding uninitialized RAM like Gambatte (SRAM is FF'd but WRAM is 00'd).
(tl;dr the list isn't really random just due to how emulators treat uninitialized RAM, for the purposes of a TAS, it shouldn't be considered random)
EDIT: There is a potential consideration regarding if the game tracks completion of the Time Trial puzzles:
If all 64 unique TT puzzles must be completed before any are repeated, then it's likely tracked internally even if there's no indicator to the player that it's tracked.
From my poking around, it seems like it does not track puzzles completed. The internal counter just goes up every time you go into the Time Trial puzzle. The game does not care if you actually complete the puzzle or not. ie if you give up right away, it will give you the next puzzle on the list when you go back to the time trial (and it will not re-randomize the list until you enter Time Trial 134 times).
Also just want to say (again), the "randomization" relies solely on what should be (what should be) non-deterministic data, both uninitialized SRAM and WRAM are used to create the "random" list (cough cough DK94 cough cough). Since Gambatte just FF's the entirety of uninitialized RAM, you will end up with a constant list 100% of the time. The fact that Sameboy got a different puzzle is simply because it does not have the same behavior regarding uninitialized RAM like Gambatte (SRAM is FF'd but WRAM is 00'd).
(tl;dr the list isn't really random just due to how emulators treat uninitialized RAM, for the purposes of a TAS, it shouldn't be considered random)
For me, this data actually does more to support my position that the unique puzzles need solved to consider the game complete.
If all the TT puzzles will be presented before any are repeated, then completion of all unique content could be performed without unnecessary repetition.
That said, if the puzzle counter simply repeats after all the TT puzzles have been presented once; the mode is not really a 'random puzzle' mode and the repeating sequence effectively makes this game a never-ending game. Therefore, based on movie rules for non-ending games, all unique content must be presented for the game to be considered complete.
This unfortunately complicates the issue with another question. If the player is able to give up on any given puzzle and still advance on to the next puzzle in sequence, is simple display of the blank puzzle & numbers enough to be considered having the content shown...or would it be more appropriate to require the puzzles to be solved?
In my perspective, the latter is more appropriate. With other non-ending games we tend to require reaching some completion point (i.e. beating the stage) AFTER the final unique content has been presented by the game; simply seeing the content isn't enough. Thus I feel that solving of the puzzles, not just visualization of the blanks & numbers, is necessary.
ALL THAT SAID, there is yet another thought that needs consideration in regards to game completion:
The only equivalent I can make to advancing the counter by quitting a puzzle to get through them more quickly would be along the lines of skipping a bonus stage in any other game. But these aren't bonus stages. They're legitimate new puzzles/content exactly like any other standard stage in the game.
Further, the normal puzzles in the other modes can technically be solved in any order (or also given up then continued with a different puzzle), and all puzzles in any other mode need solved to consider that mode complete; making order of completion a non-factor for any game mode. Therefore the order in which the TT puzzles are completed doesn't technically matter, but they all still need solved to consider the mode complete.
From this perspective which disregards order of completion, the only way to consider the entire game complete is to have all modes of the game completed. This requires all the unique puzzles in all modes to be solved.
Pseudo minor edit: The fact that the game itself doesn't track completion of the TT puzzles doesn't matter when determining if everything in the mode has actually been completed. It's still a measurable completion metric even if we have to measure it manually.
Joined: 10/29/2014
Posts: 176
Location: Bavaria, Germany
I routed all images (except for neglecting potential lag frames) manually, including those from the japanese version, at some point in the November of 2018 for Spikestuff, and I remember it was an interesting endeavouer back then to route them. Here is a ZIP file of the routes I had made: https://cdn.discordapp.com/attachments/396448200447361024/734618978592227338/All_Mario_Picross_images_routing_solutions_including_japanese_only_images.zip
In the images, for each number pair X/X, X refers to the number of steps in my routing solution in which no new tile is revealed, and initially I used an estimate via discrete mathematics' graph theory and the number of vertices that are so-called leaves (vertices that only have 1 edge to another vertex, where the vertices in the images would only be the tiles that need to be coloured in and edges between any 2 vertices would only be drawn between such vertices if one can move from one vertex to the other in 1 step), and then observing that for connected graphs there would have to be at least N-1 steps (minus the highest number of times and best manner in which one can connect leaves each via by a previous leaf forced additional step that doesn't colour in a required tile) that don't colour in another required tile if N is the number of leaves, since for each entered leaf one would have to enter it from the only vertex connected to it, meaning that the only vertex connected to it is already coloured in, leaving as (almost) only exception the very last tile that needs to be coloured in, since there is no need to move away from it anymore, except when the starting position at the top left is 0 or 1 tile away from a leaf (in which case that leaf doesn't come with the cost of an extra step as soon as there is at least another leaf). But then some later images turned out to have multiple separate components and I had to put in more thought for trying to find lower bounds for the number of steps with which no new requires tile is coloured in, and then I just kept the double notation.
I haven't seen yet what routes are used in this TAS, but I'm aware that lag minimization may lead to significant deviations from what otherwise optimal routes would be for the images.
collect, analyse, categorise.
"Mathematics - When tool-assisted skills are just not enough" ;)
Don't want to be taking up so much space adding to posts, but might be worth mentioning and letting others know for what games 1) already some TAS work has been done (ordered in decreasing amount, relative to a game completion) by me and 2) I am (in decreasing order) planning/considering to TAS them. Those would majorly be SNES games (if not, it will be indicated in the list) I'm focusing on.
1) Spanky's Quest; On the Ball/Cameltry; Musya; Super R-Type; Plok; Sutte Hakkun; The Wizard of Oz; Battletoads Doubledragon; Super Ghouls'n Ghosts; Firepower 2000; Brain Lord; Warios Woods; Super Turrican; The Humans.
2) Secret Command (SEGA); Star Force (NES); Hyperzone; Aladdin; R-Type 3; Power Blade 2 (NES); Super Turrican 2; First Samurai.
(last updated: 18.03.2018)
Joined: 2/27/2011
Posts: 69
Location: Calgary, Alberta
Thanks Zinfidel for the test encode. Hopefully your settings test worked :P
I'm torn with this submission. I'm a lover of picross and the mathematical approach to an optimal path to solve a puzzle is interesting. it would even be interesting to see a TAS input of normal play which would present more "legitimate" gameplay rather than solving a puzzle because you know the solution outside of gameplay.
It's kind of boring af though and so I'd say vault material (probably undisputed), but I have to disagree with needing time trial to be published. I'm surprised that there are unique puzzles hidden in there, but when the game doesn't track completion of those puzzles, there's no difference to the game between 100% including or excluding time trials. Is there any difference to us? Well.. I get the feeling that the pseudo random puzzle list would need to be gone through by skipping the non unique puzzles and completing the unique ones. That's not doing any favours to the entertainment value of the run. And to me, that's too high a price in the consideration of needing time trials. It's diminishing returns past the checkmarked levels.
It's a tough call for someone else :P I appreciate the effort made to TAS this game though and I'm glad I watched it
Here's some movies I made: hard-reset movie / soft-reset movie (old)
So I have finally finished one run of my bot, and netted a time save of around 02:02.5102:02.61 02:09.29 (compared with Jigwally's latest version). However, the frames aren't really mainly because I used a bot but because I used a few better strategies.
One main strategy is better menuing. During hint cancellation, the original movie uses B to cancel the hint. By instead pressing R followed by A, the movie saves 30 frames on each level. Over the whole run, this probably saves ~01:36.44.
This movie also uses a soft-reset between Easy/Kinoko, which may or may not save time.
The remaining ~00:26.07 are probably mainly due to different in-level lag. I know it was mentioned that a soft-reset between Easy and Kinoko seems to add a lot of lag at levels near the beginning, but maybe it cancels out with levels near the end? Or maybe faster hint canceling alters lag?
Overall, I think there's still quite a bit of potential to analyze further and squeeze more frames out through a variety of methods. I'd also like to switch over to using non-equal length frames in my next posted movie, since I think ELF hinders the ability to productively work on the movie. Disabling ELF will add some "frames", but the cycle count will reflect the actual time.
EDIT: 6 more frames saved by removing some extraneous inputs from Star 6B.
EDIT 2: 399 more frames saved by hard-resetting between Easy/Kinoko. This is due to seemingly random level lag, and not anything intrinsic to hard-resetting. If level lag can be mitigated through other methods, soft-resetting should be the fastest method.
