Хм, писал такую же игру под Windows, использовал минимаксный алгоритм.
С регулируемой глубиной-сложностью.
Правда поле у меня было 8х8. При глубине поиска в 4 хода выиграть у бота уже практически невозможно, только если повезет. Но и задлумываться он начинает уже на несколько минут.
Вечером поищу приложение.
Залил сюда: rghost.ru/7bhjV8tXx
Немного запамятовал, все-таки на 4 уровне сложности думает быстро, а 5й был выпилен как раз из-за долгих ходов
Приложение было написано аж в 11 году, просто для интереса, как раз для разработки ИИ к игре
Пишем тактическую игру про цифры под Android