I don't think there's a way for the computer to know what the outcome of game would be in the future so it would have to 'go' through it countless number of times. Changing 1 frame at a time because it doesn't know how nonsensical the route it could be taking is.. and how would it stop and try again?
No PC could do this
You can also argue that no player can know what their actions will yield when playing a game. The only way one does is by observing the outcomes of previous actions, observing their surroundings, and making intelligent decisions based on their observations. There is no reason why a computer can't do those things; all of the information you need is coded somewhere in the game.
http://www.robocup.org/
Here people program robots to play soccer; if that can be done, then a program surely can make intelligent decisions in a game.
Now I'm not smart enough to make a hal 9000, but this won't be brain dead at the very least.
nitsuja wrote:
"updating some memory addresses" is actually much more difficult than adding those functions to each emulator. Mainly because he does not really know where those addresses are (except where they happen to be at the time on his computer), and because providing input at the correct speed by editing the emulator's memory while it's running would be nearly impossible and would need to be re-written per emulator. It would be easier to make a universal interface for the emulators to "plug in" to.
I agree. I don't know enough about the emulators to send input by modifying their memory. I think to send input to the nes you have to strobe a bit at an address somewhere, set some register, and then rotate it a bunch of times. I just wanted to use the memory reading functions to check values in the ram. I was trying for a solution similar to how game trainers work. Sending input is where I am still stuck. I know windows has functions to send keys to a process, but I really would like to find a better way, and still not modify source code.
Another plus to not modifying the emulator source code is that this program could work with future releases of emulators, you would just have to update some offsets.
Humans can make intelligent decision independently, a program can not. A computer could take a better route based on what happened before, but it would have to be game specific for sure.
I know windows has functions to send keys to a process, but I really would like to find a better way, and still not modify source code.
I doubt you'll find anything closer to what you're looking for (for Windows) than the SendInput function. That won't work for some cases though (for instance, if the emulator uses DirectInput to check keys).
What about the problem of synchronizing with the emulation? You could make it use frame advance to control how many frames go by, but this is sounding extremely inefficient, for minimal benefit...
L4yer wrote:
Humans can make intelligent decision independently, a program can not.
Not to go into too much detail, since that's not the point of this discussion, but that's highly debatable...
I don't think there's a way for the computer to know what the outcome of game would be in the future so it would have to 'go' through it countless number of times. Changing 1 frame at a time because it doesn't know how nonsensical the route it could be taking is.. and how would it stop and try again?
This sounds like a great job for an evolution program.
Trying 127.0.0.1...
telnet: connect to address 127.0.0.1: Connection refused
telnet: Unable to connect to remote host
I think that the most practical way about it would be to design an interface between your general TAS engine and the different emulators. You could have commands to send keys, load state, save state, etc. That way you could have the same program talk to the different emulators, while still keeping it separate. It would still require a lot of tweaking source code, but not as much as building-in the bot.
Yeah, like nitsuja has been saying all along, there is no getting around modifying the emulator source. The solution I found as of now is to have the emulator communicate with the bot by sending it a message every time it needs to update the input. The bot can then reply with what ever instructions it needs to send the emulator. I tested it with fceu and so far it seems to be working fine. Now it's just a matter of figuring how to implement all of the features that I would want.
Joined: 4/25/2004
Posts: 615
Location: The Netherlands
Hm, seems I've missed this topic.
I just released a new version that improves the Basic Bot code by Luke for FCEU.
Just for the record; even though writing a universal bot for any game is not a task to be taken lightly, I think the Basic Bot design shows it's not infeasible.
Jus for another record; it is indeed impossible to try every possible route for a game from beginning to end. Even on the NES with "only" 8 buttons, the number of possibles are extremely high. No computer can currently compute that, I wonder if ever.
That said, these bots are not entirely useless in this field. Bots will try anything you wouldn't. Sometimes making a stupid move is faster. Also, there are several machine learning algo's you might wanna take a look at. I've got a lot planned for FCEU.
As for a standalone application, can't help you much there. Faking keyboard input sounds like the best shot to me since memory addresses can change with every update. You can also design a general principle and implement it in the popular opensource emulators yourself. This task should not be too hard, once decided on the principles.
As for FCEU, I'm planning on expanding the current "scripting language" (that's what it is really). I want the parser to turn the code into bytecode, to be fed to a interpreter. This should increase performance greatly (as it's currently just parsing the string over and over again ==== slow!)
When that's done I plan on implementing some basic machine learning algo's. Clustering, evolutionary algo's, pathfinding algo's, stuff like that.
The main idea I have right now is to let the bot try for x frames, x times. Each time advancing x/2 ahead. This will cause to get a quick optimization for short area's combined.
Another thing I want to try is to have it a range of values for some variable. Try x times, and pick out the value that scored best. Then keep trying this number and repeat the idea on another variable. This way you should be able to get a local peak rather fast.
Combine the both two methods and I think you can relatively easy get a run computed. Note that this does mean you need to know what certain rom addresses are. Keep in mind that for the bot, you're just messing around with numbers.
Joined: 2/15/2005
Posts: 246
Location: Torquay, England
Here's my idea: You set a goal for the bot. You also set a time for it to accomplish the goal in, which should be what the current record time is. You can tell it not to use certain buttons (e.g. up and start) and to treat others as the same (A = B = C). This distinction is important because if two or more buttons do the same thing, you can do that thing on two consecutive frames.
If the goal can be accomplished in a short time, this could be very useful. If the goal takes a while (e.g. complete a level), split it into shorter goals (e.g. reach a certain place in the level).
Joined: 4/25/2004
Posts: 615
Location: The Netherlands
And that EXACTLY what basic bot does and is going to do.
It already can do the button stuff, press or not press buttons or whatever.
It is going to be able to compute a part (x frames) so many times, take the best result, then move ahead x/2 frames and start over.
That's the main idea at least, and I think it will perform rather well, asuming you've coded your bot correctly :)
Sounds perfectly fine for me. It would certainly be useful for optimising paths.
In theory, it sounds like it should work, but we know that theory goes out the window in real life.
Any predictions on what a "short time" would be. With Bisqbot, I think it was more like a few 10s of frames took overnight to compute, and even Bisqbot was no means an exhaustive search.
Argh, I'm not talking about an exhaustive search. Say you have an isometric view and you want to move from A to B, talking to P along the way. It could easily find the best times to turn around corners etc. That does not have an overly high amount of possibilities.
Joined: 11/22/2004
Posts: 1468
Location: Rotterdam, The Netherlands
Funny you guys should mention it like this. It reminds me of the "brute force versus strategy" discussion in regards to computer chess. For long, it was believed that brute force would be completely impractical, and that strategic decisions were the best way of creating a viable computer opponent.
Of course, as you can see, it was brute force that won in the end.
Perhaps this sort of computing power will be available in the future!
Joined: 4/25/2004
Posts: 615
Location: The Netherlands
Maybe. But it has to be said that chess isn't a big game. Sure, we perceive it as "endless possibilities", but in the end it's nothing compared to games like GO, for which there is not enough time and space to brute force solve it.
Joined: 11/22/2004
Posts: 1468
Location: Rotterdam, The Netherlands
That is true. But eventually, Go might be solved as well. The ways they use for calculating when the processing power will be sufficient enough in order to do definitely holds no certainty, because it assumes no new inventions in the field of computing will be brought.
