Хватит скорости, и давным давно уже сделано. И не на 4 хода вперед, а на 8-12. Называется алгоритм: минимакс + альфа бета отсечения(самый важный) + другие оптимизации. Почитайте вторую ссылку, приведенную вами(«алгоритм и тактика поиска слов»).
Нечто подобное я тоже хотел делать поначалу. Строить префиксное дерево начиная его всегда с пустышки. Это лучше и быстрей, чем искать слова с уже поставленных букв. Но был вынужден отказаться от такого подхода потому, что в этом случае нельзя применить «доискивающую» оптимизацию.
Ну я бы не назвал «нелепые» слова не оптимальными ходами. Какой словарь скормите минимаксу — теми словами он и будет играть. Здесь я хотел рассмотреть только алгоритмы, а не как некоторые игры борются с читерами.
По поводу скорости поиска слов на 1 ход вперед на поле 30x30. Если вы имеете ввиду «полноценный» поиск, то примерно в 36 раз медленней, чем на поле 5x5, что составит десятые доли секунды. А если это поиск «доискивающий» (алгоритм которого я описал в статье), то скорость вобще не будет зависеть от размера поля.
По поводу скорости поиска слов на 1 ход вперед на поле 30x30. Если вы имеете ввиду «полноценный» поиск, то примерно в 36 раз медленней, чем на поле 5x5, что составит десятые доли секунды. А если это поиск «доискивающий» (алгоритм которого я описал в статье), то скорость вобще не будет зависеть от размера поля.