Posted: 12/29/2008 6:10 AM
Post subject: Game-specific LUA AI discussion
Quote
Ramzi
Joined: 3/25/2004
Posts: 459
I started reading about LUA scripting today. Although I don't know how to program in it, it's availability made me think about the reality or difficulty of creating AI for certain games. I think, perhaps, there has been little discussion of LUA (as far as I noticed in doing a quick forum search for it), and I think, maybe, if we kept a catalog of all scripts for specific games, this could aid TAS developers in the future, particularly those who could use the scripts, but do not know how to develop them. But providing sample code could help the aspiring programmer, such as just providing x/y coordinates of the main character or bad guys, or something general like that. Then more-specific functions can be developed by the TAS maker. I thought of two bot ideas. Zelda 1: Perform an exhaustive path search. (Depth or breadth, doesn't matter, but allowing cycles.) So, from the starting location, there are 4 options. Left, Up, Inside, Right. Make the respective goal-state be whatever let's Link reach the end of the screen. Hard-code the level conditions in, (that is, for example, Level 5 MUST BE entered and completed before Level 7. Although this isn't necessarily true, it is a basic assumption of the Zelda 1 first question, that in a TAS one should not enter and exit a temple before completing it.) If one level is entered that violates a condition, then that path can be successfully pruned. Level stategy, likewise, is exhaustive search. Except, only "completing a room," when "necessary." The "necessary" conditions will be: the room contains a key, the room contains a movable block, or a door will open by defeating all the enemies on the level. Let Link's fighting strategy use the sword, as opposed to an intelligent combination of multiple weapons, requiring that he be a tile-distance away from an enemy linearly from the direction he is facing. Value the current gamestate by some function consisting of Link's health, total enemy health if it is a "necessary" room, and distance away from the goal state. So, two states with the same amount of health and bad guys, but different distances from the door, values the one closer to the door as higher. Continuing this heuristic could allow intelligent pruning. I think this should be sufficient to beat the game, even if many specific rules need to be hardcoded, such as, "play the flute at the location with the Level 7 pond," "shoot the level 6 bad guy with the arrow," "burn the tree to level 8 if on that screen," and, "bomb this location to enter level 9." Levels 1, 2, 3, 4, 5, and 6 should be found naturally through the exhaustive search. Pac-Man: This game essentially invokes the same principles as the Zelda ones I just mentioned, although they are seemingly simpler. Perhaps I should have listed it first, but I wanted to type my ideas true to the order in which I had thought them. Anyway, do not look at Pac-Man routes as pixel by pixel decisions, but rather as intersection by intersection decisions. Suppose you're at an intersection where you were going left, and could continue left, turn up, or turn down. Simply try all three, and create the branches. If contact with a ghost is made (not during time of the power pellet effects) then stop pursuing that branch. I think this should be sufficient to beat the game.
Posted: 12/29/2008 5:19 PM
Quote
Derakon
Joined: 7/2/2007
Posts: 3960
Keep in mind that brute-forcing games is very inefficient. In your Zelda example, let's say that it takes at minimum 15 presses of left/up to get to the old man with the sword. That means that at bare minimum you will be evaluating 4^15 = 1073741824 possible variations (minus variants that are duplicates of ones you've checked before) before reaching your first goal. Basically, any approach that boils down to "exhaustive search" isn't feasible yet and probably never will be. We have to be smarter in our use of bots, or else give them much more limited goals that span only a handful of frames so that we can manually check in and lock down the search tree. I think something like this was done for the Cutman spaz-out section in the current Rockman TAS.
Pyrel - an open-source rewrite of the Angband roguelike game in Python.
Posted: 12/29/2008 7:26 PM
Quote
alden
Player (121)
Joined: 2/11/2007
Posts: 1522
I think a Lua repository would be nice too, and if I weren't so lazy I'd probably make one myself :P OK maybe someday I will :) There are a lot of sweet scripts scattered around the forums...
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: 12/29/2008 7:31 PM
Quote
Xkeeper
Banned User
Joined: 12/23/2004
Posts: 1850
I've been considering a Lua repository for myself, but I could actually go do it for you guys if you wanted.
Perma-banned
Posted: 12/29/2008 9:21 PM
Quote
Derakon
Joined: 7/2/2007
Posts: 3960
If we're going to have a repository, it should probably be under source control (CVS or SVN). In fact, how hard would it be to have a Sourceforge project for this?
Pyrel - an open-source rewrite of the Angband roguelike game in Python.
Posted: 12/29/2008 10:36 PM
Quote
ZeXr0
Joined: 8/27/2006
Posts: 883
Or a google code project
Posted: 12/30/2008 2:17 AM
Quote
Ramzi
Joined: 3/25/2004
Posts: 459
Derakon wrote:
Keep in mind that brute-forcing games is very inefficient. In your Zelda example, let's say that it takes at minimum 15 presses of left/up to get to the old man with the sword. That means that at bare minimum you will be evaluating 4^15 = 1073741824 possible variations (minus variants that are duplicates of ones you've checked before) before reaching your first goal. Basically, any approach that boils down to "exhaustive search" isn't feasible yet and probably never will be.
Hmm... I almost feel dumb for having posted it in the first place. I know it's been mentioned so many times already. Just sometimes it feels more plausible than other times. Suppose we hardcode the overworld route into the bot, an exhaustive search for dungeons would be feasible, wouldn't it? Rather than doing the exhaustive search, say, depth first, why not do it breadth first, and use each completion time of the game as a measuring stick for the next branch. So we won't claim that we have found the fastest route, just the fastest route thus far.
Posted: 12/30/2008 3:35 AM
Quote
Dromiceius
Joined: 10/3/2005
Posts: 1332
Ramzi wrote:
Hmm... I almost feel dumb for having posted it in the first place. I know it's been mentioned so many times already. Just sometimes it feels more plausible than other times. Suppose we hardcode the overworld route into the bot, an exhaustive search for dungeons would be feasible, wouldn't it?
Gunty has actually applied quite a few smaller scale Lua scripts to his latest Lufia II WIPs. I think automating a few small, especially tedious input sequences is the more practical way of botting, rather than having a bot TAS the game for you... which is actually what I've been doing with The 7th Saga. :D It's true that brute forcing large problems is impracticable, but I've found that genetic algorithms work reasonably well at solving difficult problems. For example, my bot is designed to solve battles to find the shortest tree of attack/defend/item decisions, and uses a genetic algorithm instead of exhausting the entire space, because the entire problem space is potentially infinite! Applying the same technique to everything, solving an entire game via Lua is actually less conceptually difficult than I'd imagined; all you have to do is isolate all the types of operation that the bot needs to do, and "atomize" them as functions. Smaller functions coalesce into larger functions, which are then looped to test different inputs and/or randomness. The hard part is accounting for irregularity in the game. Like when your "enemyHP" memory address fails for one particular boss halfway into the game. The harder it is to model the behavior of the game you want to TAS, the more work you have to put into writing an all-inclusive set of automations. Ultimately, writing very general bots is exponentially more difficult than writing small bots, but still practicable if you're willing to do a lot of testing, and write a lot of tedious code for a lot of special cases. ...Also, I should disclaim this little rant as being the sum of what I've observed so far, and that I haven't produced anything of actual value yet.
Posted: 1/22/2009 3:19 AM
Quote
DarkKobold
Skilled player (1652)
Joined: 11/15/2004
Posts: 2202
Location: Killjoy
Arcade TASer of 2010 PCE TASer of 2010 Arcade TAS of 2010 Lucky TAS of 2009 Lucky TAS of 2007
Dromicieus: Can you talk more about genetic algorithms? Like, how to implement them in LUA?
Sage advice from a friend of Jim: So put your tinfoil hat back in the closet, open your eyes to the truth, and realize that the government is in fact causing austismal cancer with it's 9/11 fluoride vaccinations of your water supply.
Posted: 1/22/2009 4:51 AM
Quote
Dromiceius
Joined: 10/3/2005
Posts: 1332
The basic process is as follows: Battle begins; the bot creates a savestate. It's the player's turn. The bot needs to decide what input to generate, and it does this by referring to a table of strings representing either inputs or discrete menu decisions, or whatever the situation dictates. Of course, the table is empty at first, so it just does shit at random. The battle proceeds until either the player or the enemy is dead. The bot then assesses the outcome, measuring frames taken to complete the battle, or whatever user-defined desirable state it has to work with. Now, throughout the battle, the bot keeps a record of the inputs it's generating. Having also quantified the outcome produced by these inputs, it inserts the input sequence into the input table where the index at which it is inserted is defined by the relative fitness of the battle's outcome. The first iteration is now complete. The bot reloads the initial savestate, and fights again. This time, the bot will loop downward through the list of input sequences it has already tried, starting with the best one, and randomly picks one to mutate. Since these inputs are already sorted by fitness, it has the highest probability of picking the most sane sequence, and mutating it into something hopefully more refined, and indeed, hopefully frame perfect. PS. I'm not completely lucid right now, so I hope that all made sense. edit: Oh, you asked about implementation in Lua. Here's an old version of the 7th Saga bot for your perusal. It's so awful, I decided a rewrite was in order, so take whatever you see in there with a grain of salt.