Все гениальное - просто. Редко, очень редко такая простота становится мировым достоянием, и именно так случилось с Тетрисом - программой, изменившей жизнь одного конкретного человека, оказавшей влияние на историю игровой индустрии и подарившей счастье миллионам людей. Ее создатель, Алексей Леонидович Пажитнов, не нуждается в представлении.

К сожалению, далеко не все соотечественники знают «мировую» историю становления Тетриса, а между тем - это настоящий детектив, по накалу страстей не уступающий какой-нибудь «Санта-Барбаре».

На самом деле графическая и логическая идея Тетриса была придумана не Алексеем. В конце 70-х - начале 80-х по всему миру (и в СССР - в том числе) успешно продавались головоломки американского математика Соломона Голомба, самая известная их которых называлась Pentomino Puzzle. Их идея была довольно проста и до боли знакома любому современнику - из нескольких фигур, имевших знакомые сейчас (см. рисунок снизу) формы, нужно было собирать заданные фигуры. Судьбоносное знакомство Алексея с этой забавой состоялось в начале 80-х, когда такие головоломки были ещё в диковинку.

Алексей Пажитнов получил образование обыкновенного советского инженера, как и сотни тысяч людей в СССР. Работал он в те далёкие годы в Московском Авиационном Институте (из которого впоследствии вышло много талантливых и известных людей). По образованию Алексей, как и его вышеупомянутый американский коллега, был математиком, и потому как раз в начале 80-х годов познакомился с чудом компьютерных технологий, которые людям иных профессий были фактически недоступны. Как известно, в то время равнодушных к компьютерам людей просто не существовало - либо люди не признавали их и не видели в них большего смысла, чем в мебели, либо моментально влюблялись. Стоит ли говорить, что Пажитнов - не без собственного удовольствия - стал приверженцем второй группы. По его воспоминаниям, человек, оставшийся один на один с компьютером превращался в некоего старика Хоттабыча, и был способен на своё небольшое, локальное чудо.

Как только Алексею представилась возможность, он перебрался из института в вычислительный центр при Академии Наук, убив этим ходом сразу двух зайцев: занялся работой, которая ему была действительно интересна, и получил доступ к самой мощной вычислительной технике из существовавшей в то время в Союзе. На новом месте Пажитнов вплотную занялся проблемами создания искусственного интеллекта, компьютерной графикой и вопросами компьютерного распознавания голоса. На тот момент ему было 29 лет. Поэтому ничего странного не было в том, что в свободное от работы время он баловался написанием небольших и очень простеньких игрушек. Момент его перехода на новое место работы по счастливой случайности совпал с увлечением головоломками Голомба - и в светлой голове русского инженера впервые забрезжила идея о создании компьютерного варианта. Пажитнов довольно сильно дополнил идею - собирать «фигурки в стакане» предстояло в реальном времени, причём фигурки состояли из пяти элементов (Пентамино - от греч. «Пента» - пять), и по задумке должны были во время падения проворачиваться вокруг собственного центра тяжести. Увы, электронные «мозги» машин того времени оказались слишком слабы для воплощения идеи мозгов человеческих - для компьютерного «Пентамино» попросту не хватало ресурсов. Тогда Пажитнов принимает решение сократить количество блоков, из которых состояли падающие фигурки до четырёх, воплотив, таким образом «в цифре» не такое ресурсоёмкое «Тетрамино» (от греч. «Тетра» - четыре). Сокращённое название «Тетрис» прижилось чуть позже.

Нехитрая, в общем, идея дала впоследствии удивительные результаты. Первый вариант игры Алексей написал быстро - взяв за основу семь фигурок, ставших впоследствии стандартным набором Тетриса, за две недели он запрограммировал костяк игры. В ней в «стакан» падали даже не графические изображения фигур, а их текстовые аналоги - состоящие из пробелов, скобок и т.п. Выглядело это все до жути примитивно - игра создавалась на базе «народного» языка Pascal, и на компьютере «Электроника-60», у которого даже монитора нормального не было. Но зато игра работала, и ещё как работала!

Первое время за пределы той же лаборатории Тетрис не выходил. Пажитнов, апробировав начальный вариант на себе и коллегах, привлёк к делу соратника, шестнадцатилетнего Вадима Герасимова, и в течении двух месяцев была создана первая графическая, цветная версия Тетриса, обладавшая вменяемым управлением и мелкими приятностями, вроде таблицы рекордов. Важным моментом стал тот факт, что Герасимов фактически помог «портировать» игру на платформу PC, набирающую популярность с каждым днём. Вместе с PC популярность набирали и первые 5.25"" дисководы, поэтому вопрос первоначального «тиражирования» решился довольно быстро - скопировав получившуюся забаву на дискеты, Алексей сотоварищи распространили её по кулуарам НИИ. Друг переписывал у друга, затем давал копировать ещё троим знакомым, и потихоньку электронное «письмо счастья» расползлось по столице, и выскользнуло за её пределы. Игра становилась известной в СССР.

Шёл 1985 год, о Тетрисе поступали всё более и более тёплые отзывы, и постепенно Алексей склоняется к мысли о том, что с его творением должны ознакомиться и за рубежом. Первыми иностранцами, вкусившими прелестей программы русского гения, стали будапештцы из Института проблем Кибернетики, с которыми НИИ сотрудничал в те времена по одной из многочисленных программ «братских народностей». PC-версия Тетриса просочилась за границу, и уже в Венгрии, её адаптировали под нужды альтернативных платформ - Commodore С64 и Apple 2. На удачу Алексея, в тот момент в Институте гостил Роберт Штайн, венгр английского происхождения, преимущества которого не заканчивались одним лишь иностранным паспортом. Штайн, по роковому стечению обстоятельств, оказался владельцем собственной игровой студии Andromeda. Опытный делец моментально почувствовал потенциал игрушки. Не откладывая дела в долгий ящик, Штайн предлагает выкупить права сразу на все версии игры: на Apple 2 и С64 у венгров, а РС-вариант, соответственно, у русских. Сказано - сделано: Роберт телеграфирует в АН СССР, и русским по белому предлагает выкупить права на «Тетрис», правда пока без оглашения каких-либо конкретных сумм. Кто бы отвернулся от подобного подарка судьбы? Пажитнов был не из тех, кто упускает свой шанс, и он отвечает согласием.

Штайн в это время возвращается в Лондон, и приступает к поискам рынков сбыта игры, а Лондон - это уже (по меркам середины 80-х) Дальнее Зарубежье со всеми вытекающими для тех времён препонами. Поэтому из-за политических проволочек венгр получает исторический телекс с ответом Пажитнова только спустя полтора месяца. Однако вместо того, чтобы дождаться ответа, а затем по-человечески съёздить в командировку и подписать контракт, венгр не сидит без дела, он лихорадочно ищет, кому можно сплавить будущий хит. Сначала он предлагает вариант Тетриса тем, кто находится поближе - английской Mirrorsoft. Владельцем данной компании в тот момент значился медиа-магнат Роберт Максвелл, собственник британской газетной корпорации Mirror Newspaper Group и американской Macmillan. Позже он ещё скажет своё веское слово в этой истории. Господа из Mirrorsoft ознакомились с «Тетрисом», поиграли немного, и… кощунственно усомнились в способности продукта хорошо продаваться. Проект был отослан на альтернативную пробу к их американским коллегам в компанию Spectrum Holobyte. Хорошо разбирающиеся в играх и способах делать деньги из воздуха, американцы узрели в программе немалый потенциал. Янки сообщили своё мнение англичанам, а те договорились со Штайном. Результатом подобной чехарды стал контракт между Mirrorsoft и Andromeda, который исчислялся смехотворной суммой в 3000 фунтов стерлингов и плавающим процентом от доходов (7 - 15% в зависимости от количества проданных копий). И всё это Штайн провернул, не имея на тот момент прав от самого Пажитнова!

В это время Алексей Леонидович находился в Москве, в полном неведении относительно того, что происходит с его детищем. Поэтому, когда он получил второе послание от Штайна, в котором тот предлагал Пажитнову три четверти всех своих доходов, плюс неплохую сумму наличности - радости его не было границ. Не убавилось её и тогда, когда венгр «вдогонку» предложил оплатить часть аванса компьютерами Commodore, поскольку являлся в некотором роде официальным дистрибьютором данной компании. Алексей вроде бы был расположен и к такому развитию событий, но окончательного решения пока не принимал. Важным моментом в этих переговорах остаётся то, что речь шла только о РС-варианте Тетриса. Зимой 85 года Штайн приезжает в Москву, дабы оформить отношения документально, однако так и ничего и не подписывает. Русские (в лице отдельных представителей АН) банально просят больше, чем он им предлагал в своих телеграммах. Пришлось венгру уехать ни с чем.

А тем временем события развиваются по непредсказуемому сценарию. Американцы из Spectrum Holobyte, у которых была версия игры от англичан из Mirrorsoft, на которую те якобы владели правами, проданными им Штайном, всерьёз взялись за программу. События разворачиваются в годы последствий холодной войны, противоборство капитализма и социализма заметно невооружённым глазом. И на этом фоне игра от русских уже сама по себе выглядела непередаваемо привлекательно, независимо от содержания. Именно в соответствии со своими понятиями о русских, американцы перекраивают оформление игры, оставляя механику без изменений. Чёрный фон меняют на лубочные заставки, в качестве эмбиента звучит «Калинка-малинка» и «Э-эх, ухнем!», то тут, то там появляются милитари-элементы, мелькают портреты Юрия Гагарина, а апофеозом становится заставка, в которой перед собором Василия Блаженного приземляется Матиас Руст на своём знаменитом самолётике Cessna! Одним словом - игра менялась и из программки созданной энтузиастом, превращалась в полноценный коммерческий продукт, пускай и западный.

Штайну не оставалось ничего другого, как поскорее получить контракт от русских. Шёл уже 87 год, и на западе готовились к выпуску переработанной версии Тетриса, полагая, что у них есть для этого все основания (купленные у Штайна права). А оснований-то как раз и не было. Владелец Andromeda заметался между молотом и наковальней - у него всё ещё не имелось прав от автора, и в то же время он понятия не имел, как сообщить западным коллегам о необходимости задержки почти готовой игры. В итоге победила трусость, и в 1988 году в Америке и Англии грянул релиз.

Тетрис сразу получил известность и начал продаваться очень неплохими тиражами, постепенно завоёвывая всё большую и большую популярность. Пройдёт менее года - и «Тетрису» присудят несколько важнейших наград Американской Ассоциации Разработчиков Программного Обеспечения. В частности, как лучшему потребительскому софту, лучшей оригинальной разработке и лучшей развлекательной программе.

Алексей тем временем покинул АН и влился в новообразованную компанию Элетроноргтехника (ЭЛОРГ). Там ему объяснили, что он делал неправильно, и почему его продукт вышел на западе без его же участия. Пажитнов соглашается с вескими доводами более опытных коллег. Надо ли говорить, что после этого на Штайна буквально навалились, требуя урегулировать вышедшую из под контроля ситуацию. Нажим со стороны России усугублялся аналогичными действиями со стороны соотечественников Штайна. Особенно после того, как игра огребла столько наград, а вездесущие журналисты CBS раскопали «Русского гения» и взяли у него интервью, проясняющее многие вещи. Нечистому на руку венгру не оставалось ничего другого, как в мае 1988 года подписать треклятый договор на условиях русских. И опять-таки только на РС-вариант игры. А тем временем, события не стояли на месте. Западный Тетрис обрастал славой и наградами, и продвигался далее по миру. Одновременно с этим двигался и технический прогресс - понятие «игра» и компьютер стали размежевываться, и в мире потихоньку наступала эра первых консолей...

Почуявшая куда ветер дует Mirrorsoft, потребовала от Штайна приобрести у русских права на консольный и аркадный варианты Тетриса, а тем временем сама продала права на аркадный вариант (не имея на это ровным счётом никаких оснований) довольно известной в определённых кругах компании Atari, которая тут же перепродала их японской Sega. Во как! Стоит так же упомянуть, что силившийся приобрести вожделенные права у ЭЛОРГ Штайн, так ничего и не добился. А в это время в Японии выходит PC-версия «Тетриса», а также (что намного важнее) его Famicom-вариант на консоли от Nintendo, которая в итоге расходится по стране Восходящего Солнца более чем двухмиллионным тиражом! Для того, чтобы объяснить как такое стало возможным, необходимо копнуть немного глубже и в прошлое.

Пару слов стоит сказать о приставочном «магнате». В конце 70-х Nintendo начинает набирать обороты, и выпускает на рынок революционный по тем временам продукт - карманную игрушку Game&Watch (позднее у нас появился её аналог - «Ну погоди!»), которая сразу становится бестселлером. Чуть позднее (84 г.) Nintendo выпускает ещё более значимый для своего развития продукт GameBoy, и как раз подыскивает игру, которая сможет принести карманной приставке суперпопулярность. На момент распространения «Тетриса» по миру, отношения между Nintendo и Atari были как у кошки с собакой из-за некоторых крупных «подстав» на Американском рынке, и последующих затяжных судебных разбирательств. И снова (в который уже раз!) в игру вмешивается его Величество случай. В июне 88 г. президент американского подразделения Nintendo Минору Аракава случайно увидел на какой-то выставке бытовой техники компьютер с установленным Тетрисом. Он сразу ощутил прелесть развлечения, и воспылал желанием приобрести права на портативную (консольную) версию игрушки. Он стал выяснять, кому они принадлежат в данный момент, и вышел на Atari, где совершенно искренне полагали, что все права принадлежат им, поскольку они «честно» их выкупили у Mirrorsoft. Гусь свинье не товарищ, Аракава понимает, что с Atari разговаривать бесполезно. Однако, счастливый случай стучится в двери ещё раз, и сталкивает Аракаву с Хэнком Роджерсом.

Хэнк Роджерс - одна из ключевых фигур во всей этой истории. Владелец небольшой японской фирмы Bullet Proof Software стал тем человеком, которому Spectrum Holobyte продала права публикации «Тетриса» на рынке Японии. Правда, только на её PC-версию, поскольку все остальные права на тот момент были у Atari. Но предприимчивый янки умел стучаться в двери. Совсем скоро ему удаётся выжать из Atari права и на консольную версию для этого же рынка. И практически в этот момент он знакомится с Аракавой!

Господин Аракава сразу взял быка за рога. Ему нужен был Тетрис. Выпуск Famicom-версии стал знаковым событием в истории компании, однако на момент разворачивающихся событий куда большую ценность для Аракавы представлял портативный вариант игры, как наиболее подходящего кандидата для экспансии на Gаmeboy. Причём заплатить за права на этот вариант он готов был втридорога. Роджерс по природе своей был человеком неглупым, и подозревал, что с правами-то как раз дело обстоит нечисто, поэтому он решает отследить всю цепочку правообладателей, начиная с первоисточника. В феврале 89 г. он отправляется в Москву. Штайн, у которого не задолго до этого Роджерс выпрашивал права на портативный вариант, почувствовал, что пахнет жареным, и в срочном порядке направился туда же. Третьим лицом, отправившимся в Москву становится Кевин Максвелл, сын медиа-магната, которому принадлежали Mirrorsoft и (априори) Spectrum Holobyte.

Каково же было удивление Роджерса (который приехал к Алексею и в качестве презентации показал ему Японский вариант Тетриса для Famicom), когда он узнал, что никто никому никаких прав не продавал, а про Nintendo здесь вообще слыхом не слыхивали! Полный аналог Famicom, известный как Dendy, появится в России намного позже, пока же о чудо-консолях в СССР никто ничего не знает. Впрочем, у Пажитнова поводов для удивления было куда больше: оказывается его игра уже «гуляет» по всему свету и во всех вариантах, а он так ещё ничего с этого и не получил. Пользуясь моментом, Роджерс подписывает контракт о передаче ему прав на портативную версию игры, и обещает вернуться с представителем могучей к тому времени Nintendo, ради подлинных прав для консольного варианта.

Прибывшему чуть позднее Штайну в двух словах объяснили кто он, и показали подписанный с ним в самом начале контракт, где ясно было сказано про передачу прав только на РС-вариант. Венгр не стал доказывать, что он не верблюд и согласился по всем пунктам обвинения. Поскольку доверие к товарищу было уже подорвано, то всё, чего он смог добиться от визита - передачи ему прав на аркадный вариант игры (для игровых автоматов), причём за «очень дорого». С тем он и уехал.

Чуть позже в ЭЛОРГ появляется сын Максвелла. Товарищи суют ему под нос картридж с игрой, где понятным английским языком читается название игры и имя компании-распространителя: «Mirrorsoft». После чего задают вопрос: «На каких основаниях этот картридж существует?». Паренёк, не владевший всей информацией, не может дать внятных объяснений, и уезжает в ошарашенном состоянии домой. Едва он прибывает в Англию и уведомляет о результатах встречи отца, начинается прессинг в адрес ЭЛОРГ. Осознавший, что позиции Mirrorsoft и Atari под угрозой, Роберт Максвелл задействует всю мощь созданной им информационной сети, поднимает шумиху, и с помощью этого доводит проблему до уровня правительства. По неподтверждённой официальными лицами информации, правительство Великобритании и СССР решают помочь Максвеллу, с целью чего возрастает натиск на ЭЛОРГ со стороны отечества. Однако, русские так и не «прогнулись» - и вот почему.

Потому что Роджерс не обманул. Пока Максвелл раскручивал свою интрижку, Роджерс - инкогнито, в обстановке строжайшей секретности (дабы не пронюхали конкуренты из Atari) привозит в Москву Аракаву и его юрисконсульта Говарда Линкольна (ставшего в будущем президентом Nintendo). В первопрестольной они подписывают важнейший контракт. 21 марта 1989 г. крупнейшему игроку на рынке электронных развлечений отошли все права на Тетрис (для видеорынка) за сумму, которую независимые аналитики оценивают в пределах 3-5 млн долларов. Попутно, после долгих судебных разбирательств, был нанесён серьёзный урон конкуренту Nintendo - Atari. Дальновидные бизнесмены убили одним метким выстрелом двух зайцев.

Сам Пажитнов получил с этих денег очень немного. Правда, ходили слухи, что правительство СССР подарило Алексею «За заслуги перед Родиной» такие роскошные вещи как 286-й компьютер и целую московскую квартиру.

Тетрис стал суперхитом всех времён и народов. Благодаря ему, за первые несколько лет существования, GameBoy разошелся более чем 30-миллионным тиражом, а самих картриджей с программой было продано около 15 млн. Впоследствии GameBoy стала самой успешно продаваемой консолью за всю историю электронных развлечений (более 100 млн. официально проданных консолей). Тетрис же непосредственно, принёс компании Nintendo по разным оценкам от 2 до 3 миллиардов долларов чистой прибыли, учитывая все порты, версии и лицензионные отчисления. За 20 лет существования все виды «Тетриса» (включая официальную статистику, электронные устройства и нелегальные продажи) разошлись по миру фантастическим тиражом, который оценивают в четверть миллиарда экземпляров. Стоит ли говорить, что подобной популярности не удавалось достичь ни одной игре. Да и вряд ли когда-нибудь удастся.

Дальнейшая судьба Пажитнова сложилась непросто, но интересно. Осознав, что на жизнь можно зарабатывать излюбленным делом, в 1989 году он совместно со своим другом Владимиром Похилко и при участии того самого Хэнка Роджерса основывает студию AnimaTek, основным направлением деятельности которой становится разработка различных компьютерных головоломок и проблемы искусственного интеллекта в играх. На первых порах клиентами AnimaTek выступают такие известные российские фирмы, как Параграф, Дока, Диалог и ряд более мелких компаний. В общей сложности, к 1991 году Алексей с товарищами разработал или принял участие в разработке более трёх сотен игр! Наработки AnimaTek впоследствии использовались в таких известных проектах, как Age of Empires от Microsoft и Final Fantasy Tactics (Square).

Однако в начале 90-х рынок игр на пост-советском пространстве был никаким, и для того, чтобы получать адекватную плату за свой труд, Пажитнов перебирается в Америку. Штаб-квартира AnimaTek перебазируется в Сан-Франциско, и продолжает заниматься игровым направлением. Владимир Похилко не покинул друга, и также переехал в Соединённые Штаты, где ещё долгое время оставался управляющим AnimaTek. Кстати, чуть позже в Америку переезжает и ещё одно действующее лицо нашей истории - Вадим Герасимов, усилиями которого Тетрис в своё время попал на IBM PC. Впрочем, от своих прав на Тетрис Герасимов отказался ещё в 1987 году, поэтому дальнейшая его судьба никак с игрой связана не была.

Алексей оставил руководство компанией на Похилко, а сам в том же 91 году (и снова при участии Роджерса) создаёт кампанию с говорящим именем «Тетрис», где занимается разработками разного рода головоломок, в том числе на основе классического Тетриса. И именно на этом этапе Пажитнов начинает наконец-то получать деньги с разработанных им игр. Судьба AnimaTek в Америке складывается непросто. Русские издают одну за другой игры разных жанров, однако ни одной из них так и не удаётся продаться большими тиражами. В частности общество полностью игнорирует новаторский проект El-Fish (нечто вроде компьютерного аквариума), которая, по сути, была первой компьютерной анимацией компании. А потом начинается расцвет рынка электронных развлечений, и компания Пажитнова, не имеющая возможности конкурировать с профессиональными игровыми разработчиками, переводит стрелки на рельсы программ трёхмерного моделирования графики. В частности из-под пера компании вышли такие продукты, как World Builder (программа для моделирования трёхмерных ландшафтов) и Caviar (работа с воксельными технологиями).

Сам Пажитнов в 1996 году переходит «под крыло» всемогущей Microsoft, дабы заниматься тем, что ему нравится больше всего - головоломками. Отныне он становится игровым дизайнером-консультантом, а под его началом служит небольшой сплочённый коллектив из дюжины человек. Первым результатом их совместной деятельности становится выпуск в 1997 году The Puzzle Collection, представляющей из себя набор из головоломок самого разного характера. Если одни из них задействовали исключительно серые мозговые клетки, то другие были рассчитаны на определённую скорость реакции, умение быстро принимать правильные решения, и так далее. А в сентябре 1999 года выходит и Pandora Box - сборник, состоящий из семи головоломок, обладающий интригующим названием, подобием некоего стори-лайна и красивым визуальным исполнением. Разные временные эпохи (от Древнего Египта до современных небоскребов), качественные фотографии, и репродукции известнейших художников и скульпторов - всё это служило фоном для отличных, умных игр. Причём, и в первом, и во втором случае Microsoft не постеснялись прибегнуть к дополнительному пиару - в играх присутствовала строчка «от создателя Тетриса»…

После выпуска «Ящика Пандоры» взор Алексея обратился к онлайну. На официальном сервере Microsoft даже существовал особый отдел MSN Game Zone - Mind Aerobics. По сути, это такой же набор статических головоломок, однако с некоторыми нововведениями, касающимся в основном режимов игры. В частности, люди получили возможность соревноваться друг с другом по Интернету, продвигаться на верхушку пьедестала почёта, или просто следить за «поединками» знакомых. Игра долгое время была весьма популярна.

Такова непростая история Алексея Пажитнова. Сейчас он обеспеченный и уважаемый человек, сотрудник известной Microsoft, живёт и работает в Соединённых Штатах. Русский гений выпускал ещё несколько раз свои игры - в основном головоломки, весьма интересные и добротные продукты. Его Hexic HD включен к сервис Xbox Live Arcade для Xbox 360, а пользователи ПК совсем недавно могли познакомиться с его последней работой - Dwice (описание можно найти в нашем обзоре «Казуальных игр полумесяца»). Но добиться повторно такого успеха, как с Тетрисом, им уже было не суждено. Впрочем, больше ни одна игре в мире не смогла даже приблизиться к Тетрису по популярности.

Этот проект начался как ответ на вопрос со Stackexchange:

Это теоретическая задача - она не имеет ни простого, ни тривиального ответа.

В игре «Жизнь» Конвея существуют такие конструкции, как метапиксели , которые позволяют игре «Жизнь» симулировать любую систему правил, похожую на «Жизнь». Кроме того, известно, что игра «Жизнь» Тьюринг-полная.

Ваша задача заключается в создании клеточного автомата, использующего правила игры «Жизнь» Конвея, который позволяет играть в «Тетрис».

Программа должна получать ввод ручным изменением состояния автомата в определённом поколении, представляющим собой прерывание (т.е. перемещение фигуры влево или вправо, поворот, бросание вниз или случайная генерация новой фигуры для размещения на поле). Определённое количество поколений считается временем ожидания. Результат игры показывается где-нибудь в автомате. Полученный результат должен визуально напоминать поле для настоящего «Тетриса».

Ваша программа будет оцениваться по следующим критериям, в следующем порядке (нижние критерии являются допольнительными по отношению к более высоким):

• Размер граничного прямоугольника - выигрывает прямоугольное поле с наименьшей площадью, полностью содержащее решение.
• Наименьшее количество изменений для ввода - выигрывает решение с наименьшим количеством ячеек (в худшем для вашего автомата случая), необходимых для ручной настройки в качестве прерывания.
• Самое быстрое выполнение - выигрывает решение с наименьшим количеством поколений для продвижения вперёд на один такт симуляции.
• Начальное количество живых клеток - выигрывает наименьшее количество.
• Первое опубликованное - выигрывает самый первый пост с решением.

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

Во-первых, в качестве основы для компьютера мы использовали OTCA-метапиксели . Эти метапиксели могут эмулировать любые правила игры, похожей на «Жизнь». Важными источниками вдохновения для этого проекта стали Wireworld и компьютер Wireworld , мы стремились создать похожую конструкцию на основе метапикселей. Хотя эмулировать Wireworld с помощью OTCA-метапикселей невозможно, можно установить для разных метапикселей разные правила и создать конструкции из метапикселей, работающие подобно проводам Wireworld.

Следующим шагом стало создание множества фундаментальных логических вентилей, которые можно использовать в качестве основы компьютера. На этом этапе мы уже имеем дело с концепциями, похожими на концепции дизайна процессоров реального мира. Вот пример вентиля OR, каждая ячейка этого изображения на самом деле является целым OTCA-метапикселем. Вы видите, как «электроны» (каждый из которых представляет собой единичный бит данных) входят и выходят из вентиля. Также видны все типы метапикселей, использованные нами для создания компьютера: B/S - чёрный фон, B1/S - синий, B2/S - зелёный, B12/S1 - красный.

Из этого мы разработали архитектуру процессора. Мы потратили много времени на разработку архитектуры, которая была бы одновременно и понятной, и простой в реализации. Компьютер Wireworld использует рудиментарную transport-triggered architecture, в нашем же проекте используется гораздо более гибкая архитектура RISC, имеющая множественные опкоды и режимы адресации. Мы создали язык ассемблера QFTASM (Quest for Tetris Assembly), который управлял изготовлением процессора.

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

Вот иллюстрация архитектуры нашего процессора:

С этого момента нам остаётся только реализовать «Тетрис» в компьютере. Чтобы упростить задачу, мы разработали несколько способов компилирования высокоуровневого языка в QFTASM. У нас есть базовый язык Cogol, второй, более совершенный язык находится в процессе разработки, и, наконец, мы создаём бэкенд GCC. Сейчас программа «Тетриса» пишется на Cogol и компилируется из него.

После того, как конечный код QFTASM «Тетриса» был сгенерирован, следующими шагами были сборка из этого кода в соответствующее ПЗУ, а затем из метапикселей в лежащую в основе игру «Жизнь», на чём наша работа будет закончена.

Запуск «Тетриса»

Те, кто хочет поиграть в «Тетрис» без возни с компилятором, могут запустить исходный код «Тетриса» в интерпретаторе QFTASM . Для просмотра всей игры укажите отображаемые адреса ОЗУ 3-32. Вот постоянная ссылка для удобства: Tetris in QFTASM .

Характеристики игры:

• Все 7 тетромино
• Движение, вращение, плавное опускание фигур
• Очистка линий и подсчёт очков
• Показ следующей фигуры
• Ввод игрока добавляет случайности

Дисплей
Наш компьютер представляет поле «Тетриса» как сетку в памяти. Адреса 10-31 отображают поле, адреса 5-8 - следующую фигуру, адрес 3 содержит счёт.

Ввод
Ввод в игре осуществляется ручным редактированием содержимого адреса 1 в ОЗУ. При использовании интерпретатора QFTASM это означает прямую запись по адресу 1. См. «Direct write to RAM» на странице интепретатора. Каждый ход требует изменения только одного бита ОЗУ, и этот регистр ввода автоматически сбрасывается после считывания события ввода.

Value motion
1 вращение против часовой стрелки
2 влево
4 вниз (плавное опускание)
8 вправо
16 вращение по часовой стрелке

Система подсчёта очков
Игрок получает бонус за удаление нескольких линий за один ход.

1 ряд = 1 очко
2 ряда = 2 очка
3 ряда = 4 очка
4 ряда = 8 очков

Часть 2: OTCA-метапиксель и VarLife

OTCA-метапиксель

VarLife

Я создал онлайн-симулятор правил Life-подобных игр, в котором можно задать поведение любой клетки в соответствии с любыми правилами, схожими с правилами «Жизни». Я назвал симулятор «Variations of Life». Для краткости потом это название сменилось на «VarLife». Вот его скриншот (ссылка на симулятор: http://play.starmaninnovations.com/varlife/BeeHkfCpNR):

Примечательные особенности:

• Переключает клетки между состояниями «живая»/«мёртвая» и раскрашивает поле по различным правилам.
• Способность запускать и останавливать симуляцию, выполнять по одному шагу за раз. Также возможно выполнять заданное количество шагов с максимальной скоростью или более медленно, со скоростью, устанавливаемой в тактах/с и мс/такт.
• Имеет возможность удалять все живые клетки или полностью сбрасывать поле в пустое состояние.
• Может менять размер поля и клеток, а также включать горизонтальную и/или вертикальную тороидальную свёртку.
• Постоянные ссылки (которые кодируют всю информацию url) и короткие url (потому что иногда бывает слишком много информации, но они всё равно полезны).
• Наборы правил с заданием B/S, цветов и опциональной случайности.
• И последнее - рендеринг gif!

Функция render-to-gif - моя любимая, потому что на её реализацию ушла куча времени. Было очень здорово, когда я наконец доделал её в семь часов утра. С её помощью можно запросто делиться конструкциями VarLife с другими людьми.

Основная схема VarLife

В целом компьютеру VarLife требуется всего четыре типа клеток! Всего восемь состояний, с учётом состояний «мёртвый»/«живой»:

• B/S (чёрный/белый), которое служит в качестве буфера мжеду всеми компонентами, потому что клетки B/S никогда не могут быть живыми.
• B1/S (синие/голубые) - основной тип клеток, используемый для распространения сигналов.
• B2/S (зелёный/жёлтый) - в основном используется для управления сигналами, защищая их от обратного распространения.
• B12/S1 (красный/оранжевый) - используется в некоторых особых ситуациях, например, при пересечении сигналов и хранении бита данных.

Воспользуйтесь этим коротким url, чтобы открыть VarLife с уже закодированными правилами: http://play.starmaninnovations.com/varlife/BeeHkfCpNR .

Проводники

Существует несколько различных конструкций проводников с отличающимися характеристиками.

Это простейший и основной проводник в VarLife, полоса синего, ограниченная полосами зелёного.

Это однонаправленный проводник. То есть он будет уничтожать все сигналы, пытающиеся пройти в противоположном направлении. Кроме того, он на одну клетку у́же основного проводника.

Существуют также диагональные проводники, но они почти не используются.

Шлюзы

На самом деле есть множество способов создания каждого отдельного шлюза, поэтому я покажу только по одному примеру каждого типа. На первом gif показаны, соответственно, шлюзы AND, XOR и OR. Основная идея заключается в том, что зелёная клетка действует как AND, синяя - как XOR, а красная - как OR, а все остальные клетки вокруг них просто обеспечивают правильную передачу.

Шлюз AND-NOT (сокращённо ANT) оказался жизненно необходимым компонентом. Этот шлюз передаёт сигнал от A тогда и только тогда, когда нет сигнала от B. То есть «A AND NOT B».

Хотя это не совсем шлюз , но тайл пересечения проводников очень важен и полезен.

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

Кроме того, многие компоненты намеренно создавались таким образом, чтобы умещаться в ограничивающий прямоугольник 11 на 11 (тайл ), в котором от момента входа в тайл до выхода из тайла сигналам требуется 11 тактов. Это делает компоненты более модульными и их легче соединять вместе без необходимости регулировки проводников для обеспечения пространства или таймингов.

О других шлюзах, исследованных/созданных в процессе изучения компонентов схем, можно прочитать в посте PhiNotPi: Building Blocks: Logic Gates .

Компоненты задержки

В процессе разработки оборудования компьютера KZhang придумал множество компонентов задержки, показанных ниже.

Задержка на 4 такта:

Задержка на 5 тактов:

Задержка на 8 тактов (три отдельных точки входа):

Задержка на 11 тактов:

Задержка на 12 тактов:

Задержка на 14 тактов:

Задержка на 15 тактов (проверятся сравнением с этим):

Итак, вот каковы основные компоненты схем VarLife! Описания основных схем компьютера см. в следующей части, написанной KZhang!

Часть 3: оборудование

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

Демультиплексор

Демультиплексор, или demux - критически важный компонент ПЗУ, ОЗУ и АЛУ. В зависимости от заданных данных селектора он направляет входной сигнал на один из нескольких выходных сигналов. Он состоит из трёх основных частей: последовательно-параллельный преобразователь, устройство контроля сигнала и разделитель тактовых сигналов.

Мы начинаем с преобразования последовательных данных селектора в «параллельные». Это выполняется стратегическим разделением и задержкой данных, чтобы самый левый бит данных пересекал тактовый сигна в самом левом квадрате 11x11, следующий бит данных пересекал тактовый сигнал в следующем квадрате 11x11, и так далее.

Хотя каждый бит данных будет выводиться в каждый квадрат 11x11, каждый бит данных будет пересекаться с тактовым сигналом только один раз.

Далее мы проверяем, соответствуют ли параллельные данные заданному адресу.
Мы осуществляем это с помощью шлюзов AND и ANT, применяемыми для тактовых и параллельных данных. Однако нам нужно убедиться, что параллельные данные тоже выводятся, чтобы их можно было снова сравнить. Вот шлюзы, которые в результате создал я:

Наконец, мы просто разделяем тактовый сигнал, соединяем несколько устройств проверки сигнала (по одному для каждого адреса/вывода), в результате получая мультиплексор!

ПЗУ

ПЗУ должно получать в качестве входных данных адрес, а в качестве вывода отправлять инструкцию по этому адресу. Мы начинаем с того, что используем мультиплексор для направления тактового сигнала на одну из инструкций. Затем нам нужно сгенерировать сигнал с помощью касаний нескольких проводников и шлюзов OR. Касания проводников позволяют тактовому сигналу пройти по всем 58 битам инструкции, а также обеспечивают перемещение сгенерированного сигнала (пока параллельного) по ПЗУ на выход.

Затем нам нужно просто преобразовать параллельный сигнал в последовательный, и на этом ПЗУ будет готово.

В настоящее время ПЗУ генерируется выполнением скрипта на Golly, передающего ассемблерный код из буфера обмена в ПЗУ.

SRL, SL, SRA

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

Для SL и SRL нам нужно

1. Убедиться, что 12 самых значимых битов не включены (иначе вывод будет равен 0), и
2. Выполнить задержку данных на нужное время на основании 4 менее значимых битов.

Это можно реализовать с помощью нескольких шлюзов AND/ANT и мультиплексора.

SRA немного отличается, потому что при сдвиге нам нужно копировать знаковый бит. Мы выполняем это, применив AND к тактовому сигналу со знаковым битом, а затем скопировав вывод несколько раз с помощью разделителей проводников и шлюзов OR.

Триггер Set-Reset (SR)

Многие функции процессора зависят от способности хранить данные. Мы можем реализовать её с помощью двух красных клеток B12/S1. Две клетки могут поддерживать друг друга во включенном состоянии или же вместе быть выключенными. С помощью дополнительных схем включения, сброса и чтения мы можем создать простой SR-триггер.

Синхронизатор

Преобразовав последовательные данные в параллельные, а затем включив несколько SR-триггеров, мы можем хранить целое слово данных. Затем, чтобы снова извлечь данные, мы можем просто считать и сбросить все триггеры, и соответствующим образом выполнить задержку данных. Это позволит нам хранить одно (или несколько) слов данных, пока мы ждём другое. Благодаря этому мы сможем синхронизировать два слова данных, полученных в разное время.

Счётчик считывания

Это устройство отслеживает, сколько раз оно должно выполнять адресацию из ОЗУ. Оно решает эту задачу с помощью устройства, похожего на SR-триггер: T-триггера. Каждый раз, когда T-триггер получает входные данные, он меняет состояние: если он был включен, то отключается, и наоборот. Когда T-триггер изменяет своё состояние, он отправляет выходной импульс, который можно передать в другой T-триггер, создав двухбитный счётчик.

Для создания счётчика считывания нам нужно перевести счётчик в подходящий режим адресации с помощью двух шлюзов ANT, и использовать выходной сигнал счётчика для определения того, куда направлять тактовый сигнал: в АЛУ или в ОЗУ.

Очередь считывания

Очередь считывания должна отслеживать, какой из счётчиков считывания отправил входные данные в ОЗУ, чтобы он мог отправить вывод ОЗУ в нужное место. Для этого мы используем несколько SR-триггеров: по одному триггеру на каждый вход. Когда из счётчика считывания передаётся сигнал в ОЗУ, тактовый сигнал разделяется и включает SR-триггер счётчика. Затем вывод ОЗУ проходит вмести с SR-триггером через шлюз AND, а тактовый сигнал из ОЗУ сбрасывает SR-триггер.

АЛУ

АЛУ похожа в работе на очередь считывания в том, что она оно тоже использует SR-триггер для отслеживания того, куда отправлять сигнал. Сначала с помощью мультиплексора включается SR-триггер логической цепи, соответствующей опкоду инструкции. Затем значения первого и второго аргумента вместе с SR-триггером проходят через шлюз AND, а потом передаются в логические цепи. При прохождении тактовый сигнал сбрасывает триггер, так что АЛУ можно использовать снова.

ОЗУ

ОЗУ стало самой сложной частью этого проекта. Оно требовало очень специфического управления каждым SR-триггером, хранящим данные. Для считывания адрес передаётся в мультиплексор и передаётся в сегменты ОЗУ. Сегменты ОЗУ параллельно выводят хранящиеся данные, которые преобразуются в последовательный вид и выводятся. Для записи адрес передаётся в другой мультиплексор, записываемые данные преобразуются из последовательной в параллельную форму, а сегменты ОЗУ распространяют сигнал по ОЗУ.

Метапиксель 22x22 каждого сегмента ОЗУ имеет такую структуру:

Соединив всё ОЗУ, мы получим что-то подобное:

Соединяем всё вместе

С помощью всех этих компонентов и общей архитектуре компьютера, описанной в Части 1, мы можем построить работающий компьютер!

Часть 4: QFTASM и Cogol

Обзор архитектуры

Если вкратце, то наш компьютер имеет 16-битную асинхронную гарвардскую архитектуру RISC. При создании процессора вручную архитектура RISC (компьютер с сокращённым набором команд) является практически обязательным требованием. В нашем случае это означает, что количество опкодов мало, и, что гораздо более важно - все инструкции обрабатываются очень похожим образом.

Для справки - компьютер Wireworld использует transport-triggered architecture , в которой единственной инструкцией является MOV , а вычисления выполняются записью/считыванием специальных регистров. Хотя эта парадигма позволяет создать очень простую в реализации архитектуру, результат оказывается на грани применимости: все арифметические/логические/условные операции требуют трёх инструкций. Было очевидно, что мы хотим создать более понятную архитектуру.

Чтобы оставить наш процессор простым, в то же время повысив удобство его использования, мы приняли несколько важных решений относительно его конструкции:

• Никаких регистров. Каждый адрес в ОЗУ считается равным и может использоваться как аргумент в любой операции. В каком-то смысле это значит, что всё ОЗУ можно считать регистрами. Это означает отсутствие специальных инструкций загрузки/хранения.
• То же самое касается распределения памяти. Всё, что может записываться или считываться, имеет общую унифицированную схему адресации. Это значит, что счётчик команд (program counter, PC) является адресом 0, а единственная разница между обычными и управляющими инструкциями заключается в том, что управляющие используют адрес 0.
• Данные последовательны при передаче и параллельны при хранении. Из-за «электронной» природы нашего компьютера, сложение и вычитание реализовать значительно проще, когда данные передаются последовательно в порядке little-endian (первым идёт наименее значимый бит). Более того, последовательные данные позволяют избавиться от громоздких шин данных, которые очень широки и неудобны для правильной работы со временем (чтобы данные находились вместе, все «полосы» шины должны иметь одинаковую временную задержку).
• Гарвардская архитектура, то есть существует разделение между памятью программ (ПЗУ) и памятью данных (ОЗУ). Хоть это и снижает гибкость процессора, но помогает оптимизировать размер: длина программы намного больше, чем нужное нам количество ОЗУ, поэтому мы можем разделить программу в ПЗУ и затем сосредоточиться на сжатии ПЗУ, что гораздо проще выполнить, когда она «только для чтения».
• 16-битная разрядность данных. Это наименьшая степень двойки, которая шире стандартного поля для «Тетриса» (10 блоков). Это даёт нам диапазон данных от -32768 до +32767 и максимальную длину программы в 65536 инструкций. (2^8=256 инструкций достаточно для большинства простых вещей, которые можно реализовать в выдуманном процессоре, но никак не для «Тетриса».)
• Асинхронный дизайн. Вместо центрального тактового генератора (или, что аналогично, нескольких генераторов), задающего время компьютера, все данные сопровождаются «тактовым сигналом», передающимся параллельно с данными при их перемещении в компьютере. Некоторые пути могут быть короче других, и это может вызывать сложности в дизайне с центральным тактовым генератором, но асинхронная конструкция может запросто справляться с операциями с переменным временем.
• Все инструкции имеют одинаковый размер. Мы посчитали, что архитектура, в которой каждая инструкция имеет 1 опкод с тремя операндами (значание, значение, целевой адрес) будет наиболее гибким вариантом. Они включают в себя операции с двоичными данными, а также условные переходы.
• Прострая система режимов адресации. Наличие множества режимов адресации очень полезно для поддержки таких вещей, как массивы или рекурсия. Нам удалось с помощью относительно простой системы реализовать несколько важных режимов адресации.

Иллюстрация нашей архитектуры приведена в Части 1.

Работа и операции АЛУ

После этого нужно было определиться, какие функции должен иметь наш процессор. Особое внимание стоило уделить простоте реализации и универсальности каждой команды.

Условные перемещения

Условные перемещения очень важны, они служат для маломасштабного и крупномасштабного управления. «Маломасштабное» - это способность управлять выполнением конкретным перемещением данных, а «крупномасштабное» относится к их использованию в качестве операции условного перехода для передачи управления любому произвольному фрагменту кода. У процессора нет специальных операций перехода, потому что из-за распределения памяти условное перемещение может и копировать данные в обычную ОЗУ, и копировать адрес назначения в счётчик команд (PC). Также мы решили отказаться и от безусловных перемещений, и от безусловных переходов по схожей причине: обе эти операции могут быть реализованы как условные перемещения, в котором условие всегда имеет значение TRUE.

Мы решили использовать два типа условных перемещений: «переместиться, если не ноль» (MNZ) и «переместиться, если меньше ноля» (MLZ). Функционально MNZ сводится к проверке, является ли любой бит данных равным 1, а MLZ - к проверке, имеет ли знаковый бит значение 1. Соответственно, они полезны для проверок равенства и сравнений. Мы выбрали эти два перемещения потому, что «переместиться, если ноль» (MEZ) должен был создавать из пустого сигнала сигнал TRUE, а «переместиться, если больше ноля» (MGZ) - это более сложная проверка, требующая, чтобы знаковый бит был равен 0 и при этом хотя бы один другой бит был равен 1.

Арифметика

Следующими по важности инструкциями при принятии решения о дизайне процессора стали основные арифметические операции. Как упомянуто выше, мы используем последовательные данные little-endian, а выбор endian определялся простотой операций сложения/вычитания. При получении первым наименее значимого бита арифметические устройства могут легче отслеживать бит переноса.

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

Сложение и вычитание - удел нативной поддержки арифметики нашего процессора (кроме битовых сдвигов, которые мы рассмотрим позже). Другие операции, например, умножение, слишком сложны и не могут выполняться в нашей архитектуре, и должны реализовываться программно.

Битовые операции

Как можно догадаться, у нашего процессора есть инструкции AND , OR и XOR . Вместо инструкции NOT мы решили использовать инструкцию «and-not» (ANT). Сложность с инструкцией NOT снова в том, что она должна создавать сигнал при его отсутствии, что сложно для клеточных автоматов. Инструкция ANT возвращает 1 только если первый битовый аргумент 1, а первый битовый аргумент - 0. То есть NOT x аналогично ANT -1 x (а также XOR -1 x). Более того, ANT универсальней и имеет основное преимущество при наложении маски: в случае программы для «Тетриса» мы будем использовать её для удаления тетромино.

Битовый сдвиг

Операции битового сдвига - это самые сложные операции, обрабатываемые АЛУ. Они получают два входных значения: сдвигаемое значение и величину сдвига. Несмотря на их сложность (из-за переменной величины сдвига), эти операции критичны для многих важных задач, в том числе для «графических» операций, используемых в «Тетрисе». Битовые сдвиги также служат основой эффективных алгоритмов умножения/деления.

У нашего процессора есть три операции битового сдвига - «сдвиг влево» (SL), «логический сдвиг влево» (SRL) и «арифметический сдвиг вправо» (SRA). Два первых битовых сдвига (SL и SRL) заполняют новые биты нолями (это значит, что сдвинутое вправо отрицательное число больше не будет отрицательным). Если второй аргумент сдвига находится вне интервала от 0 до 15, то, как можно догадаться, результатом будут одни ноли. Для последнего битового сдвига, SRA , битовый сдвиг сохраняет знак входных данных, а потому действует как истинное деление на два.

Конвейер инструкций

Настало время поговорить о некоторых базовых подробностях архитектуры. Каждый цикл ЦП состоит из следующих пяти этапов:

1. Получение текущей инструкции из ПЗУ

Текущее значение PC используется для получения соответствующей инструкции из ПЗУ. Каждая инструкция имеет один опкод и три операнда. Каждый операнд состоит из одного слова данных и одного режима адресации. Эти части при считывании из ПЗУ отделяются друг от друга.

Опкод - это 4 бита, чтобы была возможность поддерживать 16 уникальных опкодов, 11 из которых назначены:

0000 MNZ Move if Not Zero
0001 MLZ Move if Less than Zero
0010 ADD ADDition
0011 SUB SUBtraction
0100 AND bitwise AND
0101 OR bitwise OR
0110 XOR bitwise eXclusive OR
0111 ANT bitwise And-NoT
1000 SL Shift Left
1001 SRL Shift Right Logical
1010 SRA Shift Right Arithmetic
1011 unassigned
1100 unassigned
1101 unassigned
1110 unassigned
1111 unassigned

2. Запись результата (при необходимости) предыдущей инструкции в ОЗУ

Выполнение записи зависит от состояния предыдущей инструкции (например, от значения первого аргумента условного перемещения). Адрес записи определяется третьим операндом предыдущей инструкции.

Важно заметить, что запись выполняется после получения инструкции. Это приводит к созданию слота задержки перехода , в котором инструкция выполняется сразу после инструкции ветвления (любой операции, выполняющей запись в PC) вместо первой инструкции целевого адреса ветвления.

В некоторых случаях (например, при безусловных переходах), от слота задержки перехода можно избавиться оптимизацией. В других случаях это невозможно и инструкцию после ветвления нужно оставить пустой. Более того, такой тип слота задержки должен использовать целевой адрес ветвления, который на 1 адрес меньше самой целевой инструкции, чтобы учесть выполняемый инкремент PC.

Если вкратце, то поскольку вывод предыдущей инструкции записывается в ОЗУ после получения следующей инструкции, после условных переходов должна идти пустая инструкция. В противном случае PC не обновится для перехода правильно.

3. Считывание данных для аргументов текущей инструкции из ОЗУ

Как упомянуто выше, каждый из трёх операндов состоит и из слова данных, и из режима адресации. Слово данных равно 16 битам, той же разрядности, что и ОЗУ. Режим адресации занимает 2 бита.

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

Мы стремились унифицировать концепции использования жёстко заданных чисел в качестве операндов и применения в качестве операндов адресов данных. Это привело к созданию режимов адресации на основе счётчиков: режим адресации операнда - это просто число, определяющее, сколько раз данные должны передаваться в цикле считывания ОЗУ. В них входят непосредственная, прямая, непрямая и двойная непрямая адресация.

00 непосредственная: жёстко заданное значение. (нет считывания из ОЗУ)
01 прямая: считывает данные из этого адреса ОЗУ. (одно считывание из ОЗУ)
10 непрямая: считывает данные из адреса, заданного в этом адресе. (два считывания из ОЗУ)
11 двойная непрямая: считывает данные из адреса, заданного в адресе, заданного этим адресом. (три считывания из ОЗУ)

После выполнения расшифровки ссылки три операнда инструкции получают различные роли. Первый операнд - обычно первый аргумент для двоичного оператора, но также он служит условием, когда текущая инструкция является условным перемещением. Второй операнд служит вторым аргументом двоичного оператора. Третий оператор служит адресом назначения для результата инструкции.

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

4. Вычисление результат

Опкод и два его первых операнда отправляются в АЛУ для выполнения двоичной операции. Для арифметических, битовых и сдвиговых операций это означает выполнение соответствующей операции. Для условных перемещений это означает простой возврат второго операнда.

Опкод и первый операнд используются для вычисления условия, определяющего, нужно ли записывать результат в память. В случае условных перемещений это означает, что либо нужно определить, равен ли какой-нибудь из битов операнда 1 (для MNZ), либо нужно определить, равен ли знаковый бит 1 (для MLZ). Если опкод не является условным перемещением, то запись выполняется всегда (условие всегда истинно).

5. Инкремент счётчика команд

Затем, наконец, считывается, увеличивается и записывается значение счётчика команд.

Из-за того, что инкремент PC расположен между считыванием инструкции и записью инструкции, инструкция, увеличивающая значение PC на 1 является пустой (no-op). Инструкция, копирующая PC в самого себя, приводит к выполнению следующей инструкции два раза подряд. Но стоит учитывать, что если не уделять внимание конвейеру инструкций, то несколько инструкций PC подряд могут привести к комплексным эффектам, в том числе бесконечному зацикливанию.

Одиссея по созданию ассемблера для «Тетриса»

Мы создали для нашего процессора новый язык ассемблера QFTASM. Этот ассемблерный язык один в один соответствует машинному коду в ПЗУ компьютера.

Любая программа на QFTASM записывается построчной серией инструкций. Каждая строка форматируется следующим образом:

[номер строки] [опкод] [арг1] [арг2] [арг3]; [необязательный комментарий]

Список опкодов

Как сказано выше, компьютером поддерживаются одиннадцать опкодов, каждый из которых имеет три операнда:

MNZ [проверка] [значение] [адрес назначения] – перемещение, если не ноль; задаёт [адрес назначения] для [значения], если [проверка] не равна нолю.
MLZ [проверка] [значение] [адрес назначения] – перемещение, если меньше ноля; задаёт [адрес назначения] [значению], если [проверка] не меньше ноля.
ADD [значение1] [значение2] [адрес назначения] – сложение; сохраняет [значение1] + [значение2] в [адресе назначения].
SUB [значение1] [значение2] [адрес назначения] – вычитание; сохраняет [значение1] - [значение2] в [адресе назначения].
AND [значение1] [значение2] [адрес назначения] – битовое И; сохраняет [значение1] & [значение] в [адресе назначения].
OR [значение1] [значение2] [адрес назначения] – битовое ИЛИ; сохраняет [значение1] | [значение2] в [адресе назначения].
XOR [значение1] [значение2] [адрес назначения] – битовое XOR; сохраняет [значение1] ^ [значение2] в [адресе назначения].
ANT [значение1] [значение2] [адрес назначения] – битовое И-НЕ; сохраняет [значение1] & (![значение2]) в [адресе назначения].
SL [значение1] [значение2] [адрес назначения] – сдвиг влево; сохраняет [значение1] << [значение2] в [адресе назначения].
SRL [значение1] [значение2] [адрес назначения] – логический сдвиг вправо; сохраняет [значение1] >>> [значение2] в [адресе назначения]. Не сохраняет знак.
SRA [значение1] [значение2] [адрес назначения] – арифметический сдвиг вправо; сохраняет [значение1] >> [значение2] в [адресе назначения] с сохранением знака.

Режимы адресации

Каждый из операндов содержит и значение данных, и режим адресации. Значение данных описывается десятичным числом в интервале от -32768 до 65536. Режим адресации описывается однобуквенным префиксом к значению данных.

Режим название префикс
0 непосредственный (нет)
1 прямой A
2 непрямой B
3 двойной непрямой C

Пример кода

Числа Фибоначчи в пяти строках:

0. MLZ -1 1 1; начальное значение
1. MLZ -1 A2 3; начало цикла, сдвиг данных
2. MLZ -1 A1 2; сдвиг данных
3. MLZ -1 0 0; конец цикла
4. ADD A2 A3 1; слот задержки перехода, вычисление следующего члена

Этот код вычисляет ряд чисел Фибоначчи, в адресе ОЗУ 1 содержится текущий член. После 28657 он быстро переполняется.

Код Грея:

0. MLZ -1 5 1; начальное значение адреса ОЗУ для записи
1. SUB A1 5 2; начало цикла, определение двоичного числа для преобразования в код Грея
2. SRL A2 1 3; сдвиг вправо на 1
3. XOR A2 A3 A1; XOR и сохранение кода Грея в адресе назначения
4. SUB B1 42 4; берём код Грея и вычитаем 42 (101010)
5. MNZ A4 0 0; если результат не равен нолю (код Грея!= 101010), повторить цикл
6. ADD A1 1 1; слот задержки перехода, инкремент адреса назначения

Эта программа вычисляет код Грея и хранит код в последовательных адресах, начиная с адреса 5. В программе используется несколько полезных особенностей, например, непрямая адресация и условный переход. Она прекращается только когда получившийся код Грея равен 101010 , что происходит при вводе 51 по адресу 56.

Онлайн-интерпретатор

El"endia Starman создал очень полезный онлайн-интерпретатор . В нём можно пошагово выполнять код, устанавливать контрольные точки, вручную выполнять запись в ОЗУ и визуализировать состояние ОЗУ на экране.

Cogol

После выбора архитектуры и языка ассемблера следующим шагом в «программной» стороне проекта будет создание высокоуровневого языка, подходящего для «Тетриса». Поэтому я создал Cogol . Название является и каламбуром от «COBOL», и аббревиатурой «C of Game of Life», хотя и стоит заметить, что Cogol по сравнению с C - то же самое, что наш компьютер по сравнению с реальным.

Cogol существует всего на один уровень выше языка ассемблера. В целом, большинство строк программы на Cogol соответствуют строкам на ассемблере, но у языка есть несколько важных особенностей:

• Основные возможности включают в себя именованные переменные с присвоением и операторы с более читаемым синтаксисом. Например, ADD A1 A2 3 превращается в z = x + y; . Компилятор привязывает переменные к адресам.
• Конструкции циклов, такие как if(){} , while(){} и do{}while(); позволяют компилятору обрабатывать ветвление.
• Одномерные массивы (с арифметикой указателей), которые используются для поля «Тетриса».
• Подпрограммы и стек вызовов. Они используются, чтобы избежать дублироания больших фрагментов кода и для поддержки рекурсии.

Компилятор (который я написал с нуля) очень прост/наивен, но я постарался вручную оптимизировать некоторые конструкции языка, чтобы достичь малой длины скомпилированных программ.

Вот краткий обзор работы различных особенностей языка:

Токенизация

Исходный код линейно токенизируется (за один проход) на основании простых правил о том, какие символы могут соседствовать в токене. Когда обнаруживается символ, который не может быть соседним с последним символом текущего токена, текущий токен считается завершённым, а новый символ начинает новый токен. Некоторые символы (например, { или,) не могут соседствовать ни с какими другими, потому сами являются отдельными токенами. Другие (например, > или =) могут соседствовать только сами с собой, то есть могут создавать такие токены, как >>> или == . Символы пробелов принудительно выставляют границы между токенами, но сами в результат не включаются. Самый сложный для токенизации символ - это - , потому что он может обозначать и вычитание, и унарное отрицание, а потому требует особой обработки.

Парсинг

Парсинг тоже выполняется за один проход. В компиляторе есть методы обработки каждой из конструкций языка, и после передачи различным методам компилятора токены извлекаются из глобального списка токенов. Если компилятор обнаруживает неожиданный токен, то выдаёт синтаксическую ошибку.

Распределение глобальной памяти

Компилятор назначает каждой глобальной переменной (слову или массиву) собственный адрес (адреса) в ОЗУ. Все переменные необходимо объявлять с помощью ключевого слова my , чтобы компилятор знал, что нужно выделить для них место. Гораздо круче, чем именованные глобальные перменные - это управление памятью временных адресов. Многим инструкциям (в частности условным операторам и многим операциям доступа к массивам) требуются «временные» адреса для хранения промежуточных вычислений. В процессе компиляции компилятор при необходимости выделяет и освобождает временные адреса. Если компилятору нужно больше временных адресов, он выделят под них больше ОЗУ. Полагаю, что обычно программы используют всего несколько временных адресов, при этом каждый адрес используется много раз…

Конструкции IF-ELSE

Конструкции if-else имеют стандартный для C синтаксис:

Другой код
if (cond) {
первое тело
} else {
второе тело
}
другой код

При преобразовании в QFTASM код получает следующую структуру:

Другой код
проверка условия
условный переход
первое тело
безусловный переход
второе тело (место условного перехода)
другой код (место безусловного перехода)

Если выполняется первое тело, то второе пропускается. Если первое тело пропускается, то выполняется второе.

В ассемблере «проверка условия» обычно бывает обычным вычитанием, и знак результата определяет, нужно ли совершить переход или выполнить тело. Для обработки таких неравенств, как > или <= используется инструкция MLZ . Инструкция MNZ используется для обработки == , потому что она выполняет переход через тело, когда разность не равна нулю (то есть когда аргументы неравны). Условия с несколькими выражениями пока не поддерживаются.

Если конструкция else отсутствует, то безусловный переход тоже опускается, и код на QFTASM выглядит так:

Другой код
проверка условия
условный переход
тело
другой код (место условного перехода)

Конструкции WHILE

Конструкции while тоже имеют стандартный для C синтаксис:

Другой код
while (условие) {
тело
}
другой код

При преобразовании в QFTASM код имеет такую схему:

Другой код
безусловный переход
тело (место условного перехода)
проверка условия (место безусловного перехода)
условный переход
другой код

Проверка условия и условный переход находятся в конце блока, и это значит, что они заново выполняются после каждого выполнения блока. Когда условие возвращает false, тело не выполняется и цикл заканчивается. Во время начала выполнения цикла поток управления перескакивает через тело цикла к коду условия, поэтому если в первый раз условие ложно, то тело никогда не выполняется.

Инструкция MLZ используется для обработки неравенств вида > или <= . В отличие от выполнения конструкций if , инструкция MNZ используется для обработки!= , потому что она переходит к телу, когда разность не равна нулю (то есть когда аргументы неравны).

Конструкции DO-WHILE

Единственная разница между while и do-while заключается в том, что тело цикла do-while в первый раз не обходится, поэтому оно всегда выполняется хотя бы один раз. Обычно я использую конструкции do-while для экономии пары строк ассемблерного кода, когда точно знаю, что цикл никогда не придётся пропускать полностью.

Массивы

Одномерные массивы реализованы как смежные блоки памяти. Все массивы имеют фиксированную длину, зависящую от объявления. Массивы объявляются следующим образом:

My alpha; # пустой массив
my beta = {3,2,7,8}; # в первые четыре элемента заранее записываются эти значения

Вот возможное распределение ОЗУ для массива, показывающее, что для него зарезервированы адреса 15-18:

15: alpha
16: alpha
17: alpha
18: alpha

Адреса, помеченные как alpha , заполняются указателем на местонахождение alpha , так что в этом случае адрес 15 содержит значение 16. Переменную alpha возможно использовать внутри кода Cogol как указатель стека, если необходимо использовать этот массив как стек.

Доступ к элементам массива выполняется с помощью стандартной записи array . Если значение index является константой, то эта ссылка автоматически заполняется абсолютным адресом элемента. В противном случае она выполняет арифметику указателей (просто сложение) для нахождения нужного абсолютного адреса. Возможно также встроенное индексирование, например alpha .

Подпрограммы и вызовы

Подпрограммы - это блоки кода, которые можно вызывать из различных контекстов, они позволяют избежать дублирования кода и создавать рекурсивные программы. Вот пример программы с рекурсивной подпрограммой для генерирования чисел Фибоначчи (самый медленный алгоритм):

# рекурсивное вычисление десятого числа Фибоначчи
call display = fib(10).sum;
sub fib(cur,sum) {
if (cur <= 2) {
sum = 1;
return;
}
cur--;
call sum = fib(cur).sum;
cur--;
call sum += fib(cur).sum;
}

Подпрограмма объявляется ключевым словом sub и может быть расположена в любом месте программы. В каждой подпрограмме может быть несколько локальных переменных, каждая из которых объявляется как часть её списка аргументов. Таким аргументам также задаются значения по умолчанию.

Для обработки рекурсивных вызовов локальные переменные подпрограммы хранятся в стеке. Последняя статичная переменная в ОЗУ является указателем стека вызовов, а вся память после неё служит стеком вызовов. При вызове подпрограммы она создаёт в стеке вызовов новый кадр, в который включаются все локальные переменные и адрес возврата (ПЗУ). Каждой подпрограмме в программе передаётся один статичный адрес ОЗУ, служащий указателем. Этот указатель задаёт местоположение «текущего» вызова подпрограммы в стеке вызовов. Выполнение ссылок на локальную переменную выполняется с помощью значения этого статичного указателя плюс смещения, чтобы задать адрес этой конкретной локальной переменной. Также в стеке вызовов содержится предыдущее значение статичного указателя. Вот распределение переменных для статичной ОЗУ и кадра вызовов подпрограммы для приведённой выше программы:

RAM map:
0: pc
1: display
2: scratch0
3: fib
4: scratch1
5: scratch2
6: scratch3
7: call

Fib map:
0: return
1: previous_call
2: cur
3: sum

Интересный аспект подпрограмм заключается в том, что они не возвращают никаких конкретных значений. После выполнения подпрограммы можно считывать все её локальные переменные, поэтому из вызова подпрограммы можно извлечь множество данных. Это реализуется хранением указателя для этого конкретного вызова подпрограммы, который можно затем использовать для восстановления всех локальных переменных из (недавно освобождённого) кадра стека.

Подпрограмму можно вызвать несколькими способами, все они используют ключевое слово call:

Call fib(10); # выполняется подпрограмма, никакого возвращаемого значения не сохраняется

Call pointer = fib(10); # выполняется подпрограмма и возвращается указатель
display = pointer.sum; # доступ к локальной переменной и её присвоение глобальной переменной

Call display = fib(10).sum; # немедленное сохранение возвращаемого значения

Call display += fib(10).sum; # с возвращаемым значением можно также использовать другие виды операторов присвоения

Для вызова подпрограммы можно задать в качестве аргументов любое количество значений. Все неуказанные аргументы будут заполнены их значениями по умолчанию (если они есть). Если аргумент не указан и не имеет очищенного значения по умолчанию (для экономии инструкций/временит), то может получить в начале подпрограммы любое значение.

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

Метки отладки

Любому блоку {...} в программе на Cogol может предшествовать метка описания из нескольких слов. Эта метка присоединяется к скомпилированному ассемблерному коду в качестве комментария, и может быть очень полезной для отладки, потому что она упрощает поиск нужных фрагментов кода.

Оптимизация слотов задержки перехода

Для повышения скорости скомпилированного кода компилятор Cogol выполняет в качестве последнего прохода по коду QFTASM очень простую оптимизацию слотов задержки перехода. Для любого безусловного перехода с пустым слотом задержки перехода слот задержки может быть заполнен первой инструкцией адрес перехода, а адрес перехода увеличивается на единиц, чтобы указывать на следующую инструкцию. Обычно это экономит один цикл при каждом выполнении безусловного перехода.

Написание кода «Тетриса» на Cogol

Готовая программа «Тетриса» была написана на Cogol, и её исходный код доступен . Скомпилированный код QFTASM доступен . Для удобства постоянная ссылка указана здесь: Tetris in QFTASM . Поскольку нашей целью было создание ассемблерного кода (а не кода на Cogol), получившийся код на Cogol довольно громоздок. Многие части программы должны быть расположены в подпрограммах, но эти подпрограммы на самом деле так коротки, что дублирование кода экономит больше инструкций, чем конструкции call . Готовый код в дополнение к основному коду содержит всего одну подпрограмму. Кроме того, многие массивы были удалены и заменены либо на список отдельных переменных аналогичной длины, или на множество жёстко заданных в программе чисел. Готовый скомпилированный код на QFTASM содержит менее 300 инструкций, хотя он и немного длиннее, чем сам исходник на Cogol.

Часть 5: сборка, трансляция и будущее

Получив от компилятора ассемблерную программу, мы можем приступить к сборке ПЗУ для компьютера Varlife и трансляции всего в большой паттерн игры «Жизнь»!

Сборка

Сборка ассемблерной программы в ПЗУ выполняется почти так же, как в традиционном программировании: каждая инструкция транслируется в двоичный аналог, а затем все они конкатенируются в один большой двоичный объект, называемый исполняемым файлом. Для нас единственная разница заключается в том, что двоичный объект должен транслироваться в цепи и подсоединиться к компьютеру.

Будущее проекта

Итак, мы сделали «Тетрис», и на этом всё закончено, правда? Ничего подобного. У нас есть для этого проекта и другие цели, над которыми мы работаем:

• muddyfish и Kritixi Lithos продолжают работу над высокоуровневым языком, компилируемым в QFTASM.
• El"endia Starman работает над обновлениями онлайн-интерпретатора QFTASM.
• quartata работает над GCC-бэкендом, который позволить с помощью GCC выполнять компиляцию независимого кода на C и C++ (а возможно и на других языках, например, Fortran, D или Objective-C) в QFTASM. Это позволит создавать более сложные программы на более знакомом языке, хоть и без стандартной библиотеки.
• Одно из самых серьёзных препятствий, которые нам нужно преодолеть, чтобы двигаться дальше, заключается в том, что наши инструменты не могут создавать позиционно-независимый код (PIC) (т.е. относительные переходы). Без PIC мы не можем использовать ссылки, то есть не можем воспользоваться преимуществами компоновки с готовыми библиотеками. Мы работаем над поиском способа правильной реализации PIC.
• Мы размышляем над следующей программой, которую стоит написать для компьютера QFT. Пока хорошей целью для нас выглядит Pong.

Часть 6: новый компилятор для QFTASM

Хотя языка Cogol и достаточно рудиментарной реализации «Тетриса», он слишком простой и низкоуровневый для программирования широкого назначения на хорошо читаемом уровне.

Мы начали работу над новым языком в сентябре 2016 года. Процесс развития языка шёл медленно из-за трудно понимаемых, как и в реальной жизни, ошибок.

Мы создали низкоуровневый язык с похожим на Python синтаксисом, включая простую систему типов, подпрограммы с поддержкой рекурсии и операторы встраивания.

Компилятор из текста в QFTASM был создан на четыре этапа: токенизатор, дерево грамматики, высокоуровневый компилятор и низкоуровневый компилятор.

Токенизатор

Разработка на Python началась с использования встроенное библиотеки токенизатора, то есть этот этап был довольно простым.

Необходимо было внести только небольшие изменения в выводимые по умолчанию данных, в том числе вырезание комментариев (но не #include).

Дерево грамматики

Дерево грамматики создавалось с расчётом на удобную расширяемость без необходимости изменения исходного кода.

Структура дерева хранится в файле XML, который содержит структуру составляющих дерево узлов и их соединений с другими узлами и токенами.

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

Генерируемые токены затем парсятся по правилам грамматики таким образом, что выходные данные формируют дерево элементов грамматики, например, sub и generic_variables , которые в свою очередь содержат другие элементы грамматики и токены.

Компиляция в высокоуровневый код

Каждая функция языка должна компилироваться в высокоуровневые конструкции. Например, assign(a, 12) и call_subroutine(is_prime, call_variable=12, return_variable=temp_var) . В этом сегменте выполняются такие функции, как встраивание элементов. Они определяются как operator , их особенность в том, что они встраиваются каждый раз, когда используется такой оператор, как + или % . Поэтому они более ограничены, чем обычный код - они не могут использовать собственный оператор и любой другой оператор, зависящий от определённого.

В процессе встраивания внутренние переменные заменяются на те, которые были вызваны. Таким образом это:

Operator(int a + int b) -> int c
return __ADD__(a, b)
int i = 3+3

Превращается в

Int i = __ADD__(3, 3)

Однако такое поведение может быть вредоносным и подверженным ошибкам, если входная и выходная переменные указывают на одно место в памяти. Для использования более «безопасного» поведения ключевое слово unsafe регулирует процесс компиляции таким образом, чтобы эти дополнительные переменные при необходимости создавались и копировались из подстановки.

Временные переменные (scratch variable) и сложные операции

Математические операции вида a += (b + c) * 4 невозможно вычислить без использования дополнительных ячеек памяти. Высокоуровневый компилятор справляется с этой проблемой, разделяя операции на различные части:

Scratch_1 = b + c
scratch_1 = scratch_1 * 4
a = a + scratch_1

Таким образом вводится концепция временных переменных, используемых для хранения промежуточной информации вычислений. Они выделяются при необходимости и освобождаются после завершения работы в общий пул. Это позволяет снизить количество требуемых для работы временных участков памяти. Временные переменные считаются глобальными.

Каждая подпрограмма имеет собственный VariableStore для хранения ссылок на все используемые подпрограммой переменные и их типов. В конце компиляции они транслируются в относительные смещения от начала хранилища, а затем им даются действительные адреса в ОЗУ.

Структура ОЗУ

Счётчик команд
Локальные переменные подпрограммы
Локальные переменные операторов (используются повторно)
Временные переменные
Переменная результата
Указатель стека
Стек
...

Низкоуровневая компиляция

Единственное, с чем приходится работать низкоуровневому компилятору - это sub , call_sub , return , assign , if и while . Это сильно уменьшенный список задач, который более удобно транслировать в инструкции QFTASM.

sub

Она задаёт начало и конец именованной подпрограммы. Низкоуровневый компилятор добавляет метки, а в случае подпрограммы main добавляет инструкцию выхода (переход к концу ПЗУ).

if и while

Низкоуровневые интерпретаторы while и if довольно просты: они получают указатели на их условия и зависящий от них переход. Циклы while немного отличаются в том, что они компилируются как

...
условие
переход к проверке
код
условие
если условие: переход к коду
...

call_sub и return

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

Все локальные переменные подпрограммы хранятся в постоянном месте ОЗУ, задаваемом во время компиляции. Для реализации рекурсии все локальные переменные для функции в начале вызова помещаются в стек. Затем аргументы подпрограммы копируются в их позицию в хранилище локальных переменных. Значение адреса возврата добавляется в стек и подпрограмма выполняется.

Когда встречается конструкция return , вершина стека извлекается и счётчик команд устанавливается на это значение. Значения для локальных переменных вызывающей подпрограммы извлекаются из вершины стека и возвращаются в их предыдущую позицию.

assign

Присвоение переменных компилировать легче всего: нужно взять переменную и значение и скомпилировать их в одну строку: MLZ -1 VALUE VARIABLE

Назначение адресов перехода

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

Поэтапный пример компиляции

Мы прошли по всем этапам, теперь давайте пошагово пройдём по процессу компиляции настоящей программы.

#include stdint

Sub main
int a = 8
int b = 12
int c = a * b

Отлично, всё довольно просто. Очевидно, что в конце программы a = 8 , b = 12 , c = 96 . Для начала давайте вставим соответствующие части из stdint.txt:

Operator (int a + int b) -> int
return __ADD__(a, b)

Operator (int a - int b) -> int
return __SUB__(a, b)

Operator (int a < int b) -> bool
bool rtn = 0
rtn = __MLZ__(a-b, 1)
return rtn

Unsafe operator (int a * int b) -> int
int rtn = 0
for (int i = 0; i < b; i+=1)
rtn += a
return rtn

Sub main
int a = 8
int b = 12
int c = a * b

Так, всё стало немного сложнее. Давайте перейдём к токенизатору и посмотрим, что получится. На этом этапе у нас есть только линейный поток токенов без какой-либо структуры

NAME NAME operator
LPAR OP (
NAME NAME int
NAME NAME a
PLUS OP +
NAME NAME int
NAME NAME b
RPAR OP)
OP OP ->
NAME NAME int
NEWLINE NEWLINE
INDENT INDENT
NAME NAME return
NAME NAME __ADD__
LPAR OP (
NAME NAME a
COMMA OP ,
NAME NAME b
RPAR OP)
...

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

GrammarTree file
"stmts": , int op(*:rtn))
("call_sub", "__ADD__", , int op(*:i))
("assign", global bool scratch_2, 0)
("call_sub", "__SUB__", , global int scratch_3)
("call_sub", "__MLZ__", , global bool scratch_2)
("while", "end", 1, global bool scratch_2)
("assign", int main_c, int op(*:rtn))
("sub", "end", "main")

Затем низкоуровневый компилятор должен преобразовать этот высокоуровневый вид в код QFTASM. Переменным назначается место в ОЗУ следующим образом:

Int program_counter
int op(*:i)
int main_a
int op(*:rtn)
int main_c
int main_b
global int scratch_1
global bool scratch_2
global int scratch_3
global int scratch_4
global int
global int

Затем простые инструкции компилируются. Наконец, добавляются номера инструкций, и в результате получается исполняемый код QFTASM.

0. MLZ 0 0 0;
1. MLZ -1 12 11;
2. MLZ -1 8 2;
3. MLZ -1 12 5;
4. MLZ -1 0 3;
5. MLZ -1 0 1;
6. MLZ -1 0 7;
7. SUB A1 A5 8;
8. MLZ A8 1 7;
9. MLZ -1 15 0;
10. MLZ 0 0 0;
11. ADD A3 A2 3;
12. ADD A1 1 1;
13. MLZ -1 0 7;
14. SUB A1 A5 8;
15. MLZ A8 1 7;
16. MNZ A7 10 0;
17. MLZ 0 0 0;
18. MLZ -1 A3 4;
19. MLZ -1 -2 0;
20. MLZ 0 0 0;

Синтаксис

Итак, у нас есть простой язык, и нам нужно написать на нём небольшую программу. Мы используем отступы как в Python, разделяя логические блоки и поток команд. Это значит, что в наших программах важны пробелы. Каждая готовая программа имеет подпрограмму main , которая действует как функция main() C-подобных языках. Функция выполняется в начале программы.

Переменные и типы

Когда переменная задаётся впервые, ей нужен связанный с ней тип. Пока у нас есть заданные типы int и bool с заданным для массивов, но не для компилятора синтаксисом.

Библиотеки и операторы

Имеется библиотека stdint.txt , задающая основные операторы. Если она не встроена в программу, то даже простейшие операторы не будут определены. Можно использовать эту библиотеку с помощью #include stdint . stdint определяет такие операторы, как + , >> и даже * с % , ни один из которых не имеет непосредственного опкода QFTASM.

Кроме того, язык позволяет выполнять прямой вызов опкодов QFTASM с помощью __OPCODENAME__ .

В stdint сложение определяется следующим образом

Operator (int a + int b) -> int
return __ADD__(a, b)

Эта запись определяет, что оператор + должен делать, когда ему передают два числа int .

Теги:

• тетрис
• игра жизнь
• клеточные автоматы
• conway"s game of life

Добавить метки

Соревнования по игре «Тетрис-онлайн» проводятся по следующим правилам.

1. Каждый участник регистрируется на сайте игры под определённым игровым именем. Имена участников не повторяются.

2. Чемпионат проводится в течение определённого времени. В любой момент этого времени любой зарегистрированный участник может зайти на сайт чемпионата и начать зачётную игру. По окончании игры её результат

(количество набранных очков) фиксируется и заносится в протокол.

3. Участники имеют право играть несколько раз. Количество попыток одного участника не ограничивается.

4. Окончательный результат участника определяется по одной игре, лучшей для данного участника.

5. Более высокое место в соревнованиях занимает участник, показавший лучший результат.

6. При равенстве результатов более высокое место занимает участник, раньше показавший лучший результат.

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

Перед текстом программы кратко опишите алгоритм решения задачи и укажите используемый язык программирования и его версию.

Описание входных данных

Первая строка содержит число N - общее количество строк протокола. Каждая из следующих N строк содержит записанные через пробел результат участника (целое неотрицательное число, не превышающее 100 миллионов) и игровое имя (имя не может содержать пробелов). Строки исходных данных соответствуют строкам протокола и расположены в том же порядке, что и в протоколе.

Гарантируется, что количество участников соревнований не меньше 3.

Описание выходных данных

Программа должна вывести имена и результаты трёх лучших игроков по форме,

приведённой ниже в примере.

Пример входных данных:

Пример выходных данных для приведённого выше примера входных

1 место. qwerty (197128)

2 место. Alex (95715)

3 место. Jack (95715)

Пояснение.

Для каждого игрока нам необходимо знать только максимальное количество очков, которое тот смог набрать, и момент времени, в который это количество было набрано. Будем хранить для каждого игрока имя, максимальное количество очков, которое он набрал на данный момент, и время, в которое было набрано это количество. При добавлении новой записи будем пробегать по списку и искать игрока с данным именем. Если такого игрока нет, добавим его. Если есть, то сравним его предыдущий результат с новым и, если нужно, обновим. После того, как считаны все данные, три раза повторим процедуру: найдём игрока с максимальным количеством очков. Если таких несколько, выберем из них игрока и минимальным временем. Выпишем его результат. Теперь в его очки запишем -1, чтобы в следующий раз он никак не мог быть лучшим.

Ниже приведён код решения на языке Pascal версии 2.6.2. Эффективный по памяти и времени.

var a,a1,a2,a3,i,n:longint;

s,s1,s2,s3:string;

for i:=1 to n do begin

if a>a1 then begin

if s=s1 then begin a1:=a; s1:=s; end

else if s=s2 then begin a2:=a1; s2:=s1; a1:=a; s1:=s end

end else if a>a2 then begin

if s=s2 then begin s2:=s; a2:=a; end

else if (ss1) then begin

end else if a>a3 then begin

if (ss1) and (ss2) then begin

writeln("1 место.",s1," (",a1,")");

writeln("2 место.",s2," (",a2,")");

writeln("3 место.",s3," (",a3,")");

Ниже приведён код решения на языке Pascal версии 2.6.2. Не являющегося эффективным по памяти.

var n, i, j, cnt, p, found, best, first, ind: longint;

name: array of string;

points, num: array of longint;

for i:= 1 to n do

for j:= 1 to cnt do

if s = name[j] then

if found = 0 then

points := -1;

if p > points then

points := p;

num := i;

for i:= 1 to 3 do

for j:= 1 to cnt do

if (points[j] > best) or (points[j] = best) and (num[j] begin

best:= points[j];

writeln(i, " место.", name, " (", points, ")");

В начале июня исполнился 31 год со дня создания одной из самых популярных компьютерных игр в истории человечества - «Тетриса». Спустя год после её появления на свет - 18 июля 1985 года - вышла известнейшая в России игровая платформа Brick Games. Внешне напоминающая современные смартфоны консоль вобрала в себя сразу несколько модификаций «Тетриса» и разошлась многомиллионным тиражом.

К 30-летию появления на свет знаменитой игровой платформы сайт вспоминает историю создания «Тетриса», а также его триумфальный выход из перестроечного СССР на рынки всего мира.

Головоломка в стакане

«Тетрис» был создан в 1984 году сотрудником Вычислительного центра при Академии наук СССР Алексеем Пажитновым. Он трудился над игрой в свободное от основной работы время и хотел, скорее, порадовать себя и своих коллег, чем покорить умы геймеров всего света.

Алексей Пажитнов задумал свою знаменитую игру после знакомства с головоломкой. Фото: www.globallookpress.com

Идея «Тетриса» пришла к Пажитнову в 1984 году, когда он познакомился с головоломкой математика из США Саломона Голомба, которая называлась пентамино. Её суть была в том, чтобы из нескольких фигур сложить одну большую. Разработчик решил создать компьютерный вариант пентамино. При этом, по задумке автора, в его игре нужно было собирать фигурки в стакане в реальном времени. Пажитнов хотел, чтобы фигуры, состоявшие из пяти элементов, переворачивались вокруг собственного центра тяжести. Тогда компьютерам, находившимся в распоряжении Вычислительного центра, этого сделать не удавалось из-за недостатка ресурсов. Разработчик решил сократить количество блоков, из которых состояли фигурки, до четырех. Получился уже тетрамино. Игру Пажитнов назвал «Тетрис», скрестив «тетрамино» и «теннис». За основу программист взял семь фигурок, составивших в дальнейшем классический набор игры. Ни о какой графике на тот момент речи идти не могло, поскольку у компьютера «Электроника-60», на котором создавался «Тетрис», не было монитора, а только дисплей, выводящий буквы и цифры.

Компьютер Электроника-60М - на чуть более ранней модели создавалась игра. Фото: Commons.wikimedia.org / Sergei Frolov

Первая версия игры создавалась на популярном в те времена языке Pascal, так что всё выглядело довольно примитивно. Только через восемь месяцев Пажитнов решил портировать «Тетрис» уже на PC. Опыта работы на персональном компьютере разработчик не имел, поэтому привлек для этой задачи 16-летнего школьника Вадима Герасимова, который был в Вычислительном центре кем-то вроде юного гения. Игру перенесли на PC за четыре дня, еще примерно столько же времени ушло на отладку рабочих процессов. Далее последовала полугодовая работа над цветом и таблицей рекордов. Также прорабатывалась система защиты, чтобы затем можно было доказать авторство. Все это программисты делали в свое свободное время. Позднее коллега Пажитнова Михаил Потемкин портировал игру на компьютер «Электроника» и добавил автоматическую загрузку «мусора», когда в стакане в начале процесса уже были фигурки.

Игра быстро распространилась сперва по Москве, а затем по всему СССР - её копировали на дискетах. На тот момент никакой выгоды её создатели не извлекли, поскольку фактически она принадлежала Вычислительному центру.

Продажа без согласия

Иностранцам «Тетрис» впервые показали в 1986 году. В Москву тогда пожаловали будапештцы из Института проблем кибернетики - с ним сотрудничал Вычислительный центр. Игра зарубежным гостям понравилась, после чего они довольно быстро портировали её на компьютеры Commodore 64 и Apple 2.

Среди гостей был и владелец британской компании Andromeda Software Роберт Штайн, сразу же решивший выкупить права на игру. Он даже успел получить одобрение от Пажитнова, но никаких конкретных сумм не озвучил. Да и переписка из-за «железного занавеса» шла между ними очень долго.

Штайн, полагая, что сделка о покупке советской игры уже практически решена, предложил «Тетрис» своим партнерам из Microsoft. Там эта идея большого восторга не вызвала. На всякий случай представители компании отправили детище Пажитнова американским коллегам из компании Spectrum Holobyte. Там разглядели большой потенциал в «Тетрисе», а Microsoft и Andromeda Software успели подписать контракт о продаже на сумму 3000 фунтов стерлингов и 7-15% от продаж. Сам разработчик «Тетриса» вовсе остался в неведении.

Предприимчивый Штайн хотел как можно быстрее все легализовать, только в СССР ему уже надо было работать с верхушкой Академии наук, а не с Вычислительным центром, и уж тем более не с рядовыми его сотрудниками. Чиновникам все это показалось не особо интересно. В итоге глава Andromeda Software уехал ни с чем.

В Spectrum Holobyte, не подозревая о том, что фактически займутся пиратским распространением, доработали советскую игру. Они добавили «Тетрису» коммунистические зарисовки, портреты известных русских, а в качестве музыкального сопровождения поставили песни «Коробейники» и «Калинку». Игровую механику трогать не стали. К 1987 году готовый коммерческий продукт собирались выпустить в Британии и США, только вот Штайн прав на «Тетрис» получить так и не сумел. В итоге он принял решение вовсе никому ничего не говорить. В 1988 году на Западе состоялся релиз PC-версии игры.

Детище КГБ

Успех проекта был огромен. На Западе новинка разошлась приличными тиражами, «Тетрису» присудили множество премий и наград. Игра могла на целый день парализовать работу офисов, из-за чего ходил слух, что ради ущерба экономике других стран её и разработали в недрах КГБ.

Пажитнов в это время перешел работать в ЭЛОРГ («Электроноргтехника»), которая была закреплена за Академией наук. Этой организации предстояло отстаять международные права на «Тетрис».

В итоге на Штайна надавили, в том числе не без помощи западных СМИ. Он принял условия СССР, подписав контракт. Представители Microsoft в это время попросили главу Andromeda Sofrware приобрести у разработчиков права на консольную и аркадную версию игры, но сами почему-то продали права на аркаду компании Atari, которая впоследствии перепродала игру японской Sega.

Тетрис вышел на Game Boy и заслужил широкую популярность в мире. Фото: www.globallookpress.com

Штайну в переговорах продвинуться не удалось, поскольку он не мог оплатить русским контракт. Но в Японии ждать не стали - там выпустили «Тетрис» двухмиллионным тиражом на PC и NES от Nintendo. Последняя смогла выкупить права через несколько фирм, а затем, договорившись с владельцами прав из СССР, запустить игру на портативной Game Boy, что обеспечивало консоли успех. При этом японская компания выиграла судебный процесс у Microsoft и Atari, которым пришлось довольствоваться только аркадной версией «Тетриса».

Game Boy, в комплекте с которым продавалась игра, не в последнюю очередь благодаря детищу Пажитнова за несколько первых лет разошелся более чем 30-миллионным тиражом, а самих картриджей с игрой было продано около 15 млн. Впоследствии Game Boy стал одной из самых успешных консолей за всю историю электронных развлечений.

В России 1990-х, еще только выстраивающей рыночную экономику, японскую консоль приобрести было не просто. Куда более популярным было впервые выпущенное для стран Европы недорогое устройство Brick Game, основанное на аналоге «Тетриса». Здесь были гонки, а также игры, подобные «змейке» и «танковым боям». В данном случае о соблюдении каких-либо прав на детище советского разработчика, вероятно, речи не шло совсем. Да и появилось устройство впервые в 1985 году, когда до официального релиза «Тетриса» в Европе было еще три года.

В 1990-х именно на этой платформе большинство играло в тетрис. Фото: АиФ-Петербург/ Яна Хватова

Одна игра

Алексей Пажитнов в 1989 году, понимая, что на играх можно делать большие деньги, объединился со старым приятелем Владимиром Похилко и новым другом Хенком Роджерсом, который вел переговоры о продаже «Тетриса» в Японию. Они создали студию AnimaTek, которая занималась разработкой логических игр и вопросами искусственного интеллекта. Некоторые разработки этой компании вошли, к примеру, в мегапопулярную стратегию 1990-х Age of Emires. В перестройку AnimaTek открыла штаб-квартиру в Сан-Франциско, выпустив затем несколько анимационных игр, которые, впрочем, признания не получили. После запуска пары программ для трехмерного моделирования студия канула в Лету.

Алексей Пажитнов со своим бизнес-партнером Хенком Роджерсом. Фото: www.globallookpress.com

Возможность же зарабатывать какие-то проценты с «Тетриса» Пажитнов получает лишь в 1996 году, когда истекает срок первоначальной лицензии. Программист сразу же создал компанию The Tetris Company в сотрудничестве с Роджерсом. TTC зарегистрировал «Тетрис» как торговую марку и с тех пор начал отслеживать законность ее применения.

За свою жизнь Алексей Пажитнов успел создать порядка 13 игр, но ни одна из них так и не приблизилась к ошеломляющей популярности «Тетриса», в который играют уже на протяжении нескольких десятилетий.

Правила игры «Тетрис»

(с дополнениями для эксперимента «Тетрис-Пси»)

Цель игры : заполнить как можно больше горизонтальных линий на игровом поле, размещая опускающиеся фигуры и не оставляя пустых пространств между ними. Один сеанс длится ровно 2 минуты. Заполненные линии автоматически удаляются, предоставляя пространство для продолжения игры.

Действия с фигурами

Внимание: управление производится с помощью клавиатуры, а не с помощью мышки.

Клавиша (à) для перемещения фигуры вправо

Клавиша (ß) для перемещения фигуры влево

Клавиша (á) для вращения фигуры ПО часовой стрелке

Клавиша Z для вращения фигуры ПРОТИВ часовой стрелки

Клавиша (â) для ускоренного, но ПЛАВНОГО перемещения фигуры вниз

Клавиша (ПРОБЕЛ ) для МГНОВЕННОГО перемещения (сброса) фигуры вниз

Клавиша Shift для помещения фигуры в карман (окошко “ hold ” в левом верхнем углу ) и замены ее на фигуру из кармана. . В начале игры, когда карман пуст, фигура просто заменяется следующей.

Результат игры и советы по игре

1. Результаты игры формируются из двух показателей:

А) Простой - это количество линий, которые удается заполнить за 2 минуты.

Б) Сложный - это количество очков, которые удается набрать за 2 минуты с учетом бонусов за комбинации.

2. К оличество очков, набранных в игре, зависит от количества линий, заполненных за один ход (одной фигурой). За одну линию дается 100 очков. Больше очков Вы получите, если за один раз «заполните» 2, 3 или 4 линии. За 4 линии сразу («тетрис») Вы получите наибольшее количество очков – 1200.

3. Бонусные (премиальные) очки также даются, если Вы заполняете линии подряд несколькими ходами без пропусков.

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

5. Сверхпремия дается за последовательное (без снятых в промежуточных ходах линий) получение высших комбинаций («тетрисов» и «т-спинов»). На международных соревнованиях по Тетрису эти комбинации называются back-to-back.

6. Для планирования размещения фигур используйте подсказку в правом дополнительном поле – там показана будущая последовательность фигур («очередь»).

7. Для чего нужен карман (клавиша Shift)?

А) В зависимости от стратегии игры Вам может пригодиться какая-то фигура, которая «редко» появляется. Если она появилась, но не вовремя, используя карман (окошко “ hold ” в левом верхнем углу ), вы можете ее сохранить до «нужного» момента.

Б) Карман пригодится, если появляется «неудобная» фигура которую некуда поставить. В этом случае Вы можете использовать карман как «временную отмену» фигуры до момента, когда Вам будет удобно ее использовать.

Запуск и завершение игры, сеансы и подсказки

8. Игру на сайте-психоигротеке www. *****/tetris могут запускать только зарегистрированные игроки, которые до этого выполнили 2 опросника, включенные в программу эксперимента.

9. Если хотите, между сеансами внутри серий Вы можете делать паузы любой длительности. Однако для того, чтобы вам засчитали выполнение игрового этапа эксперимента, вы НЕ должны выходить из системы во время этих пауз.

ВНИМАНИЕ: Между сериями можно делать паузы даже на несколько дней, то есть, можно покидать личную страницу до следующей авторизации . Но главное - уложиться во время по срокам эксперимента.

10. Если игровое поле переполняется, Ваш игровой сеанс может завершиться досрочно (до истечения 2-х минут).

11. Ровно за 10 секунд до конца сеанса окошко “time” начнет мигать красным цветом - это значит, что пора завершать начатые комбинации.

12. У игры есть звуковое сопровождение. Если вам нравится играть со звуками, Вы можете подключить колонки или наушники.

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

14. Если Вы забыли какие-то правила, то в перерывах между сеансами вы можете воспользоваться подсказкой (краткой инструкцией) – она расположена под игровым полем.

15. Сразу после завершения каждого 2-х минутного сеанса в верхней части игрового окна вы увидите количество «очищенных линий» (это основной показатель) и количество набранных очков (это вспомогательный показатель).

16. В эксперименте «Терис-Пси» для каждой игровой серии создается внутренний рейтинг зарегистрированных игроков – участников эксперимента. Более высокое место в рейтинге занимают игроки, которые имеют более высокий личный рекорд по количеству «очищенных линий». При равенстве этих личных рекордов более высокое место в рейтинге занимает игрок, который набрал больше очков.