Hacker News Reader

I simply changed the distance to be dynamic based on closeness to the edge and it's getting into the many 100's of thousands. This simple change also seemed to fix the edge case of the respawn hitting the player is solved since the player never gets into that magic position (the enemy has to be in a very specific position for the eyes to reach the end just as the player does).

    function bot() {
        /* direction of the enemy: to our right (1) or to our left (-1) */
        dir = (enemy.x > player.x) ? 1 : -1;
        nearWall = enemy.x < 10 || enemy.x > 90
        /* if pac-man... */
        if (
            (
            /* ...has no powerup or powerup expires in less than 10 "ticks" */ 
            powerTicks < 10 &&
            /* ...is headed toward enemy */ player.vx == dir &&
            /* ...is too close to enemy */ abs(player.x - enemy.x) 
            /* ...the distance before running away can be lower if we're near an edge */
                < (dir == 1 ? player.x / 7 : ((100 - player.x) / 7))+7 &&
            /* and if enemy's state is not "eyes flying back" */ 
            enemy.eyeVx == 0)
        ) {
            // "ArrowUp" or any arrow key reverses the direction of pac-man
            document.dispatchEvent(new KeyboardEvent('keydown', {code: 'ArrowUp'}));
            document.dispatchEvent(new KeyboardEvent('keyup', {code: 'ArrowUp'}));
        }
    }
    setInterval(bot, 10);

Of course ! Nice.

A shorter way to change the direction of the player is to use player.vx *= -1;

Putting comments before the conditionals made my brain parser malfunction for a moment.

Same here -- but I kind of like it. I might adopt that.

I'm kind of a 'why not what' kind of guy when it comes to comments. For example "powerTicks < 10" took much less time for my brain to parse (and I get extra information, I see there is a variable called powerTicks then "/* ...has no powerup or powerup expires in less than 10 "ticks" */" did. Then my eyes had to scan for the closing comment to get to the important part.

Something different, but not for me personally.

This is really cool. My bot score stayed low because there was a single dot remaining near the middle which Pac-Man couldn't reach. They went back and forth for a long time until the ghost became fast enough to get him. Still fun to watch.

How did you (or how does one) discover that the game state consists of the variables enemy.{x,vx,eyeVx}, player.{x,vx}, powerTicks? (And are there others?)

The source code for the page doesn't have any reference to a game-specific source code, so it must have been loaded dynamically and can be found from devtools [1]. You can then read the actual code and find that every state is in the global scope, so they are directly accessible without any trick. It hasn't been minimized so all variable names make sense and you can even guess their purposes without actually checking.

[1] https://abagames.github.io/crisp-game-lib-11-games/pakupaku/...

I reverse-engineered it. This whole exercise took me about 30 minutes while half coding and half watching a TV show. Since the JS code was neither minified nor obfuscated, it was easy. Here are my exact steps:

In Chrome, right-click on the page -> View Source. Go to the "Sources" tab. When you open the tree on the left you find a file, that was dynamically loaded (so you wouldn't have found it by just looking at the HTML source of the main page), https://abagames.github.io/crisp-game-lib-11-games/pakupaku/... that seems to contain the game's code. And indeed it's less than 200 lines and implements the core game logic.

There is a main function, update(), containing a conditional "if (!ticks)" that seems to do initialization. "ticks" is probably zero at the start of the game. The code initializes multiple variables, including "player" and "enemy":

    if (!ticks) {
      player = { x: 40, vx: 1 };
      enemy = { x: 100, eyeVx: 0 };
      multiplier = 0;
      addDots();
      powerTicks = animTicks = 0;
    }

Then with a bunch of console.log() statements added to the update() function (just edit the code and type Ctrl-S to save it, Chrome allows this sort of in-place code editing), I got a sense that player.x and enemy.x was the x position, with the scale going from 0 (left edge) to 100 (right edge). Then with more console.log() statements I found enemy.eyeVx was normally 0 when the enemy is a ghost or 1 or -1 if the ghost has been eaten and its eyes are flying respectively right or left.

Some of the code is less readable, for example:

    if (enemy.eyeVx === 0 && (c.a || c.b || c.c)) {
      if (powerTicks > 0) {
        play("powerUp");
        addScore(10 * multiplier, enemy.x, 30);
        enemy.eyeVx = player.x > 50 ? -1 : 1;
        powerTicks = 0;
        multiplier++;
      } else {
        play("explosion");
        end();
      }
    }

I figured by literally typing "play(...)" in the dev console that these functions play a sound. Therefore based on the sound names "powerUp" and "explosion" I realized this code block is called when pac-man collides with a ghost. And either it has a power-up ("powerTicks > 0") or not, in which case it dies.

At this point I had the meaning of "player", "enemy" and "powerTicks" and that's all I needed to write the bot.

This is super awesome!

The trouble I ran into was after eating the ghost, the spawn point of the new ghost was too close to my current position and simply sped over me.

With this and all the considerations you've noted above, I'd probably throw an ML solution at it - imagine it takes less coding time.

The script took, at most, 5 hours to write (inclduing the time for this poster to play the game, understand the game, reverse engineer the game, and implement a bot). What type of "ML solution" to the same problem would take less than 5 hours?

You are right about the time, but 1D Pac-Man might still be a good fun toy problem to hone your ML skills on.

For the record, it took me about 30 minutes of playing, reverse-engineering, and writing the bot. So, indeed, no need for an ML solution :)

deep reinforcement learning guy here. Youre looking at coding up double dqn, and probably training it for about 5 to 30 minutes. Very likely it would not outperform a simple near perfect algorithm, and would fail in some weird ways that would annoy you a few tens of thousands of times. Youd have issues like it refusing to go left, ever, after dying. So youd need to know about epsilon then epsilon decay etc.

Coding that from nothing (and understanding it) could take days. Weeks to months if you dont know ml stuff.

In this particular case I think basic Q Tabular Learning could play optimally, no neural net required.

I could be wrong though, throw a full conv at it without temporal difference and see what happens! (probably a kinda okayish score)

You could probably throw a small fully connected net at it, and 'train' it via genetic algorithms: ie have a population of nets, let them each run a few games, and pick a few top scorers to seed the next generation with some mutation and cross-over.

This random exploration is less efficient than back propagation, but at least you don't have to muck around with temporal differences. (And it would be hard to figure out how to tweak the weights for backpropagation in this multi-step game; without falling back to reinforcement learning.)

The problem seems simple enough that evolution via mutation and artificial selection has a decent chance to get good in a reasonable amount of computing time.

NEAT? An added bonus of the evolutionary neural search is that you can still explore the solution space with small networks, which isnt really true of backpropogation without evolution. You run out of states.

With the right small neural network architecture you could probably just repeat random weight initialization until you find one that works. This is known to work for some of the Atari games. The trick is, of course, to engineer a good input encoding and to find the right model complexity and architecture in the first place.

This sounds like a simple enough problem that one could work out a provably optimal algorithm in less time than it takes to get even a non-optimal ML solution working.

But both approaches would be an interesting exercise in their respective domain!

Come to think of it, it might even be an interesting toy problem for a SAT solver! Overkill in the same way as an ML approach, of course.

You inspired me to spend the last two days to build my own bot[1]. The highest score[2] it reached is 300k but it is cannot consistently reach this score (the average score is around 50k). The algorithm is to reverse the player direction only if one of the following conditions is satisfied:

1) enemy is running away from player && power is about to expire && player is close to enemy.

2) player is getting too close to enemy's respawn point && player is too far from wall opposite to him && player has little or no power.

3) enemy is close to player (<20 units away) && the player and the enemy are facing each other.

A live preview of the algorithm in action is deployed on github[3].

[1]: https://github.com/creme332/pakupaku-ai

[2]: https://github.com/creme332/pakupaku-ai/blob/main/assets/hig...

[3]: https://creme332.github.io/pakupaku-ai/?pakupaku

This is great. That's what Alan Kay envisioned when doing Smalltalk 45 years ago: opening up a computer program while it's running and tinkering with its code directly.

And it's quite funny that JS was designed after Self/Smalltalk well before anyone cared about interactive tooling, towards which we evolved independently.

Alan Kay truly is a genius.

This is true AI! Nice work!

something similar

  eval(atob('ZnVuY3Rpb24gdXBkYXRlKCkgewogIGlmICghdGlja3MpIHsKICAgIHBsYXllciA9IHsgeDogNDAsIHZ4OiAxIH07CiAgICBlbmVteSA9IHsgeDogMTAwLCBleWVWeDogMCB9OwogICAgbXVsdGlwbGllciA9IDA7CiAgICBhZGREb3RzKCk7CiAgICBwb3dlclRpY2tzID0gYW5pbVRpY2tzID0gMDsKICB9CiAgYW5pbVRpY2tzICs9IGRpZmZpY3VsdHk7CiAgY29sb3IoImJsYWNrIik7CiAgdGV4dChgeCR7bXVsdGlwbGllcn1gLCAzLCA5KTsKICBpZiAoaW5wdXQuaXNKdXN0UHJlc3NlZCkgewogICAgcGxheWVyLnZ4ICo9IC0xOwogIH0KICBwbGF5ZXIueCArPSBwbGF5ZXIudnggKiAwLjUgKiBkaWZmaWN1bHR5OwogIGlmIChwbGF5ZXIueCA8IC0zKSB7CiAgICBwbGF5ZXIueCA9IDEwMzsKICB9IGVsc2UgaWYgKHBsYXllci54ID4gMTAzKSB7CiAgICBwbGF5ZXIueCA9IC0zOwogIH0KICBjb2xvcigiYmx1ZSIpOwogIHJlY3QoMCwgMjMsIDEwMCwgMSk7CiAgcmVjdCgwLCAyNSwgMTAwLCAxKTsKICByZWN0KDAsIDM0LCAxMDAsIDEpOwogIHJlY3QoMCwgMzYsIDEwMCwgMSk7CiAgY29sb3IoImdyZWVuIik7CiAgY29uc3QgYWkgPSBmbG9vcihhbmltVGlja3MgLyA3KSAlIDQ7CiAgY2hhcihhZGRXaXRoQ2hhckNvZGUoImEiLCBhaSA9PT0gMyA/IDEgOiBhaSksIHBsYXllci54LCAzMCwgewogICAgLy8gQHRzLWlnbm9yZQogICAgbWlycm9yOiB7IHg6IHBsYXllci52eCB9LAogIH0pOwogIHJlbW92ZShkb3RzLCAoZCkgPT4gewogICAgY29sb3IoCiAgICAgIGQuaXNQb3dlciAmJiBmbG9vcihhbmltVGlja3MgLyA3KSAlIDIgPT09IDAgPyAidHJhbnNwYXJlbnQiIDogInllbGxvdyIKICAgICk7CiAgICBjb25zdCBjID0gY2hhcihkLmlzUG93ZXIgPyAiZyIgOiAiZiIsIGQueCwgMzApLmlzQ29sbGlkaW5nLmNoYXI7CiAgICBpZiAoYy5hIHx8IGMuYiB8fCBjLmMpIHsKICAgICAgaWYgKGQuaXNQb3dlcikgewogICAgICAgIHBsYXkoImp1bXAiKTsKICAgICAgICBpZiAoZW5lbXkuZXllVnggPT09IDApIHsKICAgICAgICAgIHBvd2VyVGlja3MgPSAxMjA7CiAgICAgICAgfQogICAgICB9IGVsc2UgewogICAgICAgIHBsYXkoImhpdCIpOwogICAgICB9CiAgICAgIGFkZFNjb3JlKG11bHRpcGxpZXIpOwogICAgICByZXR1cm4gdHJ1ZTsKICAgIH0KICB9KTsKICBjb25zdCBldnggPQogICAgZW5lbXkuZXllVnggIT09IDAKICAgICAgPyBlbmVteS5leWVWeAogICAgICA6IChwbGF5ZXIueCA+IGVuZW15LnggPyAxIDogLTEpICogKHBvd2VyVGlja3MgPiAwID8gLTEgOiAxKTsKICBlbmVteS54ID0gY2xhbXAoCiAgICBlbmVteS54ICsKICAgICAgZXZ4ICoKICAgICAgICAocG93ZXJUaWNrcyA+IDAgPyAwLjI1IDogZW5lbXkuZXllVnggIT09IDAgPyAwLjc1IDogMC41NSkgKgogICAgICAgIGRpZmZpY3VsdHksCiAgICAwLAogICAgMTAwCiAgKTsKICBpZiAoKGVuZW15LmV5ZVZ4IDwgMCAmJiBlbmVteS54IDwgMSkgfHwgKGVuZW15LmV5ZVZ4ID4gMCAmJiBlbmVteS54ID4gOTkpKSB7CiAgICBlbmVteS5leWVWeCA9IDA7CiAgfQogIGNvbG9yKAogICAgcG93ZXJUaWNrcyA+IDAKICAgICAgPyBwb3dlclRpY2tzIDwgMzAgJiYgcG93ZXJUaWNrcyAlIDEwIDwgNQogICAgICAgID8gImJsYWNrIgogICAgICAgIDogImJsdWUiCiAgICAgIDogZW5lbXkuZXllVnggIT09IDAKICAgICAgPyAiYmxhY2siCiAgICAgIDogInJlZCIKICApOwogIGNvbnN0IGMgPSBjaGFyKAogICAgZW5lbXkuZXllVnggIT09IDAgPyAiaCIgOiBhZGRXaXRoQ2hhckNvZGUoImQiLCBmbG9vcihhbmltVGlja3MgLyA3KSAlIDIpLAogICAgZW5lbXkueCwKICAgIDMwLAogICAgewogICAgICAvLyBAdHMtaWdub3JlCiAgICAgIG1pcnJvcjogeyB4OiBldnggfSwKICAgIH0KICApLmlzQ29sbGlkaW5nLmNoYXI7CiAgaWYgKGVuZW15LmV5ZVZ4ID09PSAwICYmIChjLmEgfHwgYy5iIHx8IGMuYykpIHsKICAgIGlmIChwb3dlclRpY2tzID4gMCkgewogICAgICBwbGF5KCJwb3dlclVwIik7CiAgICAgIGFkZFNjb3JlKDEwICogbXVsdGlwbGllciwgZW5lbXkueCwgMzApOwogICAgICBlbmVteS5leWVWeCA9IHBsYXllci54ID4gNTAgPyAtMSA6IDE7CiAgICAgIHBvd2VyVGlja3MgPSAwOwogICAgICBtdWx0aXBsaWVyKys7CiAgICB9IGVsc2UgewogICAgICBwbGF5KCJleHBsb3Npb24iKTsKICAgIH0KICB9CiAgcG93ZXJUaWNrcyAtPSBkaWZmaWN1bHR5OwogIGlmIChkb3RzLmxlbmd0aCA9PT0gMCkgewogICAgcGxheSgiY29pbiIpOwogICAgYWRkRG90cygpOwogIH0KfQ=='))

when tired just call end()

probably better to manipulate the score directly but its not fun that way :)

Not sure why you obfuscated it but here's the code for anyone curious:

    function update() {
      if (!ticks) {
        player = { x: 40, vx: 1 };
        enemy = { x: 100, eyeVx: 0 };
        multiplier = 0;
        addDots();
        powerTicks = animTicks = 0;
      }
      animTicks += difficulty;
      color("black");
      text(`x${multiplier}`, 3, 9);
      if (input.isJustPressed) {
        player.vx *= -1;
      }
      player.x += player.vx * 0.5 * difficulty;
      if (player.x < -3) {
        player.x = 103;
      } else if (player.x > 103) {
        player.x = -3;
      }
      color("blue");
      rect(0, 23, 100, 1);
      rect(0, 25, 100, 1);
      rect(0, 34, 100, 1);
      rect(0, 36, 100, 1);
      color("green");
      const ai = floor(animTicks / 7) % 4;
      char(addWithCharCode("a", ai === 3 ? 1 : ai), player.x, 30, {
        // @ts-ignore
        mirror: { x: player.vx },
      });
      remove(dots, (d) => {
        color(
          d.isPower && floor(animTicks / 7) % 2 === 0 ? "transparent" : "yellow"
        );
        const c = char(d.isPower ? "g" : "f", d.x, 30).isColliding.char;
        if (c.a || c.b || c.c) {
          if (d.isPower) {
            play("jump");
            if (enemy.eyeVx === 0) {
              powerTicks = 120;
            }
          } else {
            play("hit");
          }
          addScore(multiplier);
          return true;
        }
      });
      const evx =
        enemy.eyeVx !== 0
          ? enemy.eyeVx
          : (player.x > enemy.x ? 1 : -1) * (powerTicks > 0 ? -1 : 1);
      enemy.x = clamp(
        enemy.x +
          evx *
            (powerTicks > 0 ? 0.25 : enemy.eyeVx !== 0 ? 0.75 : 0.55) *
            difficulty,
        0,
        100
      );
      if ((enemy.eyeVx < 0 && enemy.x < 1) || (enemy.eyeVx > 0 && enemy.x > 99)) {
        enemy.eyeVx = 0;
      }
      color(
        powerTicks > 0
          ? powerTicks < 30 && powerTicks % 10 < 5
            ? "black"
            : "blue"
          : enemy.eyeVx !== 0
          ? "black"
          : "red"
      );
      const c = char(
        enemy.eyeVx !== 0 ? "h" : addWithCharCode("d", floor(animTicks / 7) % 2),
        enemy.x,
        30,
        {
          // @ts-ignore
          mirror: { x: evx },
        }
      ).isColliding.char;
      if (enemy.eyeVx === 0 && (c.a || c.b || c.c)) {
        if (powerTicks > 0) {
          play("powerUp");
          addScore(10 * multiplier, enemy.x, 30);
          enemy.eyeVx = player.x > 50 ? -1 : 1;
          powerTicks = 0;
          multiplier++;
        } else {
          play("explosion");
        }
      }
      powerTicks -= difficulty;
      if (dots.length === 0) {
        play("coin");
        addDots();
      }
    }

Why would anyone even consider pasting obfuscated JS into their console, on HN of all places, is beyond me.

Theoretically, what's the worst thing that could happen - given it's a pacman game's console and not your online bank's?

I recall manually entered commmands have access to some APIs that are not normally accessible. Maybe timing related? So in the theoretical extreme, a timing attack to access something in your entire system memory and upload it via HTTP... while you watch the game play :)

Do they? It's easy enough to 'give' any API accessible to the console to the page by setting a variable from the page to point to a console-only accessible function.

Given there aren't many sites that say "just open the console and paste this command to win the big prize", I suspect that any console-only API's aren't very powerful if they exist at all.

Browsers now require you to manually type 'allow pasting':

https://developer.chrome.com/blog/new-in-devtools-120#self-x...

Because normies are extremely susceptible to things like "hack Facebook, see the PMs of any hot girl u want!111 just right-click and paste this into your browser console trust me bro"

As well as the usual engagement driving "challenges" like "Omg did you know there's no country starting with Z! Bet you can't think of one!" meanwhile comments are filled with "duuuuh Zanzibaaaar!" and post engagement is >>>>>>>>>>>>

No different than clicking on the links, right?

(Admittedly I typically browse with JS disabled...)

This seems to make it possible for Pac-man to stick with the ghosts while still consuming pellets, so maybe still evading the rules of the game :)