1 2
Posted: 2/8/2011 12:05 AM
(Edited: 2/12/2011 5:20 PM)
Post subject: Pure AI TAS?
Quote
Brandon
He/Him
Editor, Player (191)
Joined: 11/21/2010
Posts: 914
Location: Tennessee
Hello all, I've been fascinated with TAS's for years, and I finally want to make my own. While getting acquainted with the tools, the one that has interested me the most is the tool that allows you to execute Lua. I started playing around with it, and I tried to make a bot that played SMB1 to some success. As fun as it is to create an AI to play a game for you, it quickly became obvious it would be hard if not impossible to create one that beat the game quicker than the current record. After thinking about this, I wondered: what if I tried to do a TAS with pure AI, and didn't focus so much on beating it faster than the current record? Wouldn't that prove to be as useful if not more so than a regular TAS? For example:
  • The playing algorithms could be easily edited, allowing people to improve the times much more efficiently than playing the game again from scratch.
  • Being able to actually see what the player is doing in all cases could be interesting.
  • I'd figure that a lot of programmers like myself would get a kick from it.
One might debate what makes a submission pure AI, and what would stop me from just making a script that enters moves in like an emulator's movie file. I'd say that we could define this by a script that can start from any point in the game and play to the finish. As a programmer for seven years, I would really enjoy doing something like this, but I'd like the community's blessings. So, would something like this be worth pursuing? Would the moderators of this site post my submissions if they followed this criteria? What category would they place it under if so? Thanks, Brandon
All the best, Brandon Evans
Posted: 2/8/2011 12:17 AM
Quote
Bisqwit
Editor, Active player (297)
Joined: 3/8/2004
Posts: 7469
Location: Arzareth
With Lunar Ball / Lunar Pool it is actually possible to create an AI that beats the current TAS(es). Seeing as how those TASes were created almost exclusively with an AI to begin with. (Indeed, the bot was designed to play the game, go to next stage, etc. completely without assistance, which it did, without failure, but I sometimes finetuned its outcomes manually.) It is possible to beat them, because the features for the AI were chosen with a tradeoff between execution speed and completeness in search for best results. With the current settings, [1565] NES Lunar Pool by Bisqwit in 23:47.52 took several years of CPU time to calculate (and over a year of user time). Using an AI to play stand-alone is possible with simple games like Tetris or Sokoban. There exist many successful algorithms for Tetris AI by now. It might be possible with simple relatively invariant platform games like SMB1, too, however extremely difficult. For a game like Mega Man or Solomon's Key I don't think it is possible at all. (Solomon's Key combines puzzle with moving actors, hence extra difficulty.) Though I would really like to get to read the source code of someone's attempt! Legend of Kage is likely possible due to its simplicity, assuming that you know the mathematical secrets that make it tick. Oh, can the AI do rerecording? That matters a great deal. If rerecording cannot be used, then the AI must be able to plan ahead without any mistakes, or to recover from mistakes. A Tetris AI can simulate the game ahead with visual information alone, without rerecording, whereas the Lunar Pool bot relies on rerecording to get feedback on what each angle&velocity combination produces. And is the AI allowed to access the game's RAM to read things like actors' velocities and RNG seed?
Posted: 2/8/2011 12:46 AM
Quote
alden
Player (121)
Joined: 2/11/2007
Posts: 1522
http://tasvideos.org/forum/viewtopic.php?t=5569 among other threads springs to mind. To your question about publishability, probably only movies that people find more entertaining on an aesthetic level will get published (ie they are faster etc). Just because it was generated by a program doesn't mean it's entertaining to a large audience, and I doubt a new category would be created. I would be interested to see any of your attempts though as this sort of thing fascinates me :)
I make a comic with no image files and you should read it. While there is a lower class, I am in it, and while there is a criminal element I am of it, and while there is a soul in prison, I am not free. -Eugene Debs
Posted: 2/8/2011 1:00 AM
(Edited: 2/12/2011 5:20 PM)
Quote
Brandon
He/Him
Editor, Player (191)
Joined: 11/21/2010
Posts: 914
Location: Tennessee
I suppose it doesn't have to be submitted as a TAS...do you think they'd put it in a section for the particular game's resource page? I just would like to try this knowing that my work will have the potential to be published in some shape or form.
All the best, Brandon Evans
Posted: 2/8/2011 1:43 AM
Quote
Derakon
Joined: 7/2/2007
Posts: 3960
I'm sure that any efforts you made would be found very interesting by many members of this site, and you'd get recognition somehow even if the resulting movie were not published in the traditional manner.
Pyrel - an open-source rewrite of the Angband roguelike game in Python.
Posted: 2/8/2011 2:09 AM
(Edited: 2/12/2011 5:20 PM)
Quote
Brandon
He/Him
Editor, Player (191)
Joined: 11/21/2010
Posts: 914
Location: Tennessee
What do you think about the Game Resources page idea? By the way, it this section of the site modifiable by a normal user (like a wiki)?
All the best, Brandon Evans
Posted: 2/8/2011 2:58 AM
Quote
upthorn
He/Him
Emulator Coder, Active player (391)
Joined: 3/24/2006
Posts: 1802
Sega TAS of 2011 Sega TAS of 2010 Sega TAS of 2008 Sega TASer of 2007
What about the King's Bounty TAS? Isn't that basically AI-only already?
How fleeting are all human passions compared with the massive continuity of ducks.
Posted: 2/8/2011 3:22 AM
(Edited: 2/12/2011 5:21 PM)
Quote
Brandon
He/Him
Editor, Player (191)
Joined: 11/21/2010
Posts: 914
Location: Tennessee
I'm not saying that other people haven't done this before; I'm just wondering if I'd get any form of hosting if I don't beat the current record yet I build an AI that completely plays the game.
All the best, Brandon Evans
Posted: 2/8/2011 7:30 AM
Quote
Warp
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
One thing is for certain: Trying to find an optimal completion of a game by brute-force searching (even if you use smart pruning algorithms) is impossible in a rational amount of time. (The Sun would engulf the Earth long before the program gets to even 1% completion. And this assuming it had enough RAM, which it doesn't, not in a trillion years). Whether a heuristic algorithm can be developed that doesn't necessarily find the perfect solution but can beat humans, it depends enormously on the type of game. A Rubik's cube has an exponential amount of possible rotation combinations, but smart heuristic algorithms can solve it in less rotations than any human can (at least in average). They might not always find the minimum amount of rotations, but they can certainly beat humans. A computer can beat humans in checkers almost trivially (even though checkers also has an exponential amount of branches). With chess it becomes a lot harder (while chess programs have beaten world champions, there exist grandmasters who are specialists at beating computers, so the fight is more or less even right now). With go computers have currently no chance against humans (not even on small 9x9 boards, not to talk about the full 19x19 board). So it really depends on the game.
Posted: 2/8/2011 7:46 AM
Quote
Mitjitsu
He/Him
Banned User
Joined: 4/24/2006
Posts: 2997
TAS of 2007 N64 TAS of 2007
Warp wrote:
With chess it becomes a lot harder (while chess programs have beaten world champions, there exist grandmasters who are specialists at beating computers, so the fight is more or less even right now). With go computers have currently no chance against humans (not even on small 9x9 boards, not to talk about the full 19x19 board).
Despite Chess computers beating the very best the world has to offer. It will probably be another 100 years before they can trully play perfectly. I've heard of *anti computer* tactics where humans will try and drag out a game as long as possible so the computer runs out of branches. Still it would be interesting to know if a perfect game results in a white win or a stalemate. In relation to TASing you could certainly create intelligent AI that could TAS NES games which only have 256 possible inputs per frame. Wii games on the other hand have several billion possible inputs per frame. Even when taking heuristics into account you'll still end up with a few million feasible possibilties in a single frame.
Posted: 2/8/2011 8:30 AM
Quote
Warp
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
Mitjitsu wrote:
In relation to TASing you could certainly create intelligent AI that could TAS NES games which only have 256 possible inputs per frame.
It doesn't really matter how many buttons there are. Even if you had only one button and your only choice on each frame would be whether to press it or not, you would still end up having an exponential amount of possible combinations as the run progresses and it quickly becomes too numerous to calculate in a rational amount of time. (You just need to advance something like 50 frames and we are already talking about hours, if not even days to go through all the possible combinations. Although some smart pruning algorithms could cut down the search tree significantly, they would only allow you to advance maybe 10-20 frames more before the amount of branches once again becomes too large.) The only hope is to come up with a heuristic that does something else than brute-force searching.
Posted: 2/9/2011 2:21 AM
(Edited: 2/12/2011 5:21 PM)
Quote
Brandon
He/Him
Editor, Player (191)
Joined: 11/21/2010
Posts: 914
Location: Tennessee
Warp wrote:
The only hope is to come up with a heuristic that does something else than brute-force searching.
And that's exactly what I was planning to do. I just figured that even if I don't succeed in creating a bot that finishes faster than a normal TASer, the script would still be useful to the community, and if the consensus agrees, I'll try writing some.
All the best, Brandon Evans
Posted: 2/9/2011 3:55 AM
Quote
Derakon
Joined: 7/2/2007
Posts: 3960
I think we'd certainly find it very interesting, but any remotely successful TAS bot is going to be incredibly game-specific, and I'm not just talking about things like memory addresses. But hey, feel free to prove me wrong. :)
Pyrel - an open-source rewrite of the Angband roguelike game in Python.
Posted: 2/9/2011 4:10 AM
(Edited: 2/12/2011 5:21 PM)
Quote
Brandon
He/Him
Editor, Player (191)
Joined: 11/21/2010
Posts: 914
Location: Tennessee
Oh, yes, I wasn't planning on making a bot to beat both SMB1 and The Legend of Zelda. That'd be ridiculous. Anyways, if I'm doing this, I'm going to make a bot that plays Panel de Pon / Tetris Attack. Besides, there is no TAS for VS. mode.
All the best, Brandon Evans
Posted: 2/9/2011 5:23 AM
Quote
Derakon
Joined: 7/2/2007
Posts: 3960
I could definitely see that working. A nice, controlled environment should keep the search path fairly tidy. Basically you'd be coding an AI for the game that can abuse savestates for maximum carnage. Good luck!
Pyrel - an open-source rewrite of the Angband roguelike game in Python.
Posted: 2/9/2011 8:05 PM
Quote
MESHUGGAH
Other
Skilled player (1917)
Joined: 11/14/2009
Posts: 1353
Location: 𝔐𝔞𝔤𝑦𝔞𝔯
NES TASer of 2013 NES TAS of 2013 NES TAS of 2012 NES TAS of 2011
Brute force is the best solution to find the fastest completion input collection. Needless to say, the time needed for brute forcing a game is something like that: [2 ^ (Number of buttons * Actual TAS record frame count)] / Emulation time. For example, the shortest movie is [1145] Genesis King's Bounty by gia & Aqfaq in 00:09.93 so brute forcing it would take at least 2^(9*596)/10 = 5,3075823547897896501038675241442e+1613 seconds. Feel free to correct me, I'm not good at math. Of course, optimizations will reduce this time, but also increases the chance to be slower than the possibly fastest input series used to complete a game. The reason is that there are many bugs and glitches that happens "randomly" for normal human sense. Just like sub-pixel calculations, wrong order in the code (contra fadeout glitch), warping like a madman (castlevania aimmx), etc. edit: formula...
PhD in TASing 🎓 speedrun enthusiast ❤🚷🔥 white hat hacker ▓ black box tester ░ censorships and rules...
Posted: 2/9/2011 8:09 PM
Quote
Randil
Skilled player (1826)
Joined: 4/20/2005
Posts: 2161
Location: Norrköping, Sweden
Here is a short Galaga movie I made that was entirely recorded by a bot. It used savestates and a whole lot of trial and error. Space shooters like this, and in particular the more simple ones like Space Invaders, can probably be TASed quite well using only a bot. As Bisqwit said, having the bot use savestates makes things a whole lot easier, if the game is somewhat complex it would be quite a challenge to make a sophisticated bot that doesn't. Gameshow games can also easlily be TASed by bots (without using savestates) by looking into the game's memory what the answer is (I made a Jeopardy TAS like this some time ago), but admittedly they are of course very dull to watch. This topic also reminded me of the "Infinite Mario AI" youtube video: http://www.youtube.com/watch?v=DlkMs4ZHHr8
My own page on this site.
Posted: 2/9/2011 8:10 PM
Quote
Dada
Joined: 11/22/2004
Posts: 1468
Location: Rotterdam, The Netherlands
Warp wrote:
Mitjitsu wrote:
In relation to TASing you could certainly create intelligent AI that could TAS NES games which only have 256 possible inputs per frame.
It doesn't really matter how many buttons there are. Even if you had only one button and your only choice on each frame would be whether to press it or not, you would still end up having an exponential amount of possible combinations as the run progresses and it quickly becomes too numerous to calculate in a rational amount of time.
I once tried calculating how many possible input combinations there would be for the latest Mega Man run's amount of frames and the number was so big Google outright refused to give me the answer, even in scientific notation.
Posted: 2/9/2011 8:35 PM
Quote
Derakon
Joined: 7/2/2007
Posts: 3960
A few ad-hoc tests shows that Google won't return results much bigger than around 1.7 * 10^308, or about 2^1024. I guess they aren't willing to dedicate more than a kibibit to numeric accuracy.
Pyrel - an open-source rewrite of the Angband roguelike game in Python.
Posted: 2/10/2011 1:45 AM
Quote
Kuwaga
Joined: 10/20/2006
Posts: 1248
Has anybody on this planet ever tried to make a bot that actually somewhat emulates a human being playing a game? That is, not restrict the bot to some algorithm they've developed to beat the game, but to make the bot learn by itself through trial and error? It would be ridiculously difficult and probably take forever to program something like that, but I'd find it very exciting. F.e. in Super Mario Bros. the bot's goal could be defined as to increase Mario's x position. It'd learn the fastest method to do that and what in-game factors other than button presses have an impact on his position all by itself. Once a bot like that would be done, it should be able to play other games with slight modifications too. I know, there's probably nobody who wants to torture themselves so much as to actually write a bot like that, but I guess it'd be the only way to enable it to discover at least some of the glitches that normally only a brute-force approach would come across. It would require quite an impressive AI though.
Posted: 2/10/2011 5:39 AM
(Edited: 2/12/2011 5:21 PM)
Quote
Brandon
He/Him
Editor, Player (191)
Joined: 11/21/2010
Posts: 914
Location: Tennessee
All of these ideas are interested, but I'm only doing heuristics right now. My progress is pretty decent though; I got it to select the right mode (Requires a cheat code for Very Hard), and created a function that moves the cursor to the right location.
All the best, Brandon Evans
Posted: 2/10/2011 8:33 AM
Quote
Warp
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
MESHUGGAH wrote:
Brute force is the best solution to find the fastest completion input collection. Needless to say, the time needed for brute forcing a game is something like that: [2 ^ (Number of buttons * Actual TAS record frame count)] / Emulation time.
It's not that straightforward because even with brute force searching you can use clever algorithms to somewhat cut down the search tree, or at least prioritize branches which are more likely to give you a result. Also, in average it would take half of that time. The complexity class is correct, though (that is, O(2n).)
For example, the shortest movie is [1145] Genesis King's Bounty by gia & Aqfaq in 00:09.93 so brute forcing it would take at least 2^(9*596)/10 = 5,3075823547897896501038675241442e+1613 seconds.
<nitpick> Don't you mean "at most"? (And there's no need to specify that many decimals as they convey no useful information in this case. A 5.3*101613 would have sufficed to give a notion of the magnitude.) </nitpick>
Posted: 2/12/2011 9:56 AM
Quote
MESHUGGAH
Other
Skilled player (1917)
Joined: 11/14/2009
Posts: 1353
Location: 𝔐𝔞𝔤𝑦𝔞𝔯
NES TASer of 2013 NES TAS of 2013 NES TAS of 2012 NES TAS of 2011
Warp wrote:
It's not that straightforward because even with brute force searching you can use clever algorithms to somewhat cut down the search tree, or at least prioritize branches which are more likely to give you a result. Also, in average it would take half of that time. The complexity class is correct, though (that is, O(2n).)
I already thought and tried to come up with some clever ideas, but still the time needed to complete a game completely without human actions would take rather long. I tried to generate movie files by setting a "maximum number of inputs per frame", "enabled and disabled input combinations", "preferred inputs" (start generating movies with Left and A instead of Restart and Select), "memory investigation per frame", "possible end-game conditions". Of course it would be great for really really short movies, where everything is already known, and there are no obscure suprises. For example, I never thought that pressing the restart button warps me to the final 9th stage. However, I'm really curious that there are existing movies where possible odd thinking improvement exists like the one I mentioned before. I would rather write a program that analyses the structure of a game's source code and tries to find the shortest route to the final desired memory state.
Warp wrote:
<nitpick> Don't you mean "at most"? (And there's no need to specify that many decimals as they convey no useful information in this case. A 5.3*101613 would have sufficed to give a notion of the magnitude.) </nitpick>
You are right, I made a mistake. It's the "shortest longest time a brute force would take at 1000% emulation time" not considering other non-gameplay tasks (generating movie inputs, loading them, analyzing "possible end-game" results, etc). I just simply copied the result from windows calculator, I thought that people without proper math knowledge will fear recklessly if they have to read so many numbers after the other. edit: I failed to correct my mistake, amazing.
PhD in TASing 🎓 speedrun enthusiast ❤🚷🔥 white hat hacker ▓ black box tester ░ censorships and rules...
Posted: 2/12/2011 5:14 PM
Quote
Brandon
He/Him
Editor, Player (191)
Joined: 11/21/2010
Posts: 914
Location: Tennessee
MESHUGGAH wrote:
I would rather write a program that analyses the structure of a game's source code and tries to find the shortest route to the final desired memory state.
Although I'm primarily looking at creating heuristic algorithms to play these games (After all, that's probably the most interesting thing to look at from my point of view), this idea sounds interesting. That said, where would you acquire the source code for a specific ROM? As I've mentioned, I'm quite new, and I didn't think finding such source would be possible, and I truly doubt the language Nintendo used back in those days looks as nice as Lua or Python. Still, I'd definitely be interested in studying the source in an attempt to write these heuristic algorithms.
All the best, Brandon Evans
Posted: 2/12/2011 6:11 PM
Quote
MESHUGGAH
Other
Skilled player (1917)
Joined: 11/14/2009
Posts: 1353
Location: 𝔐𝔞𝔤𝑦𝔞𝔯
NES TASer of 2013 NES TAS of 2013 NES TAS of 2012 NES TAS of 2011
Brandon wrote:
That said, where would you acquire the source code for a specific ROM?
Depends on ROMs, but mostly you will have to disassemble them with a debugger. It's a very tedious and long task and also it's illegal, I don't know what's the situation with old games' ROMs copyright issues. Don't forget that even if you get the source code* (after spending many days), you will be still nowhere. Source codes are long, "obfuscated" and it isn't easy for human beings to read it. However, I think that this way has some advantages over the "trying all the possible combinations". (mostly the time factor as I mentioned earlier in this thread). And also, making an algorithm to find the shortest route to the final desired memory state... The idea is okay, but it's much harder than it looks/sounds. I will investigate it further later. I mostly choose the "read the source code (even if it's outdated)" method, cause they are something like a technical document and you can come up with new glitches and techniques. I already found many funny glitches for mobile games (.JAR files, you can simply open it as .zip, decompile them automatically (with the proper programs), and read it obfuscated), just like playing on custom resolutions leads to unexpected results. Not to mention PC games, I know very much glitches for Counter-strike because I already investigated Quake and HL source code (the engines based on... off topic). Links you should visit: http://en.wikipedia.org/wiki/Disassembler http://bisqwit.iki.fi/jutut/megamansource/ http://eludevisibility.org/spacy-funky-bob-source-code/ http://www.zophar.net/utilities/development.html *: The code that you decompiled. Of course, the original source codes are not obfuscated, and easily readable.
PhD in TASing 🎓 speedrun enthusiast ❤🚷🔥 white hat hacker ▓ black box tester ░ censorships and rules...
1 2