В игру Го играют тысячи лет. С большим количеством ходов на доске большим , чем количество атомов во вселенной, го представляет собой игру большой сложности и высокого уровня абстракции, возникающую из набора простых правил. Программа AlphaGo от DeepMind попала в заголовки газет, когда в 2016 году она обыграла лучшего игрока в го Ли Седоля в матче из пяти игр.. Выполнение небольших проектов, подобных этому, было большой частью моего собственного развития как программиста, поэтому я надеюсь, что вам понравится статья и вы почувствуете вдохновение, чтобы заняться своими собственными проектами!Го - игра на захват территорий.
5 основных правил игры.
- Игра начинается с пустой доски. Затем два партнера по очереди ставят на нее камни своего цвета. У одного они белые, у другого - черные.
- Побеждает тот, кто окружит больше территории.
- Камень или группа камней противника, которые вы окружили своими камнями, снимается с доски.
- Во время игры на доске появляются пункты куда нельзя ходить: запрещенные пункты.
- Запрещается повторять позицию: правило ко
Подробнее с правилами можно ознакомиться тут.
Процесс проектирования
При работе над сложным проектом полезно разбить проблему на части. Я стараюсь создавать инкапсулированные и модульные программы с различными функциями для обработки различных частей задачи. В случае с Go я решил, что мне следующие функции, :
- Нарисовать доску с помощью PyGame
- Преобразование между (x, y) координатами PyGame и дискретными позициями доски сетки 19x19
- Обновлять состояние игры на основе действий пользователя (например, щелчков мышью).
- Проверить, действительна ли попытка хода
Я создаю класс Game, в котором хранятся все данные о данной игре, такие как состояние доски и количество захваченных камней для каждого игрока. Класс Game имеет функцию draw() для обработки рендеринга состояния доски в графическом интерфейсе PyGame и имеет функцию update() для проверки действий пользователя, таких как щелчки мышью и нажатия клавиш.
Код
В приведенном ниже репозитории скрипте содержится полный код игры Go. Обратите внимание, что это только базовая реализация, в которой отсутствуют многие функции, которые вы можете добавить самостоятельно.
Создание игры с помощью PyGame
PyGame — это библиотека Python для создания базовых игр с графическим интерфейсом. Он поддерживает рисование фигур на экране, отслеживание щелчков мыши и нажатий клавиш, воспроизведение звуков и другие операции, ожидаемые в игре. После импорта PyGame вы можете использовать pygame.init() для инициализации графического интерфейса PyGame. Другие полезные функции включают pygame.mouse.get_pos() для получения текущей позиции мыши, blit() для отправки текста на экран и flip() для обновления экрана новыми формами. В коде выше приведены примеры того, как эти функции PyGame работают на практике.
Магия операций NumPy
Доска для игры в го, как вы, наверное, уже поняли, представляет собой двухмерную матрицу. В библиотеке NumPy есть много очень удобных функций для работы с массивами и матрицами.
Для создания равномерно расположенных линий сетки я использовал функции np.linspace() и np.full(). Первая функция, np.linspace(), создает список равномерно распределенных значений между заданным начальным и конечным значением. Тем временем np.full() создает массив одинаковых значений нужной формы. Это позволяет мне быстро сгенерировать набор начальных и конечных точек для сегментов линии, формирующих сетку доски Го, которые я затем передаю в функцию pygame.draw.line().
Еще одна чрезвычайно полезная функция NumPy — это функция np.where(), которая возвращает индексы в массиве, где выполняется определенное условие. Например, строка np.where(self.board == 1) возвращает позиции на доске, хранящие значение 1 (которое в правилах моей игры означает черный камня).
Itertools и коллекции
Я использовал itertools.product() для генерации позиций камней на доске. Например, чтобы быстро создать список всех точек сетки на доске Go (например, от (0,0) до (18,18)), я могу использовать itertools.product(range(19), range(19)).
Я использовал collections.defaultdict() для создания счетчика очков. Строка self.prisoners = collections.defaultdict(int) создает структуру данных, похожую на словарь Python, за исключением того, что когда ключ должен получить доступ к словарю в первый раз, ему присваивается соответствующее значение 0. Мне нравится использовать defaultdicts, чтобы сделать мой код более устойчивым к KeyErrors без необходимости писать кучу специальных проверок.
Фундаментальной единицей игрового процесса Го является группа камней.. Когда группа камней полностью окружена, их можно захватить сразу. Но пока у одного камня в группе есть хотя бы один ход (незанятое соседнее поле доски), вся группа все еще жива.
Для целей нашей игровой программы у нас есть следующая математическая задача: Дана матрица N x N, заполненная тремя различными значениями (0 для пустого камня, 1 для черного камня, 2 для белого камня),нужно создать список групп камней каждого цвет, где каждая группа камней представляет собой список камней. Описание может быть немного сложным для понимания, поэтому, пожалуйста, посмотрите к изображение ниже и посмотрите, сможете ли вы определить, сколько существует групп камней каждого цвета.
Правильный ответ: существует 6 групп черных камней и 2 группы белых камней. Пусть вас не вводят в заблуждение 3 черных камня, расположенных по диагонали — они не соприкасаются друг с другом, потому что они не связаны напрямую линиями сетки, поэтому каждый камень представляет собой отдельную группу камней. Я быстро понял, что написать программу, которая берет игровое поле и автоматически находит все группы камней, было непросто, поэтому я начал задаваться вопросом, можно ли применить уже существует алгоритм.
Я обнаружил, что использование теории графов и библиотеки графов Networkx дает удивительно элегантное решению проблемы подсчета групп камней. Допустим, мы хотим найти все группы черных камней. Основная идея заключается в том, что мы начинаем с «сетчатого графа», который выглядит точно так же, как сетка на доске Го: каждая вершина соединена с вершинами выше, ниже, слева и справа от нее. Затем мы удаляем все вершины, на которых нет черного камня, что оставляет нам граф, в котором компоненты связности непосредственно соответствуют группам камней! Мы можем просто использовать встроенную функцию connect_components() в Networkx, чтобы вернуть правильный ответ! Используя эту функцию, я смог реализовать код для обнаружения позиций в игре. Это означает, что игра автоматически обнаружит, когда группа камней окружена, удалит их с доски .
Следующие шаги
Серьезные игроки в го, посмотревшие код, могли заметить, что игра не завершена на 100%. В игре не применяется правило Ко, которое не позволяет игрокам повторять предыдущую игровую позицию. Также было бы неплохо реализовать автоматический подсчет очков в конце игры, а также сделать удобные функции, такие как «отмена». Наконец (и это большая проблема), было бы здорово иметь ИИ, который может играть против одного игрока-человека, так как сейчас игра рассчитана двух игроков-людей.
Я надеюсь, вам понравилось читать о моем опыте создания игры Go на Python, и что вы узнали несколько новых вещей по ходу дела. Если у вас есть другие предложения или отзывы, оставьте комментарий ниже!
Ссылки
[1] PyGame документация: https://www.pygame.org/docs/
[2] Networkx документация: https://networkx.org/documentation/stable/reference/index.html
#machinelearning #artificialintelligence #ai #datascience #python #programming #technology #deeplearning #go