Алгоритм и тактика поиска слов в игре Балда

[chibiryaev]

Обычно то, что выдает программа не всегда является оптимальной последовательностью ходов.
Дело в том, что в приложении балда39 читеров банят уже хотя бы по факту играния «нелепыми» словами (куэнковец, денедж, ньяя и др.). Опытные читеры никогда не ходят такими словами и вообще ходят только теми, которые знают сами. И потом, на ход ведь дается не 5 секунд, а минута или 2, за это время можно и самому успеть проанализировать игровую ситуацию (отсеивая нелепые слова)

Сколько у вас время поиска на большом поле наполовину заполненном (на один только ход вперед)? (Ну там 30х30 или большем поле)

[Pro5]

Ну я бы не назвал «нелепые» слова не оптимальными ходами. Какой словарь скормите минимаксу — теми словами он и будет играть. Здесь я хотел рассмотреть только алгоритмы, а не как некоторые игры борются с читерами.

По поводу скорости поиска слов на 1 ход вперед на поле 30x30. Если вы имеете ввиду «полноценный» поиск, то примерно в 36 раз медленней, чем на поле 5x5, что составит десятые доли секунды. А если это поиск «доискивающий» (алгоритм которого я описал в статье), то скорость вобще не будет зависеть от размера поля.

[Pro5]

Идею понял. Тоже интересный подход.

[Pro5]

Нечто подобное я тоже хотел делать поначалу. Строить префиксное дерево начиная его всегда с пустышки. Это лучше и быстрей, чем искать слова с уже поставленных букв. Но был вынужден отказаться от такого подхода потому, что в этом случае нельзя применить «доискивающую» оптимизацию.