In one of my many searches I came across a connect 4 game that used a simple Min/Max algorithm as its AI. I believe I found this at PSC (Planet-source-code.com). A search of the site or your favorite search engine should reveal some interesting results.

However, for keeping track of the play area for connect 4, a simple two dimensional boolean array or a two dimensional byte array should be sufficient...

Good Luck