LeanChess — самые маленькие компьютерные шахматы в мире

Меня зовут Дмитрий Шехтман, и я автор самых маленьких компьютерных шахмат в мире.

Началось всё с того, что моя (ныне бывшая) девушка предложила написать компьютерные шахматы. Идея меня заинтересовала, и я решил этим заняться. Правда, почитав интернет, я понял, что опоздал лет на сорок. Особенно впечатляли шахматные разработки Оскара Толедо — на Си размером в 1257 байт, на JavaScript в 1023 байта и, наконец, Atomchess на ассемблере x86, компилирующийся в 392 байта.

Прежде, чем я вернулся к теме, прошло несколько месяцев. Как оказалось, за это время был установлен новый рекорд размера — ChesSkelet для ZX Spectrum занимал всего 352 байта. Правда, он не знал всех правил и играл весьма слабо, но всё же! А не замахнуться ли мне на шахматы на ассемблере? — подумал я.

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

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

В результате нескольких «перезапусков» с исключением всего лишнего получился довольно изящный код. Предвидя возражения относительно того, что прыжок пешкой через поле нельзя считать лишним, предлагаю ознакомиться с описаним возможностей ChesSkelet-352. В какой-то момент возникла идея переключиться на оптимизацию. Как выяснилось, с уменьшением размера программы она становится более доступной для понимания и отладки. Немало помогло добавление комментариев к каждой строке. В конце концов ошибка нашлась.

Когда уже казалось, что дальше оптимизировать некуда, совершенно случайно обнаружились команды pusha и popa, позволившие сэкономить ещё около 18 байт (точные данные не сохранились). Atomchess был повержен. Правда, за счёт повышения требований к системе — до IBM PC AT.

Не останавливаясь на дальнейших этапах разработки, перейдём к итогам. Минимальная вариация в виде COM-файла для DOS занимает 328 байт — на 24 байта меньше предыдущего рекордсмена (напомним, восьмиразрядного). Как уже было сказано, речь не идёт о полноценных шахматах. Ходы соперника вообще не проверяются на корректность. Зато реализован ИИ в виде полного NegaMax-перебора глубиной в три полухода с оценкой по материалу (при увеличении глубины до четырёх скорость приемлемая).

На данный момент LeanChess доступна в следующих вариациях:

  • Barebone DOS (328 байт)
  • Barebone BIOS (333 байта)
  • Classic DOS (338 байт)
  • Classic BIOS (342 байта)
  • Все четыре (теперь) играют одинаково, различия лишь в отображении доски (и нажатий клавиш). Не удивляйтесь «офицерам» в виде О в вариациях Barebone.

    Для того, чтобы запустить игру, вам потребуется DOSBox. Вводите ходы в формате e2e4 без нажатия Enter. Проиграв, закройте окно эмулятора.

    Скриншот

    Ссылки

    P.S. Если интересны технические подробности, пожалуйста, сообщите в комментариях.
    P.P.S. Опубликована версия 1.1 с исправлением оценки слона и добавлением Classic DOS Edition.

    Оставить комментарий