There's a difference between downloading an emulator, which is one set of software that is widely used by a fairly large number of people, and joining a compute cloud, where people can submit jobs that could be doing just about anything, with relatively little oversight. You need to sandbox the program so it can't meddle with anything.
Pyrel - an open-source rewrite of the Angband roguelike game in Python.
You guys are right. I was thinking maybe it could work like a torrent client where you download ".tas" files instead. I guess the client would then have to be able to work as a front end, open up the actual emulator and inject some LUA or some key press file along with the actual ROM. Maybe we don't need to worry yet whether very same program should handle multiple formats. Not sure either if the clients should communicate directly to eachother or not.
I'd download that but I guess that goes without saying ;-)
Joined: 6/25/2007
Posts: 732
Location: Vancouver, British Columbia, Canada
I agree with BrandonE.
If, for example, someone like Adelikat wrote a Dragon Warrior 4 luck manipulation bot with a loose route to optimize and video output showing the current frame and state of various memory addresses, I'm sure a distributed computing project surrounding that could become very popular.
Obviously this sort of thing could be applied to many TAS projects. Having the video output with the current state would definitely be awesome.
There really is no need for the creation of a distributed botting framework since there's literally hundreds of distributed computing frameworks in existence. Some are over two decades old, can be readily plugged into any C/C++ program with the flip of a compiler switch, they're high-speed, feature complete, cross-platform, work on heterogeneous networks, and they're easy enough to use to be forced onto students.
Writing another is really just re-inventing the wheel for a car you don't have.
While the last few posts have finally focused on the actual problem (writing a bot that works), there's still no suggestions on how to make writing such bots any easier. Because, frankly, there isn't. It's a hard problem that'll have to be evaluated and solved for each game or situation separately, and in most cases the evaluation phase will still end with "It can't be done in a useful way".
Or maybe we could start thinking about how to distribute the LunarBot, which is already a working bot...?
The simplest way I guess would be to just let each new client evaluate its own level and if each level is already being processed I guess two clients could work on the same level not communicating with each other. We would then just pick the client with the fastest clear stage input from each level and merge the input. This requires that no input from level x is affecting level y, though. Maybe someone could confirm that?
If people find that interesting I am sure it would attract others and hopefully/eventually someone will improve the "framework" further and start writing more bots for different scenarios.
Tub's point is that LunarBot is specific to Lunar Pool, so unless you want to improve that specific game, there's no point in distributing it.
In other words, distributed computing can help bots run faster but it won't help you make bots.
Is there any interest in improving Lunar Pool? My only complaint about it was that it occasionally made "dummy" shots just to reduce the score tally time -- a smart optimization for the overall TAS but it reduced the per-shot entertainment value.
Pyrel - an open-source rewrite of the Angband roguelike game in Python.
This requires that no input from level x is affecting level y, though. Maybe someone could confirm that?
I can confirm that your assumption is wrong. As explained in the submission text, RATE does not reset between levels.
Derakon wrote:
In other words, distributed computing can help bots run faster but it won't help you make bots.
the other point was that transforming a bot into a distributed version has to be done for each bot individually. Reuse is only possible for bots that use similar algorithms, and different games are likely to require largely different bots. There's not much of a reusable "framework" you could build that goes beyond the capabilities of the existing frameworks.
Derakon wrote:
Is there any interest in improving Lunar Pool? My only complaint about it was that it occasionally made "dummy" shots just to reduce the score tally time -- a smart optimization for the overall TAS but it reduced the per-shot entertainment value.
The "smart" improvement for dummy shots would be to find a pool game with more tas-friendly rules. Surely there's more than one pool game in existence, but I haven't checked the others.
I guess I have been too optimistic when it comes to this "project" then. I just think that the concept of bots and genetic algorithms is really cool. Still hope there is someone who shares this thought and have the time to realize it somehow.
By the way, where (as in which topic) would be the best place to learn some NES LUA Scripting? Perhaps the most simple RND alteration bot has been described?
Thanks for your feedback!
Give it a few years/decades and maybe we'll have computers powerful enough to genetically evolve an input sequence that beats Mario. :p
I think the King's Bounty run involved some brute-forcing? But that was for only 0.3 seconds of input...
If you want to get an idea how infeasible brute-forcing is, do the math (again!): for 8 buttons, you have 8 bits of input per frame. You want to compute the shortest input sequence that wins the game.
One frame = 8 bits = 2^8 = 256 possible input combinations to test. Did you win? No..
Two frames = 16 bits = 2^16 = 65,536 possible input combinations.
Four frames = 2^32 = 4,294,967,295.
8 frames = 2^64 = 18,446,744,073,709,551,616.
For just eight frames you already have 18 quintillion possible input sequences. Every additional frame multiplies the number of possible sequences by 256.
Keep in mind that the only way to tell if a given sequence wins the game is to play it in the emulator from start to finish, and if you want to create the best sequence, you have to be able to backtrack - it's not enough to say that by frame 10,000, Mario's made pretty good progress, so those first 10K frames don't need any more adjustment, because maybe he headed into a dead end at frame 8000. (FYI, 2^10000 has 3011 decimal digits.)
Also mind that you don't know how long the winning sequence will be. So, assuming the winning sequence is only 8 frames long, that doesn't mean you only have 2^64 possible sequences to try - you first have to determine that you can't win in 7 frames, or 6, or 5... that means you have 2^64 + 2^56 + 2^48 ... + 2^8 sequences.
For n frames, the total number of possible input sequences is 2^(n*8) + 2^((n-1)*8) + 2^((n-2)*8) ... + 2^(2*8) + 2^(1*8).
By the time you get to frame 60 - that's one second of input - you already have 2^(60*8) possible sequences to try - that's
312,174,855,031,599,223,138,159,722,979,316,
630,574,859,814,266,497,115,085,91,569,596,
253,717,388,197,656,201,203,061,030,634,919,
711,598,269,311,214,066,22,895,447,975,679,
288,285,306,290,176 possible 60-frame movies. And that's only after you've tried every possible movie of 59 frames, 58 frames, 57 frames...
Let me know when your computer can generate the works of Shakespeare by brute-forcing strings one character at a time and then checking the entire result (no partial matches allowed!). Once you can do that... brute-forcing a TAS still won't be feasible, because now instead of a simple strcmp() to check if your input is correct, you have to feed it into a considerably more complex function, e.g. Super Mario Bros.
Noob Irdoh wrote:
Or, did you download the emulator source code, checked it all to see if it's malicious, and compiled it by your own? Very well, ask the TAS@home to be open source (and multi-platform too while that we're at it) and compile it too by your own.
And then you have to trust that your compiler isn't bugged... wrote your own in machine code? Hope you trust your CPU... ;)
[edit for less page stretchage]
Well, how I see it is that you could use a bot to solve a simplified version of the 'problem' - for example, finding the optimal movement pattern in a single area of Pokemon Red/Blue - and then implement that solution into the TAS - in this case, the movement that Red/Blue/Ash makes to get through that area. But unless you are prepared to study loads of movement patterns, which can take hours or even days to solve, I can't see how well this would work.
One frame = 8 bits = 2^8 = 256 possible input combinations to test. Did you win? No..
wouldn't it be more like 8 possible input combinations, since you can only push one of those 8 buttons in one frame? and it seems to me that for 2 frames, it would increase exponentially and thus be 16 inputs. edit: i forgot that you can push several buttons at the same time, so i think i get it now.
do you take into account that the emulator can be speeded up 1000%, thus making it 1000 times faster. also, the computer law of exponential increase of things keeps increasing, so in the future we'll have 40 yottahertz processors, so maybe it could be possible some day?
you already have 2^(60*8) possible sequences
how do you calculate that on a calculator? when i multiplied 60*8*256, i only got 122880.
Let me know when your computer can generate the works of Shakespeare by brute-forcing strings one character at a time and then checking the entire result (no partial matches allowed!).
if you change the odd and even numbers of pi into ones and zeroes, you can find the binary code for shakespeares work in there somewhere, in .txt format. good luck.
