OK, I was just fooling around in my spare time and have made this cool interface and game-playing code for a Connect-4 type game, written in Flex and playable by 2 human players in Flash. It accurately detects wins, etc. I'm smart enough to know that I've done the easy part.

Before I dig into an AI for game play, I wanted to ask if this is the kind of thing that can really be handled computationally by a Flash plugin. It seems to me that for every turn up until the end there are 8 possible moves, 8 responses to each move, etc. So wouldn't a perfect engine have to be able to potentially see 8^8 moves (over 16 million), and a fairly good engine see up to a million? I don't know game coding so this is new to me. What's a reasonable move horizon for such a game to be able to see?