Flex: Would a computational engine for a Connect-4 type game be too slow?

Question

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?

Answer 1

Connect-4 has been solved mathmatically, so your AI could win every time (if it plays first) with the right database of correct moves.

Otherwise, your brute-force 'looking ahead' scenario would not be as easy as you suggest: connect-4 has a 7 wide by 6 high board (yours may be different) - so the longest game could take 42 turns (7 possible moves each time, or fewer towards the end), so a perfect engine might potentially need nearly 7^42 moves (ie more than 3x10^35)... this is obviously a LOT more than 16 million.

It would still be an interesting project, though...