Релейный компьютер, телетайп и интересный алгоритм игры в крестики-нолики
Крестики-нолики — классическая игра, которую наверное пытался написать каждый. При этом программы иногда получаются довольно запутанные, несмотря на простоту правил. Электромагнитные реле — классическая элементная база для компьютеров и калькуляторов. Они тёплые, ламповые и прикольно щёлкают. Если добавить к этому телетайп, то получится игровая консоль в стиле 1940х.
Релейный компьютер
Релейный компьютер я делаю уже давно. В нём 8 регистров по 8 бит. Правда один из них PC, так что для данных доступно 7. АЛУ умеет выполнять операции с любой парой регистров и помещать результат тоже в любой регистр. Есть инструкция CALL, которая адрес возврата записывает в регистр L. Такой вот ARM на минималках.
Сейчас у моего компьютера всего 64 слова памяти программ. Каждая инструкция — это два восьмибитных DIP-переключателя. Записывать программу в такое ПЗУ не слишком просто, поэтому лучше писать без ошибок.
ПЗУ компьютера.
Адресное пространство восьмибитное, так что можно сделать ПЗУ немного побольше. Но очень уж долго паять, так что ограничение в 64 инструкции ещё какое-то время просуществует.
Из-за этого написание программ превращается в очень сложный квест. Но даже самая простая программа нуждается в том, чтобы получать данные от пользователя и выводить куда-нибудь результат. Вывод отдельных восьмибитных чисел возможен через индикацию, встроенную в реле, но что делать, если надо вывести что-то посложнее?
В каждом реле есть светодиод, поэтому значения регистров можно просто считывать, глядя на панель регистрового файла.
К счастью, у меня не так давно появился телетайп Consul-254. У него довольно простой интерфейс, поэтому грех не попробовать и не подключить его к релейному компьютеру.
Вывод на телетайп
Телетайп Consul-254 использовался в былые времена в качестве устройства ввода-вывода для компьютеров. Внешне он напоминает пишущую машинку, но сигналы с клавиатуры поступают в ЭВМ, а ЭВМ, в свою очередь, выводит нужный текст на печать. Менее удобно, чем дисплей, но не менее интересно.
Печатает как пишущая машинка, но не пишущая машинка.
Выводить текст на телетайп не очень сложно. В нём есть неполная матрица 8×8 из электромагнитных реле (элементная база идеально подходит к моему компьютеру). Нужно подать на нужную строку напряжение питания, столбец соединить с землёй, и выбранное реле запустит печать соответствующего символа.
Вся матрица реле для выбора печатаемых символов. Внизу подписаны номера контактов внешнего разъёма телетайпа.
Вряд ли будет разумно планировать выводить сообщение «Hello, World!» с компьютера, в котором максимальный размер программы всего 64 инструкции. Поэтому печать можно ограничить цифрами. Но какими? Использовать ли десятичную систему? Или шестнадцатеричную с цифрами ABCDEF? Или взять в качестве дополнительных АБВГДЕ, и тогда можно будет печатать ЕГГОГ?
Для шестнадцатеричной печати нужно декодировать 16 разных комбинаций. А значит, если понадобятся ещё какие-то символы (например, перевод строки), то придётся делать пятибитный дешифратор. Если же использовать только цифры от 0 до 9, то и с четырёхбитным дешифратором остаётся 6 запасных символов.
В конце концов я решил, что буду использовать четырёхбитные коды символов. Кодам 0–9 будут соответствовать такие же цифры, а коду 15 — перевод строки. Останется 5 символов, для которых я пока не придумал назначения. Получился дешифратор как на картинке ниже.
Дешифратор для печатаемых символов. Пунктиром обведены те реле, которые так и не были добавлены. Резистор подобран эмпирически для преобразования 24 вольт внутри компьютера в 12 вольт для реле телетайпа.
Точнее, тут сразу два дешифратора, потому что надо коммутировать не только «плюс», но и «минус», чтобы выбрать нужное реле в матрице внутри телетайпа. Сам выбор символов для печати здесь не показан. Просто выходы дешифратора припаяны к контактам разъёма для подсоединения телетайпа. С этого разъёма по суровому толстому кабелю сигналы поступают сразу на матрицу.
Кабели со стороны телетайпа имеют вот такие разъёмы.На стороне компьютера я использую обычные d-sub 25.
У моего релейного компьютера восьмибитная шина адреса. Сейчас её занимает ПЗУ (адреса 0×00–0×3f) и тумблеры для ввода данных (адреса 0×80–0×8f). Так как мы уже определились, что выводить на телетайп будем по 4 бита, можно их брать прямо с шины адреса, заняв адреса 0×90–0×9f. Но система команд компьютера не очень приспособлена к такому. Если в регистре хранится число, надо к нему прибавить 0×90 для получения адреса. А для этого потребуется целых две инструкции. Выходит, что проще передавать символ через шину данных. Но адреса для телетайпа я всё равно занял все, 0×90–0×9f, чтобы упростить дешифратор. Для вывода символа достаточно всего двух команд:
MOVI A, 8 ; загрузить символ в регистр
STORE A, 0x90 ; записать регистр в "память"Вроде уже можно было бы и печатать. Но оказалось, что включить реле для печати гораздо проще, чем вовремя выключить его. Телетайп работает шустрее, чем релейный компьютер. И даже если сигнал печати снимается через один такт процессора (это примерно 0.2 с), за это время успевает напечататься сразу несколько символов. Чтобы этого не случалось, телетайп замыкает определённые контакты, по которым можно понять, что печать символа произошла.
Казалось бы, достаточно использовать этот сигнал, чтобы снимать питание с катушки реле выбранного символа. Но тут снова оказалось, что телетайп слишком быстрый. Реле, которые я использую для постройки компьютера, не успевали сработать во время появления сигнала печати. Пришлось применить быстродействующие герконовые реле (не ставить же в релейный компьютер полупроводники), и тогда всё заработало.
Чтобы хорошенько протестировать печать, я написал программу для вычисления числа Пи и вывода его на телетайп. Конечно, здесь вычисляется всего лишь аппроксимация с помощью дроби 355/113, но первые несколько знаков получаются правильные.
Ввод и прерывания
Чтобы играть с компьютером, нужно вводить в него данные с помощью клавиатуры телетайпа. Телетайп передаёт в ЭВМ 8-битные коды символов. Каждая клавиша предназначена для набора двух символов, в верхнем или в нижнем регистре, поэтому выбранный регистр влияет на два старших бита кода символа (не очень понятно, почему сразу два, но сейчас это не важно). Программной памяти в релейном компьютере очень мало, поэтому работа с этими битами будет явным излишеством.
Остаётся 6 полезных битов, указывающих на нажатую клавишу. Так как от вывода букв я уже почти отказался, взглянем повнимательнее на коды цифровых клавиш:
Столбцы соответствуют битам кода клавиши. Если там что-то написано, то этот бит равен единице.
Очень удобно, что младшие шесть битов клавиш 0–9 кодируют числа 0–9. Это значит, что можно считывать эти сигналы прямо в регистр и не заниматься их дешифрацией. Так как на выводе у меня 4-битный дешифратор, то зачем мне уметь получать с клавиатуры слишком много разных клавиш? Будем сохранять только 4 младших бита. Для цифр этого достаточно. Если нужно, можно будет ещё применить какие-то из оставшихся 6 кодов. Например, это могут быть буквы К или П.
Для защёлкивания сигналов с клавиатуры я снова применил герконовые реле. Получился «быстродействующий» 4-битный регистр. Он подключается на шину при чтении процессором тех же адресов, которые использовались для вывода символа на печать.
В более простых играх, которые я писал раньше, пользовательский ввод происходил через сброс какого-нибудь регистра, через изменение ПЗУ или через тумблеры, отображённые в адресное пространство (но они появились не сразу). Естественно, чтобы игрок успел сделать выбор, программа останавливалась с помощью инструкции HALT. После набора значения, нужно было вручную нажать на панели кнопку START для продолжения работы.
С телетайпом же момент, когда работу надо продолжить, очевиден. Это когда пользователь нажал что-то на его клавиатуре. Тогда же и нужно возобновлять работу программы. Получился простенький механизм прерываний. Если процессор спит, то этот сигнал будит его, и программа продолжает работу.
Неудачная попытка сделать крестики-нолики
Типичная программа для игры в крестики-нолики для хранения игрового поля использует массив, например int a[3][3]. Это целых девять ячеек памяти. Конечно, если в моём компьютере появится ОЗУ, я смогу попробовать написать программу, использующую массив. Сейчас же в нашем распоряжении только семь восмибитных регистров общего назначения.
Но ведь каждая ячейка игрового поля может быть закодирована всего двумя битами. Значит для одной строки поля достаточно одного из регистров. Хранить состояния клеток можно как пару битов. Если один из них установлен, то это крестик, а если второй, то нолик. Если не установлен никакой бит, то клетка пустая. Но попытка написания такой программы тоже оказалась неудачной, слишком мало памяти, чтобы всё учесть: и считывание хода игрока, и выбор оптимального хода программы, и проверку условия выигрыша для вертикалей, горизонталей и диагоналей.
В общем, если удвоить объём ПЗУ, то можно использовать подобный подход. Но пока ничего не выйдет. После этой попытки я решил поискать ещё какие-нибудь идеи для программ.
Где брать другие игры?
На что больше всего похож релейный компьютер? На большой (по габаритам, конечно) программируемый калькулятор. Взять, к примеру, популярный (в своё время) МК-52 или почти такой же по возможностям МК-61.
Программируемый калькулятор МК-52
Чем он похож и чем отличается от релейного компьютера?
У МК-52 программа может состоять из 105 шагов, у моего компьютера из 64.
Но чтобы загрузить в регистр двузначное число, МК-52 тратит сразу две ячейки памяти программ.
Работать регистрами напрямую нельзя, сначала значения из них надо загрузить в стек. А потом результат записать из стека обратно в регистр. То есть в калькуляторе для имитации инструкции типа «ADD B, A, D» нужно потратить четыре команды. Конечно, если правильно организовать порядок вычислений, можно немного сэкономить.
Битовых иннструкций нет. Например, проверка числа x на чётность делается с помощью «cos (pi * x) > 0» вместо «x & 1 == 0». Не сильно сложнее, но выглядит, как чёрная магия.
Зато все числа вещественные. Можно играть в знаменитую «Посадку на Луну».
Ну и для вывода числа в десятичном виде не нужно преобразовывать его в набор цифр вручную.
Выходит, что для целочисленных вычислений плотность кода у релейного компьютера немного выше. Тогда шансы адаптировать какую-то (даже большую) программу с калькулятора должны быть достаточно неплохие.
Про калькуляторы уже много книг написано, поэтому я попробовал почерпнуть немного мудрости оттуда. Но искать придётся только игры, не использующие вещественных чисел. В книге «Микрокалькулятор, ваш ход» нашлась подходящая (на первый взгляд) программа.
Правда очень скоро выяснилось, что программа эта неправильная. А правильная напечатана в самом конце, на форзаце:
Заметили, что ссылка на 195 страницу вместо 198? Нельзя просто так взять и исправить опечатку.
Вот это поворот!
В исправленной программе тоже есть ошибка, но уже совсем небольшая.
Как это часто бывало в книгах и журналах 80х, для программы никакого объяснения не приводится, только дамп. Удивительно, как читателям удавалось их отлаживать и дорабатывать. Поэтому я первым делом загрузил дамп в IDA Pro перевёл программу на Си. Потом немного рефакторинга, поиска логики, и получается небольшая игра.
Вся программа поместилась здесь.
#include
#include
int player_move, move;
void print(int x)
{
printf("%d\n", x);
}
int input(void)
{
int x;
scanf("%d", &x);
return x;
}
void win(int x)
{
print(x);
print(77);
exit(0);
}
void check_win(int move)
{
int x = move - 4;
if (x <= 0)
{
x = x + 8;
}
if (x != player_move)
win(x);
}
void move_left(int pos)
{
move = pos - 1;
if (move == 0)
{
move = 8;
}
print(move);
player_move = input();
check_win(move);
}
int main()
{
print(9);
move_left(input());
// если второй ход компьютера был в угол
if (move % 2)
{
move_left(move);
win(move - 1);
return 0;
}
move_left(player_move);
move_left(player_move);
tie:
print(0);
}
Итак, секрет такой короткой программы в правильной нумерации клеток поля. Если делать это как обычно, слева направо и сверху вниз, то на каждый ход игрока придётся явно описывать вариант ответного хода. Дерево ходов получится не такое уж маленькое, посмотрите на картинку ниже. Вместо этого программа использует нумерацию периферийных клеток поля по часовой стрелке. Дальше мы увидим, что это даёт.
Ациклический граф позиций для игры крестики-нолики. Картинка из Википедии.
Второй секрет программы из книги в том, что первый ход она всегда делает в центр. Варианта игры, чтобы за крестиков играл человек, тоже не предусмотрено. Но третий секрет ещё интереснее. Никаких проверок корректности хода нет. Можно походить в уже занятую клетку. И даже ввести число больше 9. Но переполнения буфера и выполнения произвольного кода, к сожалению, не получается.
Итак, суть алгоритма в следующем. Он делится на две части, в зависимости от первого хода игрока и использует два вида вычисления номера клетки для возможного хода:
Клетку «левее», то есть с номером на единицу меньше (или ближайшую против хода часовой стрелки).
Клетку «напротив» с номером на 4 меньше (то есть противоположную по периметру).
Конечно же при этом ещё учитывается переход через ноль. Весь алгоритм можно разбить на такие шаги:
Делаем ход в центр.
Человек делает ход A.
Делаем ход в соседнюю от хода игрока клетку (A — 1).
Человек делает второй ход B. Если он не заблокировал линию, которую образуют два крестика программы (A — 1 — 4), то она делает победный ход туда и завершается.
Если предыдущий наш ход (A — 1) был в угол, то можно выиграть
Ставим крестик левее (A — 1 — 1), получается вилка.
Человек делает ход.
Если этот ход не блокирует линию с нашим последним ходом, то делаем победный ход туда.
В противном случае, ход игрока не заблокировал линию с предпоследним ходом, поэтому делаем последний ход туда.
Если предыдущий наш ход был не в угол, то получится только ничья
Программа делает ход в клетку (B — 1).
Человек делает ход C. Если он не заблокировал линию, которую образуют два крестика программы (B — 1 — 4), то она делает победный ход туда и завершается.
Иначе программа делает ход в клетку (C — 1).
Человек делает последний ход.
Печатается сообщение о ничьей.
Вот так это выглядит на картике:
Варианты развития событий. Не показаны заведомо проигрышные ходы «ноликов», которые не блокируют появляющуюся линию из «крестиков».
Получается очень элегантно. Если игрок не блокирует наш победный ход, всегда ходим в клетку, которая левее чего-нибудь. Левее предыдущего нашего хода, или левее хода игрока. Переменных для этого тоже нужно очень мало.
Новый вариант крестиков-ноликов
Осталось перенести этот алгоритм на релейный компьютер. В оригинале клетки поля нумеруются от 1 до 9. Причём номер 9 в самой игре не используется, а выводится только как первый ход. Остаются всего 8 клеток. Если пронумеровать их от 0 до 7, то переход в минус (или переполнение, не важно) можно исправлять с помощью побитового «И». Получается просто «next = (prev — 1) & 7». В калькуляторе такого не было, там приходилось делать ветвление и коррекцию результата. Первый ход всегда будет в центр, в клетку номер 8, а девятка используется для вывода 99 в случае победы программы или просто 9 в случае ничьей. Надо же, все распаянные символы пригодились.
Листинг программы
main:
MOVI A, 8 00: 10000000 00001000
STORE A, 0x90 01: 00110000 10010000
HALT 02: 00010000 00000000
LOAD A, 0x90 03: 00100000 10010000
STORE A, 0x90 04: 00110000 10010000
CALL move_left 05: 10001111 00011100
MOV C, A 06: 00011010 00000000
CALL load 07: 10001111 00101010
CALL check_win 08: 10001111 00100000
TST C, 1 09: 01100000 10100001
JMP NZ, tie 0a: 11100111 00010010
MOV A, C 0b: 00011000 00100000
CALL move_left 0c: 10001111 00011100
MOV C, A 0d: 00011010 00000000
CALL load 0e: 10001111 00101010
CALL check_win 0f: 10001111 00100000
SUB A, C, 1 10: 01011000 10101001
JMP win 11: 10000111 00100101
tie:
MOV A, B 12: 00011000 00010000
CALL move_left 13: 10001111 00011100
CALL load 14: 10001111 00101010
CALL check_win 15: 10001111 00100000
MOV A, B 16: 00011000 00010000
CALL move_left 17: 10001111 00011100
CALL load 18: 10001111 00101010
CALL check_win 19: 10001111 00100000
MOVI A, 9 1a: 10000000 00001001
STORE A, 0x90
HALT 1b: 00010000 00000000
move_left:
SUB A, A, 1 1c: 01011000 10001001
AND A, A, 7 1d: 01100000 10001111
STORE A, 0x90 1e: 00110000 10010000
RET 1f: 00011111 01100000
check_win:
ADD A, A, 4 20: 01001000 10001100
AND A, A, 7 21: 01100000 10001111
CMP A, B 22: 01011000 00000001
JMP NZ, win 23: 11100111 00100101
RET 24: 00011111 01100000
win:
STORE A, 0x90 25: 00110000 10010000
MOVI A, 9 26: 10000000 00001001
STORE A, 0x90 27: 00110000 10010000
STORE A, 0x90 28: 00110000 10010000
HALT 29: 00010000 00000000
load:
HALT 2a: 00010000 00000000
LOAD B, 0x90 2b: 00100001 10010000
STORE B, 0x90 2c: 00110001 10010000
RET 2d: 00011111 01100000
Набираем программу с помощью кучи переключателей, стараясь не ошибиться. Теперь можно играть:
Заключение
Оказывается, даже в такой простой игре можно найти для себя что-то новое. Например, существенно упростить алгоритм, пронумеровав клетки поля по кругу, а не слева направо. Если алгоритм с массивом не влезал в память совсем, то этот занимает меньше, чем три четверти объёма. А оставшееся место теперь можно использовать, чтобы проверять корректность ходов игрока.
