Идеи для простого и полезного ИИ для игры отелло (aka: reversi)
Привет Где я могу найти информацию о том, как реализовать ИИ для этой игры. Никогда раньше не делал ИИ.
Ищете рекомендации для лучших и простых подходов Спасибо
5 ответов
Алгоритм Negamax или минимакс прост и должен работать прилично.
Чтобы получить более высокую игру, вам нужно добавить эвристику, но простой двухходовой negamax легко реализовать и быстро реализовать.
Как и почти в каждой настольной игре, вы должны (а) оценить, насколько хорошая позиция, и (б) найти ходы, которые приведут к позициям, которые подходят вам.
Отелло немного отличается от других игр, таких как шахматы, тем, что (а) немного сложнее. Вы не можете легко определить, какие позиции хороши, потому что столы могут очень быстро развернуться. Однако, если вы только начинаете, хорошая эвристика
- Высокоценные угловые поля
- Сильно наказывать, принимая поля рядом с углами
- Оцените другие пограничные плитки выше, чем оставшиеся плитки
- Постарайтесь минимизировать количество ходов, которые может сделать противник
Для (b) вы можете использовать стандартный алгоритм поиска дерева игр, такой как Minimax или Alpha-Beta Pruning. Есть много разных на выбор.
Майкл Буро, который написал Logistello, одну из (ранее?) Сильнейших программ, играющих на отелло, написал несколько увлекательных статей на эту тему. Чтобы определить, насколько хорошая позиция, он сравнивает шаблоны на доске (каждый ранг, каждый файл, все шаблоны диагоналей) с шаблонами в базе данных, ранее изученной программой. Для поиска желаемых результатов он использует алгоритм поиска, который называется Multi-Prob Cut.
Ссылки, которые, вероятно, будут полезны:
Ну, на самом деле, Отелло является примером для игры, где Minmax/Negamax не очень хорошо работают, потому что вам нужна эвристика для оценки промежуточных состояний игры, что сложно в Отелло. Взгляните на поиск дерева Монте-Карло (MCTS). Это должно работать хорошо. На самом деле, я сам внедрил очень простой механизм, вдохновленный MCTS, и он побил все онлайн-ИИ, которые я тестировал до сих пор (в то время как ИИ делает ход за очень короткое время: 2 секунды). Механизм работает следующим образом: (a) получить все возможные ходы для текущего игрока (b) выбрать один из случайных (c) поочередно играть в игру с абсолютно случайными (действительными) ходами, пока игра не закончится. (d) оцените результат игры (e) добавьте это значение к итоговому баллу хода, выбранного на этапе (b) (f), добавьте 1 к числу посещений для хода, выбранного на этапе (b) (g), перейдите к (б) если осталось время (я дал алгоритм 2 секунды) (h) сделать ход с наибольшим средним баллом (итоговая оценка / количество посещений)
Некоторые оптимизации довольно очевидны, например, немедленное выполнение перемещения, если есть только одна, которая является допустимой, или ограничение количества случайных симуляций в дополнение к ограничению по времени (например, 2000 за допустимое движение или около того).
Опять же, это не MCTS, а всего лишь последняя часть MCTS, но она работает довольно хорошо.
Привет, погремушка
"Искусственный интеллект - современный подход" Рассела / Норвига - хорошая отправная точка для изучения теории игр, аи, эвристики и связанных с ними вещей. Посмотрите здесь: http://aima.cs.berkeley.edu/
Исходный код доступен здесь для Logistello, которая была лучшей игрой в городе десять лет назад.