Комментарии 6
Надо доработать алгоритм, чтобы он не просто подбирал себе слово, но ещё и с таким условием, чтобы противнику не подставить возможность длинного слова. Иначе так и будет получаться Полосование — ххх — ххх — ххх — ххх — голосование.
По крайней мере мы всегда играли учитывая этот фактор.
По крайней мере мы всегда играли учитывая этот фактор.
Это так, конечно. Но при попытке просматривать вглубь мы упремся в экспоненциально растущее число вариантов, и тут не хватит никакой скорости алгоритма. Особенно в приведенном Вами примере — через 4 слова!!!
К сожалению в логе нет указаний какая буква куда была поставлена, но подозреваю, что слово «голосование» было нельзя поставить (не хватало двух букв) до постановки слова «полоток», а на этом этапе достаточно просматривать только один шаг вперед. Если же использовать это слово можно было раньше, тонепонятно почему оно не было использовано.
В игре с человеком можно рассчитывать на какое-либо узкоспециальное слово, которого с большой долей вероятности не знает оппонент и подготовить его для себя, но в игре против «всезнающего» компьютера на это рассчитывать нельзя — только хардкор, только блокирование длинных вариантов для ожидаемого хода противника.
Хватит скорости, и давным давно уже сделано. И не на 4 хода вперед, а на 8-12. Называется алгоритм: минимакс + альфа бета отсечения(самый важный) + другие оптимизации. Почитайте вторую ссылку, приведенную вами(«алгоритм и тактика поиска слов»).
Да, это уже социальная инженерия! Еще один разрез, в котором можно оптимизировать, кстати, — это учет неравномерностей словаря. Я (и многие) решают подобные задачи универсальным образом, то есть для работы с любым количеством любых строк в качестве слов языка. Но можно привлекать и более изощренные методики)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Как я гонял Балду-2, или в поисках оптимального алгоритма