К вопросу о Вирте и цепочках

Алгоритмы + структуры данных = программы — Вирт Н.

«Нам представилась замечательная возможность провести небольшое, но крайне поучительное тактическое занятие»

Несмотря на первый эпиграф к данному посту, я позволю себе не согласится с автором и постараюсь показать, что в ряде случаев правильный выбор структуры данных может оказаться более значимым, нежели правильный выбор алгоритмов. Для иллюстрации подобного крамольного тезиса рассмотрим несложную, но многообещающую задачу по исследованию игры «Цепочка».

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

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

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

Для некоторых из Н ответ очевиден — при одном объекте первый выигрывает в один ход в прямую игру и проигрывает тоже в один ход в инверсную (П1=1, И1=-1). При двух объектах первый игрок проигрывает в два хода в прямую игру и выигрывает в два хода в инверсную (П2=-2, И2=2), что может породить гипотезу о простоте оценки данной игры, что подтверждается случаем трех объектов (П3=3, И3=-3). К счастью (иначе этот пост не был бы опубликован) игра с четырьмя объектами несколько изменяет картину (П4=-4, но И4=-3), так что исследование игры действительно требуется.

Для некоторых из Н и для определенного вида игры существуют эвристические алгоритмы, которые дают гарантированный выигрыш. Например, для прямой игры при нечетном начальном Н можно гарантированно выиграть, если первым ходом убрать центральный объект и затем повторять ходы противника, используя центральное место, как ось симметрии, тогда мы гарантированно забираем последний объект и выигрываем. Такая же стратегия срабатывала бы и при четном числе объектов, если бы не ограничения на первый ход, что делает игру не столь тривиальной. Вообще говоря, использование симметричных стратегий — довольно таки частое явление в счетных игра, но не панацея, поскольку, например, в нашей инверсной игре эта стратегия пасует. Следует отметить, что эвристики дают алгоритм выигрыша но не дают точную оценку позиции, поскольку могут существовать стратегии, приводящие к выигрышу быстрее (для данной конкретной игры так и есть).

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

Значит, мы должны построить полное дерево игры, но, прежде чем приступить к построению, мы должны создать модель изучаемого объекта, в нашем случае игры.

Почему я заостряю на этом этапе внимание — потому, что мы не можем исследовать объект в его материальном воплощении. Нет, чисто теоретически это возможно («в мире вообще мало что невозможно чисто теоретически») и я вполне могу себе представить картину, где весьма большое количество роботов играют в реальном мире множество партий, но материальные затраты на подобное решение задачи оценки игры превосходят разумно представимые величины, поэтому мы вынуждены вступить на путь моделирования реальных объектов их программными аналогами. И здесь очень важно пройти по тонкой грани, сочетающей достаточный уровень адекватности модели и необходимое упрощение.

Но сначала немного математики, чтобы оценить сложность задачи — нам необходимо перебрать все возможные ходы в игре (внимание — не все возможные позиции, это тема другого метода, а именно ходы) и хотелось бы до начала работы оценить требуемый объем ресурсов — определить порядок задачи. На первом ходу мы имеем возможность убрать любую фишку (я так дальше буду называть объекты) из Н имеющихся, на следующем ходу — любую из оставшихся Н-1 либо две рядом лежащие фишки (таких пар будет не более, чем Н-2), что дает общее количество вариантов Нх(Н-1+Н-2). Легко видеть, что после третьего хода мы имеем Нх(Н-1+Н-2)х(Н-2+Н-3+Δ) и так далее.

Если мы ограничимся в каждой скобке только первыми членами суммы, то получим оценку общего количества ходов, как Н!, что дает нам оценку в квадратурах Н^Н.

Это очень неприятный результат, который утверждает, что мы будем иметь очень большие проблемы при значительных Н, так что скорее всего моделирование «в лоб» повлечет за собой значительный вычислительные затраты. Например, для 16 фишек в исходной позиции мы должны будем рассмотреть приблизительно 16!=10Е13 ходов, и если выполнение одного хода составит 10Е-9 секунды (довольно таки оптимистичная оценка), то общее время составит порядка 10Е4 секунд или почти 3 часа, что многовато, но приемлемо, но уже для всего лишь 20 фишек ожидаемое время расчета составит 77 лет, что явно неприемлемо. Факториал растет очень быстро и с этим ничего не поделать.

Обратим внимание на то, что количество ходов существенно превосходит количество возможных позиций, которое составляет всего лишь 2^Н, и очевидно, что в отдельную позицию мы для 16 фишек попадем 10Е(13-5)=10Е7 раз, что довольно таки обыденное явление для переборных задач. Запомним этот факт, он нам пригодится позднее.

Тем не менее, приступим к написанию программы, для чего определимся с моделью. Для начала пронумеруем фишки от 1 до Н, затем создадим массив с количеством элементов Н, и определим, что число 1 в элементе массива с индексом н означает наличие фишки номер н, а число 0 — ее отсутствие в конкретной позиции. Такая модель адекватна, проста, наглядна, и позволяет сделать эффективными операции убирания фишки, а также определение условия «рядом расположенности».

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

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

1. нейтральная оценка меняется на новую,
2. положительная оценка меняется на меньшую положительную,
3. отрицательная оценка меняется на большую отрицательную либо на положительную.

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

Добавляем оценки в нашу процедуру генерации всех позиций и мы можем полюбоваться на результаты анализа, которые выводим в виде таблицы, добавим еще счетчик ходов и измеритель времени, затраченного на анализ. У меня на компиляторе gcc (в режиме оптимизации -О2) на машине с процессором получилась вот такая таблица, которая полностью подтверждает наши первоначальные предположения о факториальном порядке сложности задачи. Из этой же таблицы мы видим, что я прекратил ожидать результаты при Н, превосходящем 11, поскольку время вычислений стало неприемлемым (для меня, возможны, Вы готовы ждать пол-часа) и наше предположение о ходе а наносекунду никак не соответствует действительности (среднее время рассмотрения позиции составляет 100 нсек). Возникает вопрос — а что же нам делать, если мы хотим иметь оценку для бОльших, нежели 11, фишек в начальной позиции.

Мы могли бы встать на путь небольших оптимизаций, поиграть с переходами и флагами, уйти в ассемблерные вставки, применить хитрые векторные операции из системы команд нашего процессора и на этом пути можно выиграть по быстродействию в разы однозначно, на порядок — быть может, на два порядка — весьма маловероятно, а нам требуется выигрыш на много порядков, поскольку порядок (и даже больше) у нас съест увеличение Н на единицу свыше 10. Кстати, если просто включить оптимизацию компилятора, то он кое-что сделает за нас и время выполнения уменьшается в 4 раза — совсем неплохо и соответствует нашим ожиданиям.

Поэтому мы должны сначала попытаться улучшить применяемые алгоритмы, и первое из этих (и основное) улучшение — метод перебора с отсечением или «альфа-бета процедура». Ее основная идея выглядит вполне здраво и состоит в том, что если мы оценили некоторую позицию, как выигрышную, мы прекращаем улучшать оценку для данной и возвращаемся по дереву назад. Такой подход может очень сильно увеличить скорость работы алгоритма, особенно, если мы будем исследовать удачные ходы (ведущие к выигрышу) в первую очередь. Но может и увеличить время, поскольку добавляется проверка текущей оценки и усложняется процедура выбора хода, оценить заранее влияние данного метода очень трудно, надо проводить эксперимент. И еще одно соображение — мы не должны забывать, что в случае перебора с отсечением мы в случае выирышной позиции даем оценку верную, но не точную, поскольку часть вариантов не рассматриваем, а они могли бы дать выигрыш в меньшее количество ходов. Если нас такое снижение точности устраивает, то почему бы и не применять данный метод, но для точной оценки ничего, кроме полного перебора, не работает.

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

Обратим внимание на то, что принятая нами структура данных делает фишки уникальными и, например, одинокая (не имеющая рядом расположенных) фишка в позиции не эквивалентна одинокой фишке в позиции н+2, что совершенно неправильно. Выделяем ключевой элемент игровой позиции — группа рядом расположенных фишек и определяем ее основную характеристику — количество фишек в группе. Именно эта информация и определяет однозначно любое положение в игре и мы должны представить ее в удобном для программирования виде. Выберем простейшую и совершенно очевидную структуру данных — заводим массив на Н элементов и в н элементе массива храним количество групп с ровно н фишками в ней. Тогда, например. длы начальной позиции с 3 фишками мы будем иметь представление {0,0,1}. Процедура выполнения хода при данном представлении по прежнему проста и эффективна, хотя, конечно, сложнее, нежели в первом варианте. После первого хода (которых стало два вместо трех) мы получаем позиции {0,1,0} и {2,0,0}.

Попытаемся оценить ожидаемый выигрыш в количестве ходов при данной структуре данных. Для первого хода мы имеем (Н-1)/2+1 вариантов, для второго (мы разбили группу Н на м и Н-м-1) (м-1)/2+(Н-м-1-1)/2 (берем 1 фишку) +(м-2)/2+(Н-м-1-2)/2 (берем 2 фишки) = (Н-3)/2+ (Н-5)/2 и по аналогии, мы приходим к выводу, что на каждом шаге мы экономим минимум половину ходов. Тогда наш выигрыш должен составить минимум 2^Н, что для больших Н весьма и весьма неплохо. На самом деле выигрыш будет еще больше, например для позиции {8,0...} в первом варианте надо перебрать 8 ходов, а во втором всего 1 и выигрыш в данном случае составит 8 раз. Так что на 2^Н мы можем твердо рассчитывать, но ожидать намного больше, что и проверим. И точно, для программы по такому представлению мы получаем таблицу 4, в последней строке показан прирост производительности при переходе на второй вариант структуры данных (расчитаный руками). Прирост просто колоссальный и мы уверено (достигли дна) пробили потолок возможности анализа до 20 фишек в исходной позиции при разумных временных затратах.

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

Обратим внимание на полученные результаты и увидим некоторые не очевидные вещи. Например, программа утверждает, что гарантированный выигрыш в прямую игру для 9 фишек достигается вовсе не за 9 ходов, как следует из эвристического симметричного алгоритма, а всего лишь за 7, причем первый ход совпадает с эвристическим (и более того, является единственным выигрышным в позиции), а вот третий и последующие вовсе не должен повторять ходы противника, как следовало из наивного алгоритма, и ключевой здесь является позиция {1,0,0,1}, имеющая оценку +4. Теперь, когда мы дали точную оценку игры, мы можем задавать интересные вопросы относительно наличия позиций с устойчивой оценкой (в которых мы можем позволить ходить за себя противнику), наличия в дереве перебора ключевых позиций, находить позиции с единственным правильным ходом и так далее (и даже получать на эти вопросы ответы, причем верные).

Вот итоговая таблица оценок

Фишки	Прямая	Обратная	Позиции/время	Позиции/время
1	1	-1	1 / 0	1 / 0
2	-2	2	4 / 0	2 / 0
3	3	-3	17 / 0	7 / 0
4	-4	-3	82 / 0	20 / 0
5	5	4	463 / 0	71 / 0
6	5	-5	3032 / 0	263 / 0
7	7	6	22693 / 0	1107 / 0
8	-8	-7	191422 / 0	4945 / 0
9	7	-7	1798427 / 0.1	24283 / 0
10	9	8	18634228 / 0.8	125419 / 0
11	11	-9	211177537 / 10.4	699165 / 0.1
12	-10	-9	*** / 127	4057686 / 0.6
13	11	10		25056975 / 3.84
14	-12	-11		160643971 / 28
15	13	12		1082854607 / 213
16	-14	-13		*** / 1698

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

Алгоритм перебора сверху вниз мы довели до совершенства (ну, конечно, в том страшненьком виде, который я набросал на обратной стороне конверта, не довели, Вы можете существенно улучшить быстродействие, аккуратно переписав основные процедуры, и это обязательно над сделать, но кардинально проблему не решает), значит пойдем другим путем — снизу вверх. Идея этого метода интуитивно проста и понятна, но весьма сложна для применения человеком — мы начинаем с финальной позиции, оценка которой дается по правилам игры, и начинаем переносить оценку вверх по дереву по тем же правилам, как и для перебора сверху вниз. Разумеется, при этом мы рассматриваем не возможные ходы вниз из текущей позиции, а рассматриваем все позиции, из которых мы могли попасть в текущую за один ход. Оценку переносим по приведенным ранее правилам. Далее эту процедуру мы применяем итеративно и когда она перестает приносить результаты, то есть на очередном раунде ни одна позиция не поменяла оценку, задача завершена и оценка исходной позиции правильна и точна. Такой подход позволяет очень сильно сократить время перебора, особенно, если сделать некоторые улучшения, но у него есть сильный недостаток (и это классика — мы меняем время на память), существенно ограничивающий область его применения — высокие требования к памяти, поскольку мы должны хранить оценки для всех возможных позиций одновременно, так что ограничение составляет доступный нам объем оперативной памяти (с учетом нашего умения экономить ее). В случае рассматриваемой игры напрашивается метод битового представления для первой структуры данных, существуют другие методы, позволяющий сократить объем требуемой памяти (хранения только трех рассматриваемых уровня дерева с исключением нижнего слоя), но, естественно, путем ухудшения быстродействия, поскольку поиск становится весьма нетривиальным. Тем не менее, для Н не большего, чем 20, общее количество позиций составит не более 2^20, а массив такого размера в памяти для элементов, вмещающих число от -20 до 20, то есть 8-разрядное число, я вполне способ представить и реализация его не будет сложной. Так что вполне можно написать программу для такого алгоритма и оценить получающееся быстродействие, но не будем торопиться и сделаем оценки. Какую память нам придется выделить, определить несложно, а вот с временными параметра несколько сложнее. Предположим, что мы сразу создадим все возможные позиции, их будем М, тогда среднее количество ходов из одной позиции можно оценить, как не более, чем 2*Н (очень грубая оценка). Тогда на каждой итерации нам потребуется выполнить не более М*2*Н переносов оценки, и, поскольку в каждом цикле мы улучшим оценку как минимум одной позиции, то общее время работы будет иметь порядок М*2*Н*М.

Тогда для первого способа представления данных получаем 2^Н*М*2^Н=2^(2*Н)*М (еще раз подчеркнем, что это оценка очень сильно сверху) и, например, для Н=20 оценка времени перебора сверху-вниз составит 20!~10Е18, а для перебора снизу-вверх имеем 2^40*20=(2^10)^4*40=(10^3)^4*40~10^14, то есть для 20 фишек мы выигрываем во времени по крайней мере в 10Е6 раз, что очень хорошо. Посчитаем также для 9 начальных фишек, получая для перебора сверху 9!~10Е6, а для перебора снизу 2^9*2^9*18~10Е6, то есть начиная с этой цифры перебор снизу побеждает. Последнее утверждение несколько поспешно, поскольку процедура оценки очередной позиции стала существенно длительнее — нам придется искать ее среди уже сгенерированнных, но для данного конкретного представления в виде битового массива эта процедура выполняется за О(1).

Для второго представления необходимо оценить количество различных позиций, что представляет собой задачу из области комбинаторики. В качестве примера можно рассмотреть игру с 9 начальными фишками, для которой общее количество различных позиций составит: 1+(1+4)+(1+3+2)+(1+3+3+2)+(1+2+2+1+1)+(1+2+1+1)+(1+1+1)+(1+1)+1=1+5+6+9+7+5+3+2+1=39.
Тогда оценка по той же методике приведет к значению Н*М*М=39*39*9~10Е4, что на два порядка лучше по быстродействию по сравнению с первым представлением, а по мере роста Н выигрыш будет только увеличиваться. По сравнению с перебором сверху для второго представления следует также ожидать существенного улучшения быстродействия, но оценить его труднее, так что проще попробовать.

Поэтому, если и делать программу разбора снизу-вверх, то для второго представления. Программу приводить не буду, нужно же что то оставить для домашнего анализа читателями. Мы должны получить результаты для значительных Н за вполне приемлемое время. Еще одно преимущество перебора снизу — мы можем существенно сэкономить за счет фиксации оценки для нижней половины позиций (которая имеет количество фишек меньшее, нежели Н/2), поскольку однажды оцененная нижняя половина переносится без изменений для следующего количества фишек, что даст нам дополнительный выигрыш в 2 раза.

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

Ну и в заключение необходимое пояснение для тех, кто принял мой пост слишком серьезно и горит (справедливым) негодованием — я совершенно не уверен, что указание алгоритмов в качестве первого слагаемого в формуле определения программы утверждает их бОльшую значимость, я совершенно согласен с тем, что в некоторых конкретных ситуациях правильно выбраный алгоритм может дать порядковый рост производительности, и я вовсе не собирался уличать Дейкстру (к которому отношусь с уважением) в ошибках. Это все было фразой для привлечения внимания, а пост совсем о другом — что структура данных также бывает необычайно важна с точки зрения производительности и хотелось, чтобы об этом не забывали в процессе проектирования.

PS. Мне тут подсказывают из зала (привет, Макс), что существует еще один метод исследования игры — математический, и, учитывая гипотезу с двойной фамилией о том, что большинство счетных игр сводится к игре Ним, так что потребуется нам потребуется только вычислить ним-сумму исходной позиции (на мой взгляд, утверждение сомнительное), а также можно еще преобразовать исходную игру к играм на графе (вот тут возражений нет), для которой можно ожидать оценки 1.878^Н по времени работы (хотя конкретное число меня несколько озадачило). Наверное, эти соображения имеют право на жизнь, по крайней мере, статьи данного содержания выглядят убедительно, но я сугубый практик и данные варианты оставляю опять таки для пытливых читателей (ars longa, vita brevis).