Релейный компьютер, телетайп и интересный алгоритм игры в крестики-нолики

Крестики-нолики – классическая игра, которую наверное пытался написать каждый. При этом программы иногда получаются довольно запутанные, несмотря на простоту правил. Электромагнитные реле – классическая элементная база для компьютеров и калькуляторов. Они тёплые, ламповые и прикольно щёлкают. Если добавить к этому телетайп, то получится игровая консоль в стиле 1940х.

Релейный компьютер

Релейный компьютер я делаю уже давно. В нём 8 регистров по 8 бит. Правда один из них PC, так что для данных доступно 7. АЛУ умеет выполнять операции с любой парой регистров и помещать результат тоже в любой регистр. Есть инструкция CALL, которая адрес возврата записывает в регистр L. Такой вот ARM на минималках.

Сейчас у моего компьютера всего 64 слова памяти программ. Каждая инструкция - это два восьмибитных DIP-переключателя. Записывать программу в такое ПЗУ не слишком просто, поэтому лучше писать без ошибок.

Адресное пространство восьмибитное, так что можно сделать ПЗУ немного побольше. Но очень уж долго паять, так что ограничение в 64 инструкции ещё какое-то время просуществует.

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

К счастью, у меня не так давно появился телетайп Consul-254. У него довольно простой интерфейс, поэтому грех не попробовать и не подключить его к релейному компьютеру.

Вывод на телетайп

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

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

Вряд ли будет разумно планировать выводить сообщение "Hello, World!" с компьютера, в котором максимальный размер программы всего 64 инструкции. Поэтому печать можно ограничить цифрами. Но какими? Использовать ли десятичную систему? Или шестнадцатеричную с цифрами ABCDEF? Или взять в качестве дополнительных АБВГДЕ, и тогда можно будет печатать ЕГГОГ?

Для шестнадцатеричной печати нужно декодировать 16 разных комбинаций. А значит, если понадобятся ещё какие-то символы (например, перевод строки), то придётся делать пятибитный дешифратор. Если же использовать только цифры от 0 до 9, то и с четырёхбитным дешифратором остаётся 6 запасных символов.

В конце концов я решил, что буду использовать четырёхбитные коды символов. Кодам 0-9 будут соответствовать такие же цифры, а коду 15 – перевод строки. Останется 5 символов, для которых я пока не придумал назначения. Получился дешифратор как на картинке ниже.

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

У моего релейного компьютера восьмибитная шина адреса. Сейчас её занимает ПЗУ (адреса 0x00-0x3f) и тумблеры для ввода данных (адреса 0x80-0x8f). Так как мы уже определились, что выводить на телетайп будем по 4 бита, можно их брать прямо с шины адреса, заняв адреса 0x90-0x9f. Но система команд компьютера не очень приспособлена к такому. Если в регистре хранится число, надо к нему прибавить 0x90 для получения адреса. А для этого потребуется целых две инструкции. Выходит, что проще передавать символ через шину данных. Но адреса для телетайпа я всё равно занял все, 0x90-0x9f, чтобы упростить дешифратор. Для вывода символа достаточно всего двух команд:

    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 программа может состоять из 105 шагов, у моего компьютера из 64.

• Но чтобы загрузить в регистр двузначное число, МК-52 тратит сразу две ячейки памяти программ.

• Работать регистрами напрямую нельзя, сначала значения из них надо загрузить в стек. А потом результат записать из стека обратно в регистр. То есть в калькуляторе для имитации инструкции типа "ADD B, A, D" нужно потратить четыре команды. Конечно, если правильно организовать порядок вычислений, можно немного сэкономить.

• Битовых иннструкций нет. Например, проверка числа x на чётность делается с помощью "cos(pi * x) > 0" вместо "x & 1 == 0". Не сильно сложнее, но выглядит, как чёрная магия.

• Зато все числа вещественные. Можно играть в знаменитую "Посадку на Луну".

• Ну и для вывода числа в десятичном виде не нужно преобразовывать его в набор цифр вручную.

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

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

Правда очень скоро выяснилось, что программа эта неправильная. А правильная напечатана в самом конце, на форзаце:

Как это часто бывало в книгах и журналах 80х, для программы никакого объяснения не приводится, только дамп. Удивительно, как читателям удавалось их отлаживать и дорабатывать. Поэтому я первым делом загрузил дамп в IDA Pro перевёл программу на Си. Потом немного рефакторинга, поиска логики, и получается небольшая игра.

#include <stdio.h>
#include <stdlib.h>

int player_move, move;

void print(int x)
{
    printf("%dn", 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. Но переполнения буфера и выполнения произвольного кода, к сожалению, не получается.

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

1. Клетку "левее", то есть с номером на единицу меньше (или ближайшую против хода часовой стрелки).

2. Клетку "напротив" с номером на 4 меньше (то есть противоположную по периметру).

Конечно же при этом ещё учитывается переход через ноль. Весь алгоритм можно разбить на такие шаги:

1. Делаем ход в центр.

2. Человек делает ход A.

3. Делаем ход в соседнюю от хода игрока клетку (A - 1).

4. Человек делает второй ход B. Если он не заблокировал линию, которую образуют два крестика программы (A - 1 - 4), то она делает победный ход туда и завершается.

5. Если предыдущий наш ход (A - 1) был в угол, то можно выиграть

   • Ставим крестик левее (A - 1 - 1), получается вилка.

   • Человек делает ход.

   • Если этот ход не блокирует линию с нашим последним ходом, то делаем победный ход туда.

   • В противном случае, ход игрока не заблокировал линию с предпоследним ходом, поэтому делаем последний ход туда.

6. Если предыдущий наш ход был не в угол, то получится только ничья

   • Программа делает ход в клетку (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

Набираем программу с помощью кучи переключателей, стараясь не ошибиться. Теперь можно играть:

Заключение

Оказывается, даже в такой простой игре можно найти для себя что-то новое. Например, существенно упростить алгоритм, пронумеровав клетки поля по кругу, а не слева направо. Если алгоритм с массивом не влезал в память совсем, то этот занимает меньше, чем три четверти объёма. А оставшееся место теперь можно использовать, чтобы проверять корректность ходов игрока.