Player (137)
Joined: 9/18/2007
Posts: 389
duksandfish wrote:
partyboy1a wrote:
another edit:
MEM_COLS = 0x020E3F64 
MEM_ROWS = 0x020E3FA8
...
[...] what does it give for grey squares though since the addresses I found seemed to "remember" the last black or white even if the tile was grey.
If you're in Puzzle Mode this doesn't matter, the number of rows and columns is saved too, so you always know which tiles are grey. For Challenge Mode, you may need test if the row counter gets updated again and again. Otherwise, find some one-byte value which always holds the current number of rows... And it might be a good idea to find the location of the next set of tiles which are dropping.
ais523 wrote:
Best attempt before brute-forcing:
A?A?A?A?A?A?A?*?*?*
? ? ? ? ? ? ? |   ?
A?A?A?A?A?A?A-+ . *
? |               ?
K-+ . . . . . . . L
?                 ?
M . . . . . . . +-N
?                 ?
O-+ . . . . . . . P
?                 ?
* . . . . . . . +-*
?               | ?
* . +-B?B?B?B?B?B?B
?   | ? ? ? ? ?   ?
*-+-+ B?B?B?B?B . *
?     ? ? ? ? ?   ?
* . +-B?B?B?B?B?B?B
?   | ? ? ? ? ? ?
*?*?*?B?B?B?B?B?B B
This should be detected as unsolvable.
Yeah, I noticed this rule too, and is probably the most useful rule for solving that I haven't implemented yet. I need to work out how to express it in Lua.
I marked the points where two rows are disconnected using the letters K,L,M,N,O,P. You need to find a route which uses regions A,B,N,O. You write down which regions can be connected in which way: A-K-M-O-B-P-N-L-A. Now you test all routes starting with the left endpoint: O-M-K-A-L-N-right endpoint (forced) -> failure, B wasn't visited O-B-P-N-right endpoint (forced) -> failure, A wasn't visited -------------------------- I uploaded an improved version of my solver, it can be found here. If a level requires a lot of brute-force, my solver works faster. examples: stage 05 is solved within 4 minutes, the program by ais523 requires more time. I should also say that it is entirely possible to use both programs at the same time: the program by ais can be used to eliminate useless line-flip combinations for example. And also, if there is a partial solution (or some guess about it), it can be used to construct a new puzzle: turn all tiles where we stepped on to black, set a forced endpoint for the last tile which was visited. Then either my program or the program by ais can try to solve the remaining puzzle.
Player (137)
Joined: 9/18/2007
Posts: 389
Yay, I got most of the features of my solver reimplemented in C++. It made the solver about 2000 times faster, and made it use only 1/8th of the previously used RAM. Now it can solve puzzle 100 in about 4 minutes, and puzzle 9 is solved in one to two seconds. If you let me do so, I will take an attempt to "merge" our solvers in C++, basically replacing your depth-first search with my breadth-first search. The most important reasons for me to use this instead of Lua are the control about memory usage and the increased speed... If it becomes good enough, the interface can still be implemented to work with the emulator. -------------------------------------------------------------------------- Coming soon: some piece of software which converts the problem "find the shortest / fastest solution" into a boolean satisfiability problem. I hope those SAT solvers do already have a lot more optimizations than we can possibly find.
Player (137)
Joined: 9/18/2007
Posts: 389
Some news: The solver which uses SAT solvers is working fine. For the benchmark puzzle, it required 80 seconds to find some solution, and 11 seconds to find the solution when the row pattern is predefined in a nice way. Output looks like that:
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 ]=============================
|                                                                             |
WARNING! DIMACS header mismatch: wrong number of variables.
WARNING! DIMACS header mismatch: wrong number of clauses.
|  Number of variables:         32676                                         |
|  Number of clauses:           49724                                         |
|  Parse time:                   0.05 s                                       |
|  Eliminated clauses:           0.18 Mb                                      |
|  Simplification time:          0.13 s                                       |
|                                                                             |
============================[ Search Statistics ]==============================
| Conflicts |          ORIGINAL         |          LEARNT          | Progress |
|           |    Vars  Clauses Literals |    Limit  Clauses Lit/Cl |          |
===============================================================================
|       100 |   13564    49064   119444 |    17990      100    422 | 39.889 % |
|       250 |   13564    49064   119444 |    19789      250    336 | 39.889 % |
|       475 |   13564    49064   119444 |    21768      475    273 | 39.889 % |
|       812 |   13564    49064   119444 |    23944      812    269 | 39.889 % |
|      1318 |   13564    49064   119444 |    26339     1318    271 | 39.889 % |
|      2077 |   13564    49064   119444 |    28973     2077    234 | 39.889 % |
|      3216 |   13564    49064   119444 |    31870     3216    219 | 39.889 % |
|      4924 |   13564    49064   119444 |    35057     4924    201 | 39.889 % |
|      7486 |   13564    49064   119444 |    38563     7486    205 | 39.889 % |
|     11330 |   13564    49064   119444 |    42419    11330    209 | 39.889 % |
|     17096 |   13564    49064   119444 |    46661    17096    212 | 39.889 % |
|     25745 |   13564    49064   119444 |    51327    25745    216 | 39.889 % |
|     38719 |   13564    49064   119444 |    56460    38719    239 | 39.889 % |
|     58180 |   13564    49064   119444 |    62106    58180    239 | 39.889 % |
|     87372 |   13564    49064   119444 |    68317    35441    210 | 39.889 % |
|    131161 |   13564    49064   119444 |    75149    79230    269 | 39.889 % |
|    196845 |   13564    49064   119444 |    82664    86304    267 | 39.889 % |
|    295371 |   13564    49064   119444 |    90930    46382    234 | 39.889 % |
===============================================================================
restarts              : 766
conflicts             : 332362         (887 /sec)
decisions             : 1455603        (0.00 % random) (3885 /sec)
propagations          : 187711758      (501020 /sec)
conflict literals     : 107846413      (16.53 % deleted)
Memory used           : 182.00 MB
CPU time              : 374.659 s

SATISFIABLE
SAT
  **  **  **  19  18  **   6   5   4  **

  **  --  65  20  17  16   7   8   3   2

  62  63  64  21  14  15  10   9  --   1

  61  --  23  22  13  12  11  30  31  32

  60  59  24  25  26  27  28  29  --  33

  57  58  --  --  --  --  --  --  --  34

  56  --  --  --  --  --  --  --  36  35

  55  --  51  50  49  42  41  38  37  **

  54  53  52  47  48  43  40  39  --  **

  **  **  **  46  45  44  **  **  **  **


Process returned 0 (0x0)   execution time : 376.794 s
I also tried it when the row pattern has been defined to be the worst possible one (every row has exactly 7 white tiles, and 1 black tile). It could be solved in about 80 minutes. At the moment, it just finds some solution, not the best one. Getting the shortest solution is not a problem though: just give some limit for the amount of allowed steps. If there is no way to complete it, but with one step more it can be completed, then you found the shortest solution. Finding the fastest solution is more complicated, because it is not easy to translate the calculation for the amount of frames into some boolean variables, but it's definitely possible.
Joined: 3/14/2008
Posts: 152
Location: United Kingdom
Nice work partyboy1a, sorry for my lack of input on this thread recently. About a month ago I was working on making a lua script to test luck manipulation (since it seems the only way to luck manipulate drops is by waiting x though I still didn't test this enough to see how far into the future you can affect thing) but ran into a few problems and lost interest for a while, mainly due to the fact emu.frameadvance doesn't work in desumume lua requiring you to use registered functions which makes it much more difficult to put in a specified sequence of input, as well as not being able to set stylus input since it's not documented very well at all. Did you do any more work on combining yours and ais' solvers since they can be much faster than the other depending on the puzzle it seems? If someone who has experience using desmume lua could give me some examples of setting stylus input and maybe a good method to send multiple frames of input in a row with registered functions (though now I've actually thought about it a bit more I've had a few more ideas).
Player (137)
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).
Editor, Player (44)
Joined: 7/11/2010
Posts: 1029
Yeah, SAT solvers can typically be beaten if you have more information about the problem space than they do. 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.
Player (137)
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".
Player (137)
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
Player (137)
Joined: 9/18/2007
Posts: 389
Joined: 3/14/2008
Posts: 152
Location: United Kingdom
Using codeblocks on windows I get this error when compiling, after opening the p-solver.cbp file: http://duks.co.uk/i/nxEA . All the other files are in the same directory so I don't think that it's not finding them. I've yet to try it in linux though. From what you've posted it's looking good and I'm guessing will solve the 9x9 and 9x10 puzzles needed for the challenge mode tas fairly quickly.
Player (137)
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.
Joined: 3/14/2008
Posts: 152
Location: United Kingdom
I got it to compile by changing the imports to: #include "P_Puzzle.cpp" #include "P_Solution.cpp" rather than #include "P_Puzzle.h" #include "P_Solution.h" Though I've never written a program bigger than 1 file in c++ before so don't know why this worked or if the program is running properly. 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.
Player (137)
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...)
Joined: 3/14/2008
Posts: 152
Location: United Kingdom
partyboy1a wrote:
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...)
Thanks for clarifying, I had looked at them in notepad++ but was just making sure. Any idea why I had to change the extensions on the #include(s) though? Since I'm also using mingw. Also it technically doesn't need cygwin to run, just 3 of the dlls: http://duks.co.uk/i/MFUT
Player (137)
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.
Player (137)
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.
Joined: 3/14/2008
Posts: 152
Location: United Kingdom
Thanks for the new version, as well as the puzzle mode solutions you gave me in the pm. I think my problem before was the cbp file from the 1.0 since loading this new one with the same config compiles correctly with no changes. 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 (and could even be mostly scripted when I work out stylus inputs on desmume lua) but as discussed before (see page 1) a puzzle mode wouldn't be too interesting to watch though you do have some time to do "creative drawing" after each puzzle. As stated on the bad game choices page: "Many puzzle games where knowing the solution renders gameplay trivial, such as Sudoku. If you know the solution, a speed run just a matter of entering it as fast as possible." Though due to the amount of effort that has gone into the solver it might still be worth doing. Obviously this leaves challenge mode where there is a large amount of luck manipulation that can be done, which I am still working on and will post here if I make some more progress.
Warepire
He/Him
Editor
Joined: 3/2/2010
Posts: 2178
Location: A little to the left of nowhere (Sweden)
I don't see any reason to why a puzzle-mode TAS should not be publishable in the Vault tier.
Player (137)
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.
Editor, Player (44)
Joined: 7/11/2010
Posts: 1029
You can never prove that, unless the movie's so short you can brute-force. There might always be a faster way to do menuing you missed, or some glitch you didn't expect.
Player (137)
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...
Player (137)
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.
Joined: 3/14/2008
Posts: 152
Location: United Kingdom
I did some testing on this about 2 weeks ago after I uploaded that wip (progress here: http://www.youtube.com/watch?v=Ey20QsbBDqc can upload dsm when I get home if you want dsm here: http://tasvideos.org/userfiles/download/4687549396464802 (glitch visible from frame 1776)), but when I got to level 7 I found a glitch in the menus (and possibly the main game) where if either the places are close enough, or if you press on specific places, two clicks can be done in 6 frames rather than 7 (obviously you can't see this in the video but only in the dsm). Haven't done anymore testing outside of that though but if it affects the game then there's a chance it will cause the solver to be wrong in some places, so let's hope it doesn't.
Player (137)
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.
Post subject: Re: Polarium
Joined: 5/13/2013
Posts: 180
duksandfish wrote:
As there were a few requests for this game in the wish list topic, and it looked quite interesting, I decided to have a try at TASing the challenge mode of Polarium. Here is what I have so far: Link to video I've noticed a few places where it isn't optimal, so i'll redo it over the next few days. Edit: Updated the link since I deleted the old video over 2 years ago
Man, I remember when the DS first came out and I remember my dad taking me to GameStop and seeing this as a demo on the DS systems they had on display. Memories....:D
A wise man once said "Damn, that's one hell of a steak."