Руководство программиста Sanmill

Sanmill — это программа для игры в «Мельницу».

Использование исходного кода регулируется лицензией GPL: подробности см. в файле Copying.txt.

Sanmill включает консольный движок игры «Мельница», который можно использовать с отдельно доступным интерфейсом для программ игры «Мельница» или с программами интерфейса, подобными UCI. Кроме того, доступны две пользовательские программы интерфейса Flutter/Qt для Sanmill; интерфейс Flutter взаимодействует с движком игры «Мельница» через канал.

Sanmill написан на C++ и Dart. Движок игры «Мельница» Sanmill поддерживает Windows (32- и 64-разрядные версии) и другие платформы, такие как Linux.

Sanmill в основном тестировался на процессорах Intel и AMD, но код разработан так, чтобы его можно было переносить на другие процессоры.

Остальная часть этого файла содержит информацию для программистов, читающих или работающих над исходным кодом Sanmill. Я предполагаю, что вы хорошо знакомы с C++. Кроме того, если у вас нет опыта работы с компьютерными настольными играми, вам, вероятно, следует начать с чтения некоторых справочных материалов, упомянутых в конце этого документа.

Сборка Sanmill

См. файл BUILD.md для текущих инструкций по сборке.

Обучение

Sanmill имеет позиционное обучение (также известное как «постоянный мозг»). Это, по сути, постоянная хеш-таблица. Если поиск возвращает неожиданно высокий или низкий балл, позиция и её оценка сохраняются в текстовом файле с именем endgame.txt, который находится в том же каталоге, что и исполняемый файл Sanmill. Когда начинается следующая игра, сохранённые позиции из этого файла считываются в память и сохраняются в хеш-таблице, позволяя программе обнаруживать опасность или возможность раньше, чем это было ранее.

Поддержка тестирования

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

Движок игры «Мельница» поддерживает пару команд для помощи в тестировании.

Алгоритмы и структуры данных

Доска игры «Мельница»

Ниже приведена некоторая информация об алгоритмах и структурах данных, используемых Sanmill.

Доска игры «Мельница» в Sanmill представлена массивом из 24 квадратов (точек), расположенных таким образом, что квадрат A1 имеет значение 8, а квадрат C8 — значение 31.

Каждый квадрат содержит SQ_NONE, если он пуст, или идентификатор фигуры, если он занят. Белые фигуры имеют значения идентификатора от W_PIECE_1 до W_PIECE_12, чёрные фигуры — от B_PIECE_1 до B_PIECE_12. Специальное значение (MARKED_PIECE) используется для представления отмеченного квадрата.

Класс Board также поддерживает несколько «битовых досок» или величин, содержащих 32 бита. Класс Bitboard в исходном коде инкапсулирует битовую доску. Например, занятая битовая доска имеет один бит, установленный для каждой фигуры на доске (на самом деле существует три таких битовых доски: одна для белых, одна для чёрных и одна для отмеченных).

У каждого типа фигур есть своя битовая доска, в которой установлен один бит для каждой фигуры этого типа (например, существует byTypeBB[MARKED] Bitboard для хранения отмеченных местоположений).

Помимо битовых досок, в структуре Board есть ещё некоторая информация. Переменная StarSquareBB содержит положение «звёздного» квадрата.

Каждая позиция на доске также имеет связанный с ней хэш-код. Хэш-код состоит из 32 бит и вычисляется путём извлечения для каждой комбинации фигуры и квадрата уникального 32-битного кода из таблицы случайных чисел и вычисления исключающего ИЛИ этих кодов. (Этот механизм хеширования был изобретён Зобристом — см. ссылки). Затем старшие 2 бита хэш-кода устанавливаются так, чтобы определить, сколько фигур можно убрать.

Ходы

Sanmill использует 32-разрядное слово для хранения информации о ходе. Каждый ход содержит начальный квадрат и конечный квадрат. Если начальный квадрат равен 0, тип хода — размещение, а если 32-разрядное слово отрицательное, тип хода — удаление.

Генератор ходов

Логика генерации ходов в основном содержится в... Функции generate<LEGAL> имеют отдельные процедуры для поиска всех ходов.

Генерация ходов происходит в определённом порядке, см. movegen.cpp.

Поиск

Sanmill использует альфа-бета алгоритм поиска с различными расширениями поиска. Пространство поиска — это самый большой отдельный модуль в программе, и оно обязательно довольно сложное, но я попытался структурировать его и прокомментировать так, чтобы оно было понятным. Я предполагаю, что читатель знает основы альфа-бета алгоритма, и сосредоточусь на описании этой реализации.

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

Точка входа для поиска — процедура под названием Thread::search(). Эта функция выполняет некоторую инициализацию, а затем вызывает MTDF(), который реализует алгоритм поиска MTD(f). Чтобы работать, MTD(f) нуждается в первом предположении о том, где окажется минимаксное значение. Чем лучше первое предположение, тем эффективнее будет алгоритм в среднем, поскольку чем лучше оно, тем меньше проходов должен сделать цикл «повторять до» для сходимости к минимаксному значению. Если вы дадите MTD(f) минимаксное значение для начала, он сделает только два прохода, минимум: один, чтобы найти верхнюю границу значения x, и один, чтобы найти нижнюю границу того же значения. Функция MTDF() вызывает search(), которая реализует альфа-бета алгоритм поиска. Поиск продолжается один плёс (полуход, то есть ход одной стороны) за раз. То есть сначала выполняется поиск на один плёс, затем на два плёса, затем три и т. д., пока либо не будет достигнут максимальный предел плёсов, либо не превышен контроль времени. Каждый поиск использует результаты предыдущего поиска. Переменная originDepth содержит текущую номинальную глубину плёса для поиска. Однако наличие расширений поиска означает, что некоторые узлы могут быть исследованы на большую или меньшую глубину, чем эта.

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

Первый шаг в search() — проверить, не является ли текущая позиция доски ничьей из-за трёхкратного повторения ходов или правила N-хода.

Sanmill также немедленно завершит поиск, если будет достигнута абсолютная максимальная глубина плёса. Это маловероятно.

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

Хеш-таблица

Процедура поиска использует хеш-таблицу для хранения результатов оценки ранее посещённых позиций. Эта таблица реализована в нескольких статических функциях, определённых... Хэш-таблица в основном представляет собой массив списков. Каждый список содержит серию узлов, каждый из которых содержит некоторые данные. Каждый список хранит записи, которые хешируются по модулю размера хэш-таблицы к одному и тому же значению.

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

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

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

Sanmill обычно заменяет только те записи, глубина которых больше существующих записей или записи, полученные в результате более раннего поиска (т. е. чьё поле «возраст» не соответствует текущему поиску).

Размер основной хэш-таблицы по умолчанию составляет 128 мегабайт. Стандартные команды UCI также могут использоваться для изменения размера хэш-таблицы во время выполнения.

Оценка позиции

Существует примерно три основных компонента позиционной оценки, используемой Sanmill:

1. Количество фигур в руке.
2. Количество фигур на доске.
3. Количество фигур, которые можно убрать.

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

Оценка структуры пешек выполняется в два этапа. Сначала проверяется хэш-таблица, чтобы получить оценку позиции. Если позиция не найдена в хэш-таблице, то вызывается процедура Evaluation::value(). Эта процедура вычисляет только параметры оценки, зависящие только от количества фигур.

Пользовательский интерфейс Flutter

Движок игры mill теперь работает как отдельный процесс, который взаимодействует с пользовательским интерфейсом через канал.

По сравнению с Qt UI, пользовательскому интерфейсу Flutter не хватает некоторых функций: например, он не может использоваться для связи с игровым сервером mill.

Пользовательский интерфейс Flutter представляет собой довольно стандартную программу Dart.

Поддержка

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

Контактная информация и дополнительная информация о Sanmill доступны на сайте https://github.com/calcitem/Sanmill.

Развёртывание

Android

Используйте GitHub Actions для сборки. Загрузите файл aab и загрузите его в Play Console. Загрузите apk из Bundle Explorer Selector и загрузите в Cafe Bazaar и другие магазины приложений.

iOS

./flutter-init.sh
cd src/ui/flutter_app
flutter build ios --release -v

Используйте Xcode -> Product -> Archive, чтобы заархивировать и загрузить ipa. Подождите некоторое время, откройте App Store Connect, добавьте новую версию и опубликуйте.

Linux

Snapcraft:

cd Sanmill
rm *.snap
snapcraft --use-lxd
sudo snap remove mill
sudo snap install --dangerous mill*.snap
sudo snap remove mill
snapcraft login
snapcraft upload --release=stable mill*.snap

Windows

./flutter-windows-init.sh
cd src/ui/flutter_app
flutter pub run msix:create

Используйте Windows App Cert Kit для проверки src\ui\flutter_app\build\windows\runner\Release\sanmill.msix. Откройте Microsoft Partner и загрузите файл msix.

Ссылки

Arasan Programmer's Guide — версия 22.0. Chess Programming Wiki, тема Magic Bitboards. Исходный код Stockfish. Donninger, Ch. (1993). «Null Move and Deep Search» ICCA Journal, v. 16 no. 3. Duchi, John, Hazan. Элард и Зингер, Йорам. «Адаптивные методы субградиента для онлайн-обучения и стохастической оптимизации». Журнал исследований машинного обучения, том 12, 2/1/2011, стр. 2121–2159.

Эбелинг, Карл. (1987). Все правильные ходы: архитектура VLSI для шахмат. MIT Press.

Фрей, Питер В. (ред.) (1983). Шахматное мастерство у человека и машины. Нью-Йорк: Спрингер-Верлаг.

Хоки, Кунихито и Канэко, Томоюки «Крупномасштабная оптимизация для оценочных функций с минимаксным поиском», Журнал искусственного интеллекта Research 49 (2014) 527–568.

Кингман, Дидерик П. и Ба, Джимми Лей ADAM: метод стохастической оптимизации, ICLR 2015.

Лай, Мэтью (2015) Жираф: использование глубокого обучения с подкреплением для игры в шахматы. Магистерская диссертация, Имперский колледж, Лондон.

Марсанд, Т. Энтони и Шеффер, Джонатан (1990). Компьютеры, шахматы и познание. Нью-Йорк: Springer-Verlag.

Томпсон, Уильям Р. «О вероятности того, что одна неизвестная вероятность превышает другую с учётом данных двух выборок». Биометрика, 25(3–4):285–294, 1933.

Вегнер, Зак (2011) Новые инструкции Хасвелла.

Зобрист, А. Л. (1970). «Новый метод хеширования с приложениями для игр», Технический отчёт 88, факультет компьютерных наук, Университет Висконсина.