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.
