Watch A Master Centipede Player

by

So this is a master playing the retro-game centipede:

How long did you watch this? I spent at least 5 minutes…

It’s obvious watching the game that this guy is good, but it’s also weird to think of a “good” player of this game since, sort of like tick-tack-toe, the optimal strategy is easy to compute. If you just crawl your centipede across the screen from top-to-bottom (or left-to-right) getting every single row (and never deviating to snag one of the prizes) you will eventually fill the entire screen and “win”. But that would be rather boring, and that’s not what this player does. Instead, he or she often takes risks to get the prizes faster and only uses the sort of careful-nesting technique when absolutely necessary.

That indicates the player is playing a much more complex game: not just how to get the maximal length (which is easy), but how to do it quickly, which is trickier. I did a quick Google search and I couldn’t find any contests to design AI to do it. The game is still simple enough that I think it might be solveable, but if speed matters as well as length, then it’s much more interesting to think about.

8 thoughts on “Watch A Master Centipede Player”

  2. I am loathe to ask experts about it because it might be embarrassingly simple. So I want to noodle with it more first. I think the basic algorithm would be:
    1. calculate fastest path to new prize
    2. determine if that path results in a losing situation

    But, now that I write it down, it might be more involved than that. For example, the shortest path might lead to a failure, but perhaps there’s a small deviation that won’t. In addition, if the shortest path leads to a failure, you still have to generate another path, and I don’t know how to do that. It might be something as simple as merely orbiting one spot (as it were) to bide time, but there are probably more efficient strategies.

    I still can’t tell if it’s trivial or insoluble…

  3. Consider the playing field as a piece of graph paper, which it is anyways. Then instead of calculate the fastest path, calculate all possible paths to the new prize. Because I’m a neat freak I’d sort them in order of squares moved. Then calculate all paths to the prize that would result in losing and also sort by squares moved. Match squares moved between the two and then remove those solutions. The top solution remaining should be the fastest and so on. I do realize there would be duplicates but for initial purposes we’ll ignore that.

    A basic run down would be similar to:
    Identify new prize location
    Identify snake direction
    Identify snake locations
    Mark locations of snake as losing
    Identify all possible routes to new prize
    Sort all possible routes in order of squares moved (low to high)
    Identify all possible routes to new prize that result in traversing a snake location
    Sort all possible routes that result in traversing a snake location by squares moved (low to high)
    Remove all routes that traverse a snake location
    Select route with least number of squares required
    Execute command

    Doesn’t seem as easy, even if you take out sorting (which i really did for matching purposes and nothing else). Now, writing either the programming or algorithms to handle that is so far beyond my league it’s not funny, but I can do high level planning!

  4. I just realized, there is a point at which it is more beneficial to follow a reserved path for the snake rather than the fastest path to the new prize. Otherwise you will end up cutting yourself off even using proper algorithms.

  5. I would not be surprised if it can be reduced to the traveling salesman problem, although NP complete problem reductions are beyond me. There was this article I read a few years ago showing that optimal Katamari reduces to TSP: https://cs.uwaterloo.ca/~gzaveruc/katamari.pdf

    I only skimmed it now, but I would guess that the key is in their formalized description of the game in section 2.4, and whether a key part of the reduction is the “subgame” based on what size pieces you can pick at any given point.

  6. Joel, your algorithm is pretty sound, but there are two big puzzles that remain.

    First, there’s the question of whether different paths have different value based on the random location of the next prize. You could have two paths that both won’t lead to total failure, but one of them might leave open more of a path towards a larger chunk of the board, thus putting you in a (probably) better place when the next prize spawns. How do you evaluate the “worth” of board locations, especially when you’re also considering speed?

    That’s where it might boil down to a Traveling Salesman type problem, where the only way to know you’ve got the best solution is to solve all possible states of the game (which is probably computationally impossible).

    And that’s the second point: even if you are pretty intuitively sure that you’ve got the optimal strategy, you have to prove it. That’s where a lot of the work comes in. So yeah: I think you’ve got an awesome start, but there’s still tricksey stuff left.

    Dan, I actually thought this problem (is the Centipede game NP-hard?) might be fun for my wife to research for her PhD (computational complexity is one of the things she’s looking into), so I did some Googling and found a paper that proved Pac Man is NP-hard, and evaluated a bunch of other games from 1980 – 1998 as well (including Starcraft and–by proxy–the entire RTS genre).

    Here’s a popular news story about the paper: http://www.technologyreview.com/view/426712/pac-man-proved-np-hard-by-computational-complexity-theory/

    I downloaded the paper and skimmed it (just to see if it covered Centipede; it didn’t) and it looks interesting.

Comments are closed.