Как шахматные программы находят лучшие ходы? ведь невозможно найти лучший ход не перебрав всех комбинациий?

Answer 1

Для этого применяется компьютерная оценка позиции по десяткам параметров и альфа-бета отсечение. Для тебя это слишком сложно, не бери в голову.
А крестики-нолики на бесконечном поле (пять в ряд) давным-давно решены. Начинающий выигрывает. Так что впустую тратишь время.

Answer 2

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