8 ms·
Here, I found it fun to write a small bot to play automatically. Just paste this JS code in the dev console. It reached 9000 points on my first attempt to let i
by mrb 3y ago
Here, I found it fun to write a small bot to play automatically. Just paste this JS code in the dev console. It reached 9000 points on my first attempt to let it run. Feel free to tweak the code to make pac-man survive longer :-)
function bot() {
/* direction of the enemy: to our right (1) or to our left (-1) */
dir = (enemy.x > player.x) ? 1 : -1;
/* 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) < 25 &&
/* 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, 100);
The strategy is ultra simple. Every 100 ms it evaluates the situation and chooses to move away from the enemy (ghost) if it's too close to it, and has no powerup (or if the powerup is expiring very soon).
The corner cases where pac-man dies is the game difficulty progressively increases (the ghost becomes faster) until you eat it, so sometimes some pellets are left in the middle and pac-man doesn't have enough time to eat them until the ghost reaches it. The ghost will progressively get faster and faster and death is guaranteed. You could improve the code by tempting the ghost to get close to one edge, then cross over to the other edge and quickly eat the middle pellets.
Also, as soon as new pellets are added, one should prioritize eating the middle pellets.
Also, one could add code to detect the powerup pellets, and chose to NOT move away from the ghost if it calculates it can eat the powerup pellet before the ghost reaches pac-man.
- irjustin 3y agoThis 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.
- pushedx 3y agoThe 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?
- wegfawefgawefg 3y agodeep 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)
- eru 3y agoYou 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.
- deleted 3y ago[deleted]
- cdchn 3y agoPutting comments before the conditionals made my brain parser malfunction for a moment.
- tanseydavid 3y agoSame here -- but I kind of like it. I might adopt that.
- cdchn 3y agoI'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.
- TuLithu 3y ago[flagged]
- IggleSniggle 3y agoI think you may be confused about what the word "parse" means. Adding "brain" is a bit redundant, but understandable on a site dedicated to computers.
- johnisgood 3y agoYeah, I do not know why OP would imply that. The brain does actually parse. In terms of language processing, the term "parse" may refer to the mental process of syntactic analysis, in which case the brain analyzes the grammatical structure of a sentence to comprehend its meaning. Besides that, there is auditory parsing of sound patterns, along with visual parsing of visual scenes to recognize objects, shapes, and patterns. Sure, the brain does not follow the same principles of formal grammars used in computer science, but I think the term "parsing" still applies.
- elijahbenizzy 3y agoThis is true AI! Nice work!
- trevithick 3y agoThis 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.
- AnotherGoodName 3y agoI 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);
- svat 3y agoHow 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?)
- lifthrasiir 3y agoThe 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/main.js https://abagames.github.io/crisp-game-lib-11-games/pakupaku/...
- mrb 3y agoI 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/main.js 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.
- artisandip7 3y agosomething 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 :)
- oleganza 3y agoThis 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.
- xomopinok 3y agoYou 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 https://github.com/creme332/pakupaku-ai [2]: https://github.com/creme332/pakupaku-ai/blob/main/assets/high_score.gif https://github.com/creme332/pakupaku-ai/blob/main/assets/hig... [3]: https://creme332.github.io/pakupaku-ai/?pakupaku https://creme332.github.io/pakupaku-ai/?pakupaku