[HN Gopher] Show HN: I built an autopilot for the lunar lander game
___________________________________________________________________
Show HN: I built an autopilot for the lunar lander game
I got pretty good at (and very addicted to) the lunar lander game
from a few days ago... so I decided to make an autopilot for the
lander based on what I felt like was the best strategy! Now I can
have perfect landings every time without lifting a finger :D
Writing the autopilot code was a lot more fun than I expected! It
felt a bit like programming a robot. Source code:
https://github.com/szhu/lunar-lander-autopilot Original lander HN
post: https://news.ycombinator.com/item?id=35032506
Author : szhu
Score : 244 points
Date : 2023-03-10 03:30 UTC (19 hours ago)
(HTM) web link (szhu.github.io)
(TXT) w3m dump (szhu.github.io)
| hawski wrote:
| Would it be possible to put the autopilot in a bookmarklet for
| the original game?
| szhu wrote:
| I really wanted to!
|
| But unfortunately none of the lander's stats are exposed as
| global variables, so the only way I could make the autopilot
| was by modifying the existing code. (My commits are actually
| broken down exactly like this: a commit to expose the necessary
| variables globally, and another to actually add the autopilot.)
|
| I would also love to be able to play it in the original game
| though, so I made a PR! I think it would be cool for it to be
| able to be activated as an easter egg.
|
| https://github.com/ehmorris/lunar-lander/pull/7
| ehmorris wrote:
| I will take a look!
| kevinwang wrote:
| And now we've gone full circle
| mclightning wrote:
| That was my immediate thought.
|
| 1.Step: Write code to simulate freefall of an object
|
| 2.Step: Write code to negate freefall of an object
| [deleted]
| szhu wrote:
| Update: I improved the algorithm.
|
| The autopilot now scores a "perfect landing" almost every single
| time, it lands very noticeably faster, and the code no longer
| contains a complicated, trial-by-error formula!
|
| I got my first 103+ point landing! (It does this about half the
| time now)
|
| https://user-images.githubusercontent.com/1570168/224399420-...
| marketdev wrote:
| While I was playing the game, the idea of traveling in a SpaceX
| rocket ship didn't seem appealing to me. Now that I have
| experienced your autopilot feature, I feel MUCH more confident
| about it.
| handonam wrote:
| this is great! The one thing i think to optimize it is to predict
| how late to start the engine to minimize its usage. The last I
| got was 730 times used, at 53seconds.
| dsmmcken wrote:
| choosing how late you can turn it on and still land is almost a
| game in itself.
| huevosabio wrote:
| Love it! I started playing by disabling autopilot, putting the
| ship in complicated positions (e.g. spinning uncontrollably) and
| then turning the autopilot on, it's fun to which conditions it
| can recover.
| 000ooo000 wrote:
| Cool, neat code too :) Now do https://race-
| condition.reaktor.com/! I wanted to pour a few hours into race
| condition but I got it to complete a lap and never went back.
| paradite wrote:
| Lunar lander is a one of the problems in Open AI Gym, where you
| test AI against standard set of problems:
| https://www.gymlibrary.dev/environments/box2d/lunar_lander/
|
| Then you have stable baselines which implements popular
| reinforcement learning algorithms to solve these gym problems:
| https://stable-baselines3.readthedocs.io/en/master/
|
| Shamless plug: I've built a series of games where you solve
| puzzles (2048) / toy problems (MDP) like the lunar lander using
| various AI and ML algorithms.
|
| You can check it out here: https://ai-simulator.com/
| opdahl wrote:
| Looking at your website I'm curious how exactly you're building
| <<ChatGPT for mobile games>>? Are you using language models to
| build these AI solvers?
| paradite wrote:
| Well to be honest it is just a marketing term I am using to
| try to get some attention.
|
| In a way what I am building is a "general AI engine" that is
| capable of taking in an arbitrary game and play it, which is
| somewhat conceptually similar to how ChatGPT is a general AI
| that is able to solve a wide range of text-based tasks.
| hcrisp wrote:
| Yes, I would like to see the environment ported to Python,
| wrapped in gym, and given a good shaped reward, i.e. like
| reward = prior_height_delta - (height - target_height) -
| fuel_cost. Run Stable Baselines PPO or DQN on that and it
| should converge to something close to an optimized MPC
| controller.
| paradite wrote:
| It is already there, just not this particular implementation
| (or maybe it is?).
|
| You can run PPO or DQN right now on the Open AI Gym
| implementation using Stable-Baselines3: https://stable-
| baselines3.readthedocs.io/en/master/
|
| In fact I previously ran it locally and PPO solved the
| problem within 10 minutes of training with max reward of
| about 200.
| hcrisp wrote:
| This is a different lunar lander than you are maybe
| thinking. It looks more like SpaceX's Starship than an
| Apollo lunar module. I don't think it has been made into a
| gym env yet but that would be great if it is!
| tiffanyh wrote:
| Mobile?
|
| How to you trigger autopilot on mobile?
| skipnup wrote:
| Click on the red glowing "autopilot" link to turn on on
| (glowing green)
| ricardobeat wrote:
| It's amazing how a simple algorithm performs so well, the
| autopilot is able to recover from some pretty extreme situations,
| and does it gracefully.
|
| Adding some realism to the engine physics (firing delays, minimum
| firing time, power ramp up, heat limits etc) would likely make it
| 10x harder.
| giomasce wrote:
| Especially nondeterminism. Everything you say is still
| deterministic, so either you're able to land or you're not.
| With nondeterminism it's more interesting. You have to make
| tradeoffs between optimizing resources and making success
| probable.
| dwringer wrote:
| Thanks for this comment, I hadn't thought to try and sabotage
| my trajectory prior to engaging autopilot. I thought for sure
| it was gonna fail, but it managed to set me down gently right
| at the last moment quite brilliantly.
| ehmorris wrote:
| Woah this is awesome! Someone on Twitter made an autopilot with
| ML but this seems a lot better.
|
| https://twitter.com/_s_w_a_y_a_m_/status/1633468475611004928...
| mg wrote:
| It's interesting to think about how the optimal strategy to land
| the lander would look like.
|
| If the distance to the moon was large, I would expect 4 phases:
|
| 1: Turn the lander towards the moon
|
| 2: Constant thrust towards the moon
|
| 3: Turn the lander away from the moon
|
| 4: Constant thrust away from the moon
|
| But if the initial distance is small enough, turning it around
| might not be worth it or even possible.
|
| So the optimal strategy is probably a somewhat complex function
| of the initial angle and distance to the moon.
| swyx wrote:
| almost guaranteed that this problem is already solved by the
| rocket scientists out there. hopefully someone on HN can point
| us to the relevant algorithm. this seems like a closed system
| at least in newtonian physics that should be easily solvable.
|
| chatgpt pointed me to the Gravity Turn altho it refused to give
| me a formula for it
| https://en.wikipedia.org/wiki/Gravity_turn#Deorbit_and_entry
| antoinealb wrote:
| This is typically solved using a class of control algorithm
| called Model Predictive Control which are capable of
| optimizing for a given cost function (such as using minimal
| fuel).
|
| Search for "fuel optimal rocket landing algorithm" for good
| starting points.
| 4gotunameagain wrote:
| when discussing about optimality, it is worth specifying what
| are you optimising for.
|
| time optimal landing lends techniques from bang-bang control
| (e.g. starting with v=0, max thrust towards the target, before
| flipping around half way and max thrust away from target)
|
| fuel optimal landing (incuding RCS) technique would depend on
| the available time to turn retrograde (pointy end pointing away
| from direction of movement). if the duration before the
| decelerating burn is T1 (so t1 = t0+T1), the smallest possible
| rcs impulse would be applied so that at t1-T_st the lander is
| pointing retrograde (retrograde at t1), with T_st being the
| time needed to cancel the initial rcs impulse. For the
| deceleration of the lander, fuel optimal landing includes a
| single burn, constantly retrograde, so that at t_end the lander
| altitude is 0, and both the vertical and horizontal velocity
| components are 0.
|
| The time t1 to start that burn depends on the maximum thrust
| available, the rate of mass change when firing the rocket (not
| modelled in the game), the initial velocity etc.
|
| in this simple case, model predictive control is not needed,
| and an LQR (linear quadratic regulator) is sufficient to
| achieve optimality
|
| source: rocket scientist with control theory background. I
| remember this example (a bit more realistically modelled) being
| a project during my studies
| syntheweave wrote:
| In implementing an AI to achieve orbit in a Spacewar-style
| simulation with gravity, I ended up with a brute-force
| constraint optimizer that resembles MCP(I've never studied
| the theory): for each timestep, predict the solutions
| resulting for each combination of digital thrust inputs(left,
| right, forward, backwards). Then predict ahead several more
| steps with additional permutations of input. Then evaluate
| distance to goal and rank final solution by distance to
| target orbit and velocity match.
|
| In doing this, it results in a few hundreds to thousands of
| solutions to test per timestep, which modern CPUs can shrug
| off easily. Not nearly as elegant as closed-form control
| theory systems, but easy to tune and give different goals.
| 4gotunameagain wrote:
| replace the brute-force with a linear constraint solver,
| and you got yourself an MPC !
|
| non-linear constraint solvers are not used because they
| cannot guarantee a time to solution, hence useless for
| control applications
| bjd2385 wrote:
| Really cool! The fact that astronauts handled the landing in the
| Apollo missions is nerve wracking
| tired_and_awake wrote:
| Simple and fun, thanks for sharing! Have you thought of adding a
| wordle style variation - just a daily puzzle that's a different
| start orientation + velocity? Just a thought.
| szhu wrote:
| Oh that sounds like fun, I would definitely play that. You
| should suggest it to the developer who made the game!
|
| https://github.com/ehmorris/lunar-lander/issues
|
| https://news.ycombinator.com/item?id=35032506
| _ZeD_ wrote:
| uhm... it doesn't seem to work, at least on my workstation
| (firefox on a debian)
| szhu wrote:
| oh no! I'm tried it on Firefox on Mac and it worked fine?
|
| https://user-images.githubusercontent.com/1570168/224370129-...
|
| https://user-images.githubusercontent.com/1570168/224369935-...
| simonh wrote:
| That's cool, but it has a very conservative descent profile and
| would use a ton of fuel. Having played Kerbal I'm used to
| attempting fuel efficient landings, which means more of a suicide
| burn approach, but of course this game doesn't keep track of
| that.
|
| There's something timelessly appealing about lunar lander games.
| The very first game I ever played on a computer, written in
| BASIC, was a 'turn based' one dimensional lunar lander game where
| you input how much thrust you used for each second of the
| descent, and then it recalculated your altitude, velocity, etc. I
| learned programming by rewriting it to be a real-time game where
| you pressed a key to fire the engine.
| zengargoyle wrote:
| The first program I ever keyed in was the one dimensional lunar
| lander simulation on my dad's HP calculator. Must have been 6
| or 7 years old (by 9 years old I was doing BASIC on an Apple ][
| with floating point card and programming intersections of two
| pipes to make cutting templates). Even back then I got to the
| 'suicide burn' approach. Made playing the arcade game pretty
| easy years later.
| clbrmbr wrote:
| Ditto on the timeless appeal.
|
| Watching this auto pilot reminded me of landing Getaceiver on
| Barsoom in Heinlein's Number of the Beast, which has a very
| long passage describing the (fictional) orbital mechanics
| landing on (a fictional alternate reality version of) Mars.
| mft_ wrote:
| Which points to a lovely idea - the game becomes writing
| competitive lander algorithms. Just need a bit of JSFiddle
| adding...
| santiagobasulto wrote:
| That'd be very fun indeed!
| someweirdperson wrote:
| Maybe not for long, because for a given set of constraints
| to optimze for, there's probably a solution for which it
| can be proven to be optimal. At that point there's no more
| contest.
| TheMaskedCoder wrote:
| Obviously next you switch up the game to do things
| besides lunar landing. Have it be a take off ascent
| simulator for example. After a few years we can have an
| entire space mission programmed by gamers...
| simonh wrote:
| People have released very sophisticated autopilots for
| KSP. The game can practically play itself.
| rizky05 wrote:
| [dead]
| m00dy wrote:
| very similar to
| https://www.gymlibrary.dev/environments/box2d/lunar_lander/
| szhu wrote:
| Oh yeah, the author of the game said he made use of a similar
| tutorial:
|
| http://students.cs.ucl.ac.uk/schoolslab/projects/HT5/
|
| from the readme here: https://github.com/ehmorris/lunar-lander
| Nodraak wrote:
| Nice auto pilot! Very basic, but works well enough.
|
| In the real world, you would derive physics equations
| (acceleration -> velocity -> position), add constraints and then
| solve everything to obtain an optimal trajectory (mostly in term
| of fuel, but you can add other constraints too, for ex due to
| radar-ground or Antenna-Earth visibility). I wrote a blog post
| about Apollo's algorithm:
| https://blog.nodraak.fr/2020/12/aerospace-sim-2-guidance-law...
| (Described in the second section ; the first section is about a
| naive algorithm similar to yours that in the end did not work as
| well as I wanted).
|
| Also, thanks for the code, I wanted to do the same, but lost
| motivation when I could not really expose in a satisfying way the
| internal state out of these JS modules (it's not complicated in
| the end, but I'm simply not a frontend dev ; and I wanted to
| avoid forking and monkey patching everything and simply adding
| some JS code throught the console or something).
| [deleted]
| Aperocky wrote:
| A career in KSP is calling for you (Landing on the mun
| automatically):
|
| https://www.youtube.com/watch?v=TY63i8V1-DA
|
| The most I've used linear algebra since college:
|
| https://github.com/Aperocky/ksp_eng/blob/master/lib/space_li...
| iandanforth wrote:
| I'm impressed by the simplicity of the solution, well done.
| szhu wrote:
| Thanks! Yeah it's just (1) rotate to follow the trajectory line
| and (2) slow down once you get close to the bottom.
| timmaxw wrote:
| I wanted to go for a record of as many flips as possible. So I
| boosted up to 25,000 feet; started spinning until it was doing
| about one flip per second; waited a few minutes; then turned on
| the autopilot to come into a landing.
|
| The autopilot did a perfect job of stopping the rotation and
| lateral motion, so the lander came down straight as an arrow.
| Unfortunately, the autopilot didn't even try to decelerate! I
| crashed into the moon at 0.9 degrees and 770 MPH.
| szhu wrote:
| Update: I added a new algorithm, and I think it might be
| impossible to crash the ship now.
|
| Let me know if you can still reproduce the bug!
| manbash wrote:
| Max speed: 148.7 Max height: 3998 Flips: 34
|
| Perfect landing. :)
| ricardobeat wrote:
| The target velocity is a factor of height, and the autopilot
| has "160" hardcoded as the ceiling, so going above that means
| it will never decelerate fast enough.
|
| https://github.com/szhu/lunar-lander-autopilot/blob/master/a...
| szhu wrote:
| That's a ceiling for the speed the autopilot is okay with
| letting the lander descend. There is no ceiling to how much
| hard it will try to "apply the brakes".
|
| I agree that the target velocity calculation is off though. I
| was excited that I came up with something reasonably
| theoretically correct for correcting rotation... and for
| figuring out when to fire the engines I just gave up and
| eyeballed it :)
| curiousgal wrote:
| Best I could score was 102.0 with a combination of manual and
| autopilot. Neat!
| antegamisou wrote:
| Now do it with LQR :D
| khalidx wrote:
| This is awesome! The closest I got without the autopilot was 94
| or so. The autopilot consistently scores 100+
| jkonline wrote:
| "Oh SNAP! I'm amazing at this!" 101.1 point landing on my second
| try!
|
| At least, that's what I thought, until I realized I had
| previously activated the auto-pilot. Best #footgun today (so
| far!).
|
| So I guess I should say: > Oh SNAP! This auto-pilot is amazing at
| this!
|
| Thanks!
| monkellipse wrote:
| Nice! I also got hooked on the lander thing, really quick to pick
| up and good replay value! Your autopilot handles a gentle landing
| well. If I get the lander going sideways at any appreciable
| speed, then flip autopilot on, a crash is inevitable :) As a
| human my solution to that is simply slowing down with lots of
| thrust, though I still wind up turning the lander into scrap most
| of the time hah!
| tommica wrote:
| What about adding a limited fuel supply?
| acomjean wrote:
| For what it's worth fuel is in the original arcade game.
|
| "Unlike other arcade games, Lunar Lander does not feature a
| time limit; instead, the game starts with a set amount of fuel
| and inserting additional quarters purchases more fuel, allowing
| indefinite gameplay."
|
| https://en.m.wikipedia.org/wiki/Lunar_Lander_(1979_video_gam...
| dropbox_miner wrote:
| This is great but I'd like to see an autopilot that can do the
| hardest crash
| josephcsible wrote:
| One suggestion: if the lander is within about 10 feet of the
| ground and is still either swaying back and forth or going really
| fast laterally, it should thrust upwards to buy more time to
| correct those things.
| szhu wrote:
| oh yeah definitely. Left as an exercise for the reader??
|
| (accepting PRs!)
| szhu wrote:
| Actually, I think my new algorithm fixes this -- and without
| any dedicated "swaying" edge case!
___________________________________________________________________
(page generated 2023-03-10 23:02 UTC)