...

пятница, 24 июля 2015 г.

TIS-100 — паззл про многопоточный ассемблер, который никто не ждал

image

Удивительно, но никто не написал ничего про игрушку «TIS-100», которая недавно появилась в Steam (стоит всего 150 рублей, уже 460 положительных отзывов против 6 отрицательных).

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

Итак, о чем игра?
Суть в том, что вам дается задание, которое нужно выполнить. Например «читайте число из IN.A, сравниваете с числом из IN.B и если IN.A > IN.B, пишете в выход IN.A-IN.B, иначе — IN.B-IN.A.

На самом деле, она очень простая и освоить здешний ассемблер может каждый. У него есть две фишки.

1. Он жутко минималистичный и от того — неудобной
2. Он многопоточный. Вот, те блоки, которые вы видите на экране — все они выполняются одновременно.

Для того, чтобы понять, что тут и как — вот вам самый первый уровень:

Задача простая. Читать из входа, удваивать, писать в выход.

Вот мое (самое прямолинейное) решение:

Код в первом блоке:

MOV UP, ACC       // читаем число из верхнего входа и кладем его в аккумулятор
ADD ACC           // прибавляем к аккумулятору аккумулятор
MOV ACC, DOWN     // отправляем значение аккумулятора вниз

Дальше уже просто число перекидывается между выходами.

Запускаем, программа проходит контрольный тест, все ОК. И мы видим результат:

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

Немного слов об ассемблере.


Сначала — операнды. Собственно, тут все просто. Это ожидаемые LEFT, RIGHT, DOWN, UP, ACC. А так же „ANY“ (которое читает из любого порта) и „LAST“ (читает из последнего порта). Есть еще NIL для обозначения „мусорного“ порта.

Также, кроме аккумулятора, есть еще backup (BAK). С ним нельзя работать напрямую, только через swap'ы (см. ниже).

Далее — список команд.

  • NOP — ничего не делает
  • MOV [1], [2] — запись из [1] в [2]
  • ADD [1] и SUB [1] — прибавить/вычесть к аккумулятору [1]
  • NEG — инвертация значения в аккумуляторе
  • SWP — обменять значения аккумулятора и BAK
  • SAV — сохранить аккумулятор в BAK
  • JMP — безусловный переход на метку (метки обозначаются как „LABEL:“)
  • JEZ (equal zero), JNZ (not zero), JGL (greater zero), JLZ (less zero) — условные переходы (аргументом сравнения является аккумулятор)
  • JRO [1] — относительный переход (вперед/назад на [1] инструкций)

Собственно, на этом все. Т.е. по сути у вас есть всего 1 регистр (плюс 1 запасной, к которому не так-то просто добраться) и несколько команд.

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

CMP 2
MOV 1, ACC // это на выход
JE LABEL


В результате чего мы перейдем по LABEL только если на входе параметр был равен 2, и при этом в аккумулятор мы положим на выход единичку (т.к. операция „MOV“ не изменить флаговый регистр).

В TIS-100 все не так. Чтобы выполнить что-то подобное, придется сделать так:

SWP // сохраняем значение аккумулятора
MOV 1, ACC // это на выход
SWP // меняем назад
SUB 2
JEZ LABEL


И это при том, что мы испортили первоначальное значение аккумулятора. Если потом придется его сравнить с другим числом, мы испытаем проблемы.

Собственно, в этом вся игра. Есть задания, есть просто песочница.

Думаю, программистом должно быть интересно. Особенно скучающим по хардкорным временам.

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

Комментариев нет:

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