Идеи для простого и полезного ИИ для игры отелло (aka: reversi)

Question

Привет Где я могу найти информацию о том, как реализовать ИИ для этой игры.Никогда раньше не делал ИИ любого рода.

Ищем рекомендации для лучших и простых подходов. Спасибо

Answer 1

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

Отелло немного отличается от других игр, таких как шахматы, в том, что (а) немного сложно. Вы не можете легко определить, какие позиции хороши, потому что столы могут очень быстро развернуться. Однако, если вы только начинаете, хорошая эвристика это

• Угловые поля с высокими значениями
• Сильно наказывать захват полей рядом с углами
• Оценить другие граничные плитки выше, чем оставшиеся плитки
• Постарайтесь свести к минимуму количество ходов, которые может сделать противник

Для (b) вы можете использовать стандартный алгоритм поиска дерева игр, такой как Минимакс или Альфа-бета-обрезка . Есть много разных на выбор.

Майкл Буро, который написал Logistello, одну из (ранее?) Сильнейших программ, играющих на отелло, написал несколько увлекательных статей на эту тему. Чтобы определить, насколько хорошая позиция, он сравнивает шаблоны на доске (каждый ранг, каждый файл, все шаблоны диагоналей) с шаблонами в базе данных, ранее изученной программой. Для поиска желаемых результатов он использует алгоритм поиска, который называется Multi-Prob Cut.

Ссылки, которые, вероятно, будут полезны:

• Домашняя страница Logistello
• Отелло на AITopics .

Answer 2

Ну, на самом деле, Отелло является примером для игры, где Minmax / Negamax не очень хорошо работают, потому что вам нужна эвристика для оценки промежуточных состояний игры, что сложно в Отелло.Посмотрите на поиск дерева Монте-Карло (MCTS).Это должно работать хорошо.На самом деле, я сам внедрил очень простой механизм, вдохновленный MCTS, и он побил все онлайн-ИИ, которые я тестировал до сих пор (в то время как ИИ делает ход за очень короткое время: 2 секунды).Механизм работает следующим образом: (а) получить все возможные ходы для текущего игрока (б) выбрать один из случайных (в) поочередно играть в игру с абсолютно случайными (действительными) ходами, пока игра не закончится.(d) оцените результат игры (e) добавьте это значение к итоговому баллу хода, выбранного на этапе (b) (f), добавьте 1 к числу посещений для хода, выбранного на этапе (b) (g), перейдите к (б) если осталось время (я дал алгоритм 2 секунды) (h) сделать ход с наивысшим средним баллом (общее количество баллов / количество посещений)

Некоторые оптимизации вполне очевидны, например, сделать шаг немедленно, еслиесть только один, который действителен или ограничивает количество случайных симуляций в дополнение к временному ограничению (например, 2000 за действительный ход или около того).

Опять же, это не MCTS, а просто последняя часть MCTS,но это работает довольно хорошо.

Привет, погремушка

Answer 3

Рассел / Norvig "Искусственный интеллект - современный подход" является хорошей отправной точкой для изучения теории игр, ai, эвристики и связанных с ними вещей.Посмотрите здесь: http://aima.cs.berkeley.edu/

Answer 4

Алгоритм Negamax или минимакс прост и должен работать прилично.

Чтобы перейти к более высокой игре, вам нужно добавить эвристику, но простой двухходовый negamax легко реализовать и быстро реализовать.

Answer 5

Исходный код доступен здесь для Logistello, которая была лучшей игрой в городе десять лет назад.