Submission Text Full Submission Page Publication Page

Game objectives

  • Emulator used: FCEUX 2.1.5-interim
  • Collects no evidence
  • Uses paths not intended by the game's developers
  • Is still really, really boring
Where in Time is Carmen Sandiego is a game about a time traveling rookie detective, who rises through the ranks a crooked cop, who puts dozens of people in jail by obtaining warrants for their arrest without any evidence. Fortunately, he also happens to be clairvoyant, so all of the people he put behind bars were guilty.
Gameplay is painfully simple: interview witnesses and informants, collect clues, assemble a warrant, find and capture the suspect-- repeat 80 times. As far as I'm aware, only two things change as the game progresses: the number of stops you're expected to go to increases (from 4 to 12 or so) and the number of hours you have increases to allow you more time to follow those long routes.

Oh God. Why, Bobo? WHY???

Good question. A good question to which I don't really have a good answer. At least it's a simple game.
In fact, that's entirely why I did this. I've been working hard to bot Final Fantasy Legend and I decided I'd take a short break. Within a few days, I had this bot up and running. Because this game is so damn monotonous, it's quite easy to bot. Of course, I walk a fine line here-- you should know it's very straightforward to run, but I don't want you to think I didn't put any effort into this TAS. There are some nontrivial elements to it.

Like what? What's nontrivial about it? I just see you do the same thing over and over again...

To your untrained eye, of course! But there's a lot of automatic route planning behind the scenes.
Every level is randomly generated from a pool of 48 locations. These locations are randomly distributed, along with your starting and ending points as well as the suspect. To use a little bit of mathematical terminology, a random (and undirected) graph is generated (with a maximum of 4 and a minimum of 2 edges adjacent to each vertex). To use strictly non-mathematical language, random places lead to other random places.
This makes gameplay decidedly nontrivial. An early version of my bot simply did a tree search until it reached the proper destination. That didn't work well, so I tried again with a sort of double-tree search (I'm sure there's a name for it in computer science); in this search, I started out at both the starting point and the destination (reached by overwriting the RAM value), found all adjacent vertices (locations one warp away), compared the two sets, then searched one level deeper. Finally, I was able to find where the graph is stored in the RAM, so I just assembled and analyzed it directly from the RAM without all that pointless frame advancing, saving, and loading.
I've found that every level can be completed in four moves or less. Thanks to a little luck manipulation, each level in this run is completed in three moves or less, and sometimes in just one move.

Does it work?

You tell me.
No, on second thought, I'll tell you. Yes, it does work. As an example, let's consider the first level completed in the TAS. You start in Italy at 1915 AD (region 29) and your goal is to reach England in 992 (region 0). If we were to follow the game's "suggested" route (by following clues or just cheating and looking at the RAM), it would take us through 1667 Japan (region 30), 1908 USA (17), and 1407 Holland (18) before finally bringing us to England in 992. As you can see from the TAS, however, I just travel directly from 1915 Italy to 992 England, saving three stops and about 2000 frames (half a minute).
This can be conceptualized a little more easily through the following diagram. Numbers represent locations, with the starting point at 29 and the goal at 0. Arrows and circles in blue indicate the game's suggested path while green indicates the path really taken. Circles and arrows in red show other destinations not on the way and are included just to give you a vague sense of the vastness of the map (it's generally a bad idea to wander aimlessly through time and space).
That's just level 1. Although some levels are completed in two or three time jumps, no levels take the suggested path. Late in the game, the suggested route has ten stops, allowing me to save minutes with each level. Even though this movie is over two hours long, I'm confident it would be at least an hour longer if the suggested route were taken. It might even be an additional hour longer if it took the time to gather evidence (resembling human play). If anyone would like me to confirm those numbers, I can probably bot it pretty quickly.

What other things should I know about this run?

No human input was used. This game was entirely botted. This TAS aims for minimal input and while the route may be slightly suboptimal due to time, space, and processing limitations in my bot, all input along this route should be optimal (i.e., all input is entered as soon as it is valid).
The RNGs are rolled every time your chronoskimmer beeps. I have no idea why. They are also deterministic, but they do not commute when you perform different actions in a different order. What this means is if I have two paths that each take two time jumps, they both will yield the same RNGs at the end of the level if I follow the same behavior pattern. They will not yield the same RNGs if I input the evidence at a different point along the path. This is where most of the luck manipulation comes in. For a path with two time jumps, my bot obtains a warrant at the starting location, at the second location, and at the destination, each time evaluating the next case, which is generated from the same RNGs. If I can manipulate the next case into having just one or two jumps, that case is kept after pruning the tree.
And speaking of the tree, that's another aspect. Even though I don't use it to its full ability, my bot is set up to create a tree of savestates of a certain depth and breadth. In this context, depth means how many levels to complete before pruning the tree and breadth means how many of the best runs to keep. I found that my bot was rather time- and resource-intensive, so I decided to keep depth at 1 and breadth at 2. That means I evaluate around four to eight different branches with each level, pruning all but the best two. I suppose I could have set depth and breadth a little higher (at much cost to speed), however I'd much rather see what the community response is like before I optimize my code and leave my computer on all week to run the game.
Searching for suspects is a little bit strange. You're offered the usual three options of "Witness", "Informant", and "Scanner". The first option you choose will always fail to catch them. Sometimes the second option will fail and the remaining option will always succeed. I have no idea what's going on behind the scenes. The bot attempts all six permutations of the three options to minimize the time spent searching.
Each of the sixteen suspects is characterized by five different features: sex, hair color, eye color, favorite artist, and favorite author. Each of these characteristics has four different options except sex, which has two options (duh!). Because sex has just two options, it is the weakest characteristic towards deducing the suspect and obtaining a warrant-- I only use it for Gene Yuss, who is the only member of Carmen's gang who refuses to be categorized by two features. To obtain warrants for the other members, I use the two characteristics that define them. In case the suspect could be deduced from more than one pair of characteristics, I chose whichever characteristics can be most quickly entered; fewest button presses is the first priority, followed by convenient cursor alignment.

Aren't you a little late for April Fools' Day? Do you seriously expect this to be published? Isn't this gruefood?

No need to be pushy with all these questions.
Honestly, I don't expect this to be published. I have no idea why anyone would want to watch it. But, perhaps paradoxically, I do think it's worthy of publication. As far as entertainment goes, this is just about the worst game choice possible, yet a TAS is about showing off tricks and demonstrating gameplay as the designers never intended. This TAS does just that. Granted, it goes on about 79 levels too long, but it's a decent TAS nonetheless. And if this is published, I defy you to produce a less entertaining game.

Possible improvements

The primary improvement to be made is through more extensive luck manipulation. This TAS was produced with my script executing to a depth of 1 and a breadth of 2. By increasing these parameters, luck is manipulated more thoroughly, resulting in shorter cases. Unfortunately, the time it takes to execute increases linearly in the breadth and exponentially in the depth, so their values are somewhat limited.
Huge gains could be made by deciphering the RNG.
The RNG rolls whenever the chronoskimmer beeps and it would therefore be a valid strategy to enter a menu, then exit it just to scramble the RNG. This strikes me as inelegant, however.
By delaying the start of the game (when I press A to enter the elevator) until frame 465, I manipulated the first case so that it could be solved with just one time jump. I've also observed that the RNG is rolled when you leave the elevator and when you enter your name. The result could be manipulated in these areas instead, perhaps getting a good first case faster. Also, luck could potentially be manipulated so that both the first and second (and maybe even third) cases can be completed in one time jump.
I was a little lazy with the last case. I let it play out without explicitly seeking the fastest route. This may make a difference of a few dozen frames at most, but it is far from the biggest frame loss in the run.

The bot script

You may view and download the last version of the script that I used from here.

Some RAM addresses

UserFiles/Info/637936906467145874

Special thanks

I'd like to throw out a blanket thank you to the people who helped me on the TASVideos IRC channel. I don't remember everyone, but I recall adelikat, Ilari, and DarkKobold all weighing in. In particular, I believe DarkKobold was the one who suggested I use savestates and manually stitch together the entire movie (which was what I eventually did). Botting this has been a much bigger pain that I anticipated.
If I have forgotten anyone who helped me, just speak up and I'll add your name.
I'd also like to thank everyone who eagerly anticipated the "mystery TAS". I hope you're not disappointed, by which I mean, I hope you are!

Suggested screenshot

Frame 269307.

Closing remarks

Whatever the result, this has been a fun little project. For everyone who's disappointed everyone, just wait for the upcoming Final Fantasy Legend TAS.
Lol:
DarkKobold: I shall carry the ring into mo... Judge this submission.
DarkKobold: This was a really difficult decision - as it is a 2 hour game played entirely by a bot... Well, a well-written bot.(Rampage A Button Bot, anyone?). Sadly, the game choice is just so plainly and pitifully bad. Once you see the first 3 crooks get arrested, there isn't anything to be seen for 1 hour and 55 minutes more. Awesome achievement, but a horrid result. Even the people who voted yes said they were bored silly. Rejecting for horrid game choice, but keep up the good work with amazing bots.
adelikat: Unrejecting for consideration of publication to the Vault
adelikat: Accepting for publication to the Vault.
Brandon: Publication underway.

Show more

Hide
1 2 3
Posted: 6/22/2011 6:01 AM
Quote
CoolKirby
Editor, Experienced player (570)
Joined: 11/8/2010
Posts: 4036
Exotic platforms TASer of 2014 NES TAS of 2013
Torn338 wrote:
Voting yes, because it made my brain hurt from watching it :D
dwangoAC wrote:
Voting yes on technical quality only because as far as entertainment goes this is about as awful as a well-optimized run could ever get. :)
arflech wrote:
This is TASing at its purest, with absolutely no entertainment value and precise input optimization; I vote yes.
North Bus wrote:
A definite yes vote, though. The video is boring as all get-out, yet this bot is bare-bones TAS-ing at its finest.
I really hope you are all joking. If the run's so boring you can't stand it, there's no place for it on this site (the site aims to publish ENTERTAINING videos).
Posted: 6/22/2011 6:35 AM
Quote
OmnipotentEntity
He/Him
Player (36)
Joined: 9/11/2004
Posts: 2630
From the Youtube video, it doesn't look like this run completes the game.
Build a man a fire, warm him for a day, Set a man on fire, warm him for the rest of his life.
Posted: 6/22/2011 7:36 AM
Quote
Tangent
Joined: 3/9/2009
Posts: 530
Your algorithm is a kind of rudimentary version of Dynamic Programming where you're only exploring around the matrix within a few steps of the current best value instead of building the entire matrix. http://en.wikipedia.org/wiki/Dynamic_programming You can obviously see where that's dangerous and will give wrong answers when there are big differences due to major route changes or an incorrect assumption about what the target is, but if you're careful with your assumptions for how the matrix is built and pruned, you could probably use it in small bursts on just about any game.
Posted: 6/22/2011 2:54 PM
Quote
Bobo_the_King
Player (80)
Joined: 8/5/2007
Posts: 865
exileut wrote:
Voting no because the SMS version wasn't used. Also: http://www.youtube.com/watch?v=ee6eU_148uI
Video added to the submission page.
OmnipotentEntity wrote:
From the Youtube video, it doesn't look like this run completes the game.
At the end of the game, you're rewarded with these two screens: I scrolled past them too quickly to read them. What an ending!
Tangent wrote:
Your algorithm is a kind of rudimentary version of Dynamic Programming where you're only exploring around the matrix within a few steps of the current best value instead of building the entire matrix. http://en.wikipedia.org/wiki/Dynamic_programming You can obviously see where that's dangerous and will give wrong answers when there are big differences due to major route changes or an incorrect assumption about what the target is, but if you're careful with your assumptions for how the matrix is built and pruned, you could probably use it in small bursts on just about any game.
Belying your lurker status, you seem to understand this run better than a lot of vested members do. Yes, it is a very rudimentary form of dynamic programming (I don't consider myself a programmer and I never pass up an opportunity to emphasize that). As such, it's virtually certain that this run is not perfect. If I could execute my program to a search depth of 80 (not possible!), it would theoretically be perfect. This run was made by setting the depth to 1 and the breadth to 2, but if this is somehow accepted, I would like to improve it by increasing the depth to 3 and the breadth to 4 or so. To produce this run, I left my computer on overnight and even then it was only able to complete relatively small chunks (roughly 30 levels) at a time and it became very hot. I can improve it (maybe by 10 minutes or so), but it will require doing just three levels at a time and working on it for about a month before stitching all the movies together.
CoolKirby wrote:
I really hope you are all joking. If the run's so boring you can't stand it, there's no place for it on this site (the site aims to publish ENTERTAINING videos).
It would be the most boring video on the site and that would make it interesting! Kidding aside, I hope you know by now that I don't care if this is published or not. Anyone is more than welcome (perhaps somewhat encouraged...) to vote No-- I don't want anyone to think that I'm foisting a terrible run on the site or trying to prove a point about speed versus entertainment. Edit: So why hasn't anyone claimed this run for judging??? It's almost as if no one wants to have to decide what to do with it...
Posted: 6/22/2011 7:56 PM
Quote
p4wn3r
Player (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
Lucky TAS of 2011 Gameboy TAS of 2011
Bobo the King wrote:
Yes, it is a very rudimentary form of dynamic programming (I don't consider myself a programmer and I never pass up an opportunity to emphasize that). As such, it's virtually certain that this run is not perfect. If I could execute my program to a search depth of 80 (not possible!), it would theoretically be perfect. This run was made by setting the depth to 1 and the breadth to 2, but if this is somehow accepted, I would like to improve it by increasing the depth to 3 and the breadth to 4 or so. To produce this run, I left my computer on overnight and even then it was only able to complete relatively small chunks (roughly 30 levels) at a time and it became very hot. I can improve it (maybe by 10 minutes or so), but it will require doing just three levels at a time and working on it for about a month before stitching all the movies together.
This might help a bit, alongside dynamic programming, it's the most common technique for hard computational problems: http://en.wikipedia.org/wiki/Backtracking Also, instead of doing that mess to find the shortest path, you can try this: http://en.wikipedia.org/wiki/Breadth-first_search
Posted: 6/22/2011 8:44 PM
Quote
errror1
Active player (293)
Joined: 12/16/2008
Posts: 458
Location: Houston
exileut wrote:
Voting no because the SMS version wasn't used. Also: http://www.youtube.com/watch?v=ee6eU_148uI
your kidding right? the dos version should have been used
Posted: 6/22/2011 8:59 PM
Quote
Bobo_the_King
Player (80)
Joined: 8/5/2007
Posts: 865
p4wn3r wrote:
Bobo the King wrote:
Yes, it is a very rudimentary form of dynamic programming (I don't consider myself a programmer and I never pass up an opportunity to emphasize that). As such, it's virtually certain that this run is not perfect. If I could execute my program to a search depth of 80 (not possible!), it would theoretically be perfect. This run was made by setting the depth to 1 and the breadth to 2, but if this is somehow accepted, I would like to improve it by increasing the depth to 3 and the breadth to 4 or so. To produce this run, I left my computer on overnight and even then it was only able to complete relatively small chunks (roughly 30 levels) at a time and it became very hot. I can improve it (maybe by 10 minutes or so), but it will require doing just three levels at a time and working on it for about a month before stitching all the movies together.
This might help a bit, alongside dynamic programming, it's the most common technique for hard computational problems: http://en.wikipedia.org/wiki/Backtracking Also, instead of doing that mess to find the shortest path, you can try this: http://en.wikipedia.org/wiki/Breadth-first_search
I skimmed the article on backtracking and I'm not sure it's applicable. The chief issue is that this isn't a decision problem. Although it's extraordinarily unlikely, it's possible that the absolute fastest the game can be completed is done by completing the first four levels in four time jumps (which is the most time jumps a level can reasonably take) while all 76 remaining levels are completed in one time jump. Pruning therefore must be heuristic. However, I have considered pruning options before the maximum depth is reached. If the depth is set to 3 and two consecutive levels take four time jumps while the best branches complete two levels in one time jump, then that path cannot possibly be improved by playing another level. Perhaps that's basically what backtracking is. Anyway, it wouldn't have made a difference in this run since the depth was set to 1. I should also point out that my script does execute a breadth-first search. A depth-first search wouldn't even make sense (complete all 80 levels, then try again?). Also, I'd like to make the distinction clear between the tree search I do to solve a level and the one I do to navigate the entire game. The tree search for individual levels has a depth and breadth no greater than 4, so it is very easy to navigate the entire tree. Therefore, the path through every level is 100% optimal. I'm certain of it. (Okay, except for a few frames of cursor movement and stuff when comparing two routes of the same length, but that's minor.) The route through the entire game is where the heuristics come in. Ignoring luck manipulation at the start of the game (which multiplies the number of possibilities by 1000 or so), this tree has two to five branches at every level and continues to a depth of 80 levels. Figuring conservatively, that's 2^80 different states to check at the final level alone. There is absolutely no way it can be done without heuristics, and in this sense, a Carmen Sandiego TAS will never be perfect (unless the RNG can be deciphered). The only improvement I see that I could make is pruning before the maximum depth is reached, but other than that, it's just a matter of cranking up the depth and breadth and letting it run longer. Hope that clears up any confusion. Edit:
errror1 wrote:
exileut wrote:
Voting no because the SMS version wasn't used. Also: http://www.youtube.com/watch?v=ee6eU_148uI
your kidding right? the dos version should have been used
Does DOSbox (or whatever the standard DOS emulator) implement Lua scripting? If so, although I'm not familiar with the DOS version, I was impressed by its screenshots. It's a much better-looking game. I might try to use it for version 2 (if I choose to make it). Unless of course you both are joking...
Posted: 6/22/2011 9:14 PM
Quote
p4wn3r
Player (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
Lucky TAS of 2011 Gameboy TAS of 2011
Regarding to BFS, I was talking about this, in function shortestpaths, to find the shortest path for only one graph, not the entire game: 
Language: Lua
        map[0][initial]={{}}
        map[1][final]={{}}
        local depth=0
        while not(incommon(map[0],map[1])) do
                        for i=0,47 do
                                if map[depth%2][i] and #map[depth%2][i][1]==math.floor(depth/2) then
                                        for j=0,3 do
                                                local destination=graph[i][j]
                                                map[depth%2][destination]={}
                                                local temp=table.copy2(map[depth%2][i])
                                                for k=1,#temp do
                                                        table.insert(temp[k],#temp[k]*(1-depth%2)+1, destination*(1-depth%2)+i*(depth%2))
                                                        map[depth%2][destination][#map[depth%2][destination]+1]=table.copy(temp[k])
                                                        temp=table.copy2(map[depth%2][i])
                                                end
                                        end
                                end
                        end
                depth=depth+1
        end
Honestly, I'm not very sure about what this does, but it doesn't look like a BFS. Also, any optimization problem can be turned into a collection of decision ones multiplying the complexity by O(log d), where d is the max amount of turns it takes to finish. You can turn your problem into "can I finish the game using d steps?" and binary search on d. This is just meant to give you some thoughts about botting it if you intend to do this again, I give no guarantee that backtracking can be used to help. It's just something to think about.
Posted: 6/22/2011 9:52 PM
Quote
Bobo_the_King
Player (80)
Joined: 8/5/2007
Posts: 865
p4wn3r wrote:
Regarding to BFS, I was talking about this, in function shortestpaths, to find the shortest path for only one graph, not the entire game: 
Language: Lua
        map[0][initial]={{}}
        map[1][final]={{}}
        local depth=0
        while not(incommon(map[0],map[1])) do
                        for i=0,47 do
                                if map[depth%2][i] and #map[depth%2][i][1]==math.floor(depth/2) then
                                        for j=0,3 do
                                                local destination=graph[i][j]
                                                map[depth%2][destination]={}
                                                local temp=table.copy2(map[depth%2][i])
                                                for k=1,#temp do
                                                        table.insert(temp[k],#temp[k]*(1-depth%2)+1, destination*(1-depth%2)+i*(depth%2))
                                                        map[depth%2][destination][#map[depth%2][destination]+1]=table.copy(temp[k])
                                                        temp=table.copy2(map[depth%2][i])
                                                end
                                        end
                                end
                        end
                depth=depth+1
        end
Honestly, I'm not very sure about what this does, but it doesn't look like a BFS. Also, any optimization problem can be turned into a collection of decision ones multiplying the complexity by O(log d), where d is the max amount of turns it takes to finish. You can turn your problem into "can I finish the game using d steps?" and binary search on d. This is just meant to give you some thoughts about botting it if you intend to do this again, I give no guarantee that backtracking can be used to help. It's just something to think about.
I'll do my best to explain, but it makes the most sense to me when I think about it visually. This search executes what I call a double-tree search, regardless of what it's actually called in computer science. The table map[0] includes all of the locations that can be reached from the initial location while map[1] includes all of the locations that can be reached from the goal location. The function first finds all destinations that can be reached from the starting location and checks if any of them is the goal location (that's breadth-first). It then finds all destinations that can be reached from the goal location and checks if any of them match the locations that can be reached from the starting location (again, breadth-first, essentially). This continues until a match is found and because of how it was found, any match is surely the shortest path from the starting location to the goal location. Of course, it's all a bit muddled by modular arithmetic and stuff because I rewrote my code a few times and wanted to make it succinct. Anyway, this is of absolutely no consequence because my bot can find the shortest path through a level almost instantaneously (I've verified this). Virtually all of the time spent botting is lost testing the path through the game. When playing many levels (more than 20 or so), most of this time is spent solely on the savestate.load function for reasons I still don't fully understand. For just a few levels at a time, most of the time is spent on the actual game, frame advancing. I wish FCEUX had emu.emulateframeinvisible like Gens, but I'll take what I can get.
Posted: 6/22/2011 11:32 PM
Quote
p4wn3r
Player (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
Lucky TAS of 2011 Gameboy TAS of 2011
Ah, thanks, I was being more strict with the nomenclature. A BFS is done like this: 
mark all vertices as not visited
enqueue root
mark root as visited
while queue not empty do
	dequeue the vertex v
	for each (v,w) in the graph do
		if w is not visited then
			enqueue w
			mark w as visited
		end
	end
end
If you keep a linked list (or something like that) to keep track of who called each vertex, you can get your path by following the nodes starting from the destination. You can even stop the search when you reach the destination. I never doubted the correctness of your algorithm, just notice that there are some significant differences between your code and the BFS, not just in terms of implementation (copying an entire table at each iteration vs using a queue). You start the search in two nodes and constantly query the structure to know if there's any intersection. Although the idea of traversing the nodes in the right order is there, saying that the script executes a breadth-first search is a little inaccurate, "essentially" is different from "is". It's possible to come up with other algorithms that use a similar idea with sub-optimal complexity and calling them all a BFS would make the nomenclature very imprecise. If the actual graph is too small for this change to make a difference, then I wish I hadn't brought this up. Seeing as FCEUX is the main problem, you could disassemble the ROM to know the game's mechanics and run a simulation on a compiled language, assuming this is accepted, of course. And I abstained from voting.
Posted: 6/23/2011 4:24 PM
Quote
goldfish
Joined: 2/20/2010
Posts: 209
Location: I'm in space
I think this should be published so people who hate themselves can sit and watch educational and often interesting information fly by much too fast to be read. Additionally, I think the typical masochist would enjoy the migraine that'd follow. How about we start a new thread exploring the intricacies of dynamic programming and, in particular, how it relates to this game, but FOR THE LOVE OF GOD, people, I can't believe so many are voting yes just because it's a technically impressive achievement! The run is completely unwatchable for a normal human unless you slow it WAY down to read everything, but then you'd probably scale the total length out to 10 hours. Nothing personal, Bobo - and I do wholeheartedly recognize the effort invested in making this - but I vote NO on account of the fact that no sane person would ever watch the whole thing. EDIT: I just want to add that I really do think this is an impressive feat of engineering, and I have no doubt that it was a stimulating exercise in computer science and combinatorics in general... IMHO though, the result has zero entertainment value, and I just don't think a run should be published on technical merit alone.
Oh, play it cool. Play it cool. Here come the space cops.
Posted: 6/24/2011 1:40 AM
Quote
Sonikkustar
Skilled player (1326)
Joined: 9/7/2007
Posts: 1354
Location: U.S.
Sega TASer of 2021 Sega TAS of 2021 Sega TASer of 2011 Sega TAS of 2011
http://www.youtube.com/watch?v=omW1-IyYOFY HD Encode
Homepage SVN
Posted: 6/24/2011 5:23 AM
Quote
Tangent
Joined: 3/9/2009
Posts: 530
Bobo the King wrote:
Tangent wrote:
Your algorithm is a kind of rudimentary version of Dynamic Programming where you're only exploring around the matrix within a few steps of the current best value instead of building the entire matrix. http://en.wikipedia.org/wiki/Dynamic_programming You can obviously see where that's dangerous and will give wrong answers when there are big differences due to major route changes or an incorrect assumption about what the target is, but if you're careful with your assumptions for how the matrix is built and pruned, you could probably use it in small bursts on just about any game.
Belying your lurker status, you seem to understand this run better than a lot of vested members do. Yes, it is a very rudimentary form of dynamic programming (I don't consider myself a programmer and I never pass up an opportunity to emphasize that). As such, it's virtually certain that this run is not perfect. If I could execute my program to a search depth of 80 (not possible!), it would theoretically be perfect. This run was made by setting the depth to 1 and the breadth to 2, but if this is somehow accepted, I would like to improve it by increasing the depth to 3 and the breadth to 4 or so. To produce this run, I left my computer on overnight and even then it was only able to complete relatively small chunks (roughly 30 levels) at a time and it became very hot. I can improve it (maybe by 10 minutes or so), but it will require doing just three levels at a time and working on it for about a month before stitching all the movies together.
I've thought about trying to make a DP script in the past because I think it'd be very neat and useful for exploration to find glitches based on counter-intuitive inputs, but I have neither the free time nor expertise to devote to a project like that. You might give a thought to trying it some very short run that you could build the whole matrix like Donkey Kong, Monopoly or Urban Champion. That could at least verify that your algorithm appears to work and let you find any issues. It would be most powerful on one of the menu runs that has a limited amount of randomness, or at least randomness that can be well-controlled. Any run that you'd be able to prune the matrix based on homogeneity of system state results from input would be immensely more efficient. Unfortunately, most of those tend to be RPGs, which are far too long and often abuse strange glitches (Chrono Trigger's extremely non-route route comes to mind).
Posted: 6/24/2011 6:39 AM
Quote
errror1
Active player (293)
Joined: 12/16/2008
Posts: 458
Location: Houston
Bobo the King wrote:
errror1 wrote:
exileut wrote:
Voting no because the SMS version wasn't used. Also: http://www.youtube.com/watch?v=ee6eU_148uI
your kidding right? the dos version should have been used
Does DOSbox (or whatever the standard DOS emulator) implement Lua scripting? If so, although I'm not familiar with the DOS version, I was impressed by its screenshots. It's a much better-looking game. I might try to use it for version 2 (if I choose to make it). Unless of course you both are joking...
yes jpc-rr has lua yeah, having played it on a billion years ago it's a better looking and sounding game in dos but I think the animations are even longer so a run on it might be slower.
Posted: 6/28/2011 5:35 AM
Quote
TASVideosGrue
They/Them
Joined: 10/1/2008
Posts: 2785
Location: The dark corners of the TASVideos server
om, nom, nom... blech, bitter!
Posted: 6/28/2011 6:22 PM
Quote
Bobo_the_King
Player (80)
Joined: 8/5/2007
Posts: 865
Lol.
Posted: 11/5/2012 3:52 AM
Quote
jlun2
Skilled player (1738)
Joined: 9/17/2009
Posts: 4980
Location: ̶C̶a̶n̶a̶d̶a̶ "Kanatah"
GBA TASer of 2010
Bobo the King wrote:
I will not rest until my Where in Time is Carmen Sandiego run is published!!! (Just ignore me.)
 I think you'll soon be able to rest in peace, Bobo.
LLCoolDave wrote:
This seems to be competing for the "Worst looking TAS of 2011" Award.
Posted: 11/5/2012 4:49 AM
Quote
CoolKirby
Editor, Experienced player (570)
Joined: 11/8/2010
Posts: 4036
Exotic platforms TASer of 2014 NES TAS of 2013
Yes, let's get this finally published!
Posted: 11/5/2012 3:53 PM
Quote
Radiant
Player (26)
Joined: 8/29/2011
Posts: 1206
Location: Amsterdam
This should be published for its technical merit. Vault tier ahoy!
Indie game developer
Posted: 11/6/2012 4:30 PM
Quote
Bobo_the_King
Player (80)
Joined: 8/5/2007
Posts: 865
Haha, thanks, my groupies! Looks like the vault was made for this run.
Posted: 11/21/2012 3:53 PM
Post subject: Publish this to the vault - great submission description!
Quote
dwangoAC
Moderator, Senior Ambassador, Experienced player (907)
Joined: 9/14/2008
Posts: 1014
Exotic platforms TASer of 2015 Exotic platforms TASer of 2013
Just to bring things full-circle, I still think this run should be accepted based on the technical merit and the entertaining to read submission text. Furthermore, I nominate this thread for a currently nonexistent "Notable Submission Description" flag. Thanks for making this, A.C. ******
I was laid off in May 2023 and became too ill to work this year and could use support via Patreon or onetime donations as work on TASBot Re: and TASBot HD is stalled. I'm dwangoAC, TASVideos Senior Ambassador and BDFL of the TASBot community; when healthy, I post TAS content on YouTube.com/dwangoAC based on livestreams from Twitch.tv/dwangoAC.
Posted: 11/21/2012 6:37 PM
Post subject: Re: #3187: Bobo the King's NES Where in Time Is Carmen Sandiego in 2:01:54.05
Quote
Heisanevilgenius
Active player (406)
Joined: 3/22/2006
Posts: 708
Funny TAS of 2009 Innovative TAS of 2009
I have to admit, the submission text has me impressed. I'm not sure I want to sit through it, though.
TASVideoAgent wrote:
And if this is published, I defy you to produce a less entertaining game.
http://tasvideos.org/forum/viewtopic.php?t=7902 I think this fits in the same category. Both of these runs are conceptually hilarious, but are they worth actually watching?
Posted: 11/21/2012 6:38 PM
Quote
adelikat
He/Him
Emulator Coder, Site Developer, Site Owner, Expert player (3572)
Joined: 11/3/2004
Posts: 4754
Location: Tennessee
TASer of 2010 NES TASer of 2010 DS TASer of 2010 Arcade TAS of 2010 NES TASer of 2008 NES TAS of 2008 Funny TAS of 2008 TASer of 2007 NES TASer of 2007 Funny TAS of 2007
Is this Vaultable? I'm not sure I understand the goals here. Is 2 hours really the fastest you can complete this game?
It's hard to look this good. My TAS projects
Posted: 11/21/2012 6:48 PM
Quote
Warepire
He/Him
Editor
Joined: 3/2/2010
Posts: 2178
Location: A little to the left of nowhere (Sweden)
adelikat wrote:
Is this Vaultable? I'm not sure I understand the goals here. Is 2 hours really the fastest you can complete this game?
As I understand it it is not absolutely the fastest possible. But it seems to be plenty fast enough given what is known about the game. Most of the possible improvements are related to deciphering the RNG which no one will do unless there is a published TAS to improve upon in the case of this game. I vote for publication in the vault.
Posted: 11/21/2012 6:50 PM
Quote
adelikat
He/Him
Emulator Coder, Site Developer, Site Owner, Expert player (3572)
Joined: 11/3/2004
Posts: 4754
Location: Tennessee
TASer of 2010 NES TASer of 2010 DS TASer of 2010 Arcade TAS of 2010 NES TASer of 2008 NES TAS of 2008 Funny TAS of 2008 TASer of 2007 NES TASer of 2007 Funny TAS of 2007
Ok, that's good enough for me, thanks.
It's hard to look this good. My TAS projects
1 2 3