[Из песочницы] Крестики-нолики: компилятор против человека — экстремальный метапрограмминг02.07.2014 12:50

typedef fas: type_list_n< fas::int_<1>, fas: int_<2>, fas: int_<2> >:: type list1; struct list2: list1 {};

template class test {};

int main () { // test tst; test tst; tst.doit (); } В этом варианте компилятор выдаст что-то типа этого: error: «class test, fas: type_list, fas: type_list, fas: empty_list> > > >» has no member named «doit» , а для list2: error: «class test» has no member named «doit» Вы почувствуете разницу, если в списке с десяток или больше элементов. Итак, раскроем тайну, как работает экранирование, на примере определения функции определяющей длину списка. Реализация без учета экранирования: template struct length;

template struct length< type_list > { enum { value = 1 + length:: value }; };

template<> struct length< empty_list > { enum { value = 0 }; }; Если на вход функции length, в этой реализации, придет экранированный список, то получим ошибку на этапе компиляции. Для того, чтобы отличить список типов от прочих конструкций, используем волшебный metatype, определенный в структурах fas: type_list и fas: empty_list, объявив дополнительно: template struct length : length_impl {};

template struct length_impl { typedef typename L: right_type tail; enum { value = 1 + length< tail>:: value }; };

template struct length_impl { enum { value = 0 }; }; Идея в том, что если не сработают специализации length по fas: type_list или fas: empty_list, то будут задействованы специализации на базе типа metatype, который определен во входном параметре. Если он не определен или не является типом fas: metalist: type_list или fas: metalist: empty_list, то получим ошибку компиляции. Если удалить специализации length > и length, то код будет работоспособным, но компилироваться он будет медленнее. Компилятору (в данном случае g++) гораздо проще отработать специализации без «вскрытия» входных типов.Кроме того, все операции умеют проверять входные списки типов на валидность. Эта опция по умолчанию отключена, т.к. она увеличивает время компиляции. Если у вас появится желание поэкспериментировать со списками типов, то рекомендую включить FASLIB_TYPE_LIST_CHECK, для этого достаточно раскомментировать строку в CMakeLists.txt:

#add_definitions (-DFASLIB_TYPE_LIST_CHECK)

Там же можно отключить специализации операций и алгоритмов по type_list, оставив только специализации по метатипу, и оценить эффект в плане времени компиляции:

#add_definitions (-DDISABLE_TYPE_LIST_SPEC)

Далее, в комментариях, при описании списка типов, для краткости, указывать empty_list я не буду. Будем работать только с правильными списками типов.Как работает type_list_n? Слегка упрощенная, но работающая реализация: template< typename T1 = empty_list, typename T2 = empty_list, typename T3 = empty_list, typename T4 = empty_list, typename T5 = empty_list, typename T6 = empty_list, typename T7 = empty_list, typename T8 = empty_list, typename T9 = empty_list, typename T10 = empty_list, typename T11 = empty_list, typename T12 = empty_list, typename T13 = empty_list, typename T14 = empty_list, typename T15 = empty_list, typename T16 = empty_list, typename T17 = empty_list, typename T18 = empty_list, typename T19 = empty_list, typename T20 = empty_list, typename T21 = empty_list, typename T22 = empty_list, typename T23 = empty_list, typename T24 = empty_list, typename T25 = empty_list, typename T26 = empty_list > struct type_list_n { typedef type_list< T1, type_list< T2, type_list< T3, type_list< T4, type_list< T5, type_list< T6, type_list< T7, type_list< T8, type_list< T9, type_list< T10, type_list< T11, type_list< T12, type_list< T13, type_list< T14, type_list< T15, type_list< T16, type_list< T17, type_list< T18, type_list< T19, type_list< T20, type_list< T21, type_list< T22, type_list< T23, type_list< T24, type_list< T25, type_list< T26 > > > > > > > > > > > > > > > > > > > > > > > > > > bar; typedef typename organize:: type type; }; Формируем список типов из всех 26 шаблонных параметров, в голове списка будут явно заданные параметры, а хвост списка будет состоять из множества fas: empty_list — это неправильный список типов в контексте faslib. Операция fas: organize удаляет лишние fas: empty_list и в результате получаем список типов из нужного количества элементов.Вариант для с++11:

template struct type_list_n { typedef typename fas: organize< fas::type_list< Head, typename type_list_n:: type > >:: type type; };

template<> struct type_list_n<> { typedef fas: empty_list type; }; Также упрощенная реализация — fas: organize применяется к списку на каждом этапе его формирования. По-хорошему, сначала нужно создать список и потом один раз его организовать. Здесь fas: organize нужен для того, чтобы была возможность передавать списки типов в параметрах fas: type_list_n. Операции над списками типов Для манипуляций со списками типов есть набор операций, которые помимо списка типов L, могут принимать тип T и индекс I — интегральный тип. Для операций с индексом есть альтернатива с суффиксом _c, в котором индекс задается числом, например: typedef fas: erase< fas::int_<0>, fas: type_list >:: type empty; typedef fas: erase_c< 0, fas::type_list >:: type empty; Список всех доступных операций для списков типов: erase:: typeerase_c:: typeУдаляет элемент в позиции I из списка L head:: typeВозвращает элемент списка L (голова списка) index_of:: valueВозвращает позицию первого вхождения типа T в списке L. Если тип не найден, то -1 length:: valueОпределяет длину списка типов L merge:: typeОбъединяет два списка L1 и L2 в один список organize:: typeПреобразует неправильный список типов L в правильный список. normalize:: typeТо же что organize, но если L не является списком типов, преобразует его в список из одного элемента push_back:: typeДобавляет тип T в конец списка L push_front:: typeДобавляет тип T в начало списка L reverse:: typeМеняет порядок следования элементов списка L на противоположный split:: left_listsplit:: right_listsplit_c:: left_listsplit_c:: right_listРазделяет список L на два списка в позиции I tail:: typeВозвращает хвост списка L (удаляет первый элемент списка) type_at:: typetype_at_c:: typeВозвращает тип в позиции I списка L type_count:: valueКоличество типов T в списке типов L unique:: typeУдаляет все дубликаты элементов в списке типов L, оставляя последнее вхождение unique_first:: typeТо же что и unique, но оставляет первое вхождение элемента В этом списке нет таких очевидных операций, как замена типа в заданной позиции set_at (она нам потребуется для того, чтобы сделать ход) и получения последнего элемента списка типов last. Это связано тем, что рассматриваемые в этой статье пакеты faslib разрабатывались в основном для поддержки пакета fas/aop — основного пакета faslib. А операции типа set_at просто-напросто не потребовались для этого. Ну что-же, исправим это недоразумение.Для получения последнего элемента необходимо вычислить длину списка типов (fas: length) и получить тип в предпоследней позиции (fas: type_at):

template struct last { typedef typename fas: type_at_c< fas::length< L >:: value-1, L >:: type type; }; Операция set_at будет устанавливать тип в заданной позиции списка типов. Также разработаем set_at_с которая принимает в качестве позиции число. Для минимизации времени компиляции эффективней реализовать эту операцию на специализациях, но мы сделаем проще — используем имеющиеся операции. Для этого: Разделяем список типов на два списка (fas: split) Во втором списке отрезаем голову (fas: tail) Добавляем заданный тип в начало обезглавленного списка (fas: push_front) Объединяем левый и правый, модифицированный, списки (fas: merge) template struct set_at_c { typedef fas: split_c splitter; typedef typename splitter: left_list left_list; typedef typename splitter: right_list right_list; typedef typename fas: tail< right_list >:: type headless; typedef typename fas: push_front< T, headless >:: type pollywog; typedef typename fas: merge< left_list, pollywog >:: type type; };

template struct set_at : set_at_c< Pos::value, T, L> { }; Алгоритмы Помимо операций над списками типов, в faslib реализован ряд compile-time алгоритмов, по аналогии с алгоритмами stl. В отличие от операций, алгоритм — это всегда мета-функция (структура, в которой определен тип type — результирующий тип). Многие алгоритмы принимают на вход, помимо списка типов, унарную или бинарную операцию — это шаблонная мета-функция с одним или двумя параметрами. Если алгоритм с условием, то необходим унарный или бинарный предикат (также мета-функция). В качестве предиката могут использоваться операции сравнения интегральных типов, функции из пакета fas/typemanip (например, same_type, super_subclass) или классы stl (например, std: is_base_of, если вы используете c++11).Все алгоритмы, использующие операции и/или предикаты, имеют версию с суффиксом _t, которая принимает операции и предикаты в виде шаблонных-шаблонных параметров, например:

template class F > struct transform_t; которая для каждого элемента списка типов L применяет операцию F, например: typedef fas: type_list_n< fas::int_<1>, fas: int_<2>, fas: int_<3>, fas: int_<4> >:: type lst; typedef fas: transform_t:: type res; // [2,3,4,5] В результате получим список интегральных типов, где каждый элемент списка инкрементирован на единицу. Вариант без суффикса предполагает использование placeholder expressions: template struct transform; Например: typedef fas: transform >:: type res2; Подробнее о плейсхолдерах Плейсхолдеры — это такая штука, которую гораздо проще использовать, чем объяснить, как ее использовать. В общем, все аналогично boost: mpl и c++11, ограничение в том что в faslib их всего пять: _1, _2, _3, _4, _5 и есть еще универсальный _, использование которого проще описать на примерах: Пример Альтернатива foo<_> foo<_1> foo<_,_> foo<_1,_2> foo<_1,_,_2> foo<_1,_1,_2> foo<_1,_,_2,_,_> foo<_1,_1,_2,_2,_3> Иными словами, первый _ в выражении эквивалентен _1, второй — _2 и т.д. Если в выражении используются плейсхолдеры отличные от _, то лучше от последних вообще отказаться, иначе выражение становится сложным для понимания. В то же время в простых вариантах они очень даже удобны.В примере с fas: transform мы использовали функцию fas: inc, для получения интегрального типа увеличенного на единицу. Однако результат этой функции является тип вида fas: integral_c который является семантически эквивалентным fas: int_<4>, но это другой тип. Для преобразования fas: integral_c в fas: int_ можно использовать функцию fas: make_int:

typedef fas: transform< lst, fas::make_int< fas::inc< fas::_ > > >:: type res2; Список доступных алгоритмов: accumulate=plus >Для списка интегральных типов вычисляет сумму значения I и списка L используя операцию F (по умолчанию сложение). Может применяться для любых типов, т.к. для каждого типа T из списка типов L, применяет F, где Pred на первой итерации это начальный тип I, а на последующих результат предыдущего F countОпределяет количество типов T в списке типов L, аналог fas: type_count, но использует fas: count_if и fas: same_type count_if >Определяет количество типов в списке L, удовлетворяющих условию C<_> erase_if >Удаляет все типы из списка L, удовлетворяющих условию C<_> find_if >Находит тип в списке, удовлетворяющий условию C<_> (первое вхождение) for_, F<_> >Рекурсивно применяет F<_> используя начальный тип I, пока выполняется условие C<_> generator< T, F<_> >Генерирует новый тип, используя F generate< N, F >Генерирует список типов длинной N, используя генератор типов F (например, fas: generator) index_of_if >Позиция элемента в списке типов, удовлетворяющего условию C<_> is_sorted=less >Определяет упорядоченность списка типов L, используя бинарный предикат C random_shuffleПсевдо-случайно перемешивает список типов L, используя интегральный тип R в качестве зерна select< L, С<_> >Извлекает типы из списка L, удовлетворяющих условию C<_>. На выходе список типов. shuffle< L, RL>Перемешивает список типов L, используя список интегральных типов RL sort=less >Сортирует список типов L transform >Возвращает список типов элементы которого являются результатом F<_> transform2 >Возвращает список типов, элементы которого являются результатом F<_1,_2>, где _1 и _2 элементы первого и второго списков соответственно transform_if< L, F<_>, C<_> >Возвращает список типов, элементы которого являются результатом F<_>, при условии C<_>. Если условие не выполняется, то тип не изменяется transform_tail >Изменяет хвост списка для каждого элемента (включая сам элемент, в качестве головы списка) используя F<_> transform_tail_if< L, F<_>, C<_> >Изменяет хвост списка для каждого элемента (включая сам элемент, в качестве головы списка) используя F<_>, если для текущего элемента выполняется C<_> unique_if=same_type >Удаляет элементы, удовлетворяющие С<_,_> оставляя последнее вхождение unique_first_if=same_type >Удаляет элементы, удовлетворяющие С<_,_> оставляя первое вхождение Пример использования алгоритма compile-time сортировки: typedef fas: type_list_n< fas::int_<3>, fas: int_<2>, fas: int_<3>, fas: int_<1> >:: type list1; //[3,2,3,1]

typedef fas: sort_t:: type res1; //[1,2,3,3] typedef fas: sort:: type res2; //[1,2,3,3]

typedef fas: sort_t:: type res3; //[3,3,2,1] typedef fas: sort< list1, fas::greater< fas::_1, fas::_2> >:: type res4; //[3,3,2,1] typedef fas: sort< list1, fas::greater< fas::_2, fas::_1> >:: type res5; //[1,2,3,3] Сортировать можно не только интегральные типы. Например, можно отсортировать типы в порядке наследования: struct A{}; struct B: A{}; struct C: B{}; struct D: C{};

typedef fas: type_list_n< C, B, A, A, D >:: type list2;

typedef fas: sort< list2, fas::f< fas::super_subclass< fas::_1, fas::_2> > >:: type res5; // [A, A, B, C, D] Конструкция super_subclass из пакета typemanip не является мета-функцией в контексте алгоритмов faslib, т.к. в ней не определен тип type, а только value, которое принимает значение 1, если первый тип является наследником второго, и ноль в противном случае. А конструкция fas: f исправляет это недоразумение. Если ваш компилятор поддерживает c++11, то в качестве альтернативы fas: super_subclass, вы можете использовать std: is_base_of, в котором определен и type и value. Более того, т.к. преобразований для него не требуется, вы можете передавать его как шаблонный-шаблонный параметр: typedef fas: sort< list2, std::is_base_of< fas::_1, fas::_2> >:: type res5; // [A, A, B, C, D] typedef fas: sort_t:: type res5; // [A, A, B, C, D] Как работает сортировка? Результатом fas: is_sorted будет fas: true_, если для всех соседних элементов выполняется заданный бинарный предикат. Алгоритм fas: sort меняет местами соседние элементы, для которых этот предикат не выполняется, по всему списку до тех пор, пока список не будет отсортирован.Да, сортировка выполняется методом пузырька — одним из самых неэффективных алгоритмов времени выполнения. На сколько неэффективным он является с точки зрения времени компиляции — я эту тему глубоко не исследовал. Поэтому этот алгоритм, а также fas: for_, fas: shuffle и fas: random_shuffle я отношу к разряду экспериментальных, и в реальных проектах стараюсь не использовать. Эти алгоритмы разработаны для оптимизации времени компиляции прочих конструкций faslib.

Еще один пример — реверс списка типов с использованием алгоритма fas: accumulate struct A; struct B; struct C; typedef fas: type_list_n< A, B, C >:: type list4; typedef fas: accumulate< list4, empty_list, push_front<_2, _1> >:: type res4; // [C, B, A] Мы рассмотрели далеко не все возможности faslib, но этих конструкций вполне достаточно, чтобы научить компилятор играть в крестики-нолики.Крестики-нолики. Один ход Сначала определим типы крестиков, ноликов и пустое поле: struct e {}; struct x {}; struct o {}; Подключим уровень доступа и игровую доску, которую генерирует python скрипт: typedef fas: int_< #include "level.inl" > level;

typedef fas: type_list_n< #include "board.inl" >:: type board; Если файлы *.lnl отсутствуют, то система сборки создаст их (см. CMakeLists.txt). По умолчанию это второй уровень сложности и пустая доска. Так же при каждой компиляции система сборки создает файл rand.inl со случайным числом — его мы будем использовать для рандомизации ходов компилятором. Подключаем аналогичным образом: typedef fas: int_< #include "rand.inl" > initial_rand; Пустая доска будет выглядеть так: typedef fas: type_list_n< e, e, e, e, e, e, e, e, e >:: type empty_board; Далее научимся выводить игровую позицию на экран. Вывод конкретной позиции: std: ostream& operator<<(std::ostream& s, e) { s << "-"; }

std: ostream& operator<<(std::ostream& s, o) { s << "O"; }

std: ostream& operator<<(std::ostream& s, x) { s << "X"; } Для наглядности разделим каждую позицию пробелом, а каждую линию с новой строки: template std: ostream& operator<<(std::ostream& s, fas::type_list) { s << L(); // текущая позиция int len = fas::length:: value; // длина хвоста списка if (len%3 == 0) // если длина хвоста кратна трем, то с новой строки s << std::endl; else if (len != 0) // остальные, если не последний элемент, то пробел s << " "; s << R(); // "рекурсивно” выводим хвост списка }

std: ostream& operator<<(std::ostream& s, fas::empty_list) { // Конец списка. Ничего не делаем } Результатом "хода” компилятора будет кортеж из трех типов:Позиция, куда сделан ход. Если позиция равна fas::int_<-1>, значит, ход невозможен (исходная позиция ничейная, либо победа одного из игроков) Фигура победителя. Если победителя нет, то тип e (пустое поле) Доска после хода (список типов). Если ход невозможен, то пустой список Для вывода результата «хода» компилятора следующая специализация: template std: ostream& operator<< ( std::ostream& s, fas::tuple< Pos, Fig, Board>) { s << Board(); // если Board пустой список, то вывода не будет enum { // нет хода nopos = fas::same_type< Pos, fas::int_<-1> >:: value, // нет победителя nofig = fas: same_type< e, Fig>:: value, }; if (nopos) { // Если ход невозможен, то ничья или победа игрока if (nofig) s << "Draw" << std::endl; else s << Fig() << " winner (you)" << std::endl; } else if ( !nofig ) { // Есть ход и победная фигура - компилятор победил s << Fig() << " winner (compiler)" << std::endl; } } При проигрывании партии компилятором без участия человека, результатом будет список кортежей (специализация для конца списка fas::empty_list у нас уже есть ): template std: ostream& operator<<(std::ostream& s ,fas::type_list, Tail>) { s << fas::tuple() << std::endl; s << Tail(); } Ну а теперь самое интересное. Каждый ход будет делать функция game: template struct game; Здесь R — интегральный тип со случайным числом, которое генерирует система сборки, Level — уровень сложности, Board — исходная доска — список типов из девяти элементов (фигур). Результатом игры, как было отмечено выше, кортеж из трех типов: позиция, если ход возможен (-1 в противном случае), фигура победителя (e — если нет), новая доска с ходом компилятора (empty_list если ход невозможен).Алгоритм следующий:

Определяем фигуру (чей ход) Определяем список возможных ходов в порядке приоритета — это список пар: [позиция, победитель] В голове списка приоритетный ход, извлекаем его Извлекаем позицию и победителя Делаем ход Формируем результат (кортеж из трех типов) template struct game { typedef typename figure:: type fig; typedef typename available_moves:: type moves; typedef typename fas: head:: type result_move; typedef typename fas: first:: type position; typedef typename fas: second:: type win_fig; typedef typename do_move:: type board;

typedef fas: tuple< position, win_fig, board > type; }; Определить, чей ход на текущей доске, просто: если пустых клеток нечетное количество, то ход крестиков, в противном случае — ноликов: template struct figure { typedef typename fas: if_c< fas::type_count< e, Board>:: value % 2 == 1, x, o >:: type type; }; При заполненной доске получим, что ход ноликов, но это не важно, т.к. функция определения списка доступных ходов в этом случае проигнорирует этот тип.Функция определения списка доступных ходов (available_moves) возвращает список пар: [позиция, победитель], причем имеющим значение является только голова списка — по которому и определяется следующий ход. Если ход невозможен, то в голове списка будет пара с позицией -1. Возможные комбинации:

[-1, e] — ход невозможен (доска заполнена), либо ход возможен, но не имеет смысла (досрочная ничья) [-1, x] — ход невозможен, победа крестиков [N, e] — ход компилятора в позицию N [N, x] — ход компилятора, и он победил (компилятор играет за крестики) Функция available_moves формирует список, используя ряд вспомогательных функций, каждая возвращает список типов из одного или нескольких пар или пустой список: winner_list — на исходной доске есть победитель, например [-1, x]. Список из одного элемента или пустой список winning_moves — на исходной доске есть позиция, куда можно сделать ход и победить, например [4, o]. Список из нескольких пар или пустой список blocking_moves — на исходной доске есть позиция куда можно сделать ход и предотвратить победу соперника, например [7, x]. Список из нескольких пар или пустой список draw_list — на исходной доске ничья [-1, e] или пустой список Ход в свободную позицию, например [3, e]. Список из нескольких пар или пустой список Объединив эти списки, в том порядке, в котором они перечислены, получим список ходов в порядке приоритета: template< typename R, typename Level, typename Fig, typename Board > struct available_moves { typedef typename fas: type_list_n< typename winner_list< Fig, Board >:: type, typename winning_moves< Fig, Board >:: type, typename blocking_moves< Fig, Board >:: type, typename draw_list< Board >:: type, typename free_moves:: type >:: type type; }; Рассмотрим подробнее первые три функции: winner_list, winning_moves и blocking_moves. Каждая из этих функций использует вспомогательные функции, которые принимают на вход список из трех пар [позиция, фигура]. Таких списков восемь: три по горизонтали, три по вертикали и два по диагонали. Например, для доски: x — - 0 x - - — 0 Получим следующие списки: [[0, e],[1, e],[2, e]] [[3, e],[4, e],[5, e]] [[6, e],[7, e],[8, e]] [[0, e],[3, e],[6, e]] [[1, e],[4, e],[7, e]] [[2, e],[5, e],[8, e]] [[0, e],[4, e],[8, e]] [[2, e],[4, e],[6, e]] Начнем с функции, которая определяет, что на линии уже есть победитель: template struct winner_line { typedef typename fas: switch_< fas::case_c< is_win_line:: value, fas: pair< fas::int_<-1>, x> >, fas: case_c< is_win_line:: value, fas: pair< fas::int_<-1>, o> >, fas: default_< fas::empty_list > >:: type type; }; Если линия из крестиков (is_win_line), то возвращаем [-1, x] — ход невозможен, т.к. крестики победили, если линия из ноликов, то [-1, o]. В противном случае — пустой список.Для того, чтобы определить, что линия состоит из одних и тех же фигур, достаточно их посчитать:

template struct is_win_line { enum { value = fas: count_if< PairList3 , fas::same_type< Fig, fas::second > >:: value == 3 }; }; С определением победной или блокирующей позиции (куда можно сделать ход, чтобы победить или предотвратить победу противника) немного сложнее. Для начала научимся определять, есть ли такая позиция: template struct has_win_pos { enum { value = fas: count_if< PairList3 , fas::same_type< e, fas::second > >:: value == 1 && fas: count_if< PairList3 , fas::same_type< Fig, fas::second > >:: value == 2 }; }; В этой функции value примет значение 1, если на линии ровно одна пустая клетка, а остальные две заняты заданной фигурой.Далее разработаем еще одну вспомогательную функцию, которая из входного списка извлекает пары, у которых вторым типом будет e, при условии, если на данной линии возможен победный ход — это всегда список из одного элемента, и пустой список в противном случае:

template struct win_helper { typedef typename fas: if_c< has_win_pos< Fig, PairList3 >:: value, typename fas: select< PairList3, fas::same_type< fas::second, e> >:: type, fas: empty_list >:: type type; }; Для того, чтобы определить блокирующую позицию на линии, нужно обратить фигуру (превратить крестик в нолик и наоборот) и воспользоваться win_helper: template struct blocking_move { typedef typename fas: if_< fas::same_type, o, x >:: type rev_fig;

typedef typename win_helper< rev_fig, PairList3 >:: type type; }; Для определения победного хода обращать фигуру не надо, но нужно второй тип из пары (если это не пустой список, то это всегда список из одного элемента с позицией и типом e, например [8, e]) преобразовать в текущую фигуру. Для этого воспользуемся алгоритмом transform: template struct winning_move { typedef typename fas: transform< typename win_helper< Fig, PairList3 >:: type, fas: pair< fas::first, Fig > >:: type type; }; Если результатом win_helper пустой список, то на выходе также пустой список. В противном случае win_helper вернет список из одного элемента, например [[4, e]] и, в этом случае, нужно заменить тип e на текущую фигуру (Fig). Именно по причине того, что win_helper может вернуть пустой список, мы не можем воспользоваться условной конструкцией fas: if_.Итак, с линиями разобрались, далее нам потребуются функции, для конкретной линии. Сделаем одну, но универсальную:

template< template class Move, typename Fig, typename Board, int P0, int P1, int P2 > struct move_t { typedef typename fas: type_list_n< fas::pair< fas::int_, typename fas: type_at_c:: type >, fas: pair< fas::int_, typename fas: type_at_c:: type >, fas: pair< fas::int_, typename fas: type_at_c:: type > >:: type pos_list;

typedef typename Move:: type type; }; Параметром Move может передаваться одна из наших вспомогательных функций (winner_line, blocking_move или winning_move). Функция move_t формирует список из трех пар [позиция, фигура], на основе трех целочисленных параметров P0, P1 и P2 и передает их в Move.Всевозможные комбинации зададим явно: template< template class Move, typename Fig, typename Board > struct moves_list_t { typedef typename fas: type_list_n < typename move_t< Move, Fig, Board, 0, 1, 2 >:: type, typename move_t< Move, Fig, Board, 3, 4, 5 >:: type, typename move_t< Move, Fig, Board, 6, 7, 8 >:: type, typename move_t< Move, Fig, Board, 0, 3, 6 >:: type, typename move_t< Move, Fig, Board, 1, 4, 7 >:: type, typename move_t< Move, Fig, Board, 2, 5, 8 >:: type,

typename move_t< Move, Fig, Board, 0, 4, 8 >:: type, typename move_t< Move, Fig, Board, 2, 4, 6 >:: type

>:: type type; }; В результате функции для определения доступных ходов (победных или блокирующих) получаются тривиальными.Уже есть победитель:

template struct winner_list : moves_list_t< winner_line, Fig, Board> {}; Список победных ходов: template struct winning_moves : moves_list_t< winning_move, Fig, Board> {}; Список блокирующих ходов: template struct blocking_moves : moves_list_t< blocking_move, Fig, Board> {}; Итак, мы разобрали три вспомогательные функции для определения доступных ходов (winner_line, blocking_move или winning_move), осталось еще две. Следующая по списку — определение ничьей. Определяем ничью просто — если свободных клеток меньше трех, то это ничья. В общем случае это, конечно же, не верно, однако мы договорились, что используем только голову списка из списка возможных ходов. Поэтому если все предыдущие функции (winner_line, blocking_move или winning_move) вернули пустые списки, то этого достаточно. Разумеется, так мы можем пропустить ничью, которую можно было определить несколько раньше, но этого вполне достаточно, чтобы не делать игру утомительной. template struct draw_list { typedef typename fas: if_c< fas::type_count< e, Board >:: value < 3, fas::pair< fas::int_<-1>, e >, fas: empty_list >:: type type; }; Здесь все очевидно, если пустых полей меньше трех, то возвращаем пару [-1, e] — ход невозможен, ничья.Ну, а теперь, как это ни странно, самое сложное — ход в любую свободную позицию. Сложность заключается в том, что именно на этом этапе мы учитываем уровень сложности (уж простите за каламбур) и при этом делаем «случайные ходы», в зависимости от этого уровня сложности.

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

Для функции, которая возвращает список ходов на пустой доске в порядке приоритета в зависимости от уровня сложности, потребуется псевдослучайное число ® и уровень сложности:

template st