Posts for partyboy1a

1 2 3 4
15 16
Posted: 8/26/2013 10:40 AM
Quote
partyboy1a
Experienced Forum User, Published Author, Player (136)
Joined: 9/18/2007
Posts: 389
OK, so it seems to be possible to move the cursor by 40 pixels per frame without delaying. All tiles are 16x16 pixels, so speed can be at most 2.5 tiles per frame. I adjusted the solver one more time, now it has a really nice way for Lua interoperation: p-solver-v3.0.0.zip. You only need to find out the coordinates of the topmost leftmost tile and adjust the coordinates accordingly.
Posted: 8/19/2013 3:21 PM
Quote
partyboy1a
Experienced Forum User, Published Author, Player (136)
Joined: 9/18/2007
Posts: 389
The rules are just slightly more complex: 3 frames required for first tile. 1 frame if you just jump 1 or 2 tiles if you want to jump a wider distance (or to finish the path) - click the tile you want to jump from for 2 frames - one frame with no input - click your destination for 3 frames. So you need at least 3 + 2 + 1 + 3 = 9 frames to solve a puzzle. For puzzle mode, the new strategy is always better, it never makes sense to use a wide jump. For almost all cases and a board of at most 11x11 tiles (including the border), the new strategy is at least as fast as the old one. If we name the tiles like in a chess board and just write down which tile to click each frame: 
Old: ..... A1, A1, A1, nil, A11, A11, A11
New: ..... A1,[A1, A1,] A3, A5,   A7, A9, A11{, A11}
[] required if the path starts at A1, {} required if the path finishes at A11. Note that the last input from the 1-frame sequence is ignored. For example: A1, A1, A1, C1, E1, F1, nil, nil will let the path finish at E1. I already adjusted the solver for the new strategy, will be posted when both strategies can be used.
Posted: 8/14/2013 9:21 AM
Quote
partyboy1a
Experienced Forum User, Published Author, Player (136)
Joined: 9/18/2007
Posts: 389
Well, it seems that we did a bad job in finding the rules for valid input. I just made a small test which demonstrates faster input methods: http://tasvideos.org/userfiles/info/8602286225201954 Too bad this will make it necessary to rewrite the solver.
Posted: 5/5/2013 1:31 PM
Quote
partyboy1a
Experienced Forum User, Published Author, Player (136)
Joined: 9/18/2007
Posts: 389
YAY, finally we do actually have a TAS of Terranigma. Great! Now we can analyze this one, and find more time-savers, and test other strategies for grinding. One of my ideas is to use a death-warp at some point. For example, this might avoid one boat trip, and crossing the desert for the second time. It needs some set-up time save, enter an area with enemies, die. It might be worth it.
Posted: 2/20/2013 7:38 AM
Quote
partyboy1a
Experienced Forum User, Published Author, Player (136)
Joined: 9/18/2007
Posts: 389
The solver uses a quite simplistic way to measure the "score". It looks for turns in the path, and looks for long connections. If we find out that A-B-C can always be done in 6 frames, and A-B-C-D always requires 7 frames, it's easy to change the solver for that. It only matters to find the exact set of rules when we can use 6 frames for non-adjacent tiles. If the rules are really complicated, the solver might become slower, but that shouldn't be a problem.
Posted: 2/18/2013 10:03 AM
Quote
partyboy1a
Experienced Forum User, Published Author, Player (136)
Joined: 9/18/2007
Posts: 389
I did see the "WIP" for the menus. Unfortunately, I cannot really do this TAS at the moment. I do not have a Windows PC at the moment. The Linux version of DeSMuME sucks, wine doesn't work good enough for the Windows version.
Posted: 2/18/2013 9:22 AM
Quote
partyboy1a
Experienced Forum User, Published Author, Player (136)
Joined: 9/18/2007
Posts: 389
The floor skip can also be executed if you do have too much horizontal speed after a slide. In Log Trail, I had to slow down in one place close to the beginning because of this glitch. There is one frame where I had to press "left" to avoid falling through the floor. Unfortunately, I think it doesn't work in the same way for a different terrain. If you can jump through the floor from the bottom, you can fall through the floor if it is not flat. If you cannot jump through the floor from the bottom (like most floors in Gohome Cavern), the same thing doesn't work. Getting stuck in the ceiling... that looks really interesting. This might save time if this makes some kind of "Wrong Warp" possible, like it was done in Ocarina Of Time. It won't save time until level completion, the UFO stage is just too short already.
Posted: 2/14/2013 11:19 AM
Quote
partyboy1a
Experienced Forum User, Published Author, Player (136)
Joined: 9/18/2007
Posts: 389
I haven't ever seen such an action-packed run. Every single level was surprising. I guess this will become the TAS of the year. The Huffin Puffins look quite funny when they aren't supposed to exist. And thanks for the shout-out.
Posted: 2/12/2013 3:23 PM
Quote
partyboy1a
Experienced Forum User, Published Author, Player (136)
Joined: 9/18/2007
Posts: 389
Is this game compatible with lsnes or Bizhawk? If yes, we should reject this run solely for emulator choice. The whole game has been created after Snes9x has become deprecated. I don't like this sort of hack. It is almost impossible to win this game without tools. Creating games just for TASing doesn't make any sense for me. However, I liked the Bowser fight. In the 96-exit video, some levels have been completed by some sort of item overload. I think that should be faster than playing through all the auto-scrollers (if it's possible).
Posted: 1/29/2013 2:11 PM
Quote
partyboy1a
Experienced Forum User, Published Author, Player (136)
Joined: 9/18/2007
Posts: 389
Another attempt for the SAT solver: Yoshis Cookies (+ SAT solver framework + minisat / picosat) Performance is quite bad. If the puzzle is just a little bit more complicated, then the solver can take forever...
Posted: 1/24/2013 10:15 PM
Quote
partyboy1a
Experienced Forum User, Published Author, Player (136)
Joined: 9/18/2007
Posts: 389
"genetic" algorithms? I think that is much too resource-intensive to be doable in the near and in the far future... Also It cannot be possible to find the "best" solutions without human interaction... The least what is required is to tell the program when you "win", and this alone is a difficult task, and may even be subjective (just think of the glitched version of Super Mario World, which shows "The End" while playing a normal level). Just defining the winning condition is most likely only possible by disassembling each game, every single line of code... However, I wish you good luck with your project!
Posted: 1/22/2013 7:35 AM
Quote
partyboy1a
Experienced Forum User, Published Author, Player (136)
Joined: 9/18/2007
Posts: 389
Well, brute-forcing isn't gonna become possible at any time in the future. The amount of possible inputs is much too big for that, especially for the DS. All solutions have been proven to be optimal, there doesn't exist any solution which is faster. There are of course some assumptions necessary for this... One of these assumptions is p-solver is working correctly. Another one There are no glitches in this game which may provide a speed-up. Another one The menu navigation is done optimal. Another one sub-frame input won't make it possible to enter the solutions faster. (If this assumption is wrong, then p-solver does most likely not work correctly.) These assumptions will most likely never be provable... However accept the assumptions, and you cannot beat the movie. Prove one of the assumptions as wrong, and you're ready to create a shorter movie. In any case, it is still possible to create an equally-fast probably more entertaining movie, as there is a lot of spare time for creative drawings, and entertainment can definitely not be proven to be optimal...
Posted: 1/19/2013 11:17 AM
Quote
partyboy1a
Experienced Forum User, Published Author, Player (136)
Joined: 9/18/2007
Posts: 389
duksandfish wrote:
Thanks for the new version, as well as the puzzle mode solutions you gave me in the pm. [...] In terms of the actual TAS, I could now make an optimal run of puzzle mode fairly easily, since actually inputting solutions isn't that hard.
Yeah, I gave it a try, and noticed it is faster to press "START" between the puzzles than to click away the "completed" message. I'm not that terribly creative when it comes to the play-around part, my best idea was to write a text like "tool-assisted superplay". You can do that run if you want (and maybe include me as a co-author for finding the solutions).
Warepire wrote:
I don't see any reason to why a puzzle-mode TAS should not be publishable in the Vault tier.
I think so too... and also, it would possibly be the first run on this page which has been PROVEN to be absolutely frame-perfect.
Posted: 1/17/2013 9:00 PM
Quote
partyboy1a
Experienced Forum User, Published Author, Player (136)
Joined: 9/18/2007
Posts: 389
p-solver-v1.0.1, fixed a crash which could happen if the very first attempt was faster than all step-limited attempts afterwards.
Posted: 1/17/2013 8:11 AM
Post subject: SAT solvers: let them find the best solutions for your game!
Quote
partyboy1a
Experienced Forum User, Published Author, Player (136)
Joined: 9/18/2007
Posts: 389
Sometimes, your task is to solve a certain kind of puzzle optimally. At the same time, there are a lot of different possible solutions for the puzzle, probably more than you could ever handle. And now you ought to find the very best of all sollutions... This is where SAT solvers can come in very handy. These can solve the boolean satisfiability problem very very fast (most of the time). You just give them the rules of the game in an appropriate format, and it will find ONE solution for you (if a solution exists). So if it's still a solvable problem, you just have to add some more rules to find a better solution. At some point, you will have found the best solution this way, AND you even proved that the solution is optimal. The biggest problem about that is: You have to translate the game into a set of just boolean variables. This is quite hard, you need to consider absolutely every detail, even the most "trivial" rules, and rules you wouldn't really think of. So it's limited to games where you really know ALL rules. However, I got it to work for DS Polarium (there it is relatively slow on small puzzles, but very fast for larger or more difficult ones), and I made a small SAT-solver-framework.lua which simplifies the task of entering clauses, and a sample file on how to use it... I used it to implement the rules of Tetris (well, only 1 / 20th right now, and I will most probably not implement the rest, I think there is already very good software available for this game...) in a way so that a SAT solver can understand it, get Tetris.lua here. Can you think of more games where such a SAT solver approach may work?
Posted: 1/16/2013 3:01 AM
Quote
partyboy1a
Experienced Forum User, Published Author, Player (136)
Joined: 9/18/2007
Posts: 389
That's most likely some kind of misconfiguration in CodeBlocks. I could also produce these errors when I tried to compile the program by hand. There are multiple source files. It is not possible to compile AND link main.cpp right away, you first have to compile (but NOT link) P_Puzzle.cpp and P_Solution.cpp. If the IDE is configured right, all files get compiled first, and after ALL files have been compiled, they are linked. You have some kind of misconfiguration, your compiler tries both steps at once. This only works if you have exactly one source file. And by changing the includes, you basically copy-paste all six files into one big file. It does work, but this kind of workaround is not the best thing to do. Maybe it's enough to add "-c" to the compiler options somewhere. Just another idea a "complete rebuild" might help. I had to do this whenever I copied the project from my Linux PC to a Windows PC and vice versa. You can also try out puzzle_benchmark, it'll run for about an hour... but it will finish.
Posted: 1/16/2013 2:28 AM
Quote
partyboy1a
Experienced Forum User, Published Author, Player (136)
Joined: 9/18/2007
Posts: 389
duksandfish wrote:
It is outputting the shortest_puzzle_sample and fastest_puzzle_sample though. (and a file solution.txt containing just "UNSAT", though I'm guessing that's something to do with minisat.
That's nice to know, it seems to work fairly well. shortest_puzzle_sample and fastest_puzzle_sample are just ordinary text files, so you can view them with any editor you like (I recommend Notepad++). And if you don't like the Linux way of text files, just append .txt to the puzzle files, this will work well solution.txt is just an intermediate file produced BY minisat, p_puzzle.cnf is just an intermediate file produced FOR minisat, containing all the rules of the game, but in a very unreadable way (for humans, computers like this one a lot better...)
Posted: 1/16/2013 1:15 AM
Quote
partyboy1a
Experienced Forum User, Published Author, Player (136)
Joined: 9/18/2007
Posts: 389
That's looking like a linker error. Most of the time, this is happening because the compiler is incomplete, or because of a misconfiguration in the IDE. I use g++ for compiling right now. If you use another one, you might need to download that one separately, or specify the right path to the compiler, and linker inside CodeBlocks. (Well, and you need to look into the readme file, this program is very hard to setup on Windows, I'm sorry for that... There is a lot of additional work involved just for getting the solver working, you need to install Cygwin AND MinGW. Cygwin for minisat, MinGW for the compiler. Well, I chose MinGW to compile on Windows, which seems to work.) I promise this work will pay off... For "somewhat" easy puzzles, the solver from ais is faster, but for complex puzzles, mine is faster. And I'm pretty sure that the puzzle file "puzzle_benchmark" is much too hard for all the other solvers.
Posted: 1/15/2013 4:28 PM
Quote
partyboy1a
Experienced Forum User, Published Author, Player (136)
Joined: 9/18/2007
Posts: 389
Get the solver NOW!
Posted: 1/10/2013 10:50 AM
Quote
partyboy1a
Experienced Forum User, Published Author, Player (136)
Joined: 9/18/2007
Posts: 389
So... is there someone out here who tried to play this one with SNEShawk? If it's playable, it'll be quite easy to create a movie which just completes the game. So... you would vote on rejecting this movie if this game can be beaten using SNEShawk or lsnes? (And if it cannot be played on a real console, we might invent a new "console" named "snes9x" to deal with it... just some crazy idea.) It might be a hard decision to reject a good movie just for emulator choice, but I guess that Super Mario World was one of the most important reasons to deprecate Snes9x, as the improvements became highly emulator dependant...
Posted: 1/10/2013 5:58 AM
Quote
partyboy1a
Experienced Forum User, Published Author, Player (136)
Joined: 9/18/2007
Posts: 389
That's a pity... We SHOULD be consequent and reject this run for using a deprecated emulator, as this run is not listed in the allowed continuances (only the 120 exits run is listed). I'll vote yes regardlessly.
Posted: 1/9/2013 5:37 PM
Quote
partyboy1a
Experienced Forum User, Published Author, Player (136)
Joined: 9/18/2007
Posts: 389
Occasionally, I thought that some movements could have been done slightly better. There were some nice creative solutions for some levels. Improvable by a bit, but good enough right now. For example If you use two players, Toad won't appear, so you can avoid some dialogs in world one. You also don't have to do any meaningful movements with the second player, you can just put him into a bubble. An interesting question would be if it's possible to avoid using the roller coaster with four players... If it's possible, it might save a little time. I'll give it a yes.
Posted: 1/7/2013 10:08 AM
Quote
partyboy1a
Experienced Forum User, Published Author, Player (136)
Joined: 9/18/2007
Posts: 389
I invented some new way to describe the puzzle to the SAT solver (after having a closer look into the solver from ais)... and now the performance definitely outbeats all the others! The "benchmark" puzzle is solved in just one minute for both the shortest and the fastest solution... So here comes the best solutions for these: (Sorry for all those long posts, but I think these news are worth it... There are still some bugs left, I'll fix them before this gets released.) The parameters given: Download main.cpp
Language: cpp
int main()
{
    PolariumPuzzle *p = new PolariumPuzzle();
    Solution s;

    unsigned char puz[] = {
        1,0,0,0,0,0,0,0,
        0,0,0,0,0,0,0,1,
        1,0,0,0,0,0,0,0,
        0,0,0,0,0,0,0,1,
        1,0,0,0,0,0,0,0,
        0,0,0,0,0,0,0,1,
        1,0,0,0,0,0,0,0,
        0,0,0,0,0,0,0,1
    };
    p->SetPuzzle(puz, 8, 8);
    //p->Solve();

    // prove that all solutions require at least 63 frames
    p->ConvertToCNF(s, 62, -1, -1);
    // prove that all solutions are at least 44 tiles long.
    p->ConvertToCNF(s, -1, 43, -1);
    // find a solution which is exactly 44 tiles long.
    p->ConvertToCNF(s, -1, 44, -1);
    // find a solution which requires 63 frames
    p->ConvertToCNF(s, 63, -1, -1);
    delete p;
}
Download output.txt
Language: txt
solvingpattern[0]: 
0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 
0 0 1 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 1 0 0 
0 0 1 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 1 0 0 
0 0 1 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 1 0 0 
0 0 1 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 1 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 

solvingpattern[1]: 
0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 1 1 1 1 1 1 1 0 0 
0 0 1 1 1 1 1 1 1 0 0 0 
0 0 0 1 1 1 1 1 1 1 0 0 
0 0 1 1 1 1 1 1 1 0 0 0 
0 0 0 1 1 1 1 1 1 1 0 0 
0 0 1 1 1 1 1 1 1 0 0 0 
0 0 0 1 1 1 1 1 1 1 0 0 
0 0 1 1 1 1 1 1 1 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 


validpattern[0]: 
0 0 0 0 0 0 0 0 0 0 0 0 
0 1 1 1 1 1 1 1 1 1 1 0 
0 1 1 0 0 0 0 0 0 0 1 0 
0 1 0 0 0 0 0 0 0 1 1 0 
0 1 1 0 0 0 0 0 0 0 1 0 
0 1 0 0 0 0 0 0 0 1 1 0 
0 1 1 0 0 0 0 0 0 0 1 0 
0 1 0 0 0 0 0 0 0 1 1 0 
0 1 1 0 0 0 0 0 0 0 1 0 
0 1 0 0 0 0 0 0 0 1 1 0 
0 1 1 1 1 1 1 1 1 1 1 0 
0 0 0 0 0 0 0 0 0 0 0 0 

validpattern[1]: 
0 0 0 0 0 0 0 0 0 0 0 0 
0 1 1 1 1 1 1 1 1 1 1 0 
0 1 0 1 1 1 1 1 1 1 1 0 
0 1 1 1 1 1 1 1 1 0 1 0 
0 1 0 1 1 1 1 1 1 1 1 0 
0 1 1 1 1 1 1 1 1 0 1 0 
0 1 0 1 1 1 1 1 1 1 1 0 
0 1 1 1 1 1 1 1 1 0 1 0 
0 1 0 1 1 1 1 1 1 1 1 0 
0 1 1 1 1 1 1 1 1 0 1 0 
0 1 1 1 1 1 1 1 1 1 1 0 
0 0 0 0 0 0 0 0 0 0 0 0 


WARNING: for repeatability, setting FPU to use double precision
============================[ Problem Statistics ]=============================
|                                                                             |
|  Number of variables:         35815                                         |
|  Number of clauses:          137659                                         |
|  Parse time:                   0.14 s                                       |
|  Eliminated clauses:           0.40 Mb                                      |
|  Simplification time:          0.45 s                                       |
|                                                                             |
============================[ Search Statistics ]==============================
| Conflicts |          ORIGINAL         |          LEARNT          | Progress |
|           |    Vars  Clauses Literals |    Limit  Clauses Lit/Cl |          |
===============================================================================
|       100 |   23005   125256   477030 |    45927       99     10 |  2.706 % |
|       250 |   23005   125256   477030 |    50519      249     10 |  2.706 % |
|       475 |   23005   125256   477030 |    55571      474     10 |  2.706 % |
|       812 |   23004   125128   476476 |    61129      810     10 |  2.708 % |
|      1318 |   23003   123653   469868 |    67242     1315     10 |  2.711 % |
|      2077 |   23002   122891   466414 |    73966     2073     12 |  2.714 % |
|      3216 |   23001   122161   463177 |    81362     3211     14 |  2.717 % |
|      4924 |   23000   121392   459678 |    89499     4918     15 |  2.720 % |
|      7486 |   22998   119946   453165 |    98449     7478     16 |  2.725 % |
|     11330 |   22998   119946   453165 |   108293    11322     16 |  2.725 % |
|     17096 |   22998   119946   453165 |   119123    17088     16 |  2.725 % |
===============================================================================
restarts              : 82
conflicts             : 22894          (1192 /sec)
decisions             : 31340          (0.00 % random) (1632 /sec)
propagations          : 46316550       (2411667 /sec)
conflict literals     : 354771         (43.34 % deleted)
Memory used           : 25.00 MB
CPU time              : 19.2052 s

UNSATISFIABLE
no solution found!
WARNING: for repeatability, setting FPU to use double precision
============================[ Problem Statistics ]=============================
|                                                                             |
|  Number of variables:         50568                                         |
|  Number of clauses:          130856                                         |
|  Parse time:                   0.13 s                                       |
|  Eliminated clauses:           0.71 Mb                                      |
|  Simplification time:          0.52 s                                       |
|                                                                             |
============================[ Search Statistics ]==============================
| Conflicts |          ORIGINAL         |          LEARNT          | Progress |
|           |    Vars  Clauses Literals |    Limit  Clauses Lit/Cl |          |
===============================================================================
|       100 |   29069   113210   375677 |    41510       98     11 |  1.805 % |
|       250 |   29048   113210   375677 |    45661      246     10 |  1.847 % |
|       475 |   29048   112702   373494 |    50227      471     13 |  1.847 % |
|       812 |   29048   112702   373494 |    55250      808     13 |  1.847 % |
|      1318 |   29048   112702   373494 |    60775     1314     15 |  1.847 % |
|      2077 |   28988   105341   340930 |    66852      941     11 |  1.966 % |
===============================================================================
restarts              : 15
conflicts             : 2575           (1617 /sec)
decisions             : 4631           (0.00 % random) (2909 /sec)
propagations          : 3351230        (2104913 /sec)
conflict literals     : 35041          (49.05 % deleted)
Memory used           : 29.00 MB
CPU time              : 1.5921 s

UNSATISFIABLE
no solution found!
WARNING: for repeatability, setting FPU to use double precision
============================[ Problem Statistics ]=============================
|                                                                             |
|  Number of variables:         51271                                         |
|  Number of clauses:          133003                                         |
|  Parse time:                   0.13 s                                       |
|  Eliminated clauses:           0.72 Mb                                      |
|  Simplification time:          0.53 s                                       |
|                                                                             |
============================[ Search Statistics ]==============================
| Conflicts |          ORIGINAL         |          LEARNT          | Progress |
|           |    Vars  Clauses Literals |    Limit  Clauses Lit/Cl |          |
===============================================================================
|       100 |   29110   114006   379144 |    41802       98      9 |  1.818 % |
|       250 |   29110   113932   378991 |    45982      248     10 |  1.818 % |
|       475 |   29110   113932   378991 |    50580      473     13 |  1.818 % |
|       812 |   29110   113932   378991 |    55638      810     14 |  1.818 % |
|      1318 |   29090   113874   378875 |    61202     1315     14 |  1.857 % |
===============================================================================
restarts              : 10
conflicts             : 1545           (1215 /sec)
decisions             : 5911           (0.00 % random) (4647 /sec)
propagations          : 2194265        (1724944 /sec)
conflict literals     : 21216          (47.44 % deleted)
Memory used           : 29.00 MB
CPU time              : 1.27208 s

SATISFIABLE
row 1 was NOT flipped
row 2 was flipped
row 3 was NOT flipped
row 4 was flipped
row 5 was flipped
row 6 was NOT flipped
row 7 was NOT flipped
row 8 was flipped

VISITED FIELDS: 

0000000000
1100000000
1111111100
1100000000
1111111100
1011111110
1000000011
1100000001
0111111101
0000000111

START: (5,4)
END: (10,7)

SOLUTION: 

. . . . . . . . . . 
                    
x-x . . . . . . . . 
| |                 
x x-x-x-x-x-x-x . . 
|                   
x-x . . . . . . . . 
  |                 
x-x x-x-x-x x-x . . 
|   |     | | |     
x . x-x-x x-x x-x . 
|               |   
x . . . . . . . x-x 
|                 | 
x-x . . . . . . . x 
  |               | 
. x-x-x-x-x-x-x . x 
              |   | 
. . . . . . . x-x-x 
                    
WARNING: for repeatability, setting FPU to use double precision
============================[ Problem Statistics ]=============================
|                                                                             |
|  Number of variables:         36148                                         |
|  Number of clauses:          138325                                         |
|  Parse time:                   0.14 s                                       |
|  Eliminated clauses:           0.39 Mb                                      |
|  Simplification time:          0.44 s                                       |
|                                                                             |
============================[ Search Statistics ]==============================
| Conflicts |          ORIGINAL         |          LEARNT          | Progress |
|           |    Vars  Clauses Literals |    Limit  Clauses Lit/Cl |          |
===============================================================================
|       100 |   23495   127201   483784 |    46640       98      8 |  3.093 % |
|       250 |   23494   127201   483784 |    51304      247      8 |  3.096 % |
|       475 |   23494   127201   483784 |    56434      472      8 |  3.096 % |
|       812 |   23492   125965   479068 |    62078      805      9 |  3.101 % |
|      1318 |   23491   123842   469597 |    68286     1310     12 |  3.104 % |
|      2077 |   23319   123319   467901 |    75114     2062     14 |  3.580 % |
|      3216 |   23319   123319   467901 |    82626     3201     16 |  3.580 % |
|      4924 |   23318   122580   464582 |    90888     4908     17 |  3.582 % |
|      7486 |   23317   121841   461269 |    99977     7469     18 |  3.585 % |
|     11330 |   23317   121841   461269 |   109975    11313     17 |  3.585 % |
|     17096 |   23317   121841   461269 |   120973    17079     17 |  3.585 % |
|     25745 |   23317   121841   461269 |   133070    25728     17 |  3.585 % |
===============================================================================
restarts              : 116
conflicts             : 31424          (1238 /sec)
decisions             : 45215          (0.00 % random) (1782 /sec)
propagations          : 54177150       (2135179 /sec)
conflict literals     : 523569         (43.51 % deleted)
Memory used           : 25.00 MB
CPU time              : 25.3736 s

SATISFIABLE
row 1 was NOT flipped
row 2 was flipped
row 3 was flipped
row 4 was NOT flipped
row 5 was flipped
row 6 was flipped
row 7 was NOT flipped
row 8 was flipped

VISITED FIELDS: 

0000000000
1100000000
1111111100
1011111111
1000000011
1011111111
1111111101
0100000001
0111111101
0000000111

START: (3,2)
END: (14,7)

SOLUTION: 

. . . . . . . . . . 
                    
x-x . . . . . . . . 
| |                 
x x-x-x-x-x-x-x . . 
|             |     
x . x-x-x-x-x-x x-x 
|               | | 
x . . . . . . . x x 
|               | | 
x . x-x-x-x-x-x-x x 
|   |             | 
x-x x-x-x-x-x-x . x 
  |               | 
. x . . . . . . . x 
  |               | 
. x-x-x-x-x-x-x . x 
              |   | 
. . . . . . . x-x-x
-------------------------------------------------------------------------------------- Yay, now everything is done, even some fine-tuning. Now it can even solve a benchmark puzzle which is a lot harder: Download puzzle_benchmark3.txt
Language: txt
12 12
1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1
It takes one hour to find the shortest, and the fastest solution, and it takes about 20 minutes to verify that a given solution is optimal. Note that no attempt was done for finding the fastest solution for a given amount of steps, but that's possible too. The solutions take 97 tiles, or 109 frames. So the solutions: Download fastest_puzzle_benchmark3.txt
Language: txt
SOLUTION: 

X#X#X . . . . . . . . . . . 
#   #                       
X . X#X#X#X#X#X#X#X#X#X#X . 
#                       #   
X . . . . . . . . . . . X#X 
#                         # 
X#X . . . . . . . . . . . X 
  #                       # 
X#X X#X#X#X#X#X#X#X#X#E . X 
#   #                     # 
X . X#X#X#X#X#X#X#X#X#X#X X 
#                       # # 
X . . . . . . . . . . . X#X 
#                           
X#X . . . . . . . . . . . . 
  #                         
X#X X#X#X#X#X#X#X#X#X#S . . 
#   #                       
X . X#X#X#X#X#X#X#X#X#X#X . 
#                       #   
X . . . . . . . . . . . X#X 
#                         # 
X#X . . . . . . . . . . . X 
  #                       # 
. X#X#X#X#X#X#X#X#X#X#X . X 
                      #   # 
. . . . . . . . . . . X#X#X
Download shortest_puzzle_benchmark3.txt
Language: txt
SOLUTION: 

X#X#X . . . . . . . . . . . 
#   #                       
X . X#X#X#X#X#X#X#X#X#X#X . 
#                       #   
X . . . . . . . . . . . X#X 
#                         # 
X#X . . . . . . . . . . . X 
  #                       # 
. X#X X#X X#X X#X E#X#X . X 
    # # # # # # #     #   # 
. . X#X X#X X#X X#X#X#X X#X 
                        #   
. . . . . . . . . . . . X#X 
                          # 
X#X . . . . . . . . . . . X 
# #                       # 
X X#X X#X X#X X#X X#X S . X 
#   # # # # # # # # # #   # 
X . X#X X#X X#X X#X X#X X#X 
#                       #   
X . . . . . . . . . . . X#X 
#                         # 
X#X . . . . . . . . . . . X 
  #                       # 
. X#X#X#X#X#X#X#X#X#X#X . X 
                      #   # 
. . . . . . . . . . . X#X#X
Posted: 1/4/2013 1:28 PM
Quote
partyboy1a
Experienced Forum User, Published Author, Player (136)
Joined: 9/18/2007
Posts: 389
ais523 wrote:
Yeah, SAT solvers can typically be beaten if you have more information about the problem space than they do.
While they may have less information available, they are typically highly optimized, and can utilize all the available hardware trickery of today, so they should be able to find solutions faster than our strictly linear algorithms.
ais523 wrote:
I've been wondering about keeping a cache of the fastest solutions for variousy-shaped solid color areas (this is one of the things I was planning to do when I split the puzzle into regions in my solver), but that isn't implemented yet.
I don't think that is possible in most cases. It can only work if the number of exits is relatively small, and even then you would have to store one partial solution for every permutation of the exits. And you would need an insanely big amount of prepared areas, as you would need to consider every single "exit pattern".
Posted: 1/3/2013 7:35 PM
Quote
partyboy1a
Experienced Forum User, Published Author, Player (136)
Joined: 9/18/2007
Posts: 389
I managed to write the code which checks for "connectivity". It eliminates a few row patterns which split the puzzle into multiple parts if there are multiple separate regions, AND all of them can only be connected using the border, AND you can only go strictly clockwise or strictly counter-clockwise AND there are endpoints in regions which are not directly connected, THEN the row pattern is invalid... another 320 lines of code, as it is very specific... It's good enough to eliminate 26 row selections out of 168 (potentially) solvable ones. I couldn't combine the two solvers even more. And now, as I try to use such a generic program like a SAT solver, I might port it back to Lua again. Too bad that its performance doesn't seem to be better than our programs, at least for the smaller puzzles.. It needed half a second to 15 seconds (depending on an artificial step limitation) to find the fastest solution for stage 9, and another 4 minutes to prove that there is no faster solution. (And at the moment there are still some strange bugs in the code.) I still think it's worth the effort. The other solvers can have serious troubles when it comes to large areas of white tiles (or large areas of black tiles). In that case, the SAT solver approach might be the only way to find any solutions (or even the best one).
1 2 3 4
15 16