Тест 8 ферзей на МК-61: другие подходы

| рубрика «Испытания» | автор st
Метки:

Программы-победители конкурса поиска расстановок 8 ферзей на шахматной доске были опубликованы в журнале "НиЖ" №10 за 1988 год. Время счета измерялось часами, потребовались оптимизация перебора: получение 12 базовых расстановок и 80 производных от них. Тем не менее, общее время выполнения оставалось значительным.

Конкурс также был ограничен моделями второго поколения Б3-34, МК-54 и МК-56. Может показаться странным, но реализации на старых моделях -- более эффективные за счет разорванной в МК-61 связи между регистрами 0 и Е: цикл по П0 совмещался с операциями с "массивом" по КПЕ/КИПЕ, не уменьшавших значение регистра 0.

Тест производительности не требует поиска всех расстановок, достаточно найти первую. Приведенная по ссылке программа Ильи Васильева (AtH) выполняется на "железной" реплике МК-61 mini за 402 секунды (6 мин 42 сек). Замеры выполнил Алексей Сугоняев, подробнее в разделе "Спортивное программирование" в нашей телеграм-группе.

По сравнению с 8-9 секундами выполнения на МК-152, МК61 mini, использующий полный эмулятор, примерно в 40-50 раз медленнее, хотя и в 20 раз быстрее оригинала.

Есть ли другие подходы?

Подход с использованием битовых масок

Хотя реализация 8х8 на МК-61 может быть медленнее, чем простой перебор, данный алгоритм растет как n^2, а не n^3: требуются два вложенных цикла, а не три.

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

В отличие от Б3-34, МК-61 обладает логическими операциями, весьма странно реализованными: старший разряд не используется, после него алгоритм устанавливает десятичную точку, операции проводятся поразрядно над дробной частью. То есть в нашем распоряжении только 7 разрядов по 4 бита.

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

  • маска горизонталей
  • маска диагоналей

Маска вертикалей нас не интересует, ферзи устанавливаются на вертикали 1-8 последовательно, не пересекаясь.

Вычисление маски для горизонталей (координата y):

M(y) = int( 10^(y − 2) + 2 / y^2 ) + 10000000

Вычисление маски для горизонталей (координаты поля x,y):

M(x, y) = int(A + 2B) + 10000000, где

  • A = 10^a + 8 * 10^(−a),
  • B = 10^b + 2 * 10^(−b).
  • a = x − y
  • b = x + y − 9

Операция int() соответствует отбрасыванию дробной части на ПМК. Константа 10000000 требуется для перевода 7-разрядной маски в пригодный для логических операций вид.

Выражения, переведенные на язык стековой машины с набором операций МК-61, выглядят следующим образом:

-- Маска горизонтали
y 2 − 10^x 2 y x^2 / + int 10000000 +
-- Маска диагоналей
x y − 10^x dup 1/x 8 * +
x y + 9 − 10^x dup 1/x 2 * + 2 *
+ int 10000000 +

Выражения для преобразования координат поля в битовые маски подбирались с помощью БЯМ (LLM) Sonet 5.5, доступной пока бесплатно.

Как видно, даже оптимизированные выражения со стековыми операциями занимают в сумме 38 команд (12 и 26) без учета возвратов. Для основной программы остается не так уж много, 66 шагов, так что техническая оптимизация будет неизбежна.

Алгоритм на Си-подобном языке выглядит так:

int main()
{
    int x, y, a[9] = {};
    x = 8;
    do {
        int mask_lines = 0;
        int mask_diags = 0;
        for (y = 8; y > x; y--) {
            mask_lines |= make_mask_lines(y, a[y]);
            mask_diags |= make_mask_diags(y, a[y]);
        }
        if (a[x] == 0)
            a[x] = 8;
        int intersect = 0;
        for (y = a[x]; y > 0; y--) {
            a[x] = y;
            intersect = (mask_lines & make_mask_lines(x, a[x])) |
                        (mask_diags & make_mask_diags(x, a[x]));
            if (intersect == 0)
                break;
        }
        if (intersect != 0) {
            // расстановка не найдена, возврат к предыдущей вертикали
            a[x] = 0;
            do {
                x++;
            } while (--a[x] == 0);
        }
        else
            x--;
        print_result(a);
    } while (x > 0);
    print_result(a);
}

Ожидаемый результат: 8 4 1 3 6 2 7 5

Полученная программа использует все 15 регистров памяти, почти всю программную: 104 шага из 105.

Из очевидных оптимизаций: при возврате (backtrace) не пересчитывать маски для расставленных ферзей, а удалять маску последнего через операции последняя_маска Кинв ИПмаски К/\ Пмаски перед блоком на шаге 59, но потребуются дополнительные шаги для вызова подпрограмм пересчета масок. Поэтому тратится время на полный пересчет при изменении текущей вертикали.

00.ИПD   01.1     02.-    03.ПD   04.Fx=0 05.07   06.С/П 07.8    08.ПB   09.ПC
10.П0    11.ИП0   12.ПE   13.ИПD  14.-    15.Fx#0 16.28  17.KППA 18.ИПB  19.K\/
20.ПB    21.ПП    22.77   23.ИПC  24.K\/  25.ПC   26.FL0 27.11   28.KИПD 29.Fx=0
30.33    31.8     32.KПD  33.ИПD  34.ПE   35.KИПD 36.П0  37.ИП0  38.KПE  39.KППA
40.ИПB   41.K/\   42.K{x} 43.Fx=0 44.51   45.ПП   46.77  47.ИПC  48.K/\  49.K{x}
50.Kx#09 51.FL0   52.37   53.0    54.KПD  55.ИПD  56.1   57.+    58.ПD   59.KИПD
60.1     61.-     62.KПD  63.Fx#0 64.55   65.БП   66.07  67.KИПE 68.2    69.-
70.F10^x 71.2     72.KИПE 73.Fx^2 74.:    75.БП   76.99  77.ИПE  78.KИПE 79.-
80.F10^x 81.В^    82.F1/x 83.8    84.x    85.+    86.ИПE 87.KИПE 88.+    89.9
90.-     91.F10^x 92.В^   93.F1/x 94.2    95.x    96.+   97.2    98.x    99.+
A0.K[x]  A1.ИП9   A2.+    A3.В/О

Заполнение регистров:

  • 7 F10^x П9
  • 67 ПА
  • Сх П1 П2 П3 П4 П5 П6 П7 П8

Запускаем 8 БП 03 С/П

После останова в регистрах 1-8 расстановка ферзей: в i-м регистре (номер вертикали) лежит номер горизонтали: 8 4 1 3 6 2 7 5.

Тестовый пример для быстрого прогона

  • 8 П8 4 П7 1 П6 3 П5 6 П4 2 П3 7 П2 0 П1
  • 1 БП 03 С/П

После останова в регистрах 1-8 расстановка 8 4 1 3 6 2 7 5.

Обсуждение

Обсуждение в группе google