Joined: 3/14/2008
Posts: 152
Location: United Kingdom
Well done on actually getting it finished and submitted, something I probably wouldn't have gotten round to doing myself for a few months at least.
Voted yes.
I also highly recommend reading the linked topic, since if you watch some of the earlier videos you can see how much faster the TAS is now with all the advanced solvers, than if I had finished a puzzle mode TAS with the old solver, (probably about 50% faster over the whole movie). Especially this post to see the solver running in real time.
Joined: 3/14/2008
Posts: 152
Location: United Kingdom
Thanks for the solver, I made a lua script that can be used to solve and input a puzzle, though I guess you might have already made your own. The lua table output was very nice since you can just 'dofile()' it =).
Script here (needs cleaning up/comments but it shouldn't be too hard to follow):
Language: lua
MEM_COLS = 0x020E3F64
MEM_ROWS = 0x020E3FA8
MEM_CELL_ROW1_COL1 = 0x020E03C4
MEM_rowoffset = 0x0140
MEM_coloffset = 0x14
MEM_valoffset = 0x1
frame = movie.framecount()
require("queue")
queue = Queue.new()
function inputsetup()
if memory.readbyte(0x020C8D3C) == 13 then
xo = memory.readbyte(0x020E3F48)
yo = memory.readbyte(0x020E3F4A)
else
xo = 40
yo = 0
end
dofile("luabot_fastest_puzzle")
for i,v in ipairs(SolutionPath) do
Queue.push(queue, v)
end
end
function readpuzzle()
thestring = ""
puzzle = {}
rows = 9 --for challenge mode
--check if we are in puzzle mode
if memory.readbyte(0x020C8D3C) == 13 then
rows = memory.readbyte(MEM_ROWS)
end
cols = memory.readbyte(MEM_COLS)
gui.text(1,1,stylus.get())
gui.text(1,11, input.get())
for r = rows, 1, -1 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
thestring = thestring .. puzzle[r][c] .. " "
end
thestring = thestring .."\n"
end
gui.text(0,20,frame)
return puzzle
end
function solvepuzzle()
local keys= input.get()
for k,v in pairs(keys) do
if k=="left" then
os.remove("puzzle")
file = io.open("puzzle","w")
file:write(rows .. " " .. cols .. "\n")
print(file:write(thestring))
file:flush()
end
if k=="down" then
os.execute("p-solver.exe puzzle")
inputsetup()
end
end
frame=frame+1
inputtable = {}
if not Queue.empty(queue) then
inputtable = Queue.pop(queue)
if next(inputtable) then
inputtable.x = inputtable.x + xo
inputtable.y = inputtable.y + yo
inputtable.touch = true
--print(inputtable.x .. " " .. inputtable.y)
end
end
stylus.set(inputtable)
end
gui.register(readpuzzle)
emu.registerbefore(solvepuzzle)
function file_exists(name)
local f=io.open(name,"r")
if f~=nil then io.close(f) return true else return false end
end
function readsol()
file2 = io.open("fastest_puzzle", "r")
count = 0
while true do
local line = file2:read()
if (line == nil) then break end
end
end
Also requires http://pastebin.com/djQWrKWY
To use it press left then down when on a puzzle and it solves it.
0x20E3F48 = X offset of grid
0x20E3F4A = Y offset
Both also work in challenge mode, though the Y offset is a negative value corresponding to the top screen so I just hardcoded them both in if it's challenge mode.
I tested it on all 100 puzzles and it worked for all, and it also works for challenge mode, though when you get to level 2 and beyond, letting the blocks stack up can result in unsolvable puzzles. Video:
Link to video
The unsolvables start at 4:48, though on the first one just by chance doing the wrong input (the previous one as the table wasn't updated and the old input was read into the queue) happens to make it solvable. I don't know how hard it would be to calculate the required input though, or if it would even be faster than just luck manipulating for a solvable puzzle or doing it in smaller pieces.
If I can find the positions of the level select buttons in memory then the whole of the puzzle mode (without any frames for "drawing") TAS could be generated by a lua script, which I think is pretty cool. I did some checks and I'm fairly sure the required delays are the same each time though I only tested 4 puzzles (also these may be off by 1 depending on how you think of the input):
Last frame of input on "tick" to select puzzle -> First frame of input possible on puzzle = 36 frames
Last frame of input on puzzle -> First frame you can press start with the puzzle counting as completed = 115 frames (the time where you can draw whatever you want)
Start press -> First frame of input on puzzle select screen = 58 frames
Joined: 3/14/2008
Posts: 152
Location: United Kingdom
EDIT: I just did some testing and it's in fact possible to jump 3 squares in one frame - you have click at the close edges though, so that the distance is just over 2 full squares long (I'm guessing a set number of pixels) and you can only repeatedly go 3 sqaures if you change direction every time, otherwise you have to do 3-2-3 etc. Though it shouldn't overcomplicate the rules too much as if you plan ahead you should be able to position your clicks to allow you to do this. I haven't tested if it works with diagonals yet though. I'll upload a demo soon.
Edit 2: dsm here: http://tasvideos.org/userfiles/info/8726755826533573
Video:
Link to video
I did some testing with my old emulator versions and found something very odd - I have 3 versions of desmume 0.9.8, two seemingly being the official version (and same compile date) and one build by gocha (r4450). The new 2 square moving thing seems to work on all of them, however your demo doesn't sync on one of the official ones so I must have some differences in the configuration (though I couldn't find any differences apart from input hotkeys so I really don't know.
I guess it's the fact that you need extra frames of ignored input after the 2 frames that I didn't find it, however neither did Dassan back when he tried on the first page.
Anyway I think if we want to get the puzzle mode done we should choose a standard version - the official 0.9.9 or if it becomes available, a version which fixes the lua emu.frameadvance bug (though there is a sort of workaround if you only want to use it to run a bot: emu.frameadvance is partially implemented, however it only works when the emulator is in a non paused state, so you can't use it while frameadvancing, but a fully autonomous bot would be able to use it if you never paused the emulator). You can see the code for it here: http://sourceforge.net/p/desmume/code/4722/tree/trunk/desmume/src/lua-engine.cpp#l1704 where the wrong function is called if the emulator is paused. The missing code is in this strange #define 'function' http://sourceforge.net/p/desmume/code/4722/tree/trunk/desmume/src/lua-engine.cpp#l1560 . Though without understanding the whole codebase I'm not 100% that this is the right place. It seems development is active on desmume as a whole though, with the last commit to that repository 2 days ago (lua engine unchanged for 8 months) so I'll try and post a bug on whatever issue tracker they have.
Specifying paths simply as the "chess" co-ordinates seems like a good idea and would make it much easier to read the input with a bot.
Joined: 3/14/2008
Posts: 152
Location: United Kingdom
Interesting, so you can move two blocks per frame without delaying. By the looks of it this will be faster than or the same speed as tapping (3 frames on square at other end) in almost all cases, but if you had to go the full width (of your example grid) it would be one frame faster to tap.
I'm surprised I never found this, though it's also possible it's a new thing only in desmume 0.99 (if that's what you're using? I just downloaded 0.9.9 to watch your test, most of the other testing I did was with 0.9.8 official and 'improved' versions by gocha of 0.9.7 and 0.9.8).
Are the rules more complex than this, because it seems the "3 frame rule" where any touch of 2 or 1 frame would not register?
Joined: 3/14/2008
Posts: 152
Location: United Kingdom
Hâthor wrote:
When I use the lua function:
stylus.set(x,y,true)
Emulator closed without saying anything. When I run the _dev.exe, I can see that an error message is written in the console but it close too faster; I don't have time to read.
I tried on versions 0.9.9, 0.9.8, 0.9.7 and it is the same (all 32bit). Either I miss something, or it's a bug.
I don't remember where I found it out, but there's some (correct) documentation for it somewhere. For some reason the function takes a table as input, for example:
stylus.set({y=100,x=200,touch=true})
or, to use a variable
stylus.set({y=y,x=x,touch=true})
Joined: 3/14/2008
Posts: 152
Location: United Kingdom
arflech wrote:
partyboy1a wrote:
p-solver-v1.0.1, fixed a crash which could happen if the very first attempt was faster than all step-limited attempts afterwards.
That Mediafire link doesn't work for me: I've gone through 4 "Try again?" rounds when trying to download the file.
Mirror here: http://duk.im/p-solver-v1.0.1.zip if you still need it.
I haven't forgotten about this, my last exam is tomorrow so I will finally get round to spending some time identifying the cause/requirements of the 6 frame 2 touch glitch and continuing with the Tas. Also I'm a fair bit better at programming now than in November when I started looking at this so I'll have a look at scripting automated input to speed up tasing.
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=Ey20QsbBDqccan 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.
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.
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
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.
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.
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).
Joined: 3/14/2008
Posts: 152
Location: United Kingdom
partyboy1a wrote:
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
I take it this reads the puzzles from the game. I'll try it in a bit, 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 this does work though I'll try to make a bot to do some testing with luck manipulation though I'm starting to think it may only be frame on which puzzles are solved, and the frame you originally enter puzzle mode (I edited the dsm of my wip to remove the random drawing between solves and it still synced, but adding in frames of delay before starting desyncs it, can't test times of solves easily like this though due to dragging down needing to be done on specific frames).
In terms of tasing this makes the manipulation a massive/impossible task if every frame gives a different result as you would have to test waiting fastestsolution-50 frames after every single puzzle, giving a massively branching tree, and if we say the average drop over the entire puzzle mode is 3 lines then very roughly that would mean ~50^300=5x10^509 total routes (though certain routes would be cut off at a certain point if they could not be faster even with a 50 frame solution every time).
My maths on that may be completely wrong though, so feel free (and try) to correct me. The 50 is from assuming an average solution will be 100 frames (and obviously the accuracy of this guess affects the above calculation alot).
For reference, input of a successful drag down on the cancel button (the left/right movement is unnecessary):
Joined: 3/14/2008
Posts: 152
Location: United Kingdom
Unless you already have a hard drive to put in the system, I'd recommend getting one the next time they go on sale, especially if you are planning on installing steam/other games as that 128gb (actually 119) goes pretty quick. That is a good ssd though, I have the same one in my laptop.
Joined: 3/14/2008
Posts: 152
Location: United Kingdom
Dasaan wrote:
For anyone interested in the mechanics:
- It takes 3 frames to tap a square of input
- To move to an adjacent square (up/down/left/right) it takes an additional 3 frames of input
- To move to a non adjacent square (up/down/left/right) any distance away takes an additional 4 frames of input
See Dasaan's post above for some examples, but that basically sums it up.
What this means is that a route that is shorter in the number of tiles than another may actually be longer timewise if it contains lots of single tile movements, since any straight line takes 4 frames no matter the distance.
Joined: 3/14/2008
Posts: 152
Location: United Kingdom
Once again thanks for the help, I seem to have trouble working out solutions that crossover between black and white directly (in the middle). I think I'll play through puzzle mode on my actual ds for a bit just so I get better at solving them.
A note on "optimal" solutions - you have around 50 frames (I think it's exactly 50 but I'll check, my number may or may not include the no input frame after dragging down) between finishing dragging down and being able to "double tap" your solution, which means if you have one under 50 frames then it would be pointless to try and find a better one (in terms of the speed of the tas anyway). Edit: I think this may actually be completely wrong because of the puzzle completion animation delay
Could you explain your maths from the previous post a bit more? I don't really see where your numbers come from (though I understand brute force would be exponential dependent on the size of the puzzle).
Also, a somewhat relevant and funny quote from the Rubik's Cube tas submission thread:
Limne wrote:
More games should be beatable by automated solvers freely available on the internet.
Joined: 3/14/2008
Posts: 152
Location: United Kingdom
For your those two: left = 121 frames, right = 103 (they look like they should work and I'll test them when I get home). I should probably try and solve them manually before using the solver (though I'm not really that good at doing the complex ones..).
Joined: 3/14/2008
Posts: 152
Location: United Kingdom
Dolphin runs fine on my 3570k without an overclock(though I do normally run it oc), the biggest problem was my graphics card not thinking dolphin was a game and under clocking itself (though I fixed that in the driver settings).
Joined: 3/14/2008
Posts: 152
Location: United Kingdom
ais523 wrote:
EDIT: After looking at it, downswiping is going to be much faster because the main thing that slows down Challenge mode is the cutscene in which lines are eliminated. So you want to be able to remove as many lines as you can per stroke in order to get the top speed. This means waiting for the screen to fill, downswiping does that faster. (In case you don't know the trick, you put the stylus near the top of the cancel buttons and drag it downwards; it's mentioned in the manual, IIRC.)
Short video comparing the new and old methods, sort of:
Link to video
Edit: Just noticed now but the score on the old tas randomly jumps up to 15k?? I'm guessing this was an emulation glitch in 0.94+
Edit2: Proof doing multiple at a time is faster (could be even better if manipulated)
Link to video
On the left is the new one, and on the right is my old one from 2009. The old one was made on 0.94+ and new on 0.98 (is this what I should be using? The desmume page on tasvideos is outdated, and in the desmume thread gocha seems to be maintaining both 0.97 and 0.98) which means there is a slight emulation difference (first frame of input to skip the title screen is a few frames earlier on 0.98) and my old run is also suboptimal in the menu as well as swiping down late on the first block. However you can see from the video that the new method of swiping down multiple times at once is possibly faster as the 17th line appears on the scoreboard about 2 seconds earlier, though this is about what the mistakes lose so I'll have to test doing that method again just to make sure.
I think the new method doesn't save much time because of the third reason below (animation slowing down).
New things I've found out/remembered:
Swiping down on the cancel button takes 8 + 1 frames of input (8 of holding down the stylus and 1 blank frame afterwards). However the game is somewhat picky about how those 8 frames are (can't have 4 at top 4 at bottom etc, but I know the general way it works and will make a macro to do it for me to avoid errors).
Due to it pressing on the cancel button, you can't swipe down in the middle of drawing a path. This is annoying as it means you can't draw the complete route early while you are still swiping down, emphasizing the importance of optimal routes.
You can only swipe down one "block" at a time, the next block can be swiped down 2 frames after the previous one stops moving, however, swiping down while the line elimination animation still works but the block does not come down until the end of the animation.
Manipulation of the blocks is quite difficult and seems to depend only on stylus input when you are in the game (though I only tested buttons for a short number of frames in the future) or which frame you start challenge mode on (optimizing solver would be pretty much required to test this though, as it may be beneficial to wait for a certain number of frames before starting to get better puzzles, and hopefully after the first puzzle everything is possible to manipulate). I was so far only able to affect drops of blocks 5 into the future with my input (the doodling, as well as the way the puzzle is solved) but I didn't test this far ahead with button presses so they may have an effect too.
As you can see from the video, an optimal solution will be required for at the very least the first two puzzles unless they are manipulated. I have used the polarium sovler I linked in my last post and made as many optimizations to the route it gives as possible (saving I think 4 frames on the first set of three:
Original route given by solver (136 frames unless I calced wrong):
(more) Optimal route I used (131 frames):
I have contacted the creator of the solver to see if they can provide me the source code/help me with making my own solver so will hopefully get a reply, but if not I'll probably need help making my own solver since I'm not the best programmer and I'm not really sure where to start.
Joined: 3/14/2008
Posts: 152
Location: United Kingdom
goldfish wrote:
Spikestuff wrote:
F*CK SWIMMING
F*CK FLOORS
F*CK WALLS
F*CK DOORS
I think that about sums it up. 2,136,942 rerecords... is that a record??
Voting no because it completes the game instead of overwriting it with MLP.
I think so, but if something has more rerecords it will probably have used brute forcing for part of it.
Edit: http://tasvideos.org/3570S.html has the most (5,425,978) so this run would be second.
Joined: 3/14/2008
Posts: 152
Location: United Kingdom
ais523 wrote:
Hmm, now I almost want to write a script for solving Polarium puzzles optimally. It's just that I have so much else to do…
Did you ever get around to doing anything with that? I've been thinking about having another look at polarium recently and will probably try to write my own program to solve the puzzles (optimally).
There is a solver program out there: http://notabdc.vip.sina.com/EngPage/e_solver.htm (scroll down a bit) which I used before but it doesn't always give optimal solutions (sometimes obvious due to it needlessly doing a loop on the outside when it could just do a straight line) and isn't open source (from what I can tell, but I could try emailing the author I guess). Although unless the higher levels of challenge mode are much harder than the early parts, having the most optimal solution would not actually save time there (just give you more time to doodle). Obviously being frame perfect is needed for the puzzle mode.
ais523 wrote:
I'm not convinced that Puzzle mode is the best for a TAS; it's just a sequence of entering the fastest solution to each level, one after the next, and unless there's some sort of crazy glitch it's simply going to be reasonably unimpressive as a TAS. Challenge mode would seem to give more scope for interesting play, especially given that you can accelerate the drops of puzzle sections by swiping down on the cancel button.
Should a "Full game" run consist of both the Challenge and puzzle modes though? Or would a tas of just the challenge mode be enough?
Another consideration is the gba version which was actually made afterwards which did away with the challenge mode but has three (short) time attack modes and "daily" polarium which consists of 365 puzzles (I think). The gba version also includes some new mechanics such as areas of the outside that can't be "walked" on: http://duks.co.uk/i/rQ92.png , "colourless" tiles that disappear so long as all the other tiles on their row are the same colour: http://duks.co.uk/i/KH1f.png , these weird ones: http://duks.co.uk/i/dZgw.png which cause tiles above to drop when they disappear.
Motion of the "cursor" in the gba is fairly simple as it's just one tile per 2 frames, but there's no way to go x number of tiles. I did a short test a few weeks ago of one of the time trial modes: http://www.youtube.com/watch?v=Hz_JF_6VdJw (I used the solver linked above and took out the obvious non optimal parts, but the solutions used here may still be sub optimal). I'm not sure but I think there may be random puzzles (or from a set) generated each time for the time attack but I'd have to check.
(more) Optimal route I used (131 frames):
I have contacted the creator of the solver to see if they can provide me the source code/help me with making my own solver so will hopefully get a reply, but if not I'll probably need help making my own solver since I'm not the best programmer and I'm not really sure where to start.
