![[Перевод] Как я программировал шахматную партию против брата](https://habrastorage.org/webt/zx/5p/q9/zx5pq9ovg2grgxnz6yyr5rv8ire.png "[Перевод] Как я программировал шахматную партию против брата")
Это история о том, как я попытался выиграть у брата партию в шахматы. Всего лишь гребаную одну игру. Что в этом особенного? Хорош ли я в шахматах? Вовсе нет. Научился ли я чему-то в процессе игры? Тоже нет. Может, это история о путешествии ради путешествия, а не цели? Не совсем. Получил ли я хотя бы удовольствие от этого? Не уверен.
Это история о моей попытке соригинальничать в одной из самых изученных в мире игр, используя опыт разработки ПО там, где это, быть может, и не нужно.
Несмотря на свою абсолютную бестолковость в шахматах и полную бесполезность этой статьи для тех, кто стремится улучшить свою игру, я все равно считаю, что стоило поделиться оригинальным способом применения к задаче инженерных принципов. Добился ли я успеха? Об этом вы узнаете в конце.
Почему я вообще связался с шахматами
Во время пандемии 2020 года мой брат, как и многие другие люди, увлекся онлайн-шахматами. Поиграв пару месяцев, он начал очень вдохновленно рассуждать об этой игре и бросать вызов другим членам семьи. На вызов ответил наш отец (хоть и потерпел цифровое фиаско), я же не поддавался. Одним из сдерживающих факторов было мое нежелание погружаться в потенциально очень времязатратное хобби. Об этой игре я знал достаточно для понимания того, что становление даже игроком среднего уровня требует провести за ней сотни если не тысячи часов. Хотя признаю, что при этом меня также не вдохновляла идея проигрывать брату, который на тот момент сыграл уже не одну сотню партий. Я же – ни одной.
И все же однажды на его вызов я поддался. Стоит ли говорить, что проигрыш был разгромным. Я знал правила и основы игры, так как немного играл еще в детстве, но с навыками брата это ни в коей мере сопоставить было нельзя. В последствии, просматривая анализ игры на chess.com, я увидел, что мое тактическое отставание ход за ходом только росло, пока не достигло оценки в +9 (что равно потере ладьи, слона и пешки против отсутствия потерь противника). В тот момент, утратив всяческую надежду, я сдался. Подобная ситуация повторялась на протяжении еще пары партий, когда я понял – с этим нужно что-то делать.
Первым моим решением было углубиться в изучение игры.
Попытка первая: изучение
Моя первая попытка улучшить качество игры состояла в очевидном: обратиться к Reddit и YouTube за рекомендациями других обучающихся. В перерывах между уроками от GM Naroditsky, чтением и решением задачек на Lichess я также сыграл несколько игр со случайными соперниками по интернету. Несмотря на все это мой рейтинг оставался низким (1300 – 1400 Rapid на Lichess).
После еще пары партий против брата на меня снизошло, что шансов победить у меня нет. Я продолжал следовать все тем же приемам развития (играл, изучал техники и смотрел видео), но уделял этому намного меньше времени, чем брат. На тот момент он уже играл сотни партий в месяц, я же не более 10. Такими темпами мое отставание росло все больше и больше.
Тогда-то я и осознал очень важный нюанс: меня не особо интересовала сама игра, и, по сути, совершенствоваться в ней я не хотел. Основной целью для меня было всего лишь победить одного человека – моего брата.
Попытка вторая: изучение противника
Шахматная партия в общем делится на три фазы: дебют, миттельшпиль и эндшпиль. После изучения некоторых базовых матовых шаблонов перейти на стадии эндшпиля от весомого преимущества к победе обычно «легко», так что первым вопросом для меня стало получение этого преимущества.
На стадии миттельшпиля преимущество обычно достигается за счет развертывания долгосрочной стратегии и применения тактики. Стратегию можно совершенствовать чтением и изучением принципов игры (мне это нравится), а тактика вырабатывается только через решение задач (что мне особенно не нравится). Поэтому я понимал, что в тактических навыках буду однозначно отставать, учитывая, что мой брат решал на chess.com около 20 таких задач ежедневно. Для меня это был недостижимый предел. Таким образом, оставалась всего одна возможность: получать преимущество на стадии дебюта.
Теория по фазе дебюта просто огромна. При этом она требует запоминания длинных последовательностей и вариаций ходов, а также возможные ответов оппонента. Новичкам не обязательно запоминать много, но некоторая ознакомленность с наиболее типичными дебютами может принести немалую пользу (по крайней мере мне так сказали).
Тогда я решил просмотреть несколько случайных игр брата и попробовать понять используемые им дебюты. Я также изучил на Lichess дебюты «Итальянская партия» и Сицилийская защита, постаравшись запомнить их основные принципы. Помимо этого, я просмотрел кучу видео на YouTube.
Очевидно, что мой брат уже проделывал все это до меня (причем лучше), так что, естественно, я снова проиграл. Не говоря уже о том, что запоминание бессмысленных (по крайней мере для меня) открывающих ходов вызывает лишь скуку и утомляет. Все это никак не доставляло мне удовольствия. Еще одна проблема состояла в том, что, когда мой противник начинал отклоняться от прописанных в книге ходов, я абсолютно не знал, как реагировать, потому что просто не понимал формирующиеся позиции.
Пришло время снова отступить и задуматься. Тогда я осознал, что на деле старался не победить брата, а улучшить свою игру против оппонентов, которые отыгрывали те же его дебюты в совершенстве. Мог ли я действовать более направленно? Мог ли вместо этого подготовиться именно против слабых мест брата? Очевидно, что такой подход сработал бы только против него, но это вполне соответствовало моей цели.
Попытка третья: программирование
Теперь моя задача обрела иную форму: найти позиции на выходе из дебюта, которые мой брат (далее PlayerX) с наибольшей вероятностью достигнет, оказавшись при этом в невыгодном положении. Учтите, что никто из нас не является экспертом в игре, и что игроки нашего уровня играют не очень аккуратно.
Единственный способ противостоять хорошему игроку – это в точности следовать ходам из книги, потому что тогда вы по крайней мере знаете, что противник не сделает какой-либо ход, получив преимущество. Однако ситуация меняется, когда вы играете против игрока клубного уровня. Вы можете идти на риски (т.е. временно оказываться в невыгодном положении), если знаете, что противник вряд ли сможет на это правильно среагировать, в связи с чем окажется в затруднительном положении.
У меня также был список из более, чем 500 игр, которые брат сыграл на chess.com. А так как я программист, то естественным подходом для меня стало решить эту задачу инженерным путем.
Я начал скачивать сыгранные им партии с помощью API chess.com и разделять их на игры белыми и черными. Далее я сосредоточился на партиях, где брат играл за черных, потому что чувствовал, что имею больше шансов направить игру в нужное мне русло при игре за белых.
import json
import requests
def get_month_games(player, yyyy_mm):
url="https://api.chess.com/pub/player/{}/games/{}"
r = requests.get(url.format(player, yyyy_mm))
if not r.ok:
raise Exception('get_month_games failed')
games = json.loads(r.content)
# Format: {games: [{url, pgn}, ...]}
return games['games']
# ...import chess.pgn
import io
import json
with open('games.json') as f:
data = json.load(f)
games = []
for game in data:
pgn = io.StringIO(game)
games.append(chess.pgn.read_game(pgn))
black_games = [g for g in games if g.headers["Black"] == "playerx"]Далее я сформулировал задачу так: «Учитывая все позиции, которые видел PlayerX, какие из них по завершению дебюта скорее всего окажутся для него наименее выгодными?».
На этот раз задача была четко определена, и работа пошла уже в знакомой мне области. Я решил провести анализ в Python, а именно в блокноте Jupyter, потому что цели создавать переиспользуемый инструмент у меня не было, и нужно было лишь изучить доступные данные для нахождения одного решения.
Оказалось, что в Python уже есть отличные библиотеки для работы с шахматами: python-chess (генерация ходов, оценка и визуализация) и python stockfish (привязки для оценки шахматной позиции с помощью известного шахматного движка Stockfish).
Я преобразовал задачу в граф таким образом: узел – это частная шахматная позиция (описанная в нотации FEN). Ребро связывает два узла при том, что целевая позиция оказывается достижима из исходной путем допустимого хода. Для всех игр есть один одинаковый стартовый узел: начальная позиция.
Затем я построил граф всех партий, сыгранных PlayerX за черных, дополнительно обозначив каждое ребро количеством раз, которое был совершен соответствующий ход.
class GamesGraph():
def __init__(self):
self.graph = igraph.Graph(directed=True)
def add_move(self, start_fen, end_fen, uci):
vs = self._ensure_vertex(start_fen)
vt = self._ensure_vertex(end_fen)
try:
e = self.graph.es.find(_source=vs.index, _target=vt.index)
e["count"] += 1
except:
e = self.graph.add_edge(vs, vt)
e["uci"] = uci
e["count"] = 1
@property
def start_node(self):
return self.graph.vs.find(chess.STARTING_FEN)
def _ensure_vertex(self, fen):
try:
return self.graph.vs.find(fen)
except:
v = self.graph.add_vertex(name=fen)
v["fen"] = fen
v["turn"] = chess.Board(fen).turn
return vВ итоге получился взвешенный направленный граф (не дерево, потому что позицию можно получить различной последовательностью ходов) типа такого (синтетического, потому что реальный бы просто сюда не уместился):
Здесь начальная позиция обозначена квадратным узлом, цвет указывает, чей в этой позиции ход: белых или черных.
Я также хотел получить оценку каждой позиции в плане преимущества белых, для чего использовал Stockfish. Учитывая, что процесс оценки тысяч позиций требует времени, я решил выполнить его отдельно и создал объект JSON, сопоставляющий каждую уникальную позицию FEN с ее оценкой Stockfish.
from stockfish import Stockfish
stock = Stockfish(parameters={"Threads": 8})
stock.set_depth(20)
stock.set_skill_level(20)
def eval_pos(fen):
stock.set_fen_position(fen)
return stock.get_evaluation()
# fens - это сопоставление между строкой FEN и узлом графа.
for fen, node in graph.fens.items():
node.eva = eval_pos(fen)Оценка преимущества возвращалась в сантипешках или как «мат в X ходов», где положительное число означает преимущество белых, а отрицательное преимущество черных:
{"type":"cp", "value":12} # Преимущество белых в 12 сантипешек.
{"type":"mate", "value":-3} # Черные получают мат в три хода.100 сантипешек означают преимущество перед оппонентом в одну пешку, а 300 в одну легкую фигуру вроде слона. Однако стоит обратить внимание, что Stockfish присваивает фигурам значение в зависимости от их позиции, значит вполне возможно иметь преимущество в 1000 сантипешек даже при равнозначном количестве фигур на доске.
Мне нужно было отобразить эту оценку во что-то более удобное для обработки, например в числа между 0 и 1. Для этого я навскидку решил, что преимущество в 300+ будет отображаться в 1.0, а отставание в 300+ в 0. Помимо этого, любой мат в X ходов (даже если X равен 20) будет 1 или 0.
# Возвращает [-1;1]
def rating(ev, fen):
val = ev["value"]
if ev["type"] == "cp":
# Закрепить -300, +300. Достаточно захватить фигуру.
val = max(-300, min(300, val))
return val / 300.0
# Мат в X ходов: также max рейтинг.
if val > 0: return 1.0
if val < 0: return -1.0
# Это уже мат, но для белых или черных?
b = chess.Board(fen)
return 1.0 if b.turn == chess.WHITE else -1.0
# Возвращает [0;1], где 0 - это min, а 1 - это max преимущество для черных.
def rating_black(ev, fen):
return -rating(ev, fen) * 0.5 + 0.5Теперь вся информация была не месте, и мне оставалось найти узлы графа (т.е. позиции), в которых черные находились в проигрышном положении, а также наиболее подходящие для их достижения последовательности ходов. Нужно было взвесить ребра таким образом, чтобы стало возможным легко вычислять вероятность достижения конкретной позиции. Я рассуждал так:
- В каждой позиции можно оценить вероятность совершения конкретного хода путем деления количества проходов по соответствующему ребру на общее количество ходов, выполненных из этой позиции.
- Теперь каждое ребро будет иметь вес между 0 и 1, где более высокое значение отражает более высокую вероятность прохода по нему из этой позиции.
- Тогда вероятность прохождения конкретного пути будет произведением вероятностей всех пройденных ребер.
Для решения задачи с помощью стандартных графовых алгоритмов нужно было преобразовать веса ребер так, чтобы:
- Они представляли расстояние, а не вероятность (т.е. чем больше расстояние, тем ниже вероятность выбора пути).
- Расстояние между двумя узлами являлось суммой весов пройденных ребер (в противоположность произведению вероятностей).
На деле это гораздо легче сделать, чем объяснять. Формула очень проста:
distance(e) = -log(prob(e))В Python это будет выглядеть так:
def compute_edges_weight(vertex):
all_count = sum(map(lambda x: x["count"], vertex.out_edges()))
for edge in vertex.out_edges():
prob = edge["count"] / all_count
edge["prob"] = prob
edge["weight"] = -math.log(prob)Логарифмирование вероятности выбора ребра даст отрицательное число, потому что вероятность находится между 0 и 1. При этом не стоит беспокоиться о случае, когда вероятность равна нулю (в результате чего логарифмирование бы дало минус бесконечность), поскольку каждое ребро графа было пройдено не менее одного раза. Чем меньше вероятность, тем более отрицательным получится логарифм, значит инвертирование его знака даст то, что нам нужно, так как:
- Сумма логарифмов равна логарифму произведения их аргументов:
log(a) + log(b) = log(a*b). - Чем больше результат, тем ниже определяющая его вероятность.
Вооружившись этой идеей, можно вычислить кратчайший путь между стартовым узлом и всеми другими узлами, используя алгоритм Дейкстры. В результате получится сопоставление между каждым узлом и кратчайшим путем до стартовой позиции, представляющее наиболее вероятную ведущую к ней последовательность ходов.
В этот момент я произвольно выбрал минимальное значение преимущества и упорядочил пути по вероятности. Первые несколько путей представляли для меня наибольший шанс выйти из дебюта с преимуществом перед PlayerX.
Доработки
Что я выяснил? Среди выданных этим алгоритмом позиций была следующая (ход белых):
Как видите, черные находятся в очень неловком положении (+8.9 согласно Stockfish), потому что g6, последний ход черных, был ошибкой. Белые продолжат, забирая пешку с e5 и слона. На этом партия для черных практически закончена, так как спасать им придется коня, пешку на h7 и слона. Еще один результат алгоритма был таким (ход белых):
Здесь мы видим мат в один ход (детский мат).
Проблема в том, что эти ошибки PlayerX совершал только несколько раз в своих первых партиях и больше не повторял. Ранние атаки ферзем обычно делают только неопытные игроки, и эффективны они только против игроков того же уровня. Выйдя из разряда начинающих, PlayerX уже долгое время не совершал этих ошибок, потому что более грамотные противники так не ходят. Я знал, что такой дебют использовать не получится, поскольку PlayerX умел против него защищаться.
Еще одна проблема была связана с последовательностями ходов, которые происходили только раз, но из типичных позиций. Вероятность их заключительной позиции оказывалась такой же, что и вероятность последней типичной позиции, потому что каждое ребро имело вероятность 1.0 (учитывая, что другие возможности не разыгрывались). В примере ниже можно проследовать по ребрам 7 и 6 (наиболее распространенная позиция на втором ходу), а затем по одному из ребер с 1-ми. Далее все последующие ходы будут сыграны только раз (потому что данная позиция сложилась только в одном матче), в результате чего каждый ход будет иметь вероятность 1.0.
А вот и вероятности:
Такой схеме верить нельзя, потому что вряд ли однозначно будет сыграна одна и та же последовательность ходов. Для такого вывода у нас недостаточно игр, в которых игра бы происходила из этих позиций.
Известная цитата (Б. Брюстера?): «В теории нет разницы между теорией и практикой, а вот на практике есть» оказалась в этом случае верна, поэтому мне потребовались кое-какие доработки и самостоятельное исследование, чтобы найти более удачные предполагаемые позиции.
Вторую проблему я исправил, установив для вероятности ребра верхнюю границу, чтобы длинные последовательности ходов, сыгранные только раз, постепенно утрачивали свою вероятность.
def compute_edges_weight(vertex, prob_ceiling=0.9):
all_count = sum(map(lambda x: x["count"], vertex.out_edges()))
for edge in vertex.out_edges():
# Уверенности нет... Установим потолок вероятности (default 90%).
prob = min(edge["count"] / all_count, prob_ceiling)
edge["prob"] = prob
edge["weight"] = -math.log(prob)Для первой же проблемы я просто вручную отфильтровал плохие предположения. В итоге у меня для проработки осталась всего пара позиций.
Причиной еще одной модификации стало то, что я не хотел, чтобы вероятности ходов белых влияли на вероятность выбора пути, потому что играл за белых и мог сам решать, каким путем идти. По этой причине я установил все вероятности ходов белых на 1.0 (нулевой вес), получив в результате такой граф:
Подготовка
В процессе изучения я остановил свой выбор на следующей позиции:
Согласно Lichess, это защита Алехина (атака двух пешек). В этой позиции для черных есть всего один удачный ход (Nb6), после которого они все равно остаются в менее выгодном положении (+0.6 согласно Stockfish). Однако из этой позиции PlayerX зачастую играет на Nf4, что весьма для него неудачно (+2.3). Я создал на Lichess студию и начал просматривать несколько вариаций (хороших ходов и ходов, сыгранных PlayerX).
В конечном итоге получилось дерево возможностей, которое я постарался запомнить и понять. К примеру, мне нужно было узнать, чему угрожал ход вроде d5, почему ход Nf4 был неудачным, и подготовить на все оптимальные ответы.
Занимался я этим недолго, потому что мне быстро надоело, и подготовился по факту лишь частично.
Решающая партия
Все случилось так, словно я глядел в будущее: мы с PlayerX попали в позицию защиты Алехина. Оказавшись в неудобной ситуации, он прозевал своего коня на пятом ходу. Оказывается, что даже игроки намного опытнее тебя начинают одну за другой совершать ошибки, когда попадают в проигрышные условия. Легко играть четко, когда ты побеждаешь, но удастся ли тебе сохранить хладнокровие в противоположной ситуации? На 10 ходу я уже вел с преимуществом +7.1, при котором сложно проиграть, но на этом также завершалась проработанная мной схема. Взгляните, насколько стеснены сейчас черные, и как мои фигуры нацелены напасть на короля:
С этого момента я начал тут и там совершать ошибки, но при этом мне удалось сохранять некоторое преимущество вплоть до 27 хода:
К сожалению, я был очень ограничен во времени (мы играли ускоренную 10-минутную партию), поэтому ходить приходилось быстро. В конечном итоге я совершил фатальные ошибки на 32 и 33 ходах, а еще через один получил от своего недобитого противника мат :/
Вот весь матч (с грубыми ошибками и прочим):
Интерактивный просмотр партии: lichess.org/2qKKl2MI
Выводы
Чему я из всего этого научился? Нескольким вещам, большая часть из которых в ретроспективе выглядит очевидной:
- Подготовка под конкретного противника может дать значительное преимущество в дебюте.
- Начинающие игроки часто упускают возможность воспользоваться сомнительными ходами соперника. В связи с этим легко получить преимущество, доведя противника до позиции, из которой есть лишь один удачный ход.
- Дебют не является определяющим. Если вы не умеете действовать по времени и слабы в тактике, то вполне можете проиграть даже абсолютно выигрышные позиции. Шахматная партия порой решается одним неверным ходом.
- Очень важно изучать игру, и нет никакого универсального средства против оппонента, который намного опытнее вас. Однако за счет правильной подготовки разрыв в навыках можно сократить .
- Применение к шахматам принципов программной разработки оказалось занятной идеей, особенно учитывая, что самоцелью было победить брата.
Использованный мной код лежит в репозитории. Обратите внимание, что я не включил туда данные, и сам код весьма небрежен. Тем не менее, надеюсь, он окажется полезен, в особенности тем, кто еще размышляет на тему освоения компьютерной науки. Смотрите – с ее помощью вполне можно решать задачи из реальной жизни, так что это не просто перемещение битов туда-сюда.
На этом все, друзья. Надеюсь, что однажды мне удастся одолеть брата, а пока что буду стараться достичь этого…своими средствами.
