В праздничные выходные мне пришло в голову, что я давно не занимался чем-то бессмысленным. Представляю вашем вниманию... Regex Chess: набор из 84688 регулярных выражений, которые при выполнении по порядку генерируют ход (валидный, то есть не совсем ужасный) для переданного в качестве входных данных состояния шахматной доски. [Прим. переводчика: здесь в оригинале статьи есть интерактивный виджет, позволяющий сыграть с движком.]

Вот вся программа, которая делает ходы против игрока (серьёзно, я не шучу, она действительно такая короткая):

let regex_list = [/* очень длинный список регулярных выражений */]
let board = "rnbqkbnr / pppppppp / 8 / 8 / 8 / 8 / PPPPPPPP / RNBQKBNR w KQkq - 0 1";

for (regex of regex_list) {
    board = re.replace(regex.pattern, regex.target)
}
display(board)

Прочитав этот пост, вы поймёте (надеюсь), как возможна эта последовательность регулярных* выражений, а также что делают конкретные регулярные выражения.

^{* Снобы могут заявить что-то типа «Вы сказали, что будете использовать регулярные выражения, но они не регулярные!" Но меня это не волнует.}

Как всегда, код проекта выложен на GitHub.

Приступаем: CPU регулярных выражений

Как нам заставить регулярные выражения играть в шахматы? Разумеется, создав компьютер на регулярных выражениях! В частности, мы спроектируем SIMD-набор команд без ветвления и с условным исполнением. А затем создадим последовательность регулярных выражений, интерпретирующую эти команды. (Это похоже на набор команд GPU. И немного на ARM. Только намного медленнее.) И на основании этого мы сможем запрограммировать наш компьютер на игру в шахматы.

(Кто-то может сказать, что у меня есть нездоровая одержимость созданием странных компьютеров, например, моего компьютера на основе игры «Жизнь» или моего printf-компьютера. Эти люди ошибаются, просто у них есть нездоровая одержимость банальным и обычным.)

Архитектура компьютера

Начну я с объяснения того, как собираюсь упорядочивать данные, с которыми будет работать компьютер. Так как мы имеем дело с регулярными выражениями, текущее состояние компьютера будет представлено в виде одной строки, содержащей и «стек» программы, и все переменные в следующем формате:

%%
#stack:
top item on stack
second item on stack
....
#variable1: value 1
#variable2: value 2
...
#variablek: value k

Каждая команда будет или манипулировать какими-то переменными в стеке, или выполнять чтение/запись в переменную. Давайте рассмотрим примеры основных команд.

Базовые операции со стеком

Команда Push

Вот реализация команды push, добавляющей значение в вершину стека:

def push(const):
    return [(r"(%%\n#stack:\n)",
             r"\g<1>"+const+r"\n")]

Мы должны считывать возвращаемый тип этих функций как список кортежей. Каждый кортеж обозначает применяемое преобразование regex, где левый элемент — это сопоставляемый паттерн, а правый элемент — замена.

Вкратце напомню, как работают регулярные выражения. Каждый кортеж в этом списке состоит из двух частей: регулярного выражения и замены. Регулярное выражение ищет подстроку в той строке, к которой оно применено (в нашем случае это состояние). Большинство символов в регулярном выражении соответствуют сами себе, а скобки создают «группы сопоставления», на которые можно ссылаться в дальнейшем.

Второй аргумент — это строка замены. Большинство символов тоже означают «заменить на этот символ», но есть и особые последовательности наподобие \g<1>, то есть обратные ссылки, относящиеся к ранее полученным группам. В данном случае, \g<1> ссылается на первую полученную группу (на всё, что соответствует первому множеству скобок), то есть на заголовок %%\n#stack:\n.

То есть в результате выполнения этой операции со стеком мы находим в состоянии вхождение %%\n#stack:\n и вставляем под ним константу (в вершину стека).

Давайте разберём это на практике. Допустим, мы начинаем с пустого стека:

%%
#stack:

Если мы выполним push("hello"), то регулярное выражение:

• Выполнит сопоставление с паттерном %%\n#stack:\n в начале нашего состояния

• Запишет этот заголовок в группу 1 (скобки в паттерне создают эту группу)

• Заменит его записанной группой (\g<1>), за которой следует наша константа hello и символ новой строки

В результате мы получим:

%%
#stack:
hello

Если затем мы выполним push("world"), то повторится тот же процесс и мы получим

%%
#stack:
world
hello

Регулярное выражение всегда выполняет сопоставление в вершине области стека, поэтому новые элементы всегда записываются в вершину, сохраняя при этом предыдущее содержимое стека под ними.

Команда Pop

Команда pop извлекает верхний элемент из стека:

def pop():
    return [(r"(%%\n#stack:\n)([^\n]*)\n",
            r"\1")]

Здесь мы уже видим часть специальных операторов, демонстрирующих мощь регулярных выражений. Блок [^\n] означает «сопоставить с любым символом, кроме символа новой строки», а * означает «сопоставить ноль или более». Если соединить всё это вместе, получается, что мы ищем строку, начинающуюся с %%\n#stack:\n, а затем на следующей строке ноль или больше символов, не являющихся символом новой строки (то есть строку целиком). Замена — это только первая строка, которая удаляет вторую строку, выталкивая её из вершины стека.

Давайте посмотрим, как это работает на практике. Допустим, мы начинаем со следующего стека:

%%
#stack:
world
hello

При выполнении команды pop() регулярное выражение:

• Сопоставляет паттерн, начинающийся с %%\n#stack:\n (записанный в группу 1)

• Сопоставляет все символы до следующего символа новой строки (записанные в группу 2 — world)

• Заменяет всё, сопоставленное только группой 1 (заголовок), по сути, удаляя верхний элемент

В итоге мы получаем следующее:

%%
#stack:
hello

Каждая команда pop удаляет из вершины стека ровно один элемент, сохраняя все остальные элементы под ним.

Команды «переменная <-> стек»

Поиск переменной

Чтобы загрузить содержимое переменной в вершину стека, мы делаем следующее:

def lookup(variable):
    # Находим значение переменной и записываем его в стек                                                
    return [(r"(%%\n#stack:)([^%]*\n#"+variable+": )([^\n]*)\n",
            r"\1\n\3\2\3\n")]

Это регулярное выражение чуть сложнее предыдущих. Давайте разберём, что оно делает:

• [^%]* соответствует любому символу (% встречается только в начале программы), поэтому позволяет найти любую переменную в любом месте программы.

• [^\n]* соответствует значению переменной, охватывая всё до конца строки

• Замена создаёт копию значения и помещает её в вершину стека

Давайте посмотрим, как это работает на практике. Допустим, мы начинаем с такого состояния:

%%
#stack:
#foo: hello
#bar: world
#baz: 42

Если мы выполним lookup("bar"), то регулярное выражение:

• Сопоставит заголовок стека в группе 1

• Сопоставит всё до #bar: включительно в группе 2

• Сопоставит world в группе 3

• Использует эти группы, чтобы воссоздать состояние со значением, скопированным в вершину стека

То есть запустив замену, мы получим следующее состояние:

%%
#stack:
world
#foo: hello
#bar: world
#baz: 42

Операция lookup сохранила исходную переменную и её значение, также поместив копию значения в вершину стека. Это позволяет нам считывать значения переменных, не меняя их.

Присвоение значений переменным

Присвоение значения переменной — интересная задача: мы не знаем, существует ли уже переменная. Нам необходимо учитывать оба случая: и изменение имеющейся переменной, и создание новой.

Сначала я покажу реализацию, а потом разберу каждый из случаев.

def assign_pop(varname):
    return [
        (r"(%%)\n#stack:\n([^\n]*)\n" +
           "([^%]*#" + varname + r": )[^\n]*",
        r"\1`\n#stack:\n\3\2"),

        (r"(%%)([^`]\n?#stack:\n)([^\n%]*)\n([^%]*)",
        r"\1`\2\4#" + varname + r": \3\n"),

        (r"%%`",
        r"%%")
    ]

Для начала предположим, что переменная уже существует. То есть стек изначально выглядит так и мы предполагаем, что вызываем assign_pop("bar"):

%%
#stack:
world
#foo: hello
#bar: something
#othervar: othervalue

При выполнении этого списка регулярных выражений создаются следующие группы:

%%
#stack:
world
#foo: hello
#bar: something
#othervar: othervalue

После операции замены мы получаем следующий вывод:

%%`
#stack:
#foo: hello
#bar: world
#othervar: othervalue

Затем мы переходим к следующей команде, но не должны сопоставлять её, потому что второе регулярное выражение завершается со сбоем, если после %% в начале программы есть символ `. Поэтому ничего не происходит. Затем третье регулярное выражение выполняет очистку.

Обработка несуществующих переменных: давайте разберёмся, что происходит, если переменная ещё не существует. Снова предположим, что мы вызываем assign_pop("bar"):

%%
#stack:
world
#foo: hello
#othervar: othervalue

Первое regex пытается найти соответствие, но неудачно, потому что #bar отсутствует. Поэтому оно ничего не делает. Но затем второе regex пытается найти соответствие, и ему это удаётся. Оно создаёт следующие группы:

%%
#stack:
world
#foo: hello
#othervar: othervalue

Далее мы выполняем перезапись и получаем следующий вывод:

%%
#stack:
#foo: hello
#othervar: othervalue
#bar: world

Затем выполняется третье regex, но ничего не делает.

Существует множество команд, которые используют этот трюк, чтобы мы не применяли действия не в нужном нам порядке. Например, можете в качестве самостоятельного упражнения разобраться, как работает команда is equal:

def eq():
    return [
        (r"(%%\n#stack:\n)([^\n]*)\n\2\n",
         r"\1`True\n"),

        (r"(%%\n#stack:\n)([^`][^\n]*)\n([^\n]*)\n",
         r"\1False\n"),

Условные операции (без ветвления)

Для выполнения интересных задач языкам программирования обычно требуется некий поток управления. Очень сложно написать программу без использования хотя бы одного оператора if. Давайте разберёмся, как их реализовать. Вот реализация условной команды:

def cond(tag):
    return [(r"%(%\n#stack:\nTrue)",
             r"%\1`"),
            (r"%(\n#stack:\nFalse)",
             tag+r"\1`"),
            (r"\n(True|False)`\n",
             "\n")]

Давайте пошагово посмотрим, как это будет работать, начав со случая, когда вершина стека равна False.

%%
#stack:
False
#variable: value

Изначально первому regex не удаётся найти соответствие, потому что верхний элемент в стеке не равен True. Поэтому мы переходим ко второму regex и проверяем, применимо ли оно. Это выражение может выполнить сопоставление и создаёт соответствующие группы.

%%
#stack:
False
#variable: value

Применив замену, мы получим следующий стек.

%tag
#stack:
False`
#variable: value

(Затем мы снова используем трюк с очисткой и удаляем использованный маркер.)

Видите, что здесь происходит? Программа больше не начинается с %%. Это означает, что ни одна команда не будет соответствовать, потому что регулярные выражения всегда проверяют, что программа начинается с %%. Поэтому ничего не произойдёт... пока мы снова не реактивируем её позже при помощи следующей простой команды:

def reactivate(tag):
    return [(r"%"+tag+r"\n([^%]*)",
        r"%%\n\1")]

Теперь давайте вернёмся к случаю True условного оператора. Это простой случай: по сути, мы вообще ничего не делаем. Во втором regex мы заменяем стек на True`, а затем удаляем эту строку в третьем.

Стоит отметить, что благодаря этому в нашем коде отсутствует ветвление, ведь каждая команда является условной. (Это похоже на predicated execution в ARM, когда большинство команд можно выполнять условным образом на основании флагов состояния, а не при помощи явных команд ветвления.)

Циклы (невозможны)

Так как наша программа состоит из последовательности регулярных выражений, мы никак не можем реализовать циклы! Строго говоря, это означает невозможность полноты по Тьюрингу. Но мы можем выполнять любые ограниченные вычисления (bounded computation), просто развернув циклы, которые могли бы потребоваться. К счастью, вычисление следующего хода — это ограниченные вычисления, поэтому мы можем его реализовать.

Single-Instruction Multiple-Data

А теперь я расскажу о самой любимой мной части разработанного нами языка. Благодаря магии регулярных выражений (и тому, что они выполняют подстановку глобально для всей строки) мы можем одновременно выполнять несколько потоков!

То есть если записать строку состояния так:

%%
#stack:
int0000101010
int0001011100
%%
#stack:
int0000001101
int0110000000

то при вызове binary_add() оба сложения выполняются одновременно! Вот, как это выглядит после выполнения:

%%
#stack:
int0010001110
%%
#stack:
int0110001101

Это возможно потому, что сопоставления регулярных выражений выполняются глобально. Когда мы сопоставляем оператор запуска потока (%%) дважды, можно выполнять операции в обоих потоках одновременно.

Как же нам воспользоваться этой особенностью? Давайте рассмотрим примеры команд, которые позволяют создавать потоки и управлять ими.

Команды fork

Вот простая команда fork, разделяющая каждый текущий выполняемый поток на два; второй поток изначально неактивен и имеет заданный tag:

def fork_inactive(tag):
    return [(r"%%\n([^%]*)",
             r"%%\n\1" + "%"+tag+r"\n\1")
            ]

Мы можем также, например, выполнить fork() на основании булевого значения, создав для одного потока случай True, а для другого False. (Это похоже на оператор Amb Маккарти)

def fork_bool(variable):
    return [(r"%%\n([^%]*)",
             r"%%\n\1#"+variable+r": True\n%%\n\1#"+variable+r": False\n")

Давайте посмотрим, что произойдёт, если мы применим несколько fork. Начнём с простого состояния:

%%
#stack:
somevalue
#x: 10

После вызова fork_bool("condition") мы получим:

%%
#stack:
somevalue
#x: 10
#condition: True
%%
#stack:
somevalue
#x: 10
#condition: False

Если затем вызвать fork_bool("c2"), то каждый существующий поток разделится на два:

%%
#stack:
somevalue
#x: 10
#condition: True
#c2: True
%%
#stack:
somevalue
#x: 10
#condition: True
#c2: False
%%
#stack:
somevalue
#x: 10
#condition: False
#c2: True
%%
#stack:
somevalue
#x: 10
#condition: False
#c2: False

Теперь у нас есть четыре одновременных пути выполнения кода, параллельно исследующих все возможные комбинации булевых условий. Это очень полезно для шахмат, потому что нам часто нужно одновременно рассматривать множество возможных состояний доски и (например) вычислять их оценки, чтобы выбрать наилучшее. Вместо того, чтобы обходить в цикле все возможные состояния доски, мы можем притвориться, что делаем это один раз, но одновременно.

Компилируем наш маленький язык

Теперь, когда у нас есть эмулятор CPU, мы можем создать компилятор, работающий с нашим новым языком ассемблера.

Кто-то скажет: «Но я читаю этот пост, не для как урок по разработке компиляторов!» Справедливое замечание. Кроме того, я и не стремился создать компилятор в этом проекте, поэтому написал нечто, более похожее на макроассемблер. Он превращает программы, напоминающие код на Python:

def fib():
    a = 1
    b = 2
    for _ in range(10):
        next = a + b
        a = b
        b = next

в последовательность таких команд:

push(1)
assign_pop('a')
push(2) 
assign_pop('b')
lookup('a')
lookup('b')
binary_add()
assign_pop('next')
lookup('b')
assign_pop('a')
lookup('next')
assign_pop('b')
[... повторяется ещё 8 раз ...]

Компиляция при помощи символического выполнения

Вместо того, чтобы писать традиционный компилятор с этапами парсинга и генерации кода, я выбрал необычный подход: символическое выполнение. Основной смысл здесь в том, что мы можем «выполнять» код на Python особым образом: фиксировать операции, которые должны выполняться, а не выполнять их на самом деле.

Вот, как это работает: аргумент variables — это на самом деле не словарь, а особый объект, записывающий все операции, выполняемые с ним. Он создаёт так называемую «трассировку» выполнения. Когда мы записываем:

a = b + 1

объект-трассировщик записывает четыре операции:

1. lookup переменной b

2. push константы 1

3. Операцию binary_add

4. assign_pop переменной a

Работа с потоком управления

Самое сложное в таком подходе — работа с контролем ветвления и, в частности, с операторами if. (А что насчёт циклов? У нас их нет, поэтому я никогда их не использую. Циклы могут иметь только константы.) Мы должны быть уверены, что учитываем все возможные пути выполнения. Вот, как это сделать:

Если мы встречаем условную конструкцию, то создаём в трассировке два отдельных пути — одно для случая, когда условие истинно, другое для случая, когда оно ложно. Каждый путь записывает собственную последовательность операций. Позже мы снова объединяем эти пути.

Например, этот код на Python:

if x > 0:
    y = 1
else:
    y = 2

генерирует примерно такую структуру трассировки:

lookup('x')      # получаем значение x
push(0)          # Push 0
greater_than()   # сравниваем
cond('tag1')     # ветвление в зависимости от результата
  # Путь True:
  push(1)
  assign_pop('y')
pause('tag2')
reactivate('tag1')
  # Путь False:
  push(2)
  assign_pop('y')
reactivate('tag2')

Магия компилятора заключается в том, как он управляет потоком управления через ветвление. Расскажу об этом чуть подробнее.

Когда компилятор начинает обрабатывать код, он хранит в CallTree единственный линейный путь выполнения команд. В процессе обработки команды добавляются одна за другой. Этот список команд полностью линеен. Однако всё становится интереснее, когда мы добираемся до условной конструкции.

Рассмотрим, что происходит, когда мы встречаем условную конструкцию наподобие x > 0 из примера выше. Когда это случается, мы распознаём её и создаём ветвь в дереве вызовов, одновременно представляющую два пути. Затем мы притворяемся, что условие было true, и заполняем случай true дерева. Когда мы достигаем конца программы, мы выполнили часть компиляции, но не её целиком.

А теперь расскажем о хитрости: при компиляции мы не просто трассируем программу один раз, а выполняем многократную трассировку. И при каждой трассировке мы выстраиваем ветвления таким образом, чтобы они проходили по той ветви, которая выбиралась реже всего. Благодаря этому во второй раз мы записываем команды для ветви false.

После завершения ветвления мы распознаём это и снова объединяем две ветви. Такой механизм ветвления и слияния — не просто хитрый трюк, а основной принцип работы нашего CPU на основе регулярных выражений. Когда мы преобразуем это дерево в команды, каждая ветвь транслируется в условную regex-операцию (с использованием команды cond), которая может селективно активировать и деактивировать разные части состояния программы. Точки слияния становятся командами реактивации, которые гарантируют продолжение выполнения по правильному пути.

Пишем шахматный движок

Итак, мы наконец добрались до той части поста, где начнём писать шахматный движок. (И до той части, где наконец станут понятны решения, принятые при проектировании эмулятора.)

По большей мере, это достаточно простой процесс, отражающий написание шахматного движка на любом другом языке программирования. Но благодаря ветвлению SIMD мы можем сделать его выполнение быстрым.

Рассмотрим упрощённую программу, вычисляющую все допустимые ходы пешки.

def pawn_moves(initial_board):
    # Шаг 1: находим все пешки и создаём список их позиций 
    pawnpos_list = find_all_pawns(initial_board)

    # Шаг 2: создаём параллельные состояния для каждой пешки (до 8)
    MAX_PAWNS = 8
    for iteration in range(MAX_PAWNS):
        if not pawn_list.is_empty():
            pawn_pos = pawnpos_lst.remove_first()
            fork_inactive("waiting")

    # Шаг 3: переключаемся на обработку параллельных состояний
    pause("main")
    reactivate("inactive")

    # Шаг 4: генерируем ходы одновременно для всех пешек 
    candidate_moves = []
    if initial_board[pawn_pos + (0, 1)].is_empty():
        candidate_moves.append(pawn_pos + (0, 1))
        if pawn_pos.y == 2:
            if initial_board[pawn_pos + (0, 2)].is_empty():
                candidate_moves.append(pawn_pos + (0, 2))

    if initial_board[pawn_pos + (1, 1)].has_opponent():
        candidate_moves.append(pawn_pos + (1, 1))
    if initial_board[pawn_pos + (-1, 1)].has_opponent():
        candidate_moves.append(pawn_pos + (-1, 1))

    # Шаг 5: выполняем обратное переключение и объединяем результаты 
    pause("inactive")
    reactivate("main")
    candidate_moves = merge_variables_from_threads("inactive")

Шаг 1: нахождение пешек

Функция find_all_pawns() сканирует наше описание доски в поисках белых пешек (обозначенных в строке FEN как P). Она возвращает список позиций каждой из этих пешек. Например, если мы запустим программу для следующей позиции с тремя пешками на d2, e2 и f2, то функция создаст в переменной pawnpos_lst следующий разделённый точками с запятой список:

%%
#stack:
#board: 4k3/8/8/8/8/8/3PPP2/4K3
#pawnpos_lst: d2;e2;f2;

Шаг 2: создание состояния

Здесь всё становится хитрее. Команда fork_inactive, как говорилось выше, дублирует всё состояние программы. При каждом своём выполнении она создаёт точную копию текущего запущенного потока, но помечает новую копию как %waiting вместо %%. (Напомню, что это означает команды, не относящиеся к этому потоку.) В то же время она берёт одну позицию из pawnpos_lst и присваивает её новой переменной pawnpos в скопированном состоянии.

Когда цикл выполняется трижды, каждая операция fork_inactive создаёт новую параллельную вселенную, в которой мы обрабатываем отдельную пешку. Выполняющая это копирование regex-операция сохраняет все существующие переменные, но добавляет новую переменную pawnpos с конкретной позицией для обработки копией.

%%
#stack:
#board: 4k3/8/8/8/8/8/3PPP2/4K3
#pawnpos_lst: 

%waiting
#stack:
#board: 4k3/8/8/8/8/8/3PPP2/4K3
#pawnpos: d2

%waiting
#stack:
#board: 4k3/8/8/8/8/3PPP2/4K3
#pawnpos: e2

%waiting
#stack:
#board: 4k3/8/8/8/8/3PPP2/4K3
#pawnpos: f2

Шаг 3: переключатель активации

Вспомним, что операции паузы и реактивации выполняют манипуляции с маркерами %%, определяющими, какие состояния активны. Операция pause("main") меняет исходный %% на %main, по сути, деактивируя его. Затем reactivate("inactive") находит все состояния, помеченные %waiting, и меняет их на %%, делая их новыми активными состояниями.

Шаг 4: параллельная генерация ходов

Здесь происходит та самая магия SIMD. Каждая проверка возможного хода (вперёд на одну клетку, вперёд на две клетки или взятие фигуры по диагонали) выполняется для всех активных состояний одновременно. Когда мы проверяем, пуста ли клетка впереди, то мы на самом деле проверяем в одной операции сразу d3, e3 и f3. Каждый допустимый ход мы добавляем в список candidate_moves.

(Для удобства восприятия здесь я сильно упростил программу. На самом деле, я не работаю со строками FEN напрямую, а разворачиваю их в 64 независимых переменных для каждой из 64 клеток, после чего выполняю чтение и запись непосредственно в эти клетки. Это существенно упрощает обработку состояния доски. Но для объяснения проще показать это на примере работы только со строками FEN.)

%main
#stack:
#board: 4k3/8/8/8/8/8/3PPP2/4K3
#pawnpos_lst: 

%%
#stack:
#board: 4k3/8/8/8/8/8/3PPP2/4K3
#pawnpos: d2
#candidate_moves: d3;d4

%%
#stack:
#board: 4k3/8/8/8/8/8/3PPP2/4K3
#pawnpos: e2
#candidate_moves: e3;e4

%%
#stack:
#board: 4k3/8/8/8/8/8/3PPP2/4K3
#pawnpos: f2
#candidate_moves: f3;f4

Шаг 5: слияние результатов

Финальная операция слияния объединяет все списки candidate_moves из параллельных состояний. Сначала она выполняет повторное переключение активации в основное состояние при помощи pause и reactivate. Далее выполняет merge_variables_from_threads (это тоже псевдооперация, которую я придумал для визуальной понятности; на практике в реальной машине для этого требуется примерно десяток команд), сопоставляет все списки candidate_moves из неактивных состояний и конкатенирует их.

То есть хотя написанный нами код как будто обрабатывает по одной пешке за раз, благодаря способности нашего regex-движка обрабатывать множественные состояния, на самом деле, мы обрабатываем все пешки одновременно. Каждая операция, от проверки пустых клеток до создания списков ходов, выполняется параллельно для всех активных состояний.

Именно так работает операция для каждой фигуры. Этот пост и так оказался слишком длинным, поэтому вдаваться в подробности я не буду, но если вам любопытно, то изучите chess-engine.py.

Делаем ход

Теперь давайте разберём весь игровой цикл, обрабатывающий все действия.

def play_turn():
    # Шаг 1: считываем из ввода ход человека                                                  
    board_before_move, src, dst = from_pretty_utf8_to_fen()

    # Шаг 2: проверяем ход на допустимость                                                                
    after_move = board_before_move.make_move(src, dst)
    next_boards = compute_legal_boards(board_before_move)
    next_board = fork_on_list(next_boards)
    if after_move != next_board:
        destroy_active_thread()

    # Шаг 3: Генерируем ответ компьютера                                                               
    candidate_boards = compute_and_score_legal_boards(after_move)
    candidate_board = fork_on_list(candidate_boards)

    keep_best_scoring_board(score)
    from_fen_to_pretty_utf8(candidate_board)

Допустим, мы находимся в начале игры, и человек ввёл e2e4 (дебют королевской пешкой). Вот, как это обработает наш код:

Шаг 1: считываем ход

Сначала функция from_pretty_utf8_to_fen() преобразует нашу красивую доску с шахматными Unicode-фигурами обратно в нотацию FEN. Также она извлекает из ввода начальную и конечную клетки хода:

%%
#stack:
#board: rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR
#src: e2
#dst: e4

Шаг 2: валидируем ход

Теперь нам нужно определить, допустимый ли это ход. Вместо того, чтобы писать совершенно новый код, явным образом проверяющий допустимость хода, мы снова воспользуемся мощью параллельной обработки. Процесс состоит из трёх частей:

Сначала make_move применяет ход человека, чтобы создать новое состояние доски:

%%
#stack:
#board: rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNR
#after_move: rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNR

Затем compute_legal_boards генерирует все возможные допустимые из начальной позиции ходы, создавая список вида:

%%
#stack:
#next_boards: rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNR;
              rnbqkbnr/pppppppp/8/8/8/3P4/PPP1PPPP/RNBQKBNR;
              rnbqkbnr/pppppppp/8/8/8/4P3/PPPP1PPP/RNBQKBNR;
              ...

В конце fork_on_list создаёт параллельные состояния для каждой допустимой позиции доски:

%%
#stack:
#board: rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNR

%%
#stack:
#board: rnbqkbnr/pppppppp/8/8/8/3P4/PPP1PPPP/RNBQKBNR

%%
#stack:
#board: rnbqkbnr/pppppppp/8/8/8/4P3/PPPP1PPP/RNBQKBNR

Вызов destroy_active_thread() удаляет все потоки, в которых доска не соответствует after_move. В нашем случае остаётся только позиция e2-e4, подтверждая, что это допустимый ход. (Если не сделан ни один допустимый ход, то особое regex заменяет весь вывод готовым текстом Illegal Move.)

Шаг 3: ответ компьютера

Теперь мы повторяем похожий процесс для нахождения наилучшего ответа . Сначала compute_and_score_legal_boards генерирует все возможные ответы чёрных. Эта функция творит небольшую магию, и когда она возвращает следующие возможные доски, она возвращает с каждой доской и численную оценку этой доски после следующего наилучшего хода белых. Ниже я объясню, как это работает. Пока достаточно знать, что эта функция, подобно compute_legal_boards, возвращает возможные позиции, а также численную оценку позиции. (Здесь происходит «минимакс». Оценка здесь отражает качество каждой позиции с точки зрения игрока после того, как он сделает свой наилучший ответный ход.)

Запустив эту функцию, мы получим примерно такой вывод:

%%
#stack:
#board: rnbqkbnr/pppp1ppp/8/4p3/4P3/8/PPPP1PPP/RNBQKBNR
#score: 100

%%
#stack:
#board: rnbqkbnr/ppppp1pp/8/5p2/4P3/8/PPPP1PPP/RNBQKBNR
#score: 102

%%
#stack:
#board: rnbqkb1r/pppppppp/5n2/8/4P3/8/PPPP1PPP/RNBQKBNR
  #score: 98

keep_best_scoring_board(score) свёртывает эти параллельные состояния, но на этот раз только с сохранением позиции с наибольшей оценкой согласно расчётам чёрных (в этом примере это ответ f7-f5). Это вторая половина поиска «минимакс» —мы рассматриваем все варианты, в которых противник должен выбирать первым, а потом из тех, которые оказываются для нас наилучшими. В конце from_fen_to_pretty_utf8 преобразует эту позицию обратно в красивый формат Unicode. Благодаря этому мне не приходится создавать явные алгоритмы поиска или списки для хранения позиций, потому что всё выполняется параллельной обработкой.

Поиск «минимакс» (бесплатный)

Последняя часть процесса — реализация функции compute_and_score_legal_boards таким образом, чтобы она обеспечила нам поиск «минимакс» на глубину 2. И на этом этапе я жульничаю (очень активно).

Мы можем запросто генерировать псевдодопустимые ходы, то есть ходы, которые допустимы, но могут создавать шах для короля. В шахматах это не допускается (нельзя завершать свой ход шахом), поэтому далее мне нужно было сделать так, чтобы удалялись все ходы, оставлявшие короля под шахом.

Для этого я снова генерировал все возможные ответы противника и проверял, могут ли какие-то из них приводить к «взятию» короля. Если они могут, то позиция недопустима, потому что это и есть определение шаха. Но это означает, что мы уже выполняем поиск на глубину 2. У нас есть исходное состояние доски. Глубина 1: мы генерируем все возможные ходы, которые хочет сделать компьютер. Глубина 2: генерируем все возможные ходы, которые может сделать противник, чтобы гарантировать, что мы не находимся под шахом.

Теперь нам достаточно лишь вычислить оценку каждого из этих сгенерированных противником ходов и вернуть оценку позиции-кандидата как наилучшую оценку из них всех (с точки зрения противника). А затем я просто могу взять в качестве его лучшего хода их наилучшую оценку (с точки зрения компьютера).

Здесь возникает одна небольшая проблема, из-за которой этого не делают реальные шахматные движки. Дело в том, что, строго говоря, это не полный поиск «минимакс» на глубину 2, потому что позволяет быть недопустимыми генерируемым в ответ ходам противника, потому что они могут привести к шаху его короля. Поэтому чтобы всё было корректно, необходим бы был поиск на глубину 3, что существенно повысило затраты на поиск. Поэтому я просто этого не делаю.

Важно отметить, что компьютер никогда не генерирует недопустимого ответа. Это просто означает, что в некоторых случаях генерируемый им ответ не будет таким же сильным, как при выполнении полного поиска «минимакс» на глубину 2, потому что он может допускать, что противник может сделать недопустимый ход.

Всё остальное

Программа далеко не ограничивается этим. Если вам любопытно, то рекомендую изучить полный исходный код на GitHub. Мне кажется, самое интересное в нём из того, что мы не рассматривали — это:

• Как распараллелить генерацию ходов для двигающихся скольжением фигур (слоны, ладьи и ферзи) так, чтобы все они рассчитывались точно в одно время

• Как реализована рокировка со специальными обработками ситуации «эта клетка находится под боем

• Преобразование из шахматной доски FEN в доску, имеющую по одной переменной на клетку, и обратно

• Распознавание права на рокировку отслеживанием позиций короля и ладьи

• Реализация распознавания и отслеживания взятия на проходе

• Две тысячи строк тестов, валидирующих корректность движка в течение тысяч игр

Трюки для обеспечения производительности

Под конец я опишу некоторые забавные оптимизации производительности. Изначально мой код генерировал каждый ответ человеку примерно полчаса; это идеально для шахмат по переписке, но не совсем подходит для игры через браузер. Готовый код на моей машине генерирует ход примерно от одной до десяти секунд, в зависимости от позиции. То есть мне удалось ускорить выполнение примерно на два порядка.

(Я уже показал свой любимый трюк: параллельную обработку. А теперь я расскажу кое о чём ещё.)

Удаляем промежуточные переменные

Одним из самых серьёзных убийц производительности в первой реализации было хранение слишком большого количества промежуточных переменных. Каждый поиск переменной для нахождения значения требует сканирования всей строки состояния, а это операция O(n). Кроме того, когда мы выполняем fork состояний выполнения, нам нужно копировать все этих переменные, что существенно увеличивает размер используемой памяти.

Благодаря агрессивному удалению переменных сразу после того, как они становятся ненужными, и по возможности многократному использованию имён переменных мне удалось существенно снизить и время вычислений, и занимаемую память. Для оценки одного хода теперь требуется примерно 300 МБ внутреннего состояния, что значительно меньше 10 ГБ неоптимизированной версии.

Быстрое сопоставление регулярных выражений

Вспомним, что ранее я определял условный оператор следующим образом:

def cond(tag):
    return [(r"%(%\n#stack:\nTrue)",
             r"%\1`"),
            (r"%(\n#stack:\nFalse)",
             tag+r"\1`"),
            (r"\n(True|False)`\n",
        "\n")]

Как вы думаете, почему третье регулярное выражение написано таким образом? Не было ли короче написать его так:

def cond(tag):
    return [(r"%(%\n#stack:\nTrue)",
             r"%\1`"),
            (r"%(\n#stack:\nFalse)",
             tag+r"\1`"),
            (r"(True|False)`\n",
             "")]

Обратите внимание на отсутствующий символ новой строки \n.

Оказывается, первая версия повышает эффективность этой команды в два раза! И всё это благодаря изменению всего одного символа! Причина этого заключается в тонкостях работы регулярных выражений и их сопоставления.

Во всём коде будет множество строк True/False. Но большинство из них будет частью переменных, а не верхним элементом стека. Потребовав наличия предыдущего символа новой строки и префикса #stack:\n" в паттерне, мы гарантируем, что regex-движок сможет быстро пропускать все строки True/False, встречающиеся в именах или значениях переменных. Это существенно снижает количество попыток сопоставления, которые необходимо выполнять regex-движку.

Написание узкоспециализированных команд

Иногда стоит писать специализированные команды вместо того, чтобы комбинировать имеющиеся. Например, одна из самых медленных частей в первой реализации находилась в цикле, сканировавшем каждую из клеток, чтобы найти все фигуры одного типа. Для этого требовалось множество условных конструкций, а внутри каждой конструкции множество операций со стеком. Однако можно просто преобразовать всё тело цикла в одну regex-команду:

def do_piece_assign(piece_chr, piece, x, y, pos):
    return [(f"%%([^%]*#{pos}: {piece_chr}[^%]*)" +
            f"#{piece}x_lst: ([^\n]*)\n" +
            f"#{piece}y_lst: ([^\n]*)\n" +
            f"#{piece}pos_lst: ([^\n]*)\n",
            fr"%%\1#{piece}x_lst: {x};\2\n" +
            fr"#{piece}y_lst: {y};\3\n" +
            fr"#{piece}pos_lst: {pos};\4\n")]

Последняя серьёзная оптимизация связана с максимизацией параллельного выполнения. Вспомним, что наш regex-может одновременно обрабатывать множество состояний, то есть вместо того, чтобы генерировать по одному за раз, мы можем сгенерировать их все одновременно.

Например, при генерации ходов ладей вместо проверки каждого направления последовательно мы можем форкнуть восемь параллельных состояний, по каждому из возможных направлений. (Стоит отметить, что «вверх» и «вниз» — это разные направления.) Затем каждое состояние перемещает свою ладью максимально далеко в этом направлении. Это превращает то, что могло бы быть циклом, в единую параллельную операцию.

Аналогично, при вычислении оценки позиций мы не оцениваем по одной позиции за раз, а создаём параллельные состояния для каждой позиции-кандидата и оцениваем их все одновременно. Такая параллельная оценка особенно эффективна, потому что большинство наших операций (например, подсчёт значений фигур) работает идентично для всех состояний.

Заключение

Каким должно быть завершение подобного поста? Особых выводов у меня нет. Думаю, просто скажу, что больше людей должно заниматься такими бесполезными вещами. Это очень весело, да и никого не волнует, сколько времени вам потребуется для завершения, никому не важно, заработает ли результат; к тому же так вы больше узнаёте о десятках областей computer science вне вашей работы.

Надеюсь, в этом году я создам ещё несколько таких совершенно бессмысленных проектов. Если вам нравится подобное, то советую прочитать статью о том, hкак играть в крестики-нолики при помощи конструкции printf языка C или как я написал клон Doom в 13 кБ кода на JavaScript.