Игра в искусственный интеллект
Игра - важная область искусственного интеллекта. Игры не требуют особых знаний; единственное, что нам нужно предоставить, - это правила, легальные ходы и условия победы или поражения в игре.
Оба игрока пытаются выиграть игру. Итак, они оба стараются сделать лучший ход на каждом шагу. Такие методы поиска, как BFS (поиск в ширину), не являются точными для этого, поскольку фактор ветвления очень высок, поэтому поиск займет много времени. Итак, нам нужны другие процедуры поиска, которые улучшат -
- Сгенерируйте процедуру так, чтобы генерировались только хорошие ходы.
- Процедура тестирования, чтобы в первую очередь можно было изучить лучший ход.
Самым распространенным методом поиска в играх является процедура поиска Minimax . Это процедура поиска с ограничением по глубине. Он используется для таких игр, как шахматы и крестики-нолики.
Алгоритм Minimax использует две функции -
MOVEGEN: генерирует все возможные ходы, которые могут быть сгенерированы из текущей позиции.
СТАТИЧЕСКАЯ ОЦЕНКА: возвращает значение, зависящее от качества с точки зрения двух игроков.
Этот алгоритм рассчитан на двух игроков, поэтому мы называем первого игрока PLAYER1, а второго игрока PLAYER2. Значение каждого узла копируется из его дочерних узлов. Для PLAYER1 резервное значение - это максимальное значение его дочерних элементов, а для PLAYER2 резервное значение - это минимальное значение его дочерних элементов. Он обеспечивает наиболее многообещающий ход для ИГРОКА1, при условии, что ИГРОК 2 сделал лучший ход. Это рекурсивный алгоритм, так как на каждом уровне выполняется одна и та же процедура.
Рисунок 1: Перед резервным копированием значений
Рисунок 2: После резервного копирования значений
Мы предполагаем, что PLAYER1 начнет игру. Генерируется 4 уровня. Значение для узлов H, I, J, K, L, M, N, O предоставляется функцией STATICEVALUATION. Уровень 3 - это максимальный уровень, поэтому все узлы уровня 3 будут принимать максимальные значения своих дочерних элементов. Уровень 2 - это минимальный уровень, поэтому все его узлы будут принимать минимальные значения своих дочерних элементов. Этот процесс продолжается. Значение A равно 23. Это означает, что A должен выбрать ход C, чтобы выиграть.
Ссылка: Искусственный интеллект от Rich and Knight