Алгоритм генерации хода для игры Эрудит

[Sleuthhound]

А где сама то игра с этим ИИ?

[AntonRychagov]

В данный момент она проходит тестирование на wap-портале одного из операторов сотовой связи. К сожалению, исходный код я предоставить не могу — NDA никто не отменял. Как только тестирование закончится — появится ссылка ;)

[tirinox]

Статья напомнила мне «The World’s Fastest Scrabble Program» (ANDREW W. APPEL AND GUY J. JACOBSON) аж 88 года. Но там были подробнее расписаны алгоритмы и был упор именно на поиск слов, а не на стратегию выбора хода из возможных. Может, интересующимся пригодится.

Вопрос к автору. А как быть, если у игрока на руках есть универсальные фишки (ака звездочки)? Проводили ли вы какие-то оценки по этому поводу? Когда мне пришлось разрабатывать алгоритм поиска хода в эрудите, я столкнулся с тем, что наличие звездочек приводит к катастрофическому падению производительности, причем одна звезда — еще ничего, две — уже печально, три — хочется напиться с горя, пока ищется ход.

[AntonRychagov]

Разумеется. Все зависит от выбранного алгоритма: если в случае выбора максимального значения звездочки не ударят по производительности, то при полном переборе — увы, проблем не избежать. Навскидку вспоминаю, что как-то полный перебор искал лучший ход порядка 5-10 минут — как раз с тремя звездочками. Способов избежать данную проблему, на мой взгляд, всего два — радикальный и разумный. Радикальный — избавиться от звездочек, разумный — поставить таймаут на полный перебор и запустить выбор максимального значения по истечению этого времени.

P.S.: Я выбрал радикальный :) На WAP-портале всё-же время ответа очень важно.

[begezavr]

Тоже пробовали с другом реализовать сервис-помощник игры в Эрудит. Главный алгоритм реализовали очень быстро, протестил его выходом в топ одной из онлайновых версий игры во Вконтакте :) По-большому счёту осталось только собственно написать сайт, морду сервиса, но как-то отложилось на полку и пол года там уже лежит.

[sunnybear]

интересной будет битва роботов игры в Эрудит :)