Дизайн AI настольной игры: выбор контейнера данных STL - PullRequest
2 голосов
/ 25 марта 2011

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

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

Мои вопросы:
1. Логичен ли мой подход? (а если нет, то можете ли вы дать мне несколько советов, как это улучшить?))
2. Какой контейнер STL является наиболее подходящим для моих нужд? Я собираюсь использовать массив символов (конфигурация платы) в качестве ключа и счет в качестве значения.
3. Можете ли вы дать несколько советов, как сделать мой ИИ убийственным? :)

изменить: подробнее:
Доска 10х10, на ней два игрока, каждый с 10 пешками. Правила очень похожи на шашки.

Ответы [ 3 ]

4 голосов
/ 25 марта 2011

Да, обычно оцениваемые доски хранятся в хеш-таблице, которая называется таблица транспонирования . Контейнер STL может быть std::vector. В общем случае вы должны создать хеш-функцию (например, хеширование zobrist ). Функция хеширования вычисляет значение хеша конкретной платы. Результатом hash_value modulo HASH_TABLE_SIZE будет индекс для std::vector.

Запись таблицы транспонирования может содержать больше информации, чем только оценка доски и best-move , вы также можете сохранить, на какую глубину оценивается доска и если оценочный балл (если вы выполняете поиск alpha-beta ) равен

  • точный
  • Верхняя граница
  • или нижняя граница

Я могу порекомендовать сайт chessprogramming , где я многому научился. Ищите термины альфа-бета , таблица транспонирования , хеширование зобриста , итерационное углубление . Есть также хорошие статьи для дальнейшего чтения:

2 голосов
/ 25 марта 2011

Ваш логический подход в порядке, вы должны прочитать и, возможно, попробовать использовать алгоритм Minimax:

http://en.wikipedia.org/wiki/Minimax

Я думаю, что, за исключением игры Tic Tac Toe, число состояний будетслишком большой, вы должны поработать над ускорением счета.

1 голос
/ 26 марта 2011

Шахматы и шашки можно сделать с помощью этого подхода, но я бы не рекомендовал его.

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

Причина, по которой я бы не пошел по этому пути, заключается в том, что это обычно не весело.Люди понимают это интуитивно и чувствуют, что это несправедливо.Я написал игру «Connect 4», которая была непобедима, но основывалась на правилах, а не на игровом поле.Это было скучно.Каждый шаг был встречен с одинаковым ответом.Я думаю, это то, что происходит в этом подходе.Кроме того, это зависит от того, почему вы это делаете.Если это для изучения ИИ, очень мало ИИ делается таким образом.Если это веселая игра, то обычно это не так.Если это было сделано по тем причинам, по которым был создан Deep Blue, чтобы расширить границы возможностей компьютера, то конечно.

Я бы либо использовал индивидуальный ИИ на основе кусочков, а затем выбрал бы тот, у которого самый убедительный аргумент, илиЯ бы использовал вариант восхождения на гору и поставил на доску своего рода стратегическую высоту.Это зависит от того, сколько частей поддержки дают друг другу.Для индивидуального ИИ я бы использовал нейронные сети.

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

...