Experienced Forum User, Published Author, Player
(136)
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:
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.
Experienced Forum User, Published Author, Player
(136)
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.
Experienced Forum User, Published Author, Player
(136)
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:
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.
Experienced Forum User, Published Author, Player
(136)
Joined: 9/18/2007
Posts: 389
Congratulations, you win the battle for the best program. I did some optimizations to my program (which is essentially brute-forcing the complete puzzle), and it gave me the same solution, but it required several hours for finding it:
-----------------------------------
Edit: Another good idea would be:
Before you start to brute-force, calculate an estimation on how many frames and how many fields are required at least. For example for the benchmark puzzle it's (3 frames + 4 frames)*(math.min(rows, colums)-1) = 49 frames and sum over all rows i (min(black in row i, white in row i)) = 1*8 = 8.
To measure partial solutions, just add 7 frames * (min(incompletely solved rows, incompletely solved columns) - 1) for minimum score, or #unused fields for minimum fields.
Then when searching for solutions, look on how hard it will be to brute-force. If it might take very long, calculate an estimate and enqueue. First calculate the "easy" solutions which don't require too much brute-force.
Now after you found some "easy" solutions, you can come back to the solutions requiring a lot of brute-force. You should be able to find the solution given above pretty fast. Now that was done: If you can only find solutions which take more fields and more frames than the currently best solution, then throw it away and don't brute-force at all.
example:
This requires 29 turns at least, and ~70 fields. The solution found above requires 18 turns, and 51 fields. It is definitely impossible for this situation to get a better solution than the one above.
-------------------------------------------
This should be detected as unsolvable. The reason is easy: Take one starting point. Now solve the top part. If you now continue, then you come across the other endpoint and didn't solve the lower part.
Now take a starting point, and assume you could solve the lower part. You can't get to the top part afterwards without coming across the other endpoint.
------------------------------------
If there are already two endpoints, it is safe to assume that every cell which has two forced neighbors is also a forced cell connected to both of them - otherwise it would create an additional endpoint, which is forbidden.
In this case, the 1 at the lowest left would also become a forced cell this way.
---------------------------------
Also: If two rows are completely disconnected, then finding the solution can be split in two parts. For example, in my solution for the benchmark puzzle, the top two rows are disconnected from the rest of the puzzle, so finding the solutions can be split as following:
- solve the top part, use row 2, column 0 as an endpoint, use row 2, column 9 as an endpoint. at the same time: solve the bottom puzzle, use (3,0) and (3,9) as endpoints, allow two additional endpoints anywhere in the bottom part.
- solve the top part using two endpoints, one of them being (2,0). at the same time, solve the bottom part using two endpoints, one of them must be (3,0).
- solve the top part using two endpoints, one of them being (2,9). at the same time, solve the bottom part using two endpoints, one of them must be (3,9).
- solve the top part by using a total of 4 endpoints, two of them are (2,0) and (2,9). solve the bottom part using (3,0) and (3,9) as endpoints.
-----------------------------------------
another edit:
MEM_COLS = 0x020E3F64
MEM_ROWS = 0x020E3FA8
MEM_CELL_ROW1_COL1 = 0x020E03C4
MEM_rowoffset = 0x0140
MEM_coloffset = 0x14
MEM_valoffset = 0x1
function readpuzzle()
local puzzle = {}
local rows = memory.readbyte(MEM_ROWS)
local cols = memory.readbyte(MEM_COLS)
for r = 1, rows do
puzzle[r] = {}
for c = 1, cols do
puzzle[r][c] =
memory.readbyte(
MEM_CELL_ROW1_COL1
+ MEM_rowoffset * (r - 1)
+ MEM_coloffset * (c - 1)
) - MEM_valoffset
end
end
return puzzle
end
Experienced Forum User, Published Author, Player
(136)
Joined: 9/18/2007
Posts: 389
Yay, I could get a Polarium Solver working! It tests ALL starting points and ALL possible paths. When one is found, this one is printed out.
This program solves stage 14, but it shouldn't be difficult to adjust it to let it work with every maze.
Download PolariumSolver.lua
Language: lua
function deepcopy(orig)
local orig_type = type(orig)
local copy
if orig_type == 'table' then
copy = {}
for orig_key, orig_value in pairs(orig) do
copy[orig_key] = deepcopy(orig_value)
end
else -- number, string, boolean, etc
copy = orig
end
return copy
end
puzzlestring = {
".***.",
"**.**",
".***."
}
puzzle = {}
for y,str in ipairs(puzzlestring) do
puzzle[y] = {}
s = puzzlestring[y]
for x = 1, string.len(s) do
puzzle[y][x] = (string.sub(s, x, x) == ".")
end
puzzle[y][0] = "*"
puzzle[y][string.len(s) + 1] = "*"
end
height = #puzzle
width = #puzzle[1] - 1
for y = 0, height + 1, height + 1 do
puzzle[y] = {}
for x = 0, width + 1 do
puzzle[y][x] = "*"
end
end
function printpuzzle(p)
local s = ""
local puz = p.puzzle
for y = 0, #puz do
for x = 0, #puz[y] do
local c = puz[y][x]
if p.solutionrequired[y] == nil or p.solutionrequired[y] == "*" then
if c == true then
s = s .. " #"
elseif c == false then
s = s .. " ."
elseif type(c) == "number" then
s = s .. string.format("%3u", c)
else
s = s .. " " .. c
end
elseif p.solutionrequired[y] == true then
if c == true then
s = s .. " +"
elseif c == false then
s = s .. " -"
elseif type(c) == "number" then
s = s .. string.format("%3u", c)
else
s = s .. " " .. c
end
elseif p.solutionrequired[y] == false then
if c == false then
s = s .. " +"
elseif c == true then
s = s .. " -"
elseif type(c) == "number" then
s = s .. string.format("%3u", c)
else
s = s .. " " .. c
end
else
s = s .. "!failure " .. y .. ";" .. x .. ";" .. tostring(c) .. ";" .. tostring(p.solutionrequired[y]) .. "!"
end
end
s = s .. "\n\n"
end
print(s)
end
fifo = {}
elementcount = 0
maxelements = 0
-- start an attempt for every starting point
for y = 1, #puzzlestring do for x = 1, #puzzlestring[y] do
current = {
puzzle = deepcopy(puzzle),
x = x, y = y, step = 1,
solutionrequired = {}
}
current.solutionrequired[y] = puzzle[y][x]
current.puzzle[y][x] = 1
--printpuzzle(current)
table.insert(fifo, current)
elementcount = elementcount + 1
maxelements = math.max(maxelements, elementcount)
end end
counter = 1
current = table.remove(fifo, 1)
while(current) do
print("counter: ".. counter .. "; elements: " .. elementcount .. "; max: " .. maxelements)
printpuzzle(current)
--check if this one solves the maze
validvalues = 0
for y = 1, #puzzlestring do
for x = 1, #puzzlestring[y] do
if type(current.puzzle[y][x]) == "number"
or (
current.solutionrequired[y] ~= nil
and current.puzzle[y][x] ~= current.solutionrequired[y]
)
then
validvalues = validvalues + 1
end
end
end
if validvalues == #puzzlestring * #puzzlestring[1] then
print("!! best solution found !!")
break
end
--check if it is possible to go one step up
if --field limit hasn't been reached
(current.y >= 1)
and --we didn't already visit this place
(type(current.puzzle[current.y-1][current.x]) ~= "number")
and --visiting this place is allowed
( --place can be visited if it is on the outside
(current.x == 0 or current.x == #puzzlestring[1] + 1 or current.y == 1)
--we didn't visit any field on this row
or (current.solutionrequired[current.y - 1] == nil)
--we visit a field of the same colour
or (current.solutionrequired[current.y - 1] == current.puzzle[current.y-1][current.x])
)
then
newpuzzle = deepcopy(current)
newpuzzle.step = newpuzzle.step + 1
newpuzzle.y = newpuzzle.y - 1
if newpuzzle.y >= 1 then
if newpuzzle.puzzle[newpuzzle.y][newpuzzle.x] ~= "*" then
newpuzzle.solutionrequired[newpuzzle.y] = newpuzzle.puzzle[newpuzzle.y][newpuzzle.x]
end
end
newpuzzle.puzzle[newpuzzle.y][newpuzzle.x] = newpuzzle.step
table.insert(fifo, newpuzzle)
elementcount = elementcount + 1
maxelements = math.max(maxelements, elementcount)
end
-- check if it is possible to go one step down
if --field limit hasn't been reached
(current.y <= #puzzlestring)
and --we didn't already visit this place
(type(current.puzzle[current.y+1][current.x]) ~= "number")
and --visiting this place is allowed
( --place can be visited if it is on the outside
(current.x == 0 or current.x == #puzzlestring[1] + 1 or current.y == #puzzlestring)
--we didn't visit any field on this row
or (current.solutionrequired[current.y + 1] == nil)
--we visit a field of the same colour
or (current.solutionrequired[current.y + 1] == current.puzzle[current.y+1][current.x])
)
then
newpuzzle = deepcopy(current)
newpuzzle.step = newpuzzle.step + 1
newpuzzle.y = newpuzzle.y + 1
if newpuzzle.y <= #puzzlestring then
if newpuzzle.puzzle[newpuzzle.y][newpuzzle.x] ~= "*" then
newpuzzle.solutionrequired[newpuzzle.y] = newpuzzle.puzzle[newpuzzle.y][newpuzzle.x]
end
end
newpuzzle.puzzle[newpuzzle.y][newpuzzle.x] = newpuzzle.step
table.insert(fifo, newpuzzle)
elementcount = elementcount + 1
maxelements = math.max(maxelements, elementcount)
end
--check if it is possible to go one step left
if --field limit hasn't been reached
(current.x >= 1)
and --we didn't already visit this place
(type(current.puzzle[current.y][current.x - 1]) ~= "number")
and --visiting this place is allowed
( -- place can be visited if it is on the outside
(current.y == 0 or current.y == #puzzlestring[1] + 1 or current.x == 1)
-- or if we visit a field of the same colour
or (current.solutionrequired[current.y] == current.puzzle[current.y][current.x - 1])
)
then
newpuzzle = deepcopy(current)
newpuzzle.step = newpuzzle.step + 1
newpuzzle.x = newpuzzle.x - 1
newpuzzle.puzzle[newpuzzle.y][newpuzzle.x] = newpuzzle.step
table.insert(fifo, newpuzzle)
elementcount = elementcount + 1
maxelements = math.max(maxelements, elementcount)
end
--check if it is possible to go one step right
if --field limit hasn't been reached
(current.x <= #puzzlestring[1])
and --we didn't already visit this place
(type(current.puzzle[current.y][current.x + 1]) ~= "number")
and --visiting this place is allowed
( -- place can be visited if it is on the outside
(current.y == 0 or current.y == #puzzlestring[1] + 1 or current.x == #puzzlestring[1])
-- or if we visit a field of the same colour
or (current.solutionrequired[current.y] == current.puzzle[current.y][current.x + 1])
)
then
newpuzzle = deepcopy(current)
newpuzzle.step = newpuzzle.step + 1
newpuzzle.x = newpuzzle.x + 1
newpuzzle.puzzle[newpuzzle.y][newpuzzle.x] = newpuzzle.step
table.insert(fifo, newpuzzle)
elementcount = elementcount + 1
maxelements = math.max(maxelements, elementcount)
end
current = table.remove(fifo, 1)
elementcount = elementcount - 1
maxelements = math.max(maxelements, elementcount)
counter = counter + 1
end
Note that this one doesn't minimize the amount of frames, it minimizes the amount of fields to visit. There's some more adjustment necessary for minimizing the amount of frames.
It even works for stage 78, it just takes a lot longer (and if you don't utilize the symmetries in this one, you would need about 2.100.000 steps, and 140.000 stored mazes). Quite an evil one, the shortest solution requires 50 fields.
Experienced Forum User, Published Author, Player
(136)
Joined: 9/18/2007
Posts: 389
duksandfish wrote:
Could you explain your maths from the previous post a bit more? I don't really see where your numbers come from
I just used FieldWidth*FieldHeight *4 (directions to choose from the starting point) * 3 (directions to choose from, as going back doesn't make sense) * 3 * 3 * 3 * ...
This number is too big, I just wanted to find some upper limit. For example it includes paths like start->right->up->left->down which is invalid, and it doesn't matter which end of the path you choose, so it's 2 times too big.
I think it should be possible to brute-force through all black-white-combinations (it's always 2048 or a lot less, so it shouldn't cause any trouble, most of them aren't solvable anyway), and check if the maze may be solvable. Then: count how many fields have to be changed, and how many outer fields must be used at least. Then search for solutions for all black-white-combinations which seem to be somewhat reasonable. Or if you want to make sure to find the best solution: search a path through every solvable maze.
Experienced Forum User, Published Author, Player
(136)
Joined: 9/18/2007
Posts: 389
Sorry, I found one more:
The main idea is to avoid using the outer fields as much as possible. If you can avoid using the outer fields by walking through more fields in the middle this is always a good idea.
The next idea: Try to avoid placing the two ends of the paths too close to each other.
Experienced Forum User, Published Author, Player
(136)
Joined: 9/18/2007
Posts: 389
stage 09:
stage 10:
stage 14:
stage 18: http://www.mediafire.com/?5rsb2dp0ala8875
I hope this gives you enough ideas for good solutions.
I think that using the current solver is just a way to prove if there actually is some solution at all, nothing more.
The problem "Does there exist a solution?" is in NP, but asking for the fastest solution is most likely something like O(3^n) where n is the amount of steps for the shortest solution (choose one new direction from "up", "down", "left", "right", but don't go back to the place you just came from). So... solving the easiest of all of them -- stage 14 -- would have taken about 3*5*4*3^8 = 393.660 attemps at worst. Well, most of these attempts would be cancelled rather quickly because the solution would become invalid. Brute-forcing the fastest solution might be possible (and it would even prove that the chosen solution is optimal), but this becomes a lot worse for bigger puzzles...
Experienced Forum User, Published Author, Player
(136)
Joined: 9/18/2007
Posts: 389
Pasky13 wrote:
I see we're still not voting on whether to accept submissions out of the vault and just relying solely on judgement...=/
I think most people actually can't decide the technical quality of a run. If it is some fairly unknown game, it's unlikely that the voters ever played the game. We need some expert (who hopefully chooses the right decision) for that. And: Everyone has the opportunity to write down his or her opinion about the quality in the submission thread.
And as far as I know, some experiments with more difficult voting options already failed in the past. Just one example: If we ask "how should this submission be handled?" and give the choices "reject!", "Vault", "Moon", "Star" for answering, everyone needs to know about the tiers. Answering "Did you find this movie entertaining?" doesn't require any knowledge about the tiers at all. The less knowledge necessary for voting the better.
(Feel free to move this post to somewhere else or to create a topic out of it if it is worth to be discussed more in detail.)
Experienced Forum User, Published Author, Player
(136)
Joined: 9/18/2007
Posts: 389
Too bad the game starts with a totally trivial game, Color Memory is absolutely boring to watch. And the encode isn't even complete, so there is more boringness to be expected.
3
00000 0058 b u 0 y
00001 043C b u 0 y2
00002 0056 b u 0 x
I made a discovery which allows for a faster strategy than the (unsubmitted) TAS by Inzult: You don't need to shoot the solar ramp to get the Vortex points, it also works -> this way <- (extract the file to your fceux folder, start the game, load the movie, let the movie play until the flipper table appears, then load first savestate. If you load the savestate instantly after starting the movie, you will get messed up graphics). Well, and this strategy would allow you to get 10.000.000 points without ever using the flippers, might be somewhat interesting.
I did some math with it: The best strategy for ball 3 would be: start double ball, shoot solar ramp once with each ball (vortex multiplier is then 4, and multiplier for double ball is 2, so each vortex shot gives 800.000 points.), then try to get the two balls to score vortex shots in the same way as demonstrated (which is very difficult to do, I just was really lucky that it worked at all.) If it is fast enough, it should save about 1.000 frames.
Shooting the solar ramp once more doesn't save time, because you can either get 1 vortex shot + increased multiplier or 3 vortex shots in the same time.
Experienced Forum User, Published Author, Player
(136)
Joined: 9/18/2007
Posts: 389
This game really doesn't offer that much, but I was nonetheless excited all the way through. (I might be biased about that since I did see this game during my childhood.) Yes vote. One more time against the mayority.
Experienced Forum User, Published Author, Player
(136)
Joined: 9/18/2007
Posts: 389
As far as I have understood, there can be a Vault run, and a slower Moon run for the same game with the same goals.
Can there also be a Moon run, and a slower Star run on the same game with the same goals? Then we would have to un-obsolete one NES Battletoads movie, and we would need to do some changes in the obsoletion chain for threeSM64movies
Experienced Forum User, Published Author, Player
(136)
Joined: 9/18/2007
Posts: 389
Would it also have gone back to the first level at the same frame if you hadn't committed suicide?
(That gives me an idea maybe we should ask for suicide right after the "end" of the infinitely-repeating game has been reached.)
Experienced Forum User, Published Author, Player
(136)
Joined: 9/18/2007
Posts: 389
I think we need a once-and-for-all decision for the "fastest crash" or "fastest softlock" goal.
I would say It doesn't beat the game -> it doesn't qualify for Vault, Moon, Star -> it must be rejected. However, these bugs might be used in a Playaround. And I also think it can be added to the game resource page.
Experienced Forum User, Published Author, Player
(136)
Joined: 9/18/2007
Posts: 389
Feature request: (almost the same as already posted here, but it was the wrong thread, so no response for good reasons)
Now that we aim on publishing movies for (almost) every game, there should also be an easy way to view these.
I noticed it's possible to view movies on a per-game base, for example NES Battletoads, DS You have to burn the rope!, N64 Super Mario 64, NES Archon, and they offer more information than the pages on the movie list, and we already have a big list of games on the submission page. I was only able to find these pages because I discovered a link to the Battletoads page somewhere, but I haven't found any easy method to access these pages other than guessing the URL.
Let's put a "View all movies for a specific game"-button to the movie page, or even better: right at the front page. Just use the same drop-down list as for the submission site, and redirect to the game site.
Or let's replace the movie list page by a game list page.
Maybe we can also add a link to each forum thread for the specific game to the game information tab (if it exists, note that some games have multiple threads), but this would require quite a lot of work at the start.
Experienced Forum User, Published Author, Player
(136)
Joined: 9/18/2007
Posts: 389
Well, there are at least no major flaws in your (Inzult's) run. I think it is improvable, but not by much. If you want to, you can just upload it to the WIP storage or Microstorage, I will try to improve it then. (This would most likely take a few months or a year, I'm one of the slowest TASers around here.)
Experienced Forum User, Published Author, Player
(136)
Joined: 9/18/2007
Posts: 389
Feature request (well, somewhat off-topic)
Now that we aim on publishing movies for (almost) every game, there should also be an easy way to view these.
I noticed it's possible to view movies on a per-game base, for example NES Battletoads, SNES Plokshameless self-advertizing, N64 Super Mario 64, NES Archon, and they offer more information than the pages on the movie list, and we already have a big list of games on the submission page. I was only able to find these pages because I discovered a link to the Battletoads page somewhere, but I haven't found any easy method to access these pages.
Let's put a "View all movies for a specific game"-button to the movie page, or even better: right at the front page. Just use the same drop-down list as for the submission site, and redirect to the game view site.
Or let's replace the movie list page by a game list page.
Experienced Forum User, Published Author, Player
(136)
Joined: 9/18/2007
Posts: 389
Marx wrote:
Looks sloppy
I think so too. For example: Around the 8 minute mark up to the 9 minute mark, there are several places where you have to jump into holes. I think quite a few of these jumps have been done too late. At least it looks like that.
I haven't played this game, but I was surprised I actually liked watching it.
Experienced Forum User, Published Author, Player
(136)
Joined: 9/18/2007
Posts: 389
Nice, you proved that this run can be beaten by a minute. Now there is no choice but to rereject this one. Well, the better movie wouldn't be acceptable too. The "name" entered is a speed-entertainment tradeoff, which is disallowed in the Vault.
The main idea is to avoid using the outer fields as much as possible. If you can avoid using the outer fields by walking through more fields in the middle this is always a good idea.
The next idea: Try to avoid placing the two ends of the paths too close to each other.
stage 10:
stage 14:
stage 18: http://www.mediafire.com/?5rsb2dp0ala8875
I hope this gives you enough ideas for good solutions.
I think that using the current solver is just a way to prove if there actually is some solution at all, nothing more.
The problem "Does there exist a solution?" is in NP, but asking for the fastest solution is most likely something like O(3^n) where n is the amount of steps for the shortest solution (choose one new direction from "up", "down", "left", "right", but don't go back to the place you just came from). So... solving the easiest of all of them -- stage 14 -- would have taken about 3*5*4*3^8 = 393.660 attemps at worst. Well, most of these attempts would be cancelled rather quickly because the solution would become invalid. Brute-forcing the fastest solution might be possible (and it would even prove that the chosen solution is optimal), but this becomes a lot worse for bigger puzzles...
