AI boffins take on Angry Birds

Re: What's that, then?

Ever played any sort of Scorched Earth clone or the Worms series?

You've played it then.

It was a cheap (free with adverts for lots of people) game with some basic 2d physics where you fire birds with different properties over obstacles to knock down a house and kill all the "pigs" (green circles with faces) inside.

About the best bit of it is the physics library used, Box2D, which is free and open-source. Since it was free and quite polished and bundled with app stores etc. it became very popular to people who didn't game during the DOS era (because they thought it was "new") and sold millions of copies. But all their spin-offs have to be angry-birds related or they don't sell, because the game itself is nothing special but the brand is now "famous". So you have angry-birds in lots of different locations, with different "types" of birds and even one in space where they've played with the gravity a little. But all attempts to do anything but merchandise angry-birds (everything from Christmas annuals to cuddly toys to a game with a little catapult to fire birds at structures with pigs in them) from the same company fail.

Remember tetris? How everyone went mad for it on Gameboy even though it was already out years before and there were several million clones within a week, and how the creator of Tetris never really went on to do anything else because it was the tetris name that was selling things? Same thing, 20 years later.

Re: Random levels required

For me, the problem is mildly interesting, if they do it properly and have full levels and full physics.

You have only very limited input (angle, power). But the results can be incredibly chaotic given that input (i.e. a tiny pixel either way, or a slight rounding error, and the whole screen collapses in a totally different way).

The problem is, though, that the amount of debris on the screen will be quite high and tracing parabolic paths through it to find a given target (even if you know where that target is), not to mention physics-based rolling and momentum, is extremely tricky. So I don't think that a "naive" interpretation would be interesting enough, or capable of enough. If you're just relying on finding a "magic set" of shots on each level, you might be sadly disappointed if the engine isn't 100% replayable. And to find that magic set, you would need so many attempts that it becomes a laughable task to attempt.

But looking for a path is also complicated, you wouldn't be able to use traditional game theory branching techniques to try to find an optimal path to the goal, there are just too many variations. You are basically looking at a high-level tree controlling, say, which target you actually target, in what order, and modify based on the amount of obstruction to them. However, the actual shots will have to be calculated quite well to be any good.

Worms AI, for example, used to pull off some incredible shots because it knew the end result of the physics was you dying. But it wasn't able to prioritise targets effectively, or know which were the greatest threat, and didn't cope well with obstructions (best way to win, if I remember, was to bury youself underneath the enemy and wait for him to run out of weapons and/or kill himself), and that's a lot more important in this game - if you aim for the wrong target first, or even cause collateral damage elsewhere, you can make it impossible to take out later targets because you've covered them in debris or blocked off access to the optimal parabola.

That said, I don't think it's particularly "new" or "interesting" in terms of AI. We won't be seeing any great computer science come out of it, because almost all the problems involved are "solved", just tricky to do and with huge amounts of analysis required to get it right. And absent that, it's about throwing away the right bits of information and doing things in larger discrete steps rather than analysing every possibility.

It's an interesting kind of "competition", in the everyday sense of the word (i.e. £250 to the winner or whatever), but it's not very interesting in terms of pushing forward AI or finding out anything new. It's just a new application for old techniques and developing some heuristic to optimise those techniques for this particular case.