Algorithms for Connect 4?
Connect Four was solved in 1988. The first solution was given by Allen and, in the same year, Allis coded VICTOR which actually won the computer-game olympiad in the category of connect four. 

I would suggest you to go to Victor Allis' PhD who graduated in September 1994. You can get a copy of his PhD here. In Section 6.3.2 Connect-Four (page 163) you can actually read the following:

"In September 1988, James Allen determined the game-theoretic value through a brute-force search (Allen, 1998): a win for the player to move first. A few weeks later, in October 1988, connect-four was solved through a knowledge-based approach, resulting in the tournament program VICTOR (Allis, 1988; Uiterwijk et al., 1989a; Uiterwijk et al., 1989b). Recently John Tromp has calculated the game-theoretic value for all 8-ply connect-four positions (Tromp, 1993)."

You will find all the bibliographical references in the Bibliography chapter of the PhD in case you need further information. Of these, the most relevant to your case is Allis (1998). A Knowledge-Based Approach of Connect-Four. The Game is Solved: White Wins. M.Sc. Thesis, Faculty of Mathematics and Computer Science, Vrije Universiteit, Amsterdam. Go to Chapter 6 and you'll discover that this game can be optimally solved just by considering a number of rules. And this take almost no time!

So, my first suggestion would be for you to consider none of the approaches you mention but a knowledge-based approach instead. From what I remember when I studied these works, most of these rules should be easy to generalize to connect six though it might be the case that you need additional ones. However, if all you want is a computer-game to give a quick reasonable response, this is definitely the way to go.

Additionally, in case you are interested in trying to extend the results by Tromp that Allis mentions in the exceprt I was showing above or even to strongly solve the game (according to Jonathan Schaeffer's taxonomy this implies that you are able to derive the optimal move to any legal configuration of the game), then you should read some of the latest works by Stefan Edelkamp and Damian Sulewski where they use GPUs for optimally traversing huge state spaces and even optimally solving some problems.

Hope this helps,