Привет, Хабр!
Все мы знаем Го — глубокую, медитативную игру на доске 19x19. Камни, пересечения, территории... А что, если выкинуть саму сетку и разрешить ставить камни куда угодно в пределах доски?
Мы в команде YSDA (Yandex School of Data Analysis или Школа Анализа Данных, ШАД) задались этим вопросом и решили проверить. Получилось азартно, хаотично и, что самое главное для нас как разработчиков, — чертовски интересно с точки зрения алгоритмов.
А в конце встретим неожиданный твист! Узнаем, что такое такое Суго.
В этой статье я расскажу, как мы реализовали эту идею на Python и Pygame, с какими геометрическими головоломками столкнулись и как Диаграмма Вороного помогает считать очки в реальном времени, превращая статичную доску в живое поле битвы.
Демо видео функциональности
Обязательно посмотрите пример игры и все возможности в видео.
Работа над репозиторием проекта все еще ведется и ждут ваших идей, а может быть PR!
Что поменялось? Идея непрерывного Го
Классическое Го (Бадук) — это игра про контроль. Контроль над точками, линиями и, в конечном счете, территориями. Но строгая сетка диктует свои правила. Вы можете ходить только на пересечения.
В нашей версии этой привязки нет. Камень можно поставить в любую точку. Это полностью меняет ощущение от игры. Стратегии становятся более интуитивными и "живыми". Вместо подсчета точных свобод (дамэ) вы начинаете мыслить областями влияния. Вместо четких построений — плавные, органические формы. И это, как нам кажется, добавляет игре азарта и на порядок больше вариативности.
Как мы это реализовали: 3 главных вызова
Отказавшись от сетки, мы, по сути, выкинули три столпа, на которых держатся правила Го: понятие соседней клетки, понятие "дыхания" (дамэ) и способ подсчета территории. Пришлось изобретать их заново, но уже в мире непрерывной геометрии.
1. "Куда ставить камень?" — Алгоритм прилипания (Snapping)
Проблема: В непрерывном пространстве камни — это окружности. Как сделать так, чтобы они красиво касались друг друга, а не "залезали" один на другой?
Решение: Мы разработали "умный" алгоритм прилипания. Если место под курсором свободно — камень ставится туда. Но если оно занято (или включен специальный режим), система ищет лучшее место для "прилипания".
Работает это так: мы генерируем огромный список всех "особых" точек-кандидатов вокруг существующих камней и границ доски, где новый камень мог бы встать идеально "впритирку". Это точки касания двух камней, камня и края, и так далее. А затем из всех этих валидных точек просто выбираем ту, что ближе всего к курсору.
Под капотом это выглядит как решение чистой геометрической задачи: найти точки пересечения двух окружностей.
Ключевой фрагмент кода: поиск точек касания двух камней
# goysda/utils.py
def compute_double_touch_points(game_state, game_config, snap_color=None):
"""
Returns all possible placements where the point would touch two other stones simultaneously.
"""
r = game_config['stone_radius']
doubletouch_points = []
for s1 in game_state.placed_stones:
for s2 in game_state.placed_stones:
# ... Пропускаем проверки на цвет и идентичность камней ...
# v is the s1 -> s2 vector
vx = x2 - x1
vy = y2 - y1
# Если расстояние между камнями больше 4 радиусов, они не могут коснуться третьим
if norm(vx, vy) > 16 * r ** 2:
continue
# ... тут магия векторной алгебры для нахождения точек ...
# ... пересечения двух окружностей радиусом 2R ...
# ...
return [s for (s, intersect) in zip(doubletouch_points, is_ok) if not intersect]
2. "Как понять, что группа захвачена?" — Геометрическое "дыхание"
Проблема: У группы камней больше нет конечного числа соседних пустых клеток (дамэ). Как определить, что она окружена и "мертва"?
Решение: Мы ввели новое определение. "У группы есть дыхание (даме), если на всей доске существует хотя бы одна точка, куда можно было бы поставить новый камень того же цвета, чтобы он коснулся этой группы".
Наш алгоритм после каждого хода делает следующее:
Разбивает все камни на связанные группы (обычный поиск в ширину по графу соседства).
Для каждой группы противника запускает проверку
group_has_dame.Эта функция генерирует все возможные точки касания для этой группы (как в алгоритме snapping) и пытается найти хотя бы одну, куда можно "вдохнуть" новый камень.
Если ни одной такой точки не найдено — группа считается "мертвой" и удаляется с доски.
Ключевой фрагмент кода: определение 'жизни' группы
# goysda/utils.py
def kill_groups_of_color(color, game_state, game_config):
# Разделяем все камни на связанные группы
groups = split_stones_by_groups(game_state, game_config)
stones_to_kill = []
# Для оптимизации заранее считаем точки возможного касания
precomputed_doubletouch_points = compute_double_touch_points(game_state, game_config, None)
for group in groups:
# Проверяем только группы нужного цвета
if game_state.placed_stones[group[0]].color == color:
# Если у группы нет "дыхания" (даме)...
if not group_has_dame(group, game_state, game_config, precomputed_doubletouch_points):
# ...добавляем все камни из нее в список на удаление
stones_to_kill += group
kill_group(stones_to_kill, game_state, game_config)
def group_has_dame(group, game_state, game_config, precomputed_doubletouch_points=None):
"""
Проверяет, есть ли у группы хотя бы одна точка, куда можно поставить
камень того же цвета, чтобы он коснулся этой группы.
"""
r = game_config['stone_radius']
# Перебираем все камни в группе
for i in group:
s = game_state.placed_stones[i]
x0, y0 = s.x, s.y
# Ищем ближайшую точку "прилипания" для каждого камня в группе
x1, y1 = compute_closest_snap_position(x0, y0, game_state, game_config, snap_color=None, precomputed_doubletouch_points=precomputed_doubletouch_points)
# Если можно поставить камень вплотную (или почти вплотную) к одному из камней группы,
# значит "дыхание" есть.
if norm(x1 - x0, y1 - y0) <= 4 * r ** 2 + 10**(-5):
return True # Нашли! Группа жива.
return False # Не нашли ни одной точки. Группа мертва.
Этот подход элегантно решает и проблему самоубийственных ходов: если после вашего хода ваша же группа оказывается без "дыхания", она просто удаляется.
3. "Чья территория?" — Магия Диаграмм Вороного
Проблема: Как посчитать очки? Делить доску на пиксели — безумие. Нужен был более изящный способ.
Решение: На помощь пришла библиотека shapely и Диаграммы Вороного.
Если коротко, Диаграмма Вороного для набора точек (наших камней) — это разбиение всей плоскости на регионы так, что каждая точка в регионе находится ближе к "своему" камню, чем к любому другому. Это идеальный математический инструмент для определения "зон влияния"!
После каждого хода мы:
Строим диаграмму Вороного для всех камней на доске.
Вычисляем площадь каждого полигона, принадлежащего камням черного и белого цвета.
Суммируем площади и получаем точный счет в реальном времени.
Это не только позволяет честно считать очки, но и создает потрясающий визуальный эффект, когда зоны влияния динамически перекраиваются после каждого хода.
Ключевой фрагмент кода: расчет территорий через диаграмму Вороного
# goysda/game_state.py
def calculate_voronoi_polygons(self):
# Берем все камни на доске + "камень-подсказку" под курсором
stones_list = self.placed_and_suggestion_stones()
# Строим диаграмму Вороного с помощью shapely.
# extend_to=self.board обрезает бесконечные полигоны по границам доски.
voronoi_polygons = shapely.voronoi_polygons(
geometry=shapely.MultiPoint([[stone.x, stone.y] for stone in stones_list]),
extend_to=self.board,
ordered=True,
).geoms
self.voronoi_polygons = [shapely.intersection(elem, self.board) for elem in voronoi_polygons]
# Для каждого игрока считаем территорию
for i in range(len(self.colors)):
# ... логика определения цвета ...
# Суммируем площади полигонов, "принадлежащих" камням нужного цвета
area_i = sum(elem.area * (stone.color in player_colors) for elem, stone in zip(self.voronoi_polygons, stones_list))
# Нормируем на площадь камня, чтобы получить счет в "камнях"
self.territory[i] = round(area_i / (2 * math.pi * self.config["stone_radius"] ** 2), 2)
Заключение
Эксперимент по "освобождению" Го от сетки оказался невероятно увлекательным. В итоге получилась не просто клон, а, как нам кажется, самостоятельная стратегическая игра со своими тактиками и ощущением. Геометрический подход открыл много интересных алгоритмических задач, решать которые было одно удовольствие.
Проект полностью открыт, и мы будем рады любому фидбеку. Попробовать поиграть, заглянуть в код и предложить свои идеи можно на GitHub.
UPD. Суго или аналог непрервного Го (бадук)
После публикации, нам подсказали в комментарии (за что большое спасибо!) и оказывается такую игру уже давно придумали (но тогда не было возможности сохранять и воспроизводить матчи удобно)
Эта игра называется Суго, автор - Валерий Трубицын. Впервые публикация о ней появилась в 1987 году.
Описания игры Суго.
Главная идея заключается в переносе известной игры на внеструктурное пространство. При этом подразумевается знакомство игроков с классическими правилами го-бадук. Но они будут дополнены.
Запись партии в суго возможна только при составлении фотодиаграмм или телекамеры. Каждая партия является уникальной и повторенной без технических средств быть не может. То есть разбор сыгранной партии возможен, а повторение ходов в реальной партии с целью точного копирования — нет, так как игроки будут выполнять ходы «вручную».
Так же автор подмечает, что сейчас не очень просто сохранять и воспроизводить матчи, из-за чего она может не иметь популярности и продвижения. Теперь это легко и удобно!
Мы пытались найти упомнинания о похожих играх. Ни поиск. Ни GPT. Ни Perplexity не смог найти игру Суго.
Что дальше?
Следующие необходимые шаги - [1]перевести игру на JS, чтобы без приседаний запускаться онлайн в web. [2]поработать еще над UI и [3]возможность играть двум людям по сети.
Во время рутинной работы: верски, написания документации довольно хорошо помогал Cursor. Так как вся логика уже написан планируется активно продолжить им пользоваться для решения [1] и [2].
Все таки можно с помощью AI срезать углы, но нужно понимать где и как. Для получения такой насмотренности может помочь Telegram-сообщество @datafeeling
Спасибо за внимание!