Эта заметка посвящена игровым главам Udacity AI Nanograde.
Тип проблем с ИИ
- Полностью наблюдаемый против частично наблюдаемого
- Детерминированный против стохастического
- Дискретный и непрерывный
- Доброкачественный (действия принимает только один человек) против состязательного
Минимаксный алгоритм
- Выберите выигрышную стратегию. В изолированной игре выигрышной стратегией может быть максимизация возможных ходов на каждом уровне дерева игры.
- На каждом уровне дерева игры предполагается, что игрок выберет ту ветвь, которая максимизирует преимущества (противник выберет ветвь, минимизирующую эффект выигрышной стратегии)
Фактор ветвления
- сколько ветвей в среднем будет иметь каждый узел
Ограниченный по глубине поиск
- Используя фактор ветвления и ограничение количества узлов, которые можно искать каждый ход, мы можем определить, насколько глубоким может быть поиск.
Спокойный поиск
- Если решение сильно различается на двух соседних уровнях, это означает, что критическое решение принимается между этими двумя уровнями.
- Таким образом, мы будем использовать неактивный поиск для более глубокого поиска.
Итеративное углубление
- После завершения поиска глубины N, затем исследования дерева глубины N+1
- Поскольку во временной сложности преобладает поиск на последнем уровне, итеративное углубление не увеличит временную сложность по сравнению с обычным поиском.
Эффект горизонта
- Выбор, очевидный для человека, может быть неочевиден для ИИ
Альфа-бета-обрезка
- алгоритм состязательного поиска, который стремится уменьшить количество узлов в дереве поиска.
- Повысить эффективность
- Плохо работает с мультиплеером
Тад в стороне
- ИИ = умные решения экспоненциальных проблем
