Реализация игры "Клетки"

[iflamberg]

2Gbee: В данном случае это не поиск пути, а поиск решения скорее. ИИ перебирает варианты, скажем "а что если поставить точку здесь", каждому такому варианту назначает "цену", т.е. насколько такой вариант эффективен. Потом для каждого варианта продолжает алгоритм "а что если поставить точку здесь, а потом еще одну здесь", и назначает цену уже для такой цепочки действий. И так до определенной глубины. Фактически строится дерево вариантов и это очень похоже на поиск пути. Скажем, принципы A* здесь тоже применимы.

[GBee]

iflamberg, какую точку? Зачем дерево? Можно мне на пальцах объяснить, вот буквально на примере этой игры? Ставим черточку так, чтобы не дать противнику закрыть клетку.
Мы же об одной игре говорим?

[iflamberg]

Да без разницы черточки или точки. В мои школьные годы в этой игре ставили точки, но суть не меняется. ИИ для такой игры делается так же, как и для шахмат, или шашек.
Если у тебя ИИ будет думать "плоско", только об одном ходе вперед, то играть он будет из рук вон плохо. Он должен уметь оценивать ситуацию в будущее, как человек. "Так, надо помешать противнику закрыть этот квадрат. Но, если поставить черточку именно тут, а потом еще здесь, то через два хода у противника случится "вилка", какое бы решение он не выбрал, я смогу закрыть эту или эту клетку. Выбираю это решение". Поэтому строится дерево возможных решений, каждому решению назначается цена, или вес, и выполняется решение с наибольшим весом/ценой.

[GBee]

Точки - другая игра. Я всегда думал, что проф шахматы очень шаблонизированная игра. В этой игре он плохо сыграть не сможет думая плоско. Реально сыграйте в нее с кем нить, хоть сам с собой. Она как крестики нолики - есть пара выигрышных комбинаций для крестиков. и зная их нолики всегда могут сводить партию к ничьей.

[iflamberg]

Шахматы или не шахматы - без разницы. Это универсальный алгоритм. Вот тут http://www.youtube.com/watch?feature...&v=p32hELKeYXI видео прототипа игрушки над которой я работаю. Суть в том, что каждому из игроков каждую секунду в инвентарь добавляются плитки, которые можно выкладывать на игровое поле, соединяя друг с другом; и башни, которые стреляют строго прямо перед собой.
Как видишь не очень похоже на шахматы - это игра в реальном времени и совсем по другим правилам. Но тем не менее используется точно такой же алгоритм. Только вот функция оценки эффективности еще не отлажена достаточно хорошо.

[GBee]

Не сегодня я не выспался, видимо. Ничего не понимаю. Что за алгоритм то? Алгоритм поиска решения? Какие шаги конкретно в нем, как он может быть универсальным?

Я к чему интересуюсь - мне матч3 ботов надо улучшать. А путей интересных не вижу.

[iflamberg]

Ты поспи. А потом открой гугл и почитай последовательно несколько статей по теме "алгоритмы поиск в ширину" и "поиск пути A*". А потом представь, как бы эти алгоритмы можно было бы переложить не на поиск пути в лабиринте, а на поиск наилучшего решения для ИИ игрушки. Задача одна и та же. В лабиринте возможных вариантов найти наиболее короткий, приводящий к победе.

[wvxvw]

Я как бы не говорил ничего про поиск пути... я говорил про поиск по деревям. Дерево в этом контексте - это разновидность направленного соединенного графа без зацикливаний. В контексте ИИ, каждый узел такого дерева - это состояние решения. Листья - это результаты (целевые состояния решения). Задача алгоритма (программы играющей за ИИ) заключается в том, чтобы найти ветку ведущую к состоянию обладающeму желаемыми свойствами (в нашем случае - состоянию в котором больше клеток принадлежит ИИ).
Есть стратегии, как найти такое состояние. Как правило такие стратегии предполагают наличие функции, которая может оценить промежуточное состояние, тогда можно оптимизировать алгоритм.
Если такую функцию найти не удается, то остаются варианты "поиск вглубину" - очень еффективный по памяти, но совершенно нееффективный по времени и поиск вширину - очень эффективный по времени, но очень нееффективный по памяти. В большинстве задач поиск вширину просто не применим т.как память более дорогой ресурс, чем время, и кроме того, конечный.

[Котяра]

Я как-то писал логику бота в игре, по сложности малоуступающей шахматам, а то и превосходящей...
Смысл тут. Очень большое поле для подумать.
Но написал на основе перебора вариантов и предположительного предугадывания действий соперников.
В итоге оказалось, что бот очень умный) пришлось умность рандомайзить. Вернее ввести для разных ботов степень "умности".
Т.е. простой пират был "тупой", а вот боссы уже считали вовсю.
вот тупые боты:
http://www.islandsworld.ru/sea_battle.html

PS - для выбора лучшего варианта юзал astar.
Сложность была в составлении графа в основном.

[iflamberg]

Я как бы не говорил ничего про поиск пути... я говорил про поиск по деревям.

Ну, я пытался GBee аналогию объяснить: почему поиск эффективного решения АИ игры и поиск выхода из лабиринта - это, по сути, одна и та же задача, решаемая в обоих случаях построением графа.

2Котяра: ну, сейчас в крутых шахматных программах используется намного более сложные алгоритмы, там и словари эвристик и чего только нет, так что тебе есть еще куда стремиться =)