[Из песочницы] 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 доступна в трёх вариациях:
- Classic BIOS (342 байта)
- Barebone DOS (328 байа)
- Barebone BIOS (333 байта)
Все три играют одинаково, различия лишь в отображении доски (и нажатий клавиш). Не удивляйтесь «офицерам» в виде О в вариациях Barebone.
Для того, чтобы запустить игру, вам потребуется DOSBox. Вводите ходы в формате e2e4 без нажатия Enter. Проиграв, закройте окно эмулятора.
Ссылки:
P.S. Если интересны технические подробности, пожалуйста, сообщите в комментариях.
