Слияние кода завершено, страница обновится автоматически
В 2016 году AlphaGo победил ведущего шахматиста Ли Се-Джона, а в 2017 году AlphaGo одержал победу над чемпионом мира Ким И-Су, что привлекло внимание к искусственному интеллекту в шахматах. Однако, AlphaGo, основанный на надзорном обучении, имитирует поведение ведущих шахматистов, и его суть заключается в подражании человеческому стилю игры. В то же время, новое поколение AlphaGo, основанное на усилении обучения и безнадзорном обучении, использует другой подход, начиная с нуля и не изучая исторические партии людей, а вместо этого проводя самоигры и оптимизацию. Новое поколение AlphaGo получило кодовое имя AlphaGo Zero, которое одержало победу над AlphaGo Master со счетом 100-0.
Процесс обучения AlphaGo Zero включает следующие шаги:
AlphaGo Zero использует технологии, которые в сущности имитируют поведение MCTS (Монте-Карло дерева поиска) с помощью нейронной сети. Однако, MCTS не всегда находит оптимальное решение, поэтому нейронная сеть должна имитировать MCTS 700 000 раз, чтобы найти "оптимальную нейронную сеть", которая была бы обучена MCTS, и отбросить худшие случаи, найденные MCTS, и искать оптимальные ходы.
Поскольку пространство состояний в шахматах огромно, чистый алгоритм поиска не может достичь хорошего результата без огромных затрат. Поэтому AlphaGo использует методы с меньшими затратами, такие как нейронные сети, чтобы обучаться знаниям, полученным из MCTS.
Когда пространство состояний в игре меньше, алгоритм поиска может выполняться быстрее, и поэтому не требуется использовать нейронные сети для обучения поведению алгоритма поиска.
На основе AlphaGo изучается применение алгоритмов поиска в играх. Как было упомянуто выше, пространство состояний в шахматах огромно, и поэтому требуется использование нейронных сетей для обучения знаниям, полученным из алгоритмов поиска, и имитации поведения этих алгоритмов. В играх с меньшим пространством состояний можно напрямую использовать алгоритмы поиска для обучения.В данном проекте выбрана игра黑白棋 (также известная как Reversi), которая имеет доску размером 8x8 и относительно небольшое пространство состояний, что позволяет эффективно использовать алгоритмы поиска для реализации ИИ. В проекте реализованы три алгоритма поиска для игры Reversi: Монте-Карло дерево поиска (MCTS), алгоритм Alpha-Beta среза и алгоритм жадного поиска.
Входными данными для алгоритма являются текущее состояние доски (фигуры, которые уже находятся на доске).
Каждый шаг алгоритма MCTS состоит из выбора, расширения, симуляции и обратного распространения. В начале цикла необходимо выполнить расширение.
Выбор осуществляется с помощью функции ucb1, которая реализует поиск максимума и минимума. AI выбирает максимальное значение, а противник — минимальное.
На основе выбранного пути, находим последний узел дерева поиска и добавляем все возможные следующие ходы в дерево поиска.##### Симуляция
AI и виртуальный противник случайным образом делают ходы, играя друг против друга, до окончания игры.
На основе результата симуляции обновляются значения награды для каждого узла выбранного пути дерева поиска. Если AI выигрывает, награда увеличивается на 1, в противном случае уменьшается на 1.
После нескольких циклов алгоритм выбирает ход с максимальной наградой и выводит координаты этого хода.
Алгоритм Alpha-Beta среза также использует поиск максимума и минимума. AI выбирает максимальное значение награды для своих узлов, а виртуальный противник — минимальное значение для своих узлов.
Alpha-Beta срез назван так из-за двух границ, которые передаются в процессе вычислений. Эти границы ограничивают множество возможных решений на основе уже просмотренной части дерева поиска. Alpha представляет собой максимальное нижнее ограничение для всех возможных решений, а Beta — минимальное верхнее ограничение.
Для узлов Max, если Beta значение для подузлов меньше текущего Alpha значения узла, расширение этих подузлов не требуется.
Узлы Max имеют значения Alpha, а узлы Min имеют значения Beta, которые фактически получены от их дочерних узлов. Значения дочерних узлов наследуются от внучатых узлов, а истинные значения награды (Reward) получены из конечных состояний игры, достигших максимальной глубины поиска или из конечных результатов игры. Таким образом, поиск в дереве игры представляет собой метод проб и ошибок, который идеально подходит для реализации с помощью рекурсивного алгоритма.
В игре переворачивающейся шашки, постановка фишек на различных позициях доски может привести к различным наградам. Например, постановка фишек в четырех углах доски явно приносит большую награду. Поскольку поиск всех возможных положений игры занимает слишком много времени, мы можем выполнять поиск только до определенной глубины. Если игра не завершена, награда должна быть определена на основе текущего положения игры.
На основе опыта игры в переворачивающуюся шашку, наградные веса для каждого возможного хода определены вручную:
weight = [
[70, -20, 20, 20, 20, 20, -15, 70],
[-20, -30, 5, 5, 5, 5, -30, -15],
[20, 5, 1, 1, 1, 1, 5, 20],
[20, 5, 1, 1, 1, 1, 5, 20],
[20, 5, 1, 1, 1, 1, 5, 20],
[20, 5, 1, 1, 1, 1, 5, 20],
[-20, -30, 5, 5, 5, 5, -30, -15],
[70, -15, 20, 20, 20, 20, -15, 70]
]
В соответствии с правилами переворачивающейся шашки, доска и интерфейс игры реализованы с использованием библиотеки pygame. Файл main.py содержит основной код. Для запуска игры достаточно запустить main.py.
Правила игры, методы завершения игры и определения ходов реализованы в файле util.py.
Методы поиска дерева Монте-Карло реализованы в классе MCTS_Player, определенном в файле MCTS.py:
class MCTS_Player():
Этот класс реализует игру в переворачивающуюся шашку с использованием алгоритма поиска дерева Монте-Карло, выводит время обработки, количество циклов, награду для каждого возможного хода, выбранный ход и оценку вероятности победы AI.
В классе определены максимальное время обработки и максимальное количество циклов (количество симуляций), которые могут быть настроены через командную строку при запуске игры. Если достигнуто максимальное количество циклов или максимальное время обработки, AI прекращает обработку.
В файле AlphaBeta.py определен класс для реализации алгоритма Альфа-Бета обрезки:
class Alphabeta_Player():
Реализует игру в переворачивающуюся шашку с использованием алгоритма Альфа-Бета обрезки, выводит время обработки.
В классе задана максимальная глубина поиска, которую можно установить с помощью командной строки при начале игры.### Жадный алгоритм
В файле greedy.py определен класс для реализации жадного алгоритма:
class greedy_player():
Реализует игру в黑白棋 с использованием жадного алгоритма, выводит время обработки.
Классы всех трех алгоритмов имеют унифицированный интерфейс для ввода текущего состояния доски и вывода выбранного хода. В каждом классе определена функция с одинаковым названием и параметрами:
def NextPosition(self, board):
В файле main.py при выборе различных алгоритмов создается соответствующий объект AI, который затем вызывает эту функцию.
ai_pos = ai.NextPosition(board)
Если упорядочить силу трех AI, то, по моему мнению, это будет выглядеть так:
MCTS (время обработки 2 секунды) > Альфа-Бета обрезка поиска (глубина поиска 6) > Жадный алгоритм
После тестирования несколькими людьми, MCTS и Альфа-Бета обрезка поиска показали хорошие результаты. То есть, вероятность победы AI над человеком (конечно, новичками) обычно превышает 50%. При этом, если время обработки MCTS составляет 5 секунд, то его сила значительно возрастает, и только в редких случаях человек может выиграть.
В файле greedy.py определен класс для реализации жадного алгоритма:
class greedy_player():
Реализует игру в黑白棋 с использованием жадного алгоритма, выводит время обработки.
Классы всех трех алгоритмов имеют унифицированный интерфейс для ввода текущего состояния доски и вывода выбранного хода. В каждом классе определена функция с одинаковым названием и параметрами:
def NextPosition(self, board):
В файле main.py при выборе различных алгоритмов создается соответствующий объект AI, который затем вызывает эту функцию.
ai_pos = ai.NextPosition(board)
Если упорядочить силу трех AI, то, по моему мнению, это будет выглядеть так:
MCTS (время обработки 2 секунды) > Альфа-Бета обрезка поиска (глубина поиска 6) > Жадный алгоритм
После тестирования несколькими людьми, MCTS и Альфа-Бета обрезка поиска показали хорошие результаты. То есть, вероятность победы AI над человеком (конечно, новичками) обычно превышает 50%. При этом, если время обработки MCTS составляет 5 секунд, то его сила значительно возрастает, и только в редких случаях человек может выиграть.
В файле greedy.py определен класс для реализации жадного алгоритма:
class greedy_player():
Реализует игру в黑白棋 с использованием жадного алгоритма, выводит время обработки.
Классы всех трех алгоритмов имеют унифицированный интерфейс для ввода текущего состояния доски и вывода выбранного хода. В каждом классе определена функция с одинаковым названием и параметрами:
def NextPosition(self, board):
В файле main.py при выборе различных алгоритмов создается соответствующий объект AI, который затем вызывает эту функцию.
ai_pos = ai.NextPosition(board)
Если упорядочить силу трех AI, то, по моему мнению, это будет выглядеть так:
MCTS (время обработки 2 секунды) > Альфа-Бета обрезка поиска (глубина поиска 6) > Жадный алгоритм
После тестирования несколькими людьми, MCTS и Альфа-Бета обрезка поиска показали хорошие результаты. То есть, вероятность победы AI над человеком (конечно, новичками) обычно превышает 50%. При этом, если время обработки MCTS составляет 5 секунд, то его сила значительно возрастает, и только в редких случаях человек может выиграть.
Вы можете оставить комментарий после Вход в систему
Неприемлемый контент может быть отображен здесь и не будет показан на странице. Вы можете проверить и изменить его с помощью соответствующей функции редактирования.
Если вы подтверждаете, что содержание не содержит непристойной лексики/перенаправления на рекламу/насилия/вульгарной порнографии/нарушений/пиратства/ложного/незначительного или незаконного контента, связанного с национальными законами и предписаниями, вы можете нажать «Отправить» для подачи апелляции, и мы обработаем ее как можно скорее.
Комментарии ( 0 )