Я всегда хотел написать движок для шахмат, но никак не решался. Интересно, так ли это безумие?

Своего рода отвлечение

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

Так или иначе. Учитывая, что это Рождество будет не похоже ни на одно другое — мы находимся в изоляции от COVID на время — я подумал, что было бы интересно выбрать программный проект, с которым можно было бы повозиться — своего рода отвлечение от бесконечного потока рождественских фильмов Hallmark.

Игра королей

Я всегда хотел написать движок для шахмат, но никак не решался. Еще до того, как появились компьютеры, люди писали шахматные движки — Алан Тьюринг, как известно, спроектировал один из них на бумаге и запустил его на бумаге до того, как в Манчестере были построены первые машины, которые могли запускать такую ​​программу.

В прошлом я несколько раз писал половину шахматной программы — каждый раз попадая в разные кроличьи норы, исследуя различные необходимые структуры данных и методы манипулирования ими на скорости. Замечательная вещь в программировании шахматного движка заключается в том, насколько хорошо документированы прошлые проекты — от научных исследований до проектов с открытым исходным кодом, таких как «Crafty» Роберта Хаятта.

Существование такого большого количества существующих исследований и разработок является одновременно и благословением, и проклятием, потому что меня всегда интересовало изобретение велосипеда. Хотя повторение того же пути, что и бесчисленное множество предыдущих разработчиков, может показаться безумием, в умственном упражнении по разбиению проблемы есть академическое очарование — решение каждого аспекта гораздо более крупной проблемы и наблюдение за тем, как кусочки головоломки медленно соединяются с друг друга.

Не хватает точки

Мне интересно, не упускаю ли я смысл в создании шахматного движка с нуля. Конечно, самое интересное в обучении машины играть в игру — это играть против своего творения? Имея это в виду, я начал искать готовые библиотеки с исходным кодом, которые, по сути, «решают» большое количество задач более низкого уровня в шахматной программе — например, «учитывая эту позицию на доске, каковы действительные движется?».

Имитация интеллекта

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

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

Я думаю, пожалуй, одним из самых интересных наблюдений — для меня — за последние годы стало появление искусственного интеллекта в сфере оценки. После того, как проект Deep Mind «Альфа-Ноль» уничтожил Stockfish в серии демонстрационных игр, академическое упражнение перешло не от «как заставить машину думать?», а к «как понять, как машина находит ответы? ».

Дуглас Адамс писал об этом

Мы уже были здесь раньше — в «Автостопом по Галактике» Deep Thought был создан, чтобы найти ответ на вопрос «Жизнь, Вселенная и все остальное». Он классно придумал ответ «42». Затем вопрос стал «если 42 — это ответ, то в чем вопрос?» — для расчета которого требовался гораздо больший компьютер. Она называлась «Земля» и, к сожалению, была уничтожена в первой главе книги, чтобы освободить место для межзвездного обхода.

Когда начать?

Проведя небольшое исследование, я собираюсь встать на плечи тех, кто был раньше — позаимствовав библиотеку Python Chess и просмотрев предыдущие статьи, такие как Андреас Стокл, — которые изложили основные строительные блоки реализации поиска и оценки. Я, наверное, вернусь и разберу еще Crafty — он реализует почти все известные трюки в погоне за человеческой игрой.

Если вы понятия не имеете, насколько успешными могут оказаться мои усилия — очевидно, что это далеко не Alpha Zero, и это ужасно точное восприятие окружающего мира. Но не в этом дело, а в том, чтобы повеселиться.

Первоначально опубликовано на https://jonbeckett.com 24 декабря 2020 г.