В настоящее время я реализую черновой вариант сервера онлайн-игры в Eralang. (Мобильная игра). У меня проблема с подходом ИИ. (будь то подход minmax, генетический алгоритм или любой другой). Также возникла проблема с определением правильной эвристической функции. По сути, мне нужна идея, как начать реализацию, учитывая язык, ограниченное количество ресурсов и время ответа сервера (TIME OUT), поскольку это мобильная онлайн-игра.
Требуются некоторые идеи об алгоритме и эвристической функции.
Как говорил мой профессор искусственного интеллекта: в игровом ИИ основная разница в производительности программ заключается в деталях, а не в используемом алгоритме. Алгоритмы, используемые для этих настольных игр, обычно состоят из 20-30 строк, что делает движок искусственного интеллекта сильным или слабым, так это способность разработчика сокращать пространство поиска за счет использования деталей игры. Это можно сделать эффективно только при хорошем знании конкретной игры.
У Checkers есть среднее пространство для поиска (и фактически оно уже было полностью решено), но это хорошая отправная точка для начала изучения искусственного интеллекта для настольных игр. По этой причине я предлагаю вам начать с классического алгоритма обрезки альфа-бета.
Но, как я уже говорил, выбрать алгоритм составляет всего 10% работы. Детали гораздо важнее, поэтому давайте посмотрим на них:
Эвристическая функция: это важный момент. Эвристическая функция должна быть быстрой и простой, чтобы вычислять и хорошо описывать значение данного состояния. Обычно эвристическая функция - это просто взвешенная сумма набора характеристик. В этой статье вы можете найти простая эвристическая функция (плюс генетический способ ее настройки), использующая такие функции, как количество фигур, количество королей и значение мобильности (количество разрешенных ходов для каждого игрока). Еще один совет: эвристические функции должны возвращать целочисленные значения: глупо отдавать предпочтение ветви только для разницы в 0,0003, поэтому лучше округлить эвристику до целых значений.
Использование симметрии: если вы можете обнаружить симметрию в положении доски, необходимо принять ее во внимание! В шашках не так много симметрии, но я думаю, что еще можно кое-что сделать.
Предварительное вычисление: вот так решаются шашки. :) Но явно не обязательно все хранить. Шахматный ИИ обычно имеет библиотеку дебютов и библиотеку концов игры. Это предварительно вычисленные действия (или действия на основе правил), которые позволяют вашему программному обеспечению избежать большого количества вычислений на начальной и конечной фазах.
Изучите расслабленную (обманутую) проблему: это огромные советы, которые мне очень помогают. Например, вы можете предположить, что можете сделать два хода подряд, в то время как ваш оппонент ничего не делает. Если вы не можете достичь хорошей позиции с помощью читерства, тогда вы не сможете достичь хорошей позиции в обычной игре (с оппонентом, который пытается противостоять вам), и вы можете просто отказаться от этого пути.
Это всего лишь небольшой совет, который я могу дать вам для решения этой проблемы. Я не могу быть полным, потому что это действительно большая область, но я надеюсь, что вы уловили суть. Благодаря опыту вы найдете новые и лучшие идеи. :)
По вопросу, связанному со временем: ограниченные по времени движки ИИ используют итеративную версию с углублением альфа-бета-алгоритма отсечения (в эту статью, вы можете найти подробную информацию и дополнительные материалы). Этот подход имеет два основных преимущества: вы можете остановить вычисления в любой момент и можете использовать предыдущие итерации для улучшения эвристики поиска в следующих. Кроме того, если вам придется перезапускать поиск несколько раз, это определенно превосходит традиционный алгоритм отсечения альфа-бета.
Я надеюсь, вы найдете это полезным.
