Динамо-машины  Метод Сократа 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 [ 59 ] 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90

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

q, R, -в , n, Р или . .

Используя эту схему и сохраняя доску по горизонталям от 1 до 8, и по вертикалям от я до А в пределах каждой горизонтали, возможное представление полухода может быть таким:

WRWNWBWQWKWBWNWR wpwpwp..WPWPWPWP

......WP........

ВРВРВРВРВРВРВРВР

brbnbbbqbkbbbnbr

.Здесь представлен полуход 1. d4 , с которого я обычно начинаю партию.

б) 32 байта на полуход

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

Мы можем снизить количество необходимой памяти до 32 байт на полуход, храня всего лишь 4 бита информации для каждой клетки: 3 бита для указания фигуры (например, представление О для короля, 1 для ферзя, 2 для ладьи, 3 для слона, 4 для коня, 5 для пешки и 6 - для пустой клетки требуется 3 бита, при этом одно значение остается неиспользованным), и 1 бит для цвета (значение этого бита игнорируется для пустой клетки).

При использовании такой схемы для сохранения всей доски как и ранее, по горизонталям от 1 до 8, и по вертикалям от а до А в пределах каждой горизонтали, требуется всего лишь 32 байта:

хххххххххххххххххххххххххххххххх

в) от 4 до 8 байтов на полуход

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

Старая описательная запись шахматной партии идентифицирует клетки с использованием дескрипторов переменной длины, наподобие КЗ или QN8 вместо двух-символьных дескрипторов вроде еЗ или Ь8. Для записи полухода при этом требуется как минимум 4 символа (например, P-Q4) и не более 8 символов (например, RKN1 -КВ1, Р-КВ8(0)). Заметим, что никакие завершающие нули или другие ограничители строк не требуются, поскольку записанные таким образом ходы дешифруются однозначно.

При этой схеме запись полухода может выглядеть как p-kb8(q)

г) от 2 до 4 байтов на полуход

Это достигается путем хранения полуходов как текста в современной записи шахматных партий.

Современная алгебраическая запись более компактна, и любой полуход можно записать с использованием от 2 символов (например, d4) до 4 символов (например.

Rgfl, gh=Q). В этом случае, также не нужны никакие разделители в силу однозначности декодирования.

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

gh=Q

д) 12 битов на полуход

Еще более компактную запись можно получить, применив иной подход. Полуход однозначно определяется исходной клеткой и клеткой назначения. Поскольку всего клеток 64, для представления одной клетки достаточно 6 битов, так что всею для записи полухода требуется 12 битов. Этого достаточно для обычных ходов; однако для записи рокировки потребуется большее количество памяти.

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

Кстати, основное достоинство такого представления вне компьютерного мира в том, что такая запись может быть легко выполнена на бумаге человеком, даже в условиях цейтнота. Оказывается, уменьшение длины записи от максимум 8 символов до максимум 4 вместе с определенной концептуальной простотой Ифает большую роль для пользователей (которых в шахматном мире называют игроками :)).

Задача 27. Форматы данных

и эффективность. Часть 2: игры с битами Сложность: 8

Пришло время рассмотреть более компактные и эффективно использующие память структуры данных, и поработать с кодом, оперирующим на битовом уровне.

Вопрос для профессионала

1. Для реализации решения д) второго вопроса задачи 26 вы решили создать класс, управляющий буфером битов. Реализуйте его максимально переносимо, с тем чтобы он корректно работал на любом компиляторе, соответствующем стандарту С+ + , независимо от платформы.

class BitBuffer { public:

... добавьте при необходимости другие функции... добавляет num битов, начиная с первого бита р. void Append С unsigned char* р, size t num ); Запрос количества используемых битов (изначально 0). si2e t size О const;

получает num битов, начиная с start-oro бита, и сохраняет результат, начиная с первого бита dst.

void Get(size t start, size t num, unsigned char* dst)

const;

private:

...дополнительные детали...

2. Нельзя ли хранить партию в шахматы с использованием менее чем 12 битов на полуход? Если можно - покажите, как. Если нет - поясните, почему.

Решение

BitBuffer, убийца битов

1. Для реализации решения д) второго вопроса задачи 26 вы решили создать класс, управляющий буфером битов. Реализуйте его максимально переносимо, с тем чтобы он корректно работал на любом компиляторе, соответствующем стандарту С++, независимо от платформы.

Для начала обратите внимание, что здесь нет упоминания о том, что байт состоит из 8 битов, которое было в предыдущей задаче - здесь это условие попросту неприменимо. Нам нужно решение, компилирующееся и корректно работающее в любой реализации С++, соответствующей стандарту, независимо от того, на какой платформе она работает.

Требуемый условием задачи интерфейс выглядит следующим образом.

class BitBuffer {

public:

void Append( unsigned char* p, size t num ); size t Size() const;

void Get(size t start, size t num, unsigned char* dst)

const;

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 [ 59 ] 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90