Hash table with complex variable-length keys

Question

I'm trying to implement the game Snake in Javascript and getting the computer to play it by itself, and want to check whenever the snake loops (repeats the same set of moves twice) so I can kill it.

To do this, the first thing that came to mind is saving the state the entire game at every frame (the state being the position of the snake's head and body segments, as well as the position of the 'pallet' it's looking to eat) in some sort of dictionary, and checking every frame if the new state of the game exists in this dictionary.

I don't quite know what's the best/most efficient/most readable way to implement this is. Here's what I tried so far:

const Snake = {
  direction: new Vector2(0, 1), // Up
  pallet: Vector2.random(0, 100, 0, 100).floor(),
  head: Vector2.random(0, 100, 0, 100).floor(),
  body: [], // Array of Vector2's
  loopHistory: {}, // Records every state
  checkForLoop: function () {
    // Current state of the system:
    const arr = [this.direction.hash(), this.pallet.hash(), this.head.hash(), ...this.body.map(x => x.hash())];
    //True if a loop is found, false if the state is completely new:
    let found = true;
    let obj = this.loopHistory;
    for (let i = 0; i < arr.length; i++) {
      if (!obj.hasOwnProperty(arr[i])) {
        //This is a part of the state that has never been seen before (new pallet position, new body segment etc.)
        found = false;
        // Record it for the next time:
        obj[arr[i]] = {};
      }
      obj = obj[arr[i]];
    }
    return found;
  }
}

loopHistory and checkForLoop are the relevant bits. Here's the Vector2 class for reference:

 const Vector2 = function (x, y) {
   this.x = x;
   this.y = y;
 };

 Vector2.random = function (xmin, xmax, ymin, ymax) {
   return new Vector2(
     xmin + Math.random() * (xmax - xmin),
     ymin + Math.random() * (ymax - ymin)
   );
 };
 Vector2.prototype.hash = function () {
   return this.x + 73856093 * this.y;
 };
 Vector2.prototype.floor = function () {
   return new Vector2(Math.floor(this.x), Math.floor(this.y));
 };

The issue with this implementation is it generates a massive ever growing arbitrarily deep object (loopHistory) for every game being run. With each game there could be thousands of states before the snake actually loops to its death, and there could be up to one hundred games running at once. The solution feels inefficient and clumsy and difficult to read/maintain, plus it takes a lot of memory, but that seems inevitable. So I'm looking for the go-to solution for situation like this, if one exists, or just any better implementation.

Please help me kill the snake! Thanks in advance for answers.

Edit: I forgot to mention that the behavior of the snake is only dependent on the state of the system that we captured earlier (head position, body positions, pallet position) so if it finds itself in the exact same circumstance it will inevitably react the same way and repeat the same moves.

Answer 1

So I'm looking for the go-to solution for situation like this, if one exists

Big step, small step. Rather than run the snake once, you run it twice in parallel, but the two instances run at different speeds:

snake1 = ...;
snake2 = snake1.clone();
while (true) {
    snake1.step();
    snake2.step();
    snake2.step();
    if (snake1.equals(snake2)) {
       // Loop detected
    }
}

If the cycle is of length \$n\$ and you enter the cycle for the first time at \$t_0\$ then this will detect the cycle as long as there's a number \$t \ge t_0\$ for which \$t \equiv 2t \pmod n\$. But that reduces to \$t \equiv 0 \pmod n\$, so \$t\$ is the first multiple of \$n\$ greater than or equal to \$t_0\$, and it's guaranteed to find the loop.

Essentially you trade memory saving (no history required) for execution time (it takes \$3t\$ calls to step() rather than \$t_0 + n\$).

---

That renders rather unnecessary the following observation:

    const arr = [this.direction.hash(), this.pallet.hash(), this.head.hash(), ...this.body.map(x => x.hash())];

Most of those don't need to use a Vector2 with a hash: there are 4 possibilities for the direction, and the body can be represented by a series of directions. Using arrays of length 4 might be more efficient than object properties.