Donkey Kong Forum
General Donkey Kong Discussion => General Donkey Kong Discussion => Topic started by: marinomitch13 on April 14, 2013, 07:55:54 pm
-
I just saw this video where a programmer makes a program that can play NES games: http://techcrunch.com/2013/04/14/nes-robot/ (http://techcrunch.com/2013/04/14/nes-robot/)
I was just wondering if a similar program of this could be made to play DK. I'm not super good at computer programming. I know the basics of some languages, but it would take me a while to get up to par to do something like this. However, I have a past of programming quite a lot of my own games and math functions on calculators back in high school, so maybe I'll eventually be able to attempt this. Ever since I started playing DK, I always longed to see someone do this. My question is: Does anyone on this forum think they could pull something like this off without too much difficulty?
This program could end up being very useful. I think once a basic program is made that could run boards, it would be very fun to experiment with different pressing techniques. You could just let the program run over and over and keep track of points vs deaths (i.e. the actual risk/reward involved -assuming the program actually plays the situations well). Eventually it could be fine-tuned for the best overall strategy(s). Lots of other ways a program like this could be helpful could be listed, but you get the picture.
-
I'm not sure what language would need to be used but I would enjoy tackling this problem. Good find on the video and thanks for posting it! Very cool.
-
Jeff Willms once told me that it would probably best be done on mame with some language that he mentioned (I can't remember what it is called!). Otherwise, for arcade, it would probably have to be done with utilizing z-80 at some point.
-
I know that you can script stuff in MAME with Lua but I'm not sure how to read the data in a way that makes the computer iteratively better like the PhD did in the video.
-
Interesting idea. I'll have a very quick shot tonight at writing something. As far as I know all you would need is a program that is capable of sending keystrokes which is easy, capturing the screen is easy enough too but as for writing the code that interprets what is on the screen and then having jumpman act accordingly would be a hell of a job.
There are several programming competitions run, one is a competition where programmers pit their programming efforts against each other in Texas Hold'em. That is a massive thing to try and do and I'd be guessing that teaching a computer to play DK would be an even harder thing to do.
To do it successfully you'd need to be a very capable DK player (which I am not), so you'd need someone like Hank, Vincent or Dean (or any number of you guys on here) to play a game and then put into pseudo code (plain English) exactly what the thought process is as you play a level - given that the best players are analyzing lots of stuff at the same time and changing their decisions on the fly it would be a very difficult thing to do.
To complete even one board will be difficult, the springs of course would be the easiest (if that's possible) to do.
-
I'm thinking there are two main ways this program could be set up:
1) A more 'reactive' program. In this method, screen capture is somehow incorporated. An added problem with this approach is dealing with any lag/delay. It may actually be an insurmountable challenge, however, the languages needed to do this type of programming are more common.
2) A method that incorporates the actual physical measurements of the game (speeds of objects, lengths of girders, heights of jumps/ledges) and is tapped into the actual changing RNGs that govern the random elements of the game, so that the program 'knows' what is happening just as instantaneously as it happens. This is probably the more viable method, IMHO, but it would likely require learning an additional, particularly uncommon coding language. Also, this program would likely have a greater potential to be programmed to play the game superbly (possibly even close to the theoretical max of any particular game's actual randomness -assuming the program could also predict the actual deterministic relationship between its inputs and how it affects/will affect the RNG outputs in the future -like knowing when a fireball will turn around or climb)
For both methods, as you suggested, John, there will have to be a lot of compiling of nested If-Then relationships that basically comprise/mimic what is actually going on in a player's head when they are playing the game. This would be a lot of work, but for me -someone who loves trying to parse out all the rules and principles that go into playing games- this would actually be the fun part (p.s. If anyone actually takes up this challenge, I would love to try to help with this part if you gave me screen shots of situations where the program did the wrong thing and caused Jumpman to die)! It would really fun, in my opinion, to constantly be upgrading a program by making the governing gameplay principles more precise. It would be fun/funny to be testing the program and have to run it and see how it messes up. For basic cases, the missing principles would be obvious to figure out and therefore easy to troubleshoot. However, complicated situations would require a lot of subtlety in the code, which, again, would be fun (IMHO) to tinker with.
-
It would certainly be an interesting exercise. I'll let you know if I get anywhere tonight, just going to get the program to control DK to start with, won't worry about too much logic at this stage. I don't program very much these days, so that will be enough for one nights effort.
Who knows, maybe this will take off and at the 2014 Kong Off there will be a Mame PC setup up for the program to play alongside the 20+ best DK players.
If there is one thing the computer program will do, it will be able to play the perfect (never dying) L4+ spring stage :) That only leaves what, about 110 other boards to worry about lol
-
Looking forward to progress on this.
I'll finally be able to go do other things while the computer plays my Donkey Kong games for me.
-
I guess if mame allways starts at the same spot you would just need 1 set of recorded moves from the coin drop onwards. Everything would be much the same just keep modifying till it makes the kill screen, Kinda just like making an inp file. But to say write a program that could play through running the different ways with different coin drop times and and 1 player start times to get a game that will give the opertunity to crack a massive score. That would be interesting imagine knowing that you had to drop a coin 7.36 sec after the rom starts and then wait 22.76 sec to press start to even have a chance at getting the record :)
Or maby I'm just rambling.
-
It would certainly be an interesting project for someone, even though I'm a little more skeptical about programming the intelligence to play at the level we are playing now. I think it would be an accomplishment to have someone program something that could at least finish levels without dying. Something about installing all the intelligence to handle all barrel situations, mainly the one's that can't be jumped. Also, fireball avoidance on rivets, the decision making involved there. But it would be interesting to see.
-
Well, in the original article linked, the program not only played Mario, but "learned" as it played. So, AI involved. This is different than just writing a program to play through Donkey Kong.
Writing a program to play through Donkey Kong would be a really fun project to work on. If only I had the time for another project :)
Heck, I would consider it a feat to write some code to successfully play through 1-1 on its own.
There is a competition (in Java) for the Super Mario games, to see who can develop a program to play through that game: http://julian.togelius.com/mariocompetition2009/index.php (http://julian.togelius.com/mariocompetition2009/index.php)
I could see somebody doing this for Donkey Kong. I wonder if there is a Java port of the game out there that is available for downloading?
-
I'm among the top DK players, and I am a computer programmer by profession. Furthermore, my primary role at my job is in automation, where I write software that mimics user actions (launching programs, entering keyboard inputs, mouse clicks, etc.). The scripting software I write pilots software in development, and navigates different end-to-end paths based on sometimes planned, and sometimes random choices -- it's even capable of making reactionary choices by searching for objects presented on the screen and acting accordingly. In a sentence, I manage a team of software "robots" that do my job faster and more accurately than I ever could, and they do it without experiencing fatigue.
My co-workers know about my DK hobby, and the question has come up many times before: "So why don't you make one of your robots play Donkey Kong?"
I never want to truly start the conversation where I explain the challenges involved in such an undertaking, so I always just laugh saying "Haha, wouldn't that be something!?"
The truth is, that guy from KOK had it right: "If you could hack into the machine and program it to play itself, you couldn't even program it that well."
I'm confident that a DK playing program is "vaporware." That is to say, it's an idea that could never be correctly implemented.
I say all of this because I run into similar issues at work all the time. The client's understanding of how the automation should work, and a programmer's understanding of how the automation actually does work, is fundamentally different. From one person's perspective, the question is "Couldn't you just... make it work?" From the other person's perspective, the question is "How do I handle every possibility?" The program will only do exactly what you teach it to do.
To offer an example, consider the barrel board.
We know that to some degree you can influence the behavior of the barrels, and sometimes steer them down ladders.
Consequently, when you're playing, even though Jumpman is what you're controlling primarily, your focus is on the screen as a whole. You're anticipating barrels as they cross over ladders, because you might want to steer them down for better/easier groupings, or you may want to steer them down to keep them away from you. Of similar concept, there are times when you will want to return the controls to a "neutral" position so the barrels have a greater chance of continuing across the ladder without coming down it. These decisions occur while you're controlling Jumpman to progress up the screen without dying, while maximizing opportunities to score points.
On a fully populated barrels screen, your program is tasked with tracking 7-8 barrels. In some situations, you begin tracking fewer barrels as Jumpman proceeds up the screen, because at some point a barrel "becomes dead" as it has no more influence on your score. It's difficult to always determine the circumstances as to what makes a dead barrel, because if you're moving down ladders, a barrel that has passed you still has potential for earning more points.
From a programming perspective, you'd have to store the color of barrel (brown, blue), their x,y position, and type (first thrown (predictable), first rolled (can't be controlled), normal (can be controlled), wild (multiple types), bomb). Tracking them would be challenging, because they have different frames of animation, look different when they're grouped on top of each other, and effectively change sprites when they are on the ladder. If a barrel falls off a platform edge, they have a slight bounce to them, meaning that you couldn't necessarily use a static image to track at all times relative to the top pixel of a girder.
When barrels roll through fireballs, the fireball sprite overwrites the barrel sprites. When you jump over a barrel or a group of barrels, the points awarded sprite appears beneath Jumpman at the peak of his jump, often overwriting part of the barrel sprites. Again, using static images, or isolated pixels that are used to track the barrels, turns into a nightmare.
Tracking the fireballs present similar challenges, since fireballs have flippable sprites, that have a slight bounce as they move, and change color when the hammer is held.
Even Jumpman himself is challenging to track, due to his multiple conditions and corresponding sprites: Facing right with no arms showing. Facing left with no arms showing. Facing right with arms showing. Facing left with arms showing. Jumping straight up facing left. Jumping straight up facing right. Jumping left facing left. Jumping left facing right. Jumping right facing right. Jumping right facing right. On the ladder with one foot on a rung. On the ladder sticking your butt out. At the top or bottom of a ladder with both feet on the ground, facing away from the user. With hammer and hammer is on upswing, with hammer and hammer is on downswing. With expiring hammer and hammer is on upswing, with expiring hammer and hammer is on downswing. Landed from a high jump and survived. The death animation.
Most of the Jumpman sprites have the potential to partially touch obstacles (girders, fireballs, barrels) without dying. The Jumpman sprite overwrites girders, while the fireballs and barrels overwrite him.
... I could continue delving into the subject, but I'm not sure it's worth it. When Jeff W came out with his Pauline tool, a companion tool to MAME that tracks your DK pace, I was impressed. As a programmer, I could see the behavior of his tool and understand how he made it. The screen objects that Pauline detects are in fixed positions, to read the score, the current level, and type of level. He put in additional logic to detect if you died, and calculated the pace appropriately. It was awesome.
Now, Jeff's tool is relatively simple compared to the "DK Autopilot" you're suggesting now, but I'm certain that even Jeff's tool had its challenges.
What it really comes down to is that there are two camps. People who understand programming, and people who understand Donkey Kong. People at my work are in the first camp, people on this forum are in the second camp, and a select few belong to both.
I may possess the correct combination of DK understanding and programming experience to attempt this task, but I won't. I believe it is actually easier to beat the DK world record manually, than try to create a program to do it for me. The first challenge is challenge enough. The second challenge is much more work, and a lot less fun.
-
All that said, cool video on gaming AI. If someone can apply the same concepts to DK, and/or take the holistic approach to try and handle every situation possible rather than attempt to make AI learn it, then more power to them. All of my respect to whoever can have success at this.
-
All that said, cool video on gaming AI. If someone can apply the same concepts to DK, and/or take the holistic approach to try and handle every situation possible rather than attempt to make AI learn it, then more power to them. All of my respect to whoever can have success at this.
I agree this would be a bear to write. However, the op said "..a basic program is made that could run boards..." not break the record. Still tough, but probably could be done. I don't think there would be a way to write a program in which Jumpman would killscreen every time, but you could write a program in which you run it countless times he eventually makes it to the end.
-
To write a DK AI you will almost definitely want to use lua scripting with the emulator mame-rr (http://code.google.com/p/mame-rr/) (or any other emulator that has similar scripting capabilities). Bascially, mame-rr allows you to write a lua script to execute alongside a game. This script can be programmed to do things such as executing code every frame, reading any value from RAM, sending controller input to use for a particular frame, etc. This avoids having to do any image/screen shot interpretation, ]which would be a total mess to implement, and instead allows you to read all information directly from RAM.
The only downside of this approach is that you might have to write your entire AI in lua. However, there are probably ways around this in which you could write the AI in any language you want. For example, you could write a program in any language and then make the lua script connect to this program and every frame it could send the entire contents of RAM to your program. The program would then use the AI logic to determine which inputs should be used on that frame and would send back the inputs, which the lua script would then use as input for that particular frame. Of course this requires a whole bunch of additional work over just writing the AI in lua.
-
That is interesting Jeffw.
Do you have any links to examples of controlling a game in an editor with lua? I did find the lua manual:
http://www.lua.org/manual/5.1/ (http://www.lua.org/manual/5.1/)
To write a DK AI you will almost definitely want to use lua scripting with the emulator mame-rr (http://code.google.com/p/mame-rr/) (or any other emulator that has similar scripting capabilities). Bascially, mame-rr allows you to write a lua script to execute alongside a game. This script can be programmed to do things such as executing code every frame, reading any value from RAM, sending controller input to use for a particular frame, etc. This avoids having to do any image/screen shot interpretation, ]which would be a total mess to implement, and instead allows you to read all information directly from RAM.
The only downside of this approach is that you might have to write your entire AI in lua. However, there are probably ways around this in which you could write the AI in any language you want. For example, you could write a program in any language and then make the lua script connect to this program and every frame it could send the entire contents of RAM to your program. The program would then use the AI logic to determine which inputs should be used on that frame and would send back the inputs, which the lua script would then use as input for that particular frame. Of course this requires a whole bunch of additional work over just writing the AI in lua.
-
To write a DK AI you will almost definitely want to use lua scripting with the emulator mame-rr (or any other emulator that has similar scripting capabilities). Bascially, mame-rr allows you to write a lua script to execute alongside a game. This script can be programmed to do things such as executing code every frame, reading any value from RAM, sending controller input to use for a particular frame, etc. This avoids having to do any image/screen shot interpretation, ]which would be a total mess to implement, and instead allows you to read all information directly from RAM.
The only downside of this approach is that you might have to write your entire AI in lua. However, there are probably ways around this in which you could write the AI in any language you want. For example, you could write a program in any language and then make the lua script connect to this program and every frame it could send the entire contents of RAM to your program. The program would then use the AI logic to determine which inputs should be used on that frame and would send back the inputs, which the lua script would then use as input for that particular frame. Of course this requires a whole bunch of additional work over just writing the AI in lua.
I totally agree Jeff, I would've said the same thing!... lol.
-
That is interesting Jeffw.
Do you have any links to examples of controlling a game in an editor with lua? I did find the lua manual:
http://www.lua.org/manual/5.1/ (http://www.lua.org/manual/5.1/)
I've attached an example lua script I wrote a while back that tests for bias in the random number generator (RAM value 0x6018). Specifically, it tests if even random numbers are as likely as odd random numbers, and also if the previous random number being even vs odd affects the probability that the next one is even vs odd. I never found any bias with this script. When running the script a test is started by pressing 1 and stopped by pressing 2, at which point it will display the statistics it computed. Keep in mind I know hardly anything about lua programming and was mainly concerned with writing something that worked rather than making sure I was following good practices.
For the case of a DK AI instead of recording statistics on the value of the RNG each frame like this script does you will want to set the input using the joypad.set() function. A complete list of functions provided by mame-rr can be found here: http://code.google.com/p/mame-rr/wiki/LuaScriptingFunctions (http://code.google.com/p/mame-rr/wiki/LuaScriptingFunctions)
In order to make the AI move in response to what is happening on the board, you will need to read values from RAM. Here are some useful RAM values that could help get you started. All values are in hexadecimal.
0x6203 - Mario's X position
0x6205 - Mario's Y position
0x6700 is the start of the barrel array. Each barrel has a 0x20 byte range in which information for that barrel is stored. So for example barrel 1 info is in 6700 to 671F, barrel 2 info is in 6720 to 673F, etc. Here are some offsets from a barrel's range starting point that contain some useful info:
offset 00 - barrel status indicator (value 00 means inactive, 01 means active, 02 means it's being deployed)
offset 01 - wild barrel indicator (value 00 for normal and 01 for wild barrel)
offset 03 - barrel x position
offset 05 - barrel y position
0x6400 is that start of the fire array. Like the barrel array each fireball/firefox has a 0x20 byte range. Here are some useful offsets:
offset 00 - fire status (value 00 means inactive, 01 means active)
offset 03 - fire x position
offset 05 - fire y position
If you guys want, I can see if I can release a full RAM map with the meaning of a whole bunch of other RAM values. You can always try to find out what other RAM values, such as other offsets in the fire/barrel array, do by observing their values using RAM watch as you play.
-
Interesting idea. I'll have a very quick shot tonight at writing something. As far as I know all you would need is a program that is capable of sending keystrokes which is easy, capturing the screen is easy enough too but as for writing the code that interprets what is on the screen and then having jumpman act accordingly would be a hell of a job.
There are several programming competitions run, one is a competition where programmers pit their programming efforts against each other in Texas Hold'em. That is a massive thing to try and do and I'd be guessing that teaching a computer to play DK would be an even harder thing to do.
To do it successfully you'd need to be a very capable DK player (which I am not), so you'd need someone like Hank, Vincent or Dean (or any number of you guys on here) to play a game and then put into pseudo code (plain English) exactly what the thought process is as you play a level - given that the best players are analyzing lots of stuff at the same time and changing their decisions on the fly it would be a very difficult thing to do.
Capturing the screen is entirely unnecessary as the screen output is only there so humans know what they're supposed to do. You can ignore this and instead read everything from memory. Playing hold 'em well is exponentially harder than an undertaking like this, since it has to react to another player as well as act on imperfect information while also determining the proper adherence or divergence from game theoretic optimal play.
The last paragraph shows a fundamental misunderstanding of the initial problem - you don't need to copy a good player's inputs nor to actually attempt to copy all the things that a top-level player simultaneously thinks about, to do so would be impossible. Instead the program should focus on maximizing something like points, or even easier - bonus score. The best application of this type of program would be in a speedrun format where it just plays as fast as possible to get to a killscreen.
-
Do you have any links to examples of controlling a game in an editor with lua? I did find the lua manual:
http://www.lua.org/manual/5.1/ (http://www.lua.org/manual/5.1/)
http://forums.shoryuken.com/discussion/133401/trust (http://forums.shoryuken.com/discussion/133401/trust) is an example of controlling some aspects of Super Street Fighter II Turbo.
-
The last paragraph shows a fundamental misunderstanding of the initial problem - you don't need to copy a good player's inputs nor to actually attempt to copy all the things that a top-level player simultaneously thinks about, to do so would be impossible. Instead the program should focus on maximizing something like points, or even easier - bonus score. The best application of this type of program would be in a speedrun format where it just plays as fast as possible to get to a killscreen.
We'll have to agree to disagree. I know some of my fundamental problems when playing DK which is why my best score is only mid 200's and no matter how hard a practice, I can not get my brain to think several steps ahead (i.e. Barrel screens). I still see stuff done when watching events like the Wildcard event that I new even knew existed in the game which is why I think you would need a high level of expertise/input to make this work.
I do agree that a speed run would be the best approach, but given that you could even get the speed run to work, then it would be a matter of building up the rule base to increase score, point press.
Anyway, I'll have a bit more of a look around at some of the links guys have posted. Not saying I can or could do this, but I find the idea interesting.
Also agree over the screen capture, but then it really just comes down to you want to solve the problem. I guess you would have two very different types of programs, one which uses data (which is not how a human player plays - well they convert the visual image into data for their brain I guess) and the other would be using capturing visual information and interpreting what to do, which is what a human does when playing.
-
Thanks for this. I'm excited to dig in and see what I can tinker with.
Paul
That is interesting Jeffw.
Do you have any links to examples of controlling a game in an editor with lua? I did find the lua manual:
http://www.lua.org/manual/5.1/ (http://www.lua.org/manual/5.1/)
I've attached an example lua script I wrote a while back that tests for bias in the random number generator (RAM value 0x6018). Specifically, it tests if even random numbers are as likely as odd random numbers, and also if the previous random number being even vs odd affects the probability that the next one is even vs odd. I never found any bias with this script. When running the script a test is started by pressing 1 and stopped by pressing 2, at which point it will display the statistics it computed. Keep in mind I know hardly anything about lua programming and was mainly concerned with writing something that worked rather than making sure I was following good practices.
For the case of a DK AI instead of recording statistics on the value of the RNG each frame like this script does you will want to set the input using the joypad.set() function. A complete list of functions provided by mame-rr can be found here: http://code.google.com/p/mame-rr/wiki/LuaScriptingFunctions (http://code.google.com/p/mame-rr/wiki/LuaScriptingFunctions)
In order to make the AI move in response to what is happening on the board, you will need to read values from RAM. Here are some useful RAM values that could help get you started. All values are in hexadecimal.
0x6203 - Mario's X position
0x6205 - Mario's Y position
0x6700 is the start of the barrel array. Each barrel has a 0x20 byte range in which information for that barrel is stored. So for example barrel 1 info is in 6700 to 671F, barrel 2 info is in 6720 to 673F, etc. Here are some offsets from a barrel's range starting point that contain some useful info:
offset 00 - barrel status indicator (value 00 means inactive, 01 means active, 02 means it's being deployed)
offset 01 - wild barrel indicator (value 00 for normal and 01 for wild barrel)
offset 03 - barrel x position
offset 05 - barrel y position
0x6400 is that start of the fire array. Like the barrel array each fireball/firefox has a 0x20 byte range. Here are some useful offsets:
offset 00 - fire status (value 00 means inactive, 01 means active)
offset 03 - fire x position
offset 05 - fire y position
If you guys want, I can see if I can release a full RAM map with the meaning of a whole bunch of other RAM values. You can always try to find out what other RAM values, such as other offsets in the fire/barrel array, do by observing their values using RAM watch as you play.
-
I agree! I can't promise it will be fast work, but I'll try to get caught up on Lua when I have free time as well. It'll be cool to see what we can put together. Make sure to provide good notes for anything you guys code in case we need to share stuff with one another or ask for help on certain things.
-
Kicking the tires on this thread, bumping it up.
Anybody make any progress on this yet? I have had a head cold for the past few weeks, effectively laying dormant the analytic part of my brain.