My connect 4 AI has improved yet again. This time around I just tweaked it so that I compute the full score for each state in the BFS potion of the tree and sort each group. With this improvement, I'm running to a depth of 12 in less than 30 seconds. I've still got a bit of tuning to do (some ad-hoc testing shows that running the BFS to a depth of 3 is several times faster than a depth of 4 on the single core machine I was using)
After that's done, the next bit is to figure out how to do a sliding depth scale to leverage all the remaining time. I expect that the progress vs time plot is going to be rather interesting.
On another front, I am back in the lead; I figured out how to beat the AI while playing second!