Помимо всего перечисленного, есть и некоторые нестандартные алгоритмы, отсящиеся к искусственному интеллекту:

1) Сделать нейронную сеть. В качестве входа давать некоторую оценку исходной позиции( сколько у тебя три подряд, у врага, сколько у тебя 4 подряд, и т.д.) - в качестве выхода - оценка позиции от 0 до 1. Потом выбирать позицию с макс. очками. Придётся эту сетку долго тренировать(давать исходные данные, напрмер против стандартного алгоритма или друг с другом), а затем просчитать её.

2) Генетические алгоритмы: придумываем примитивный язык программирования позволяющий складывать и вычитать. Генерируем случайную программу, которая на входе берёт всё поле, а на выход - куда ставить. Генерируется некоторое количетсво таких программ, они играют друг с другом и с эталоном(стандартной программой). Дольше всех продержавшиеся программы с небольщими случайными изменениями , новые случайные и перекрещивание этих проблем берём в следующее поколение. С некоторого поколения получатся достаточно неплохие программы

3) Кластерный анализ: разбиваем пространство на некоторые группы (кластеры). Например доску 20*20 можно ещё дополнить диагоналями, количеством кестиков и ноликов на горизонтали,вертикали,всех диагонолях - создаём многомерное пространство. Далее разбиваем возможные комбинации на разные группы(возможные группы- следующим ходом выигрыш, следующим ходом проигрыш,необходимо атаковать врага(строить 3 и 4), необходимо защищаться(не давать врагу строить 3 и 4)

4) Нечёткая логика. Посколько есть разные вссыказывания насчёт игры( не давать врагу сторить слищком много открытых троек, стараться увеличавть свои но не помогаю врашу делать четвёртуи и так далее), то применения нечёткой логики позволит достаточно просто сформулировать правила как следует ходить в той или иной ситуации... правда где найти специалистов с их советами?
5) Эмулирование поведения муравьёв,эмулирование отжига - к сожалению сразу не соображу,как это здесь можно применить )), однако для расстановки n ферзей на доске n на n и для задачи коммиваяжора они работают классно.

Ну а если всё вышепречисленное кажется надуманным и неправильным, то подойдёт и таблица дебютов - стандартные позиции со всем возможными ходами на начальном этапе игры