Author Topic: Calling all Dk-playing programmers!  (Read 16151 times)

0 Members and 3 Guests are viewing this topic.

Offline marinomitch13

  • Spring Jumper
  • *
  • Posts: 1806
    • How to Play DK
    • Awards
Calling all Dk-playing programmers!
« 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/

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.
"Thou hast made us for Thyself, and our heart is restless until it finds its rest in Thee." -Augustine, Confessions.
Member for 11 Years IGBY 2015 DKF Team Member DK Killscreener Blogger Twitch Streamer

Offline ebinsugewa

  • Elite Member
  • *
  • Posts: 253
    • Awards
Re: Calling all Dk-playing programmers!
« Reply #1 on: April 14, 2013, 08:34:58 pm »
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.
« Last Edit: April 14, 2013, 08:36:37 pm by ebinsugewa »
we're in the yellow pages under 'spatulas'
Member for 11 Years Twitch Streamer Blogger IGBY 2014 DKF Team Member

Offline marinomitch13

  • Spring Jumper
  • *
  • Posts: 1806
    • How to Play DK
    • Awards
Re: Calling all Dk-playing programmers!
« Reply #2 on: April 14, 2013, 08:38:17 pm »
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.
"Thou hast made us for Thyself, and our heart is restless until it finds its rest in Thee." -Augustine, Confessions.
Member for 11 Years IGBY 2015 DKF Team Member DK Killscreener Blogger Twitch Streamer

Offline ebinsugewa

  • Elite Member
  • *
  • Posts: 253
    • Awards
Re: Calling all Dk-playing programmers!
« Reply #3 on: April 14, 2013, 08:51:55 pm »
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.
« Last Edit: April 14, 2013, 08:54:04 pm by ebinsugewa »
we're in the yellow pages under 'spatulas'
Member for 11 Years Twitch Streamer Blogger IGBY 2014 DKF Team Member

Offline John73

  • Senior Member
  • *
  • Posts: 128
    • Awards
Re: Calling all Dk-playing programmers!
« Reply #4 on: April 15, 2013, 12:10:45 am »
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.



DK Mame 266K Level 8-6
CK Mame 559K Killscreen
Member for 11 Years CK Killscreener Twitch Streamer

Offline marinomitch13

  • Spring Jumper
  • *
  • Posts: 1806
    • How to Play DK
    • Awards
Re: Calling all Dk-playing programmers!
« Reply #5 on: April 15, 2013, 12:34:42 am »
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.
"Thou hast made us for Thyself, and our heart is restless until it finds its rest in Thee." -Augustine, Confessions.
Member for 11 Years IGBY 2015 DKF Team Member DK Killscreener Blogger Twitch Streamer

Offline John73

  • Senior Member
  • *
  • Posts: 128
    • Awards
Re: Calling all Dk-playing programmers!
« Reply #6 on: April 15, 2013, 12:58:39 am »
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
DK Mame 266K Level 8-6
CK Mame 559K Killscreen
Member for 11 Years CK Killscreener Twitch Streamer

Offline ChrisP

  • Spring Jumper
  • *
  • Posts: 1764
  • I'm going to jump next to your leg.
    • Donkey Blog
    • Awards
Re: Calling all Dk-playing programmers!
« Reply #7 on: April 15, 2013, 03:38:31 am »
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.
« Last Edit: April 15, 2013, 03:40:35 am by ChrisP »
http://donkeykongblog.blogspot.com

4 Quarters :-* - 800K Avg. Per Qtr. :o - No Restarts 8) - No Proof :'(

7/26/2013   Coin 35,946   710,800   18-1
7/28/2013   Coin 35,947   903,700   22-1
8/16/2013   Coin 35,948   694,100   17-6
8/17/2013   Coin 35,949   893,100   22-1

3,201,700: the $1 World Record?
Member for 11 Years DK Masters - Rank D DKJR Killscreener IGBY 2016 DKF Team Member IGBY 2015 DKF Team Member IGBY 2014 DKF Team Member Blogger Twitch Streamer DK Killscreener CK Killscreener

Offline Monstabonza

  • Senior Member
  • *
  • Posts: 237
    • Awards
Re: Calling all Dk-playing programmers!
« Reply #8 on: April 15, 2013, 03:55:28 am »
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.
Dk PB 391800
Dk jr PB 42000
CK 481400 lvl 19-1
CK On CC 567100 KS

Twitch =
Member for 11 Years IGBY 2014 DKF Team Member CK Killscreener Blogger Twitch Streamer

Offline LMDAVE

  • Spring Jumper
  • *
  • Posts: 639
    • Awards
Re: Calling all Dk-playing programmers!
« Reply #9 on: April 15, 2013, 06:15:47 am »
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.

Donkey Kong (Arcade): 1,108,100

Donkey Kong 1-1: 12,900

http://twitch.tv/LMDAVE
Member for 11 Years DK 1.1M Point Scorer Winner of a community event Blogger DK 1M Point Scorer DK Killscreener Former DK Level 1-1 World Record Holder Twitch Streamer

Offline hooch66

  • Senior Member
  • *
  • Posts: 139
    • Personal Blog
    • Awards
Re: Calling all Dk-playing programmers!
« Reply #10 on: April 15, 2013, 06:39:58 am »
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

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?
Member for 11 Years Blogger

Offline lifereboot

  • Full Member
  • *
  • Posts: 74
    • http://www.lifereboot.com
    • Awards
Re: Calling all Dk-playing programmers!
« Reply #11 on: April 15, 2013, 10:23:50 am »
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.
lifereboot
DK personal best (arcade / 3 men) 1,037,500
http://www.lifereboot.com
Member for 11 Years DK Killscreener DK 1M Point Scorer Twitch Streamer

Offline lifereboot

  • Full Member
  • *
  • Posts: 74
    • http://www.lifereboot.com
    • Awards
Re: Calling all Dk-playing programmers!
« Reply #12 on: April 15, 2013, 10:31:06 am »
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.
lifereboot
DK personal best (arcade / 3 men) 1,037,500
http://www.lifereboot.com
Member for 11 Years DK Killscreener DK 1M Point Scorer Twitch Streamer

Offline hooch66

  • Senior Member
  • *
  • Posts: 139
    • Personal Blog
    • Awards
Re: Calling all Dk-playing programmers!
« Reply #13 on: April 15, 2013, 11:07:40 am »
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.



Member for 11 Years Blogger

Jeffw

  • Guest
Re: Calling all Dk-playing programmers!
« Reply #14 on: April 15, 2013, 12:41:30 pm »
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.