Comments 102
Хоть бы скриншот вставил.
Здорово! Все же хочется крупную картинку, а лучше видео с процессом, и т.п… И самое главное — мировое сообщество уже знает об этом прорыве? Автор Atomchess уже прислал поздравления? Это я без иронии, я в смысле, что нужен пиар достижений.
Сразу вспомнилось, как в свое время с товарищем в техникуме решили написать резидентный переключатель клавиатуры (с русского на английский и обратно) под MS-DOS, который бы занимал в памяти как можно меньше места. В итоге получилось что-то около 80 с чем-то байт (точный размер не помню уже )) ). Была толстая книжка по командам ассемблера и я выискивал более короткие аналоги использованных команд. Например, классическое XOR DX,DX для очистки регистра вместо MOV DX,0.
80 с чем-то байт? Да это просто монстр :P
А я в детстве написал вирус. Поскольку делать TSR я не умел, придумал полностью спрятать в таблице векторов прерываний. С тех пор и пытаюсь всё ужать до предела…
А я в детстве написал вирус. Поскольку делать TSR я не умел, придумал полностью спрятать в таблице векторов прерываний. С тех пор и пытаюсь всё ужать до предела…
Ну получилось так мало, потому что PSP-блок в 256 байт нужно было еще убрать, он в резидентной части был уже не нужен после загрузки.
Помню, в детстве был у меня на рабочем столе com-файл для перезагрузки, состоящий из одного far-jump на начало BIOS. :)
(смахивая пыль с тетради), так эта ж:
dec [0000:0413]
А можно для тех, кто не в теме, что этот код делает? Если речь об x86, то по этому адресу должен обработчик int 82h располагаться, а я такого раньше не встречал (максимум 80h в Linux/FreeBSD, а в DOS я помню только 33h для работы с мышкой).
В эпоху, когда «640К должно было хватать всем» в этой ячейке размещался объем доступной ОЗУ и MS-DOS выстраивала структуры памяти до этой границы. Boot-вирусы тех времен уменьшали значение и размещались в этом заветном килобайте.
И да, это не «код» в чистом виде, а лишь иллюстрация.
должен обработчик int 82h располагаться256*4=1024=400h [0000:0400]
Не должен.
Круто. А картинки русских букв не загружались? У меня бел резидентный переключатель треков на CD в 252, кажется, байта. Правда MSCDEX был нужен, не смог найти как прочитать список где треки прочитаются, а запускать с произвольного месте совсем без драйверов получилось (после очень долгих копаний в отладчике, оказалось, что довольно просто).
Я испугался, что вы о русских буквах в шахматах :O
Кстати, в Classic-вариации LeanChess русификация реализуется элементарной заменой значений disp_db без увеличения размера (естесвенно, требуется кириллический BIOS).
Кстати, в Classic-вариации LeanChess русификация реализуется элементарной заменой значений disp_db без увеличения размера (естесвенно, требуется кириллический BIOS).
Нет, только переключение. KeyRus вроде как умел загружать русские буквы и переключение.
Вам срочно надо в Google, клавиатура для Android уже больше 300Mb
Не удивительно, учитывая, сколько туда напихано: словари и раскладки под любой язык (минимум 2 предустановлено), ввод свайпом, голосовой ввод, рукописный ввод (с локальным распознаванием), подсказки с самообучением, несколько режимов отображения, интеграция с поиском, переводчиком и облачным буфером обмена, эмоджи, адаптив, кастомизация. Может ещё что-то забыл.
Минимальная вариация в виде COM-файла для DOS занимает 328 байт
Получается, что можно погрузить это в MBR и пока не выиграешь система не загрузится?
А если добавить размножение, то уу...
Ага, Atomchess, например, запускается из boot-сектора (LeanChess пока так не умеет).
Ну лучше уж в шахматы сыграть, чем на криптовымогателя глазеть.
Кстати да, MBR можно весьма сильно упростить, если принять «первый раздел — всегда валидный загрузочный», то хватит 40-50 байт на его копирование и передачу управления.
Мсье определённо знает толк… Молодчина.
Тэг "новости" порадовал.
Что то вспомнилась попытка редакции «Техники Молодёжы» (и читателей) написать программу шахмат для ПМК МК-61, Б3-34 в 1986-1988 гг. Правда у них только эндельшпильды получились.
Ещё можно попробовать более полноценную программку сделать под Win32, но скажем чтобы килобайт 5-6 была.
Ещё можно попробовать более полноценную программку сделать под Win32, но скажем чтобы килобайт 5-6 была.
Кстати, мне давно не дает покоя философская мысль о том, что любое ПО (программа) – это набор байт. А набор байт – это какое-то (агроздоровенное) число. Т.е. фактически весь существующий и будущий софт – пронумерован!
И появление таких крохотных шедевров все быстрее и быстрее приближает момент, когда по новостям прозвучит: «открыто очередное число, которое играет в шашки лучше всех на свете, и история этой игры теперь благополучно закончена навсегда».
Число само по себе ничего не делает даже если является точной копией программы.
Чтобы программа работала нужно железо которое ее будет выполнять.
Более того нужно железо подходящее именно для этой программы.
Не говоря о том что программы работают на голом железе в основном в микроконтроллерах, в ПК программы работают взаимодействуя с кучей других программ зашитых в железки
Ладно «число», вот когда-нибудь «решат» шахматы — и всё закончится.
Забавная шахматная шутка от кубинского гроссмейстера Хосе Рауля Капабланки.
«Однажды я участвовал в турнире в Германии, когда ко мне подошел мужчина. Решив, что ему нужен всего лишь автограф, я потянулся за ручкой, но тут мужчина сделал поразительное заявление:
— Я решил шахматы!
Я стал благоразумно отступать, на случай, если мужчина был столь же опасен, сколь и безумен, но он продолжил:
— Спорим на 50 марок, что если вы пойдете со мной в мой гостиничный номер, я смогу это доказать?
Что же, 50 марок есть 50 марок, так что я решил быть снисходительным, и проводил мужчину к его номеру.
Оказавшись в номере, он уселся за шахматную доску.
— Я все понял, белые ставят мат на 12 ходу независимо ни от чего.
Я играл черными возможно чересчур осторожно, но обнаружил, к своему ужасу, что белые фигуры координируются как-то странно, и что я получу мат на 12-м ходу!
Я попробовал снова, разыграв на этот раз совершенно иной дебют, из которого в принципе невозможно было попасть в такое положение, но после серии очень странно выглядящих ходов, я снова обнаружил своего короля окруженным, и мат должен был прийтись на 12-й ход. Я попросил мужчину подождать, а сам сбегал вниз и позвал Эммануэля Ласкера, который был чемпионом мира до меня.
Он был настроен крайне скептично, но согласился хотя бы придти и сыграть. По пути мы наткнулись на Алехина, который был текущим чемпионом мира, и вот все трое мы вернулись в тот номер.
Ласкер не рисковал, но играл настолько осторожно, насколько это вообще возможно, и тем не менее, после причудливой, бессмысленно выглядящей серии маневров, обнаружил себя зажатым в матовой сети, из которой не было выхода. Алехин тоже попробовал, но опять же не преуспел.
Это был какой-то кошмар! Вот они мы, лучшие игроки в мире, люди, посвятившие все свои жизни игре, и вот теперь всё кончено! Турниры, состязания, всё — шахматы решены, белые побеждают...»
Тут один из друзей Капабланки вмешивается, со словами:
— Погодите минутку, я никогда ни о чем таком не слышал! И что случилось дальше?
— Как что, мы его убили, конечно!
Я тебе больше скажу — любую шахматную программу можно найти в двоичной записи числа Пи. Нужно только знать откуда начинать.
Нет. Из бесконечного количества цифр в числе πи вовсе не следует, что они образуют в нём все возможные комбинации.
Однако можно разбивать код этой шахматной программы на последовательность байтов, которые гарантированно содержатся в π, и получать не пару «смещение+размер», а последовательность таких пар. Кажется, я где-то это уже видел. Ах, да, точно. :)
Вот так из комментариев к статье о самой маленькой шахматной программе я и узнал, что в числе Пи, оказывается, не закодированы Халф-лайф и «Война и мир». Спасибо!
Пожалуйста) Даже если принять нормальность числа пи, то для поиска произвольного набора чисел их нужно знать заранее. Любое декодирование невозможно без предварительного кодирования; и поскольку в число πи Халф-лайф 3 никто не кодировал, то для его извлечения его всё равно необходимо закодировать в смещении, а длина этого смещения совсем не обязательно должна иметь конечный набор цифр.
Если выбросить из LeanChess всю шахматную логику, она и будет таким (самым маленьким на сегодня) числом. Шашки это слишком просто.
не дает покоя философская мысль о том, что любое ПО (программа) – это набор байтТаки да. Рекомендую хорошую книгу «Читаем Тьюринга» Петцольда, там в частности это разбирается.
И появление таких крохотных шедевров все быстрее и быстрее приближает момент, когда по новостям прозвучит: «открыто очередное число, которое играет в шашки лучше всех на свете, и история этой игры теперь благополучно закончена навсегда».
Насколько я помню, шашки уже решены довольно давно.
Т.е. фактически весь существующий и будущий софт – пронумерован!
И не только софт, но и все возможные данные, все прошлые, будущие, и никогда не выпущеные фильмы, музыка, изображения, и да, третья часть той самой игры тоже существует в виде числа!
Более того, научно доказано, что любой файл можно разложить на два числа Бабушкина и за счёт этого этот файл можно сильно сжать(иногда) — habr.com/ru/post/198114 :-)
В какой-то момент возникла идея переключиться на оптимизацию. Как выяснилось, с уменьшением размера программы она становится более доступной для понимания и отладки.
Это наблюдение вполне совпадает с моим опытом. И показывает, что в ассемблере не надо боятся оптимизировать на ранних стадиях разработки. Они часто помогают сделать код проще и понятнее.
Проиграв, закройте окно эмулятора.
— шансов выиграть нет совсем?
А вот интересно — какой размер занимает ИИ и какой графика, управление и прочее вспомогательное?
Как организовано хранение данных?
Вы оптимизировали алгоритм или только ассемблерный код?
Сколько процедур и сколько goto-переходов? Рекурсия применялась?
Как организовано хранение данных?
Вы оптимизировали алгоритм или только ассемблерный код?
Сколько процедур и сколько goto-переходов? Рекурсия применялась?
Благодарю за вопрос, коллега :)
Объём модулей в Barebone DOS edition:
- Инициализация — 56
- Вывод — 26
- Ввод — 24
- Логика игры — 204
- Управление и прочее — 18
Данное разделение несколько условно, поскольку, вследствие жёсткой оптимизации, рамки между модулями немного размыты. У меня нет точных сведений по размерам отдельных модулей (в какой-то момент перестал отслеживать).
Данные хранятся в виде массива 10+10x12.
Статистика по Barebone DOS edition (в BIOS на процедуру больше):
call— 5ret— 2loop/loopz— 5rep— 2jmp— 1 (бесконечный основной цикл)
Последний можно считать управлением, т.о., размер модуля управления — 2.
Оптимизировано всё, алгоритм и код неразделимы. Рекурсия, естественно, применялась — иначе не было бы ИИ.
Спасибо! Под «управлением» подразумевался пользовательский ввод, это же игра )
Можно чуть подробнее про данные? Что хранится в векторах? Мне не очень понятно, возможно потому, что ничего не смыслю в шахматах :( Догадываюсь что один из массивов это возможные ходы разных фигур, это так?
Код действительно впечатляет (что вполне ожидаемо). Сколько приблизительно по времени заняла вся работа?
Можно чуть подробнее про данные? Что хранится в векторах? Мне не очень понятно, возможно потому, что ничего не смыслю в шахматах :( Догадываюсь что один из массивов это возможные ходы разных фигур, это так?
Код действительно впечатляет (что вполне ожидаемо). Сколько приблизительно по времени заняла вся работа?
В общем, надо писать продолжение статьи :)
Будем рассматривать отдельно метаданные (то, что уже в коде) и данные (шахматную доску).
Метаданные заданы в массивах (опять-таки, в самой "тощей" вариации):
init_db— то, из чего формируется доска при инициализации,moves_db— на каждую фигуру: кол-во векторов, дальность, адрес первого вектораvec_db(условно) — векторы ходовeval_db— величина для оценочной функции на каждую фигуру
Данные — стандартные 10x12 плюс дополнительный ряд сверху от верхнего ряда (вместо байта слева).
Вся работа заняла около двух недель (при этом остались наработки для полной реализации).
Самые легковесные шахматы для ПК были созданы Дэвидом Хорном (David Horne) в 1982-м. Они занимали 672 байта из 1000 байт тогдашних внутренних накопителей. Сегодня на компьютерах можно встретить тербайтные накопители, но это не помешало Оливеру Паудади (Olivier Poudade) сделать 472-х байтную версию шахмат. Но ваши, это круто!!!
Верно, я не упомянул 1K ZX Chess в статье (но не забыл о них, см. описание на английском). LeanChess немного не дотягивают по функционалу, но получились более, чем в два раза легче.
<francophilia-mode>Не Оливеру Паудади, а Оливье Пудад</francophilia-mode>
Что за килобайтный накопитель в 1982 году? Странное уточнение.
Я не понял, как ей можно проиграть. Ощущение, что программа делает первый ход из возможных, а не ищет что-то каким-то алгоритмом.
Вы выиграли? Тогда будьте добры, опубликуйте партию.
Детский мат можно влегкую поставить (другое дело, при таких жестких ограничениях на размер программы вряд ли можно что-то с этим сделать):
Кстати, программа продолжает играть после мата, так что в каком-то смысле у нее и правда нельзя выиграть :)
1. e4 h6
2. Bc4 h5?
3. Qf3 h4??
4. Qxf7#
Кстати, программа продолжает играть после мата, так что в каком-то смысле у нее и правда нельзя выиграть :)
Думаете, это так сложно? Эта штука делает совершенно неадекватные ходы.
1. e4 h6
2. d4 h5
3. Nf3 h4
4. Bc4 h3 LeanChess как будто продолжает делать первый ход из возможных
5. gxh3 Rxh3 чудо-дебют
6. Nc3 Rg3?? отдает ладью
7. hxg3 g6
8. Ne5 Bg7?? отдает ферзя
9. Nxf7 Bh6
10. Nxd8 Bxc1
11. Qxc1 e6 не забирает коня
12. Qg5 d6
13. Qxg6+ Kd7 дальше уже не интересно
14. Qxe6+ Kxd8
15. Qf7 Ne7
16. Rh8+ Kd7
17. Qe8# d5 на доске мат, LeanChess как ни в чем не бывало продолжает
18. Qxd7 съедаю короля, продолжаем игру... Bxd7Там нужно ставить глубину поиска ходов хотя бы 4. Я собирал на 4, вполне неплохо играет (хоть и по прежнему со странного дебюта 1… h6).
При этом скорость эмуляции CPU желательно хотя бы поднять до 30000 (cycles=30000) в конфиге dosbox.
Попозже попробую поднять глубину поиска выше 4 (интересно, до какого значения можно ее поднять, так, чтобы не упереться в лимит производительности железа).
При этом скорость эмуляции CPU желательно хотя бы поднять до 30000 (cycles=30000) в конфиге dosbox.
Попозже попробую поднять глубину поиска выше 4 (интересно, до какого значения можно ее поднять, так, чтобы не упереться в лимит производительности железа).
Спасибо. Должен признаться, что опыт как в DOSBox, так и в шахматах, у меня нулевой.
Дебют h6 объясняется очень просто: поиск снизу вверх с выбором первого максимума. Если поменять порядок поиска (или критерий выбора), получится дебют Na6, а дальше (если защищаться от коня) ладья начинает тупо метаться в углу.
В рамках ограничений, думаю, получилось не так плохо.
Дебют h6 объясняется очень просто: поиск снизу вверх с выбором первого максимума. Если поменять порядок поиска (или критерий выбора), получится дебют Na6, а дальше (если защищаться от коня) ладья начинает тупо метаться в углу.
В рамках ограничений, думаю, получилось не так плохо.
Попробовал глубину 5. Думает по десять-двадцать секунд, но играет поинтереснее:
1. e4 g7
2. Qg4 h7
1. e4 g7
2. Qg4 h7
Здорово! Кстати, есть такой шахматный движок, Stockfish, так его в свое время портировали с C++ на assembler. И эта портированная версия стала называться asmFish. Размер при портировании уменьшился с ~1 Mb до 100 Kb, при том что скорость работы движка выросла на 10-15%. В голове не умещалось, как 100 Kb файлик может играть на уровне 3600 эло человеческих
Stockfish был до недавнего времени лучшим в мире.
Не представляю, как такое портируется на ассемблер. Думаю, проще взять откомпилированный C++ и оптимизировать проблемные участки.
P.S. Говоря о 100Kb, мы, скорее всего, не учитываем объём библиотек дебютов и эндшпилей.
Не представляю, как такое портируется на ассемблер. Думаю, проще взять откомпилированный C++ и оптимизировать проблемные участки.
P.S. Говоря о 100Kb, мы, скорее всего, не учитываем объём библиотек дебютов и эндшпилей.
Да, библиотеки из asm версии «выпилены». Но можно избавиться от них компиляцией с ключом static, что ужмет C++ версию до 250 Kb.
P.S. Говоря о 100Kb, мы, скорее всего, не учитываем объём библиотек дебютов и эндшпилей.
В принципе они не так уж и важны. В сумме дают около 100 пунктов рейтинга. Что составляет примерно половину разницы в один спортивный разряд. Ощутимо, но не определяюще.
Мощно
Это всё очень круто, но как отличить свои от чужих, если на скриншоте все фигуры одного цвета?
leanchess, полагаю, вы знаете про Code Golf, ваше достижение — именно из этой сферы (и это действительно круто). Вот тут обсуждение по теме: codegolf.stackexchange.com/questions/45179/smallest-chess-program
Спасибо.
Size-coding и code golfing — немного разные вещи. Я как раз добавил там ответ, но его стёрли (при этом ответ reeagbo оставили) — может, потому что указал ссылку, а не выложил код целиком.
Да, я перепутал size-coding и code golfing. И у reeagbo там тоже в качестве показателя размера указан размер скомпилированного бинарника (т.е. характеристика с точки зрения size-coding). И да, похоже, там надо выкладывать код, иначе трудно объяснить, почему ваше решение стёрли (как минимум по размеру бинаря вы «выиграли» у reeagbo.
Это довольно распространённая ошибка; собственно, Alex Garcia сам об этом написал. В любом случае, я добавил код и проголосовал за undelete. Для того, чтобы ответ стал видимым, нужны ещё голоса ;)
Да, автор по ссылке оставил свой ответ за три часа до публикации этой статьи, предвосхитив мой комментарий, что неплохо бы там отметиться – и теперь его там стёрли. Облом-с. :/
Ходы соперника вообще не проверяются на корректность.
Проверку хода можно сделать на основе допустимых ходов компьютера — это должно помочь сэкономить место.
Думал, что меньше 10 килобайтных «Chess88» Дона Берга шахмат не бывает. Правда, там была ещё CGA графика.
Проверку хода можно сделать на основе допустимых ходов компьютера — это должно помочь сэкономить место.
Разумеется. Задача — не просто сэкономить место, а максимально сэкономить место.
UFO just landed and posted this here
Почему-то вспомнилась игра на Dendy c Take 5 в качестве саундтрека и очень слабым ИИ. Интересно, можно ли используя современные оптимизации написать реально сильные шахматы на восьмибитную платформу?
Что вы называете современными оптимизациями? Не думаю, что за последние двадцать лет изобрели что-то новое. Подозреваю, что для того, чтобы получить сильные шахматы на слабом процессоре, придётся идти окольными путями — например, запихнуть в картридж огромный ROM с библиотеками дебютов и эндшпилей.
Ну, CPU помощнее тоже можно в картридж запихнуть, как это на SNES делали, с en.wikipedia.org/wiki/List_of_Super_NES_enhancement_chips#SA1 или тем же Super FX.
А если серьёзно, то всё же продвинутые ассемблеры, дебаггеры, накопленный опыт и т.д. позволили к концу жизненного цикла Famicom/NES делать более сложные и навороченные игры, чем ранние, даже если они уже использовали мапперы и доп. (V)ROM/(V)RAM.
А сейчас еще и эмуляторы есть, что позволяет перепробовать разные финты гораздо быстрее, чем прошивая каждый раз eeprom и втыкая в консоль
А если серьёзно, то всё же продвинутые ассемблеры, дебаггеры, накопленный опыт и т.д. позволили к концу жизненного цикла Famicom/NES делать более сложные и навороченные игры, чем ранние, даже если они уже использовали мапперы и доп. (V)ROM/(V)RAM.
А сейчас еще и эмуляторы есть, что позволяет перепробовать разные финты гораздо быстрее, чем прошивая каждый раз eeprom и втыкая в консоль
Насколько мне известно, как раз в те поры основная стратегия шахматного ПО была в зашивании как можно большего количества исторических данных, с оценками тех или иных ситуаций. Современные шахматные приложения становятся все более и более «умными», в них хитрым образом закладываются различные стратегии. Возможно это бред, но учитывая развитие шахматных машин как таковых, шахматная машина написанная сейчас, даже с известными техническими ограничениями, по моей версии должна на голову побеждать шахматную машину из прошлого. Не знаю:)
Не вопрос.
1. Выше уже писали про ассемблерную версию Стокфиша размером 120 Кб. Если выкинуть из него код поддержки эндшпильных баз (все равно нет места под сами базы), поддержку UCI-протокола (всё равно не будет универсальной графической оболочки), bench (тестировать будем по-другому), а также возможно кое-что ещё, то размер наверняка можно будет сократить.
2. Стокфишу можно дать в тысячу раз меньше времени, чем топовым движкам середины нулевых, обыгрывавшим тогда супергроссмейстеров, и он не уступит. Так что с силой игры тоже всё будет в порядке.
1. Выше уже писали про ассемблерную версию Стокфиша размером 120 Кб. Если выкинуть из него код поддержки эндшпильных баз (все равно нет места под сами базы), поддержку UCI-протокола (всё равно не будет универсальной графической оболочки), bench (тестировать будем по-другому), а также возможно кое-что ещё, то размер наверняка можно будет сократить.
2. Стокфишу можно дать в тысячу раз меньше времени, чем топовым движкам середины нулевых, обыгрывавшим тогда супергроссмейстеров, и он не уступит. Так что с силой игры тоже всё будет в порядке.
UFO just landed and posted this here
Может быть вы слышали про Micro-Max? Он, правда, написан под несколько иную задачу — программа должна быть сильнее в пунктах рейтинга, чем число символов в этой программе.
Sign up to leave a comment.
LeanChess — самые маленькие компьютерные шахматы в мире