vector<bool> buf ;

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

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

Плотная упаковка

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

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

Да, но если вы захотите использовать это представление в коде, вам потребуется специальный битовый контейнер вроде BitBuffer. Например, имеется три способа.

Достичь упаковки полухода в 10 битов достаточно просто. Нам достаточно указать, какая именно фигура (а для каждого полухода их не более 16) и в какую клетку (которых на доске 64) ходит. Цвет фигуры определяется номером полухода. Перенумеровав фигуры (например, в порядке их размещения по горизонталям, а в пределах горизонтали - по вертикалям) и клетки доски, мы получаем, что для указания фигуры нам надо 4 бита, а для указания клетки, в которую она ходит, - 6 битов; итого достаточно 10 битов, чтобы однозначно определить полуход.

Можно ли улучшить этот результат? Судите сами: мы можем закодировать все клетки доски в качестве целевых клеток полухода, в то время как правила игры позволяют быть таковыми только малому количеству клеток. Таким образом, в нашем представлении явно имеется избыгочность. Аналогично, наше представление позволяет записать ход любой фигуры в заданную клетку, в то время как такой ход могут сделать далеко не все фигуры, причем некоторые фигуры в принципе не могут попасть в некоторые клетки. Так что, например, можно использовать для кодирования клетки 6 битов, а затем выяснить, какие фигуры могут пойти в данную клетку, и использовать от О до 4 битов для указания одной из них. Если таких фигур мало, нам не потребуются все 4 бита. При декодировании из анализа текущей позиции мы знаем, какое количество фигур может попасть в целевую клетку, а значит, нам известно, сколько именно битов из входного потока требуется запросить, чтобы декодировать полуход.

Мы можем закодировать полуход с использованием не менее О и не более 8 битов следующим образом: сначала надо разработать способ упорядочения разрешенных шагов; например, мы можем упорядочить фигуры описанным выше способом, в соответствии с занимаемыми ими позициями, а для каждой фигуры - упорядочить возможные ходы с использованием того же принципа, что и для фигур. Затем номер фактического хода записывается с использованием минимально необходимого количества битов. Например, начальная позиция имеет 20 возможных ходов; для представления их в бинарном виде требуется ceil(log2(20)) = 5 битов.

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

то в требуется в наихудшем случае? Этот вопрос непосредственно связан с вопросом о том, каково максимальное количество различных ходов может быть сделано в корректной шахматной позиции? Насколько мне известно, текущий известный максимум - 218 ходов в следующей позиции:

- - - Q - - - 3Q4

-Q----Q - 1Q4Q1

- - - Q - -- - 4Q3 --Q----R 2q4r Q----Q- - Q4Q2

- - Q - - - - 3Q4 -Q----RP 1Q4RP -K-BBNNk iKlBBNNk

В этом наихудшем случае для кодирования хода в виде обычного двоичного числа достаточно 8 битов. В среднем, по-видимому, 5 битов будет достаточно для того, чтобы хранить типичный ход. Начальная позиция имеет 20 возможных ходов; типичный эндшпиль, например, король, ладья и две пешки на пустой доске, имеет около 30 допустимых ходов - что также приводит к 5 битам при использовании описанного метода.

Если задуматься, то становится понятным, что описанный метод близок к оптимальному, поскольку он представляет точный и непосредственный ответ на вопрос: Какой разрешенный ход был сделан? Мы используем минимальное количество битов для представления всех возможных ходов в виде двоичного числа, располагая полной информацией о том, что происходило до этого хода.

Можно ли улучшить и этот результат? Да, но теперь результаты будут не столь впечатляющими, так как нам потребуются новые знания о шахматах, а речь идет об экономии долей битов. Для того чтобы проиллюстрировать возможность улучшения достигнутых нами результатов, обратимся еще раз к начальной позиции. В ней имеется 20 возможных ходов, что в нашей схеме требует ceiling(!og2(20)) = 5 битов. Теоретически же в этой ситуации имеется только log2(20) = 4.3 битов информации, если считать все ходы равновероятными, так что в среднем нам должно хватить еще меньшего количества битов, если вспомнить о том, что большая часть всех партий начинается с одного из двух популярных ходов белых. Короче говоря, если мы располагаем дополнительной информацией об относительных вероятностях каждого хода (например, встраивая в механизм сжатия детерминистскую шахматную программу, которая может предположить, какие ходы в любой заданной позиции будут наиболее вероятны), то мы можем использовать кодирование с переменной длиной, такое как код Хаффмана или арифметическое сжатие, чтобы использовать меньшее количество битов для хранения более вероятных ходов. Цена такой высокой степени сжатия информации - повышенное время вычислений, использующих знания о предметной области.

Резюме

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

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

> Рекомендация

Оптимизация должна опираться на точные знания о том, что вы должны оптимизировать, и как вы должны это делать. Знания предметной области ничем невозможно заменить.

Ловушки, ошибки и головоломки

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

Почему С+ + , как и большинство других языков программирования, резервирует ключевые слова, так что вы не можете, например, использовать переменную с именем class? Почему строка кода, которая выглядит, как вполне правильная, выполняющая определенную работу, в результате не приводит ни к одной команде процессора, как будто она никогда и не существовала? И почему, казалось бы, вовсе некорректный текст нормально компилируется и работает? Почему при работе с числами с плаваю щей точкой желательно пользоваться double?

И наконец - мы когда-нибудь сможем разобраться с макросами?..