Найти оптимальную / достаточно хорошую стратегию и ИИ для игры «Близость»?

Question

' Proximity ' - стратегическая игра территориального доминирования, похожая на Othello, Go и Risk.Два игрока, использует гекс 10x12 сетки.Игра, изобретенная Брайаном Кэйблом в 2007 году.

Кажется, что это достойная игра для обсуждения а) оптимального алгоритма, б) как построить ИИ.
Стратегии будут вероятностнымиили на основе эвристики, из-за фактора случайности и безумного фактора ветвления (20 ^ 120).Так что будет сложно сравнивать объективно. Максимальное время вычисления в 5 секунд на ход кажется разумным => это исключает все попытки перебора. (Играйте в ИИ игры на уровне эксперта, чтобы почувствовать - он делает очень хорошую работу, основываясь нанемного простой эвристики)

Игра: Флэш-версия здесь , iPhone версия iProximity здесь и множество копий в других местах навеб-правила: здесь

Объект : иметь контроль над большинством армий после размещения всех плиток.Вы начинаете с пустой гексборд.Каждый ход вы получаете случайно пронумерованный тайл (значение от 1 до 20 армий) для размещения на любом свободном месте на доске.Если эта плитка соседствует с любой плиткой ЭЛЛИ, она укрепит каждую из защит этой плитки +1 (до максимального значения 20).Если он находится рядом с какими-либо вражескими тайлами, он получит контроль над ними, ЕСЛИ его номер больше, чем номер на вражеском тайле.

Мысли о стратегии: Вот некоторые начальные мысли;установка искусственного интеллекта компьютера на эксперта, вероятно, многому научит:

1. минимизация вашего периметра представляется хорошей стратегией, чтобы предотвратить сальто и минимизировать наихудший урон
2. , как в Go,Оставлять дыры внутри вашей формации смертельно, только в случае с гекс-сеткой, потому что вы можете потерять армии на расстоянии до 6 клеток за один ход
3. плитки с низким номером - это ответственность, поэтому размещайте их подальше от вашей основной территории, возле доски края и разбросаны.Вы также можете использовать плитки с низким номером, чтобы закрыть отверстия в вашей формации, или сделать небольшие усиления по периметру, которые противник не будет беспокоить при атаке.
4. треугольная формация из трех частей сильна, так как они взаимно усиливают друг друга, а также уменьшить периметр
5. Каждая плитка может быть перевернута не более 6 раз, то есть когда соседние плитки заняты.Контроль над формацией может течь взад и вперед.Иногда вы теряете часть строения и закрываете все дыры, чтобы сделать эту часть доски «мертвой» и заблокировать свою территорию / предотвратить дальнейшие потери.
6. Плитки с низким номером - это очевидные, но невысокие обязательства, но плитки с высокими номерами могут быть большими обязательствами, если их перевернуть (что сложнее).Одна удачная игра с тайлом из 20 армий может вызвать размах 200 (от +100 до -100 армий).Таким образом, размещение плиток будет иметь как наступательные, так и оборонительные соображения.

Комментарий 1,2,4, похоже, напоминает минимаксную стратегию, в которой мы минимизируем максимально возможную возможную потерю (измененную некоторым вероятностным рассмотрением значения ßоппонент может получить от 1..20, то есть структура, которая может быть перевернута только плиткой с = 20, «почти неуязвима».) Я не понимаю, каковы последствия комментариев 3,5,6 для оптимальной стратегии.Интересуют комментарии игроков в Go, Chess или Othello.

(Продолжение ProximityHD для XBox Live, позволяет локальному многопользовательскому режиму для 4-х игроков или -конкурентоспособности увеличивает коэффициент ветвления, поскольку теперь у вас есть5 плиток в вашей руке в любой момент времени, из которых вы можете играть только одну. Укрепление плиток союзников увеличено до +2 на каждого союзника.)

Answer 1

Бывший член группы U GAMES здесь.

Этот фактор разветвления безумен. Гораздо хуже, чем Го.

По сути, вы обручены.

Проблема этой игры в том, что она не является детерминированной из-за выбора случайной плитки. Это фактически добавляет еще один слой узлов между каждым существующим слоем узлов в дереве. Вас заинтересуют мои публикации на * -Minimax , чтобы узнать о методах поиска в стохастических областях.

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

Answer 2

Для общих алгоритмов я бы посоветовал вам проверить исследование, проведенное группой AI Games Университета Альберты: http://games.cs.ualberta.ca Многие алгоритмы гарантируют нахождение оптимальных политик. Однако я сомневаюсь, что вы действительно заинтересованы в поиске оптимального, стремитесь к «достаточно хорошему», если вы не хотите продавать эту игру в Корее: D

Из вашего описания я понял, что игра состоит из двух игроков с полной наблюдаемостью, то есть без скрытых юнитов и такими полностью детерминированными, т.е. результаты действий игрока не требуют броска, тогда вам следует взглянуть на реальный минимаксные производные с ограниченным временем поиска, предложенные ребятами из U Alberta. Тем не менее, возможность также связывать глубину резервных копий функции value, возможно, будет хорошим способом добавить «уровень сложности» в вашу игру. Они проделали некоторую работу - немного подозрительно - по сэмплированию пространства поиска для улучшения оценок функции стоимости.

О разделе «стратегия», который вы описываете: в рамках, о котором я упоминаю, вам придется закодировать эти знания как функцию оценки. Посмотрите на работы Михаэля Бюро и других, в том числе и в группе U Alberta, примеры такой инженерии знаний.

Другая возможность состояла бы в том, чтобы представить проблему как проблему обучения подкреплению, где движения противника компилируются как «промежуточные состояния». Посмотрите на это в книге Барто и Саттона: http://webdocs.cs.ualberta.ca/~sutton/book/the-book.html Однако функция значения для задачи RL, возникающей в результате такой компиляции, может оказаться немного трудной для оптимального решения - число состояний взорвется, как H-бомба , Однако, если вы видите, как использовать факторизованное представление, все может быть намного проще. И ваша «стратегия» может быть закодирована как некоторая функция формирования, которая значительно ускорит процесс обучения.

РЕДАКТИРОВАТЬ: чертовски английские предлоги