Post subject: Denki Blocks!
Joined: 3/7/2011
Posts: 23
Location: Location:
A nice remake of an old puzzle game, and I think this has potential to be quite entertaining. A full TAS would require lots of planning, mostly solving puzzles in the least number of moves (since each move takes the same amount of time.) There would also be planning for avoiding "Pairs" or "Three of a Kind" since the game wastes time congratulating you for getting them. I guess if anyone wants to know more about the game, or if you want to help with planning and such just comment here. I already have a work in progress of the first ranking (out of eight in total I believe). http://www.youtube.com/watch?v=L44_TRwDvEU
Player (75)
Joined: 8/26/2015
Posts: 70
So, many years later, I resurrect thee with mention of progress! I'm not convinced it will be a brilliant TAS to watch, but I thought I'd summarize my research so far anyway: * Text is SLOW. Intros are boring and unskippable. The fastest way through text is to hold A from the frame before characters start appearing to the frame before the red A button appears, release, press, release. * During puzzles, the minimum gap between moves is 9 frames (i.e. you can move every 10th frame) * Each completed shape takes about 85-90 frames. I haven't found a consistent number for this. * "Nice pair!" takes about 180 frames, or 18 moves. Well worth skipping at the cost of moves. While the third point can be mitigated by forming two shapes simultaneously, I assume that's impossible for the majority of levels while going at a reasonable pace, to come up with the following time estimates for the first stage's levels: https://docs.google.com/spreadsheets/d/1TdpN7CvHJjB83i2X-MG4hhWs4Ekixljh1znb5TpwRVI/edit?usp=sharing I also found this website of someone who wrote a program to find optimal solutions, giving us a partial list to work from: http://mzrg.com/games/denki/index.shtml ---- Update: I have a pretty decent WIP of Stage 1 now complete: BizHawk movie.
Player (138)
Joined: 8/27/2004
Posts: 165
What a coincidence! I'm the guy who made that website/program, and I've actually been recently getting into the game again. In the past week or so I've been optimizing some existing solutions and finding decent solutions for puzzles I didn't have a good one for yet (mostly in the later areas), and I think I'm nearly satisfied with the GBA levels for now. I've been also thinking about TASing this lately, but haven't started yet. It's cool and surprising to see someone else interested in this game, especially since you have started work on a TAS! Would you be interested in collaborating? Finding and proving optimal solutions is pretty tough for a lot of the levels, even with a computer program, as the number of states often expands exponentially. So sometimes 100+ move solutions can be proved optimal, but other times you can't even reach 20 moves without running out of memory (in my case about 10 million states can be stored in RAM at once). So, for most of the game, suboptimal solutions are the way you have to go. My program can generate some pretty impressive suboptimal solutions although, of course, the heuristic I use works better on some levels than others. For the hardest levels, I've had to start off by doing some moves (anywhere from a handful to 50+) and letting the program optimize the rest. So there will always be room for improvement, but if we try our best we can end up with solutions that are pretty tough to beat. As for "Nice Pair"/"Three Of a Kind"/"Bonus Shape", I definitely agree it's worth it to avoid them when possible. This should mainly be a problem in the earlier levels because a lot of those are gimmes, whereas in the later levels they can be very difficult and shouldn't show up in optimal solutions. Something that will be a problem throughout is completing colors; it'll save time to finish two or more colors on the same move, but it may not always be possible to avoid that without wasting more moves than it's worth. I think all of these requirements can be worked into the program, to look for solutions with various constraints and see if they are worth using instead of the unconstrained one. I can try to
Player (75)
Joined: 8/26/2015
Posts: 70
Ooh, great, of course I'd like to collaborate! Would you mind either making your program open source or sharing it with me? I was just starting to plan my own Denki Blocks AI already... :) Also, about memory requirements, how much sharing do you do? Are any of your states degenerate? If that isn't helpful, how about using depth-first search, but limited to a number you know is possible for a solution?
Player (138)
Joined: 8/27/2004
Posts: 165
Sure, I'm willing to share it. It's not the most user-friendly thing ever, but it does its job. Not sure what you mean by sharing or degenerate states, but I do avoid positions that clearly don't have enough moves left to match up the pieces. I haven't tried extremely large depth-first searches but I imagine they'd take forever without some heuristics about what moves to try first. http://pastebin.com/HRHi4698 Here are a lot of details about the program: The format of a puzzle is a 256-length string of digits: 0 is empty space, 1 is a wall, 2-4 are colors that need to be paired up to solve the puzzle, and 5-7 are any other colors that don't need to be paired up. This string can contain any extra newlines, so I usually have it broken into the 16 rows for readability. After the string, you can put a | and then a number to give a movecount goal which the program will try to beat; the default is 100. The input file is at least one of these puzzles with newlines between them, and I run the program with "denki.exe < levels.txt". The basic heuristic is a "minimum distance" function, which puts a lower bound on the number of moves it must take to pair up the necessary colors. This provides some basic pruning, as we can throw out positions where moves so far + minimum distance >= goal. This is only based on the walls, not on other pieces, so it works really well on mazelike puzzles and not as well on puzzles with very large pieces that can only move a little. There is also a "looksSolvable" function. Normally this just returns 1 (true), but for some puzzles writing a small custom function and recompiling the program can help by forcing the program to avoid positions that I know will make the puzzle unsolvable, like pairing certain pieces too early. There are a bunch of different solving functions: - iterativeDeepeningSolve: (old) try a depth-first search with depth 0, depth 1, ... - singleMapSolve: try a breadth-first search, storing every position in a hashmap, so we can ignore positions we've already seen. If the map gets too big, kill the search. - moduloMapSolve: same as singleMapSolve, but keep a small rotating list of maps storing the positions in depths i, i+1, i+2, etc. and ignore positions in any of the currently used maps. If the maps get too big in total, kill the search. - moduloMapSuboptimalSolve: same as moduloMapSolve, but have a size limit on each map, and when it gets too big throw out positions with high (minimum distance + penalty * number of groups) to keep the "best" positions. I use this one a lot, and penalties 0, 1, and 5 seem good - often one will catch a solution the others won't. This one will never run out of memory but of course it will often miss fast solutions because it throws out intermediate states. 10000 states per map works okay; 100k is better but very slow. - iterativeDeepeningSolve2: try a depth-first search with depth 0, depth 1, etc. and try to cache recently seen positions so we can . Shouldn't run out of memory but may take extremely long to find optimal solutions. Right now I would use moduloMapSolve for optimal solves and moduloMapSuboptimalSolve for suboptimal. Some things I haven't figured out yet: - Figure out a minimum-distance function that takes other pieces into account, such as knowing we have to move around the big fixed piece in 6-3 or 3-13. - Write a fast algorithm for "can this set of pieces still form into this shape". This would make build-a-shape bonus puzzles solvable, as well as some of the harder puzzles where the board/piece geometry means a specific shape must be made to complete the puzzle. - Handle the case of a piece blocking a hallway, like in the level 2 bonus levels. If something is stuck, we can't go around it, and we have to match pieces on each side of the obstruction, prune the position. - Figure out which pieces can go where and prune positions based on that. For instance, if the only way between two areas is a 1-wide horizontal hallway then we can't match vertical 1x2 blocks on either side of it.
Joined: 12/10/2006
Posts: 118
I like the run so far. Because you don't need to play all levels to advance there is enough choice for the run. It thus differs quite much from a casual play.
Player (75)
Joined: 8/26/2015
Posts: 70
I just wrote a utility to generate the input log from the format used by qqwref on his website. http://jsbin.com/foqerisore/1/edit?html,js,output I'm currently working on Stage 2, but there are 3 possibly improvable stages within it still. ---- I also suspect that it may be possible to get faster times by dropping frames near the end of the puzzle. For example, on my current WIP of stage 2-7, ending either one or two frames later loses me an additional 3 frames, measured from last input of the stage to control regained at the menu. The ending animations shown are the same. Depending on the reason for this loss, it may also be possible to gain frames. However, I'm wondering whether it's merely waiting for a previous animation to complete before playing a new one, in which case such gains are unlikely.
Player (138)
Joined: 8/27/2004
Posts: 165
I'm done getting decent solutions for all the normal levels, and I put all those solutions on the website. So we at least have a baseline solution for everything. I'm planning on putting all my level strings into a single pastebin, to make things easier if you want to try to optimize them. EDIT: Here it is: http://pastebin.com/PLk9tARB I'm also planning on playing through all the solutions and checking the number of ticks for each one. I'd like to reorganize the Google Doc a bit, if you're OK with it - I'd like (a) an extra column for whether the best solution gets an extra cutscene (pair / 3 of a kind / shape), and (b) each level sorted not by proposed order but by estimated ticks. Proposed order should be very quick to figure out when we actually TAS each level, and for planning, the number of ticks would give us a much better sense of what we should try to improve.
Joined: 12/10/2006
Posts: 118
would it be an easy change in the code to pusnish a join with like 7 moves and run for a solution say 2-1 or 2-4 again? do you check for joins after each move at all currently? edit: maybe add +18 moves for a pair in the solution too edit2: Just played with the frame advance in bizhawk. Movement seems a bit more complex. So when you make your first move, there is indeed 9 frames where the next move is not accepted. But after that, it seems that 6 wait frames are enough. If you stop for some frames, the next movement will again be blocked for a waittime of 9 frames once, after that 6 again are enough again. So that should save about 3*#moves frames per level. I found a ram adress: It is 5484 (to use with bizhawk's ram watch). If it is 0 the move will be accepted on the current frame, if it is 1 it won't.
Player (138)
Joined: 8/27/2004
Posts: 165
Ah, that's cool about the 6 frames thing. That means those long waits for matches or pairs are worth even more moves. Does that just apply to any solution, or just a series of moves in the same direction? Punishing a join with a number of moves doesn't really make sense with the way my program works. However, yesterday I added some code to only allow ONE join per level, and then I ran it on all the levels with multiple joins (on the 10000-per-depth suboptimal mode), and it came up with lots of interesting new solutions. Here are all the ones with no pair or 3-of-a-kind cutscene: 1x10: L2 D2 R4 L U2 L U2 L U (16) 1x20: U6 R D12 R12 U9 D3 L D L2 (47) 1x22: D2 L2 D2 L D2 L3 D L D2 L2 U R L2 (22) 1x23: R5 D R D L2 D L3 U3 L D L D2 (22) 2x2: R4 D2 R U5 R2 U3 R2 L U L2 U L3 U L D R D4 U3 L U L D L D2 L2 R D R2 (51) 2x4: D6 L D R D R2 D2 U R3 D R4 D2 R D R (28) 2x10: R3 D3 R D2 R4 U R2 (16) 2x11: L D5 L U7 R U L U L3 D2 L3 D L2 (29) 2x13: L2 U2 L U L2 U L6 U L U R2 D3 R3 U2 L U4 D2 L U L2 U2 R2 U3 (46) 2x15: R3 D4 R2 D U6 R U R U L2 U L D2 R5 D L D2 R (36) 2x21: R U R2 U R6 U3 R2 D2 R D L D L D L U2 L3 D2 R L U L U L U R3 D R3 D2 L3 U R3 L2 D3 U R L D3 U R3 (70) 2x25: U R U3 L3 U L D5 R U2 L U R4 D R3 D5 L U (35) 3x4: R D R D R L2 D L D L2 D R D L U2 L D R U R3 U D R D R3 D L D L U D L D L U R U2 (45) 3x14: D4 L3 D L D R2 D R U L U2 L4 U6 R3 U L U4 L2 D4 R D3 R U3 L U L2 D (56) 3x15: R4 L D L6 D R D U R3 U R U D R D2 R D R2 D3 (33) 3x18: U3 R2 U L2 U9 L4 U3 L R U L5 U L D2 L D2 L2 D R2 U L2 R U2 R U R U L U2 D L (59) 3x22: L2 D2 L D L U R6 U L3 U L U2 L D2 L U R3 (30) 4x3: R7 U2 R U3 R U2 R2 L9 R6 U R U D L7 R6 U2 (52) 4x5: D2 R L2 D2 L U2 L2 D2 L U4 L D2 L2 R2 D L2 D L D L U L D R D R2 D R D U2 L R2 D4 L (53) 4x8: U L U2 L U L D R U R2 U2 L2 U4 L5 R D2 R D R5 D R D3 L2 D4 L2 U5 D L3 D2 L D L2 (63) 4x9: R D R2 D R U3 R2 U R U2 R U2 R U3 L3 R2 D2 L2 U2 R3 U (37) 4x10: R8 D2 R D L D4 L D2 R2 L2 U R2 (27) 4x13: U2 L U6 L D L D L2 U L2 D3 L D L R3 D R L U3 R U D R3 L U L2 D L D2 L D2 L D R D (54) 4x21: D L D2 R D2 U L D L D U R2 U2 L5 R D2 U R2 U2 L D2 L4 U2 R U2 L3 U (46) 4x24: D3 R2 U R U D2 R2 D L D4 R2 L D2 U2 L D L U L2 D5 R D U R U L D L2 (45) 5x2: U4 L2 D L D L U2 L2 U (15) 5x4: L R D R D2 L D L4 D L U4 L R2 U3 L2 U R2 D R2 U L U (35) 5x6: R U2 L3 D L U4 L R U (15) 5x10: L D2 R D R3 D2 U R3 U2 L5 U2 L R D L D2 (29) 5x11: L2 D L2 D2 U L2 U2 L2 U R U R U5 L2 R U2 R D L D8 L D U2 L (44) 5x18: L3 R2 D L3 U5 L2 U2 R2 D3 L2 D L D2 L (30) 6x1: U2 R3 U R4 U3 L U2 L U L3 U2 L U L2 D L D3 R D U R6 (41) 6x7: R2 U L D2 R6 D3 L U3 R U4 L5 R U3 L10 D R D2 U R3 D R (53) 6x8: L2 U R2 L U2 R D3 L4 R U (18) 6x9: L U L U L R U2 L U4 R2 U2 R U3 D R U2 R7 D5 U R3 D R (43) 6x16: R D R L U3 L U R2 D L2 R U R U L2 U2 R (23) 6x17: L D R D L D2 L D3 L5 D4 R U L2 D U2 D L2 (30) 6x23: R3 D5 R D2 L D L2 D L3 U2 R L2 U R U2 R2 L U R2 D2 L5 R D (43) 7x1: R4 D4 L4 D4 R4 D3 L D L U L2 D L5 D R U L U L2 U L3 R2 L U (50) 7x6: D2 L U2 L2 U2 L D4 R4 U2 R3 U3 R U L D L2 U4 L D L2 R4 U7 D L2 U L5 R U R U2 R (66) 7x8: R U5 L U L U L3 U4 R2 U2 R U6 D2 L4 U L U2 (38) 7x14: U3 L2 U L2 R2 U D L2 D4 R D2 R U R L U L2 (28) 7x17: R D2 L D U L U L3 U3 L2 R U3 L U D L D U L U L2 D3 R D U L R U2 (40) 7x18: R3 D3 U L4 U2 L2 U L2 U L (20) 7x20: U R2 U L U R U2 L U R (12) 8x1: R U R2 U3 L U L2 U5 D R2 U2 R U3 L U L3 D L D L U2 L D2 L D L4 U3 L (49) 8x5: U2 L D2 L U R U L2 U3 L5 R4 U2 R3 L U R2 D L2 U R4 D U L U L D L D R D R3 D R L2 U D2 R3 L U D L2 D3 U R3 L U3 D3 R3 (85) 8x6: D3 L2 U2 L3 U L2 D R3 D L D2 U2 L U D L U L2 U R12 D2 L2 (47) 8x16: U3 L D L U L7 U R2 L U2 L U L U R2 U2 L U L U2 L4 U R2 D2 R U (44) There were also solutions for 1x16, 2x1, 2x18, 3x9, 4x15, 6x10, 6x20, and 7x22 that only had one join but made a pair or 3 of a kind. I'm going to try to add some code to ignore pair solutions and then re-run those.
Joined: 12/10/2006
Posts: 118
Nice solutions. It it is 6 frames in any direction as far as i can see, so direction changes don't matter.
Player (75)
Joined: 8/26/2015
Posts: 70
After some computer issues, I'm back in business! On the subject of the number of frames for moving: I can't believe I didn't find that, but then I was using a binary search to find when I could next move, assuming the region where a move could happen is continuous and consistent (it's not). I just tested it out myself now, and found these results:
  • Gaps: 9,6,6 - 4 moves done
  • Gaps: 9,7,{6,7,8} - 3 moves done; last move eaten
  • Gaps: 9,7,9 - 4 moves done
From these results, it looks like if you don't move again on the first frame, you can't continue with the 7-frame movement pattern, and have to restart with the 10-frame. At least it's an easy pattern to TAS with, and the memory watch you found will really help :) I'm just knocking up a lua script to overlay that memory address to make it easier to see when moves can be inputted; I'll edit it in when I'm done. ---- Edit: Basic lua script to watch the memory address found. It unfortunately is more a "are pieces moving" address; it doesn't work to see when a move can be input following a shape complete animation. I'm looking for one of those now. I've found an almost-there address: 0x5410. The value returns to zero the frame after a move is first possible again following a join, which isn't ideal. Update! Found a better address: 0x6A88. This byte has the value 2 while a shape is joining; otherwise 0. Updated script now linked. ---- Another edit: Updated Lua! Automatically does the best input based on the memory addresses mentioned above; press Ctrl+I to open a form to type the solution into in the format used by qqwref's website. (Script moved to gist for easier versioning, etc. Can be put in a github repo if we feel like it.) https://gist.github.com/adituv/6bcc89d7d125e604b0b8 ---- Should I just double post?: Using your new awesome single-join routes, and actually measuring the time taken, I've improved Stage 1 by a further 60 frames, now complete at 13669. The only real improvement now that I can see is a single-join 1-16. http://tasvideos.org/userfiles/info/25419665607784644
Player (138)
Joined: 8/27/2004
Posts: 165
Cool lua stuff, and nice to see the improved Stage 1. I expect the improvements will only become more important after the start, since there are more and more colors and thus more chances to save joins. I put together a program to test solutions. There's a lot of code but most of it is just ported from the C program. Choose the level first, and then you can paste in a move sequence or add and subtract moves with the buttons. Hopefully this is a bit easier than loading up the emulator, and it'll also give you textual positions from partyway through a solution that you can then feed into my program. http://mzrg.com/games/denki/tester.html I also ran the program a bunch to generate more solutions (with no 2-of-a-kinds, or with 2 matches instead of just 1 or 3) but there's a lot of output, so I'll post stuff later after I've looked at it. ----------------------------- EDIT: I looked through the output, and also tried out a new heuristic (in the suboptimal solver, it keeps the best solutions in terms of the sum of the minimum distance for each color, not the overall minimum distance). Sometimes it saves moves and sometimes it doesn't. I put my big table of solutions up as a sheet on the planning spreadsheet. There are always more improvements that can be made, but this is enough to chart out a potential run of the whole thing. I used rough timings of 85 frames for each match and 180 for a pair/3-of-a-kind cutscene, but those are probably not super accurate, so when two solutions are close it's probably worth testing both.
Player (138)
Joined: 8/27/2004
Posts: 165
Bump. I ran through all of the remaining levels without a 1-pair solution, and tried to find better solutions (or convince myself they are certainly or probably impossible). I used the technique of starting partway through a solution I already have, which can sometimes give solutions that are only a few moves off the current best. That Javascript program in the previous post came in really handy for that! There are still a bunch of levels where I couldn't find solutions (or couldn't find good ones), but this should be good for now. The new solutions are on the Google Doc. While we plan out the levels and make a WIP... I'm thinking about maybe a 100% run too. I'd at least like to max out the trophy room. I'm pretty sure that requires completing all main-game levels (30 in the first 7 areas and 25 in the last), plus the 30 Club levels (which require enough stars in the main levels to unlock). It might be cool to also get all available stars, which is only a small difference and will definitely feel more complete. You can get stars by making a bonus shape (1 star) or a 3-of-a-kind (3 stars) on certain levels, and since the ingame par is irrelevant, we would only have to complete those levels once, getting the bonuses as we go. Right now, I can find some 3-of-a-kind and bonus shape solutions, but it's not easy since it's common to end up with incompatible shapes, so I can only really get solutions if they're relatively easy. My plan is to add some code where you can set a fixed shape, and get rid of any positions with shapes that can't be part of that shape. For instance, in 1x15, the bonus shape doesn't include any 2x2 blocks, so if we ever form a 2x2 block we know we have made a wrong move. For 3-of-a-kind puzzles, this will help make sure the pieces all form part of the same goal shape.
Player (75)
Joined: 8/26/2015
Posts: 70
To be honest, I've never even completed the game :P. I'm still after many years stuck at 13/15 required Puzzle Master puzzles. So 100% would be pretty cool, but I actually don't want to do it until I've completed the game ^^. Naturally you can go for it, though! Anyway, for the club puzzles: each of the five rows requires 15 20 stars to wholly unlock, for a total of 75 100 minimum stars required. I believe that X1-X5 don't require stars, but I don't currently have a save file where I can verify that. Trying to route the club puzzles could be an interesting challenge with the various different mechanics like stickers, colour changing blocks, and so on... I'm interested, I think! Time to beat the game, I guess :P
Player (138)
Joined: 8/27/2004
Posts: 165
I've got solutions for the remining Puzzle Master puzzles written up, so you can key those in if you don't mind a bit of cheating :) A lot of the ones near the end are pretty nasty even if you're careful. I don't actually have a sequence for all of the stars yet, but through careful playing and ASchultz's FAQ I could get most of them. He's missing a bunch of the harder ones (so I am too), and as a general rule not all of his move sequences actually work. I think the Club puzzles actually require 20 for each row (2+3+4+5+6) so you would need 100 out of 125. And yeah, the bonus Club puzzles don't require stars, you just have to beat the first 25. A few timings I just did on 2x1, from last button press to the level screen showing again: - Pairing one block takes 313 frames - Pairing three blocks at once takes 313 frames (0 extra) - Nice Pair! takes 493 frames (180 extra) - 3 of a Kind! takes 734 frames (421 extra) due to the star cutscene That 3-of-a-kind penalty only really matters for 1-4, because only that and 6-2 require a pair or more (and in 6-2 a 3 of a kind is impossible). Good to know though. Also, on 2x5, same timing: - Pairing takes 313 frames (whether or not we hit the par time/move!) - Bonus Shape takes 673 frames (360 extra)
Player (138)
Joined: 8/27/2004
Posts: 165
I went through and finished a full any% run: User movie #25736156978858764 Time is 31:42.21 [113614 frames]. Making the TAS itself went really quickly because of TAStudio and AdituV's lua script. I tried to optimize menuing and text, but I'm not an experienced TASer, so it's quite probable I missed something. For a fun sidenote, earlier today I was bored and tried to make a Denki Blocks puzzle with the longest possible solution. I played around with it in my tester program and got 874 moves. Here's what it looks like (the blues need to be solved):
Player (138)
Joined: 8/27/2004
Posts: 165
I coded in some shape-checking functionality, and using that I was able to find some pretty good solutions to all of the bonus-shape and 3-of-a-kind puzzles. They are up on my website (http://mzrg.com/games/denki/shapes-GBA.shtml and http://mzrg.com/games/denki/3kind-GBA.shtml) as well as on the Google Doc (https://docs.google.com/spreadsheets/d/1TdpN7CvHJjB83i2X-MG4hhWs4Ekixljh1znb5TpwRVI). I wasn't sure if I would be able to do 8-10, since that one is really nasty, but I eventually did end up with a solution after a bunch of trial and error, and doing partial solves to see how to get one or two more matches without ruining the shapes I wanted to set up. So, even after a bunch of optimizations I've already made, it's longer than any solution I have for anything else, with the current one weighing in at 217 moves. Much better than the 371-move solution the FAQ gives for 7-9, though :p Here's the current solver program. It has a bunch of #define options for checking for pairs, keeping track of joins, forcing shapes, etc., some of which are only set up for the suboptimal search function I've been using. The idea is that you can change the #define statements and recompile as necessary. C++ can be a bit cumbersome, but I need the speed, since searches already take quite a while and there are 200+ puzzles. http://pastebin.com/kXm3KLvB
Player (75)
Joined: 8/26/2015
Posts: 70
The old spreadsheet was getting pretty crowded, so I started making a new one for 100% planning. https://docs.google.com/spreadsheets/d/1pZvB3le8qxXBW4u4vEqZ5P9K5pRhCxFDk22V3yNq2Q0/edit?usp=sharing I've started planning and tweaking existing solutions to use fewer joins in a couple of places. I'm thinking of creating separate input logs for each level so it's easier to just stitch them together if we improve a single level rather than more manual editing after that point, but not sure it's worth it overall. I've also improved my lua script. It now has keybinds for frame-perfect input, as well as pausing when a certain condition is reached. https://gist.github.com/adituv/6bcc89d7d125e604b0b8
Joined: 12/10/2006
Posts: 118
Nice work you both.
Player (138)
Joined: 8/27/2004
Posts: 165
I've been searching for TAS-optimized solutions for the shape and 3-of-a-kind challenges, as well as the five bonus levels for each stage (only levels 2, 5, and 7 have multiple colors). These are all on the old spreadsheet. For now, I'd say I'm done with that part. I'm pretty happy with what I found, but improvements are always possible and welcome. This means that the last optimization hurdle is the Club levels. Apart from having to add all the special blocks into the optimizing program, I've noticed another problem: some types of blocks cost time, and the program is set up to think in terms of movecount, not time. Specifically, the Painter block costs a constant number of frames for every turn where at least one block is painted, and the Joker blocks have a cascade effect which costs more time the further a triggered joker is from the triggering block. The Joker only appears in two short levels, so we can probably get away without coding to it, but the Painters are pretty common and occur in long levels, so optimizing that will be important for the Club part of 100%. Finally, a lot of cutscenes (e.g. tournament explanation, stage start, stage clear) can be skipped with a reset - the game assumes you watched them and won't show them again. I don't know if this saves time or not yet, and I'll look into this for both any% and 100%.
Player (75)
Joined: 8/26/2015
Posts: 70
qqwref wrote:
Finally, a lot of cutscenes (e.g. tournament explanation, stage start, stage clear) can be skipped with a reset - the game assumes you watched them and won't show them again. I don't know if this saves time or not yet, and I'll look into this for both any% and 100%.
I had a few minutes of free time, so I looked into hard resetting to skip tournament explanation. I failed to get a reset to skip the new account intro dialog, though. Anyway, the result is in: 232 frame saving of hard reset over no reset on that dialog! Resets take ~419 frames (modulo selecting which ranking, which might matter a bit in 100%, but don't think it will in any%) I can't believe resets didn't occur to me before... ^^
Player (75)
Joined: 8/26/2015
Posts: 70
Two minutes saved by resetting! Woah! http://tasvideos.org/userfiles/info/26225779388733190 (Aside: I'm surprised it only took me 100 more rerecords or so, as I brute forced every reset in a relatively large window!)
Player (138)
Joined: 8/27/2004
Posts: 165
I ran through 100%, up to and including stage 8: http://tasvideos.org/userfiles/info/26553525549446392 This includes getting all 125 stars (4 from tutorials) and completing the 5 extra levels in stages 1-7. I also reset to skip cutscenes. The 3-of-a-kind cutscenes take a while but I have a feeling skipping them would just lead to the level not recording. For a little extra entertainment, I did each stage's levels in a different order without wasting time. The orders for levels 1-7 have something to do with the extra levels' shapes (for instance, level 1 goes in a spiral). As for the Club levels... it seems like painting blocks with a Painter takes 10 extra frames per move (no matter how many pieces are painted), and joining Jokers takes 10 extra frames per wave of recoloring. I'm going to see if I can find a way to work this kind of thing into my program.
Player (137)
Joined: 9/18/2007
Posts: 389
I said it might be possible to use a SAT solver for this game. I took some time to think about it how that game can be modeled. I try to write down ALL rules which decide which block can be moved to the right side on the first turn. It shouldn't be any problem to do the same for left, up, down. If everything works well, all what needs to be done in the next step is to write these rules for each move. We need a few variables.
1 <= i <= total rows
1 <= j <= total columns
1 <= c <= number of different colors
1 <= d <= 4, d = direction, 1 = right, 2 = left, 3 = up, 4 = down (for example)

M_{i,j,d} <=> The tile which is located in row i, column j can be !M!oved in direction d
C_{i,j,c} <=> The tile at {i,j} has the !C!olor c. 
F_{i,j} <=> There is no tile at {i,j} (!F!ree)

RSC_{i,j} <=> tiles {i,j} and {i,j+1} (one !R!ight) have the !S!ame !C!olor
DSC_{i,j} <=> tiles {i,j} and {i+1,j} (one !D!own) have the !S!ame !C!olor
Some of these are obvious, some are not. Let's start with the more obvious.
RSC_{i,j} <=> (not F_{i,j} AND (not F_{i,j+1}) AND (forall c: C_{i,j,c} == C_{i,j+1,c})
DSC_{i,j} <=> (not F_{i,j}) AND (not F_{i+1,j}) AND (forall c: C_{i,j,c} == C_{i+1,j,c})
if there is a non-movable tile at {x,y} then all the following boolean values must be false:
M_{x,y,1}, M_{x,y,2}, M_{x,y,3}, M_{x,y,4}
M_{x,y-1,1}
M_{x,y+1,2}
M_{x+1,y,3}
M_{x-1,y,4}
The real difficulty is to determine the correct value of M_{i,j} in all the other cases. If X is a non-movable tile, the following cases are easy:
_ _ 1 _ X _ _
..............
_ _ 1 X _ _ _
but we also need to make sure that it works well in the following cases:
1 1 1 _ _ _ _
_ _ 1 _ _ _ _
_ 1 1 1 1 1 _
_ 1 2 1 _ _ _
_ 1 1 1 _ _ _
..............
1 1 1 _ _ _ _
_ _ 1 _ _ _ _
_ 1 1 1 1 1 _
_ 1 2 1 _ _ _
_ 1 1 1 X _ _
..............
1 1 1 _ _ _ _
_ _ 3 _ _ _ _
_ 1 1 1 1 1 _
_ 1 2 1 _ _ _
_ 1 1 1 _ _ _
I'm not sure how to code that in such a way that every movable thing gets moved. I take the following guess:
M_{i,j,1} if (and only if???) ALL of the following conditions are met:

1) either F_{i,j+1} or M_{i,j+1}
2) if RSC_{i,j} then M_{i,j+1,1}
3) if RSC_{i,j-1} then M_{i,j-1,1}
4) if DSC_{i,j} then M_{i+1,j,1}
5) if DSC_{i-1,j} then M_{i-1,j,1}
If the above works for every case you can think of, I can go on and encode the winning condition, which will be quite hard. I hope you have a good idea for that, my idea would require N*R*C variables per turn, where N is the number of tiles which must become connected. And with 200 tiles on a 32*32 field, and a solution of 100 turns, this would need 20.480.000 variables and many clauses just for the winning condition. Improving that in some way might be necessary for a usable solver. -------------------------- From the mathematical point of view, I guess it would be sufficient to only encode "movable to the right", because all other cases can be done in other ways: move left: flip the playing field horizontal move up/down: flip diagonal Both ways of encoding work, I'm not sure which one works better