Abnormal programming
C++
2 July 2014

Крестики-нолики: компилятор против человека — экстремальный метапрограмминг

From Sandbox
"- После Мятежа Галактическое Содружество наложило строгие ограничения на метафункции высшего порядка. И не только из соображений этики; их власти опасаются вообще всякого проявления мании величия..."
(из поисковой выдачи google)
Предлагаю Вам сыграть в крестики-нолики с компилятором. Для игры знания c++ не потребуются, достаточно наличия cmake, python и собственно компилятора c++ ( потянет даже такой древний как gcc-3.3 ). Python используется только для ввода данных пользователя, запуска компилятора после каждого хода, и скомпилированной программы для получения результата. Все вычисления (следующий ход, определение победителя или констатации ничьей) производятся на этапе компиляции, в run-time только вывод результата.

Для тех, у кого возникнет желание разобраться, как это работает: будет все по-честному, никаких хитрых трюков, хаков и генерации кода скриптом (ну почти). На выходе скрипта два файла, один с исходной позицией — это строка вида e,x,e,o,e,e,e,e,x, где e — пустое поле, а во втором файле число 0,1 или 2 — это уровень сложности. Будет 3 уровня сложности, и ходы компилятора будут случайны в зависимости от этого уровня. Также научим компилятор играть с самим собой на разных уровнях сложности.

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

Для того, чтобы сыграть, загружаем проект с github (faslib подключена как субмодуль):
git clone https://github.com/migashko/tictactoe.git
cd tictactoe/
git submodule init
git submodule update

Убеждаемся, что cmake и c++ доступны, и запускаем игру:
./tictactoe.py

При первом запуске скрипт сам создаст директорию сборки и запустит cmake. Если что-то пошло не так, делаем это вручную:
mkdir build
cd ./build
cmake ..
make tictactoe

Пример одного раунда игры
Level [0,1,2]: 2
Figure [X,x,1,O,o,0]: o
compiling...
- - -
- X -
- - -

Move [0..8, a1..c3]: a2
compiling...
- O -
- X -
X - -

Move [0..8, a1..c3]: a3
compiling...
X O O
- X -
X - -

Move [0..8, a1..c3]: b2
BUSSY
Move [0..8, a1..c3]: b1
compiling...
X O O
O X -
X - X
X winner (compiler)


Скрипт в начале игры записывает в файл level.inl число, введенное пользователем, которое задает уровень сложности, а после каждого хода в файл board.inl новую расстановку фигур (крестиков или ноликов), анализируя которую, компилятор делает ход. Эти действия можно сделать вручную, запустить компилятор и посмотреть результат. В качестве примера запишите в level.inl второй уровень сложности:
echo 2 > level.inl

а в board.inl задайте исходные позиции с помощью текстового редактора (можно вставлять переносы строк):
e,e,e,
x,o,e,
e,e,e

или так:
echo "e,e,e,x,o,e,e,e,e" > board.inl

перейдите в build и запустите make, затем ./tictactoe.
Пример нескольких компиляций
$> make
$> ./tictactoe
- - -
X O -
- - X
$> make
$> ./tictactoe
- - X
X O -
- - -
$> make
$> ./tictactoe
X - -
X O -
- - -


Помимо tictactoe, есть программа tictactoe_its, которая проигрывает партию до конца (также на этапе компиляции). Для исходного расположения фигур используется board.inl. Если нужно проиграть партию с начала, то просто удалите этот файл.
Пример для исходной позиции с двумя ходами
$> ./tictactoe_its 
- - -
X O -
- - -

X - -
X O -
- - -

X - -
X O -
O - -

X - X
X O -
O - -

X O X
X O -
O - -

X O X
X O -
O X -

Draw


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

Беспроигрышный алгоритм:
  1. Ходим в позицию, приводящую к победе
  2. Блокируем победу противника
  3. Вилка
  4. В центр
  5. Если противник пошел в угол, ход в противоположный угол
  6. В любой угол
  7. В любую свободную позицию

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

Чтобы получить шанс выиграть у компилятора на втором уровне сложности, нужно сделать первый ход в самую “неправильную” позицию — в боковую клетку. Ход компилятора ноликами будет в центр. Ваш следующий ход должен быть в один из противоположных углов, относительно вашего первого хода. Компилятор, следуя алгоритму, сделает ход в любой из свободных углов, и, если он выберет угол не рядом с вашим первым ходом, то вы гарантированно можете поставить вилку и выиграть.
Вилка компилятору на втором уровне сложности
e> ./tictactoe.py
Level [0,1,2]: 2
Figure [X,x,1,O,o,0]: x
Move [0..8, a1..c3]: b1
compiling…
- - -
X O -
- - -

Move [0..8, a1..c3]: c3
compiling...
- - O
X O -
- - X

Move [0..8, a1..c3]: c1
compiling...
- - O
X O -
X O X

Move [0..8, a1..c3]: a1
compiling...
X - O
X O -
X O X
X winner (you)


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

Краткий обзор faslib


Ориентироваться в библиотеке просто — каждая конструкция (даже самая простая) в отдельном файле. Достаточно просмотреть список файлов, чтобы определить доступный функционал. faslib — это мета-библиотека, run-time кода там практически нет, поэтому под функциями и алгоритмами будем понимать мета-функции и мета-алгоритмы.

На дизайн faslib оказали влияние несколько библиотек. Списки типов (fas/type_list), а также всевозможные операции над типами (fas/typemanip) — это, разумеется, Loki. Многие конструкции из typemanip могут быть заменены аналогами <type_traits> в c++11. Идеи для пакета fas/mp (placeholder expressions и лямбда мета-функции) и fas/integral(обертки над интегральными типами и операции над ними) взяты из boost::mpl. Интерфейсы для мета-алгоритмов я постарался сделать похожими на алгоритмы STL.

Начнем с интегральных типов. При работе с шаблонами не всегда удобно использовать числа, для этих целей удобнее специальные обёртки, например:
typedef fas::int_<2> level;

Определение этой конструкции, а также для других интегральных типов в пакете fas/integral. Там же можно найти и базовые операции, например, сложения:
std::cout << fas::int_<1>::value << std::endl; // 1
std::cout << fas::plus< fas::int_<1>, fas::int_<2> >::value 
          << std::endl; // 3

Пример, как найти наименьшее общее кратное на этапе компиляции, можно изучить здесь.

В пакете fas/typemanip набор конструкций для работы с различными типами данных. Нам потребуются same_type для определения того, совпадают ли два типа:
std::cout << fas::same_type<int, long>::value; // 0 
std::cout << fas::same_type<int, int>::value;  // 1 

Пары и кортежи типов и функции получения типа из определенной позиции:
typedef fas::pair< fas::int_<1>, fas::int_<2> > pair;
typedef fas::tuple< fas::int_<3>, fas::int_<4>, fas::int_<5> > tuple;

std::cout << fas::first<pair>::type::value << std::endl;   // 1
std::cout << fas::second<tuple>::type::value << std::endl; // 4
std::cout << fas::third<tuple>::type::value << std::endl;  // 5

Кортеж может принимать до пяти типов. Если нужно больше, то удобнее использовать списки типов. Функции для получения четвертого и пятого типов: fourth и fifth.

Условные операции:
std::cout <<
  fas::if_< 
    fas::true_, 
    fas::int_<42>, 
    fas::int_<24> 
  >::type::value 
<< std::endl; // 42 

std::cout << 
  fas::switch_< 
    fas::case_< fas::false_, fas::int_<24> >,
    fas::case_c< 1, fas::int_<42> >, 
    fas::default_< fas::int_<44> > 
  >::type::value 
<< std::endl; // 42 

Списки типов. Не буду подробно описывать концепцию, укажу лишь особенности реализации. Итак, базовые конструкции:
struct empty_list
{
  typedef metalist::empty_list metatype;
};

template< typename L, typename R = empty_list >
struct type_list
{
  typedef metalist::type_list metatype;
  typedef L left_type;
  typedef R right_type;
};

Список из четырех типов:
typedef fas::type_list<A, 
 fas::type_list<B, 
 fas::type_list<C, 
 fas::type_list<D
> > > > list_abcd; // [A,B,C,D,empty_list]

Неправильный список:
typedef fas::type_list<A, B > list2_ab_invalid;

В faslib, в отличии от Loki, список типов всегда должен оканчиваться типом fas::empty_list. Если это правило не соблюдается, то такой список называется неорганизованным. Исправить ситуацию поможет функция fas::organize, например вот так:
typedef fas::type_list< A, B > list_ab_invalid; // [A,B]
typedef fas::type_list< C, D > list_cd_invalid; // [C,D]
typedef fas::type_list< list_ab_invalid, list_cd_invalid> list_abcd_invalid; // [[C,D],[C,D]]
typedef fas::organize<list2_abcd_invalid>::type list_abcd; // [A,B,C,D,empty_list]

Искренне не понимаю, почему Александреску и последователи используют #define для формирования списка типов, можно гораздо элегантнее, например:
typedef fas::type_list_n<A,B,C>::type list; // [A,B,C,empty_list]

До c++11 type_list_n принимает до 26 параметров, после не ограничено (variadic templates).
Подробнее о списках типов
Кроме построения списков типов type_list_n может их организовывать, используя fas::organize, снимая ограничение на число параметров, например:
typedef fas::type_list_n<
  fas::type_list_n<A,B>::type, // [A,B,empty_list]
  fas::type_list_n<C,D>::type  // [C,D,empty_list]
>::type list; // [A,B,C,D,empty_list]

Следующая замечательная особенность списков типов в faslib — это возможность их экранирования структурами, например, так:
struct list_bc: fas::type_list<B, fas::type_list<C> > {}; // [B,C,empty_list]
struct list_abc: fas::type_list<B, list_bc > {}; // [A,list_bc]

Все операции и алгоритмы, работающие со списками типов, разработаны так, чтобы детектировать экранирование и, по возможности, не перестраивать их. Поясню на примере объединения списков:
typedef fas::merge<
  list_bc,  // [B,C,empty_list]
  list_abc  // [A,list_bc]
>::type list; // [B,C,A,list_bc]

Тривиальная реализация этой операции перестроила бы список в [B,C,A,B,C,empty_list]. Реализация в faslib не намного сложнее, но и реального профита она не дает в плане оптимизации времени компиляции и практического уменьшения лога в случае ошибок при экранировании хвоста списка. Но сама возможность экранирования может быть полезна для формирования списка, например, так:
template<int A, int B, int C>
struct list123: fas::type_list_n< 
  fas::int_<A>, fas::int_<B>, fas::int_<C> 
>::type {};

Кроме того, экранированный список при передаче в качестве шаблонного параметра какому-либо классу позволяет сделать более читабельным лог ошибок:
#include <fas/integral.hpp>
#include <fas/type_list.hpp>

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

template<typename L>
class test {};

int main() 
{
  // test<list2> tst;
  test<list1> tst;
  tst.doit();
}

В этом варианте компилятор выдаст что-то типа этого:
error: ‘class test<fas::type_list<fas::int_<1>, fas::type_list<fas::int_<2>, fas::type_list<fas::int_<2>, fas::empty_list> > > >’ has no member named ‘doit’

а для list2:
error: ‘class test<list2>’ has no member named ‘doit’

Вы почувствуете разницу, если в списке с десяток или больше элементов. Итак, раскроем тайну, как работает экранирование, на примере определения функции определяющей длину списка. Реализация без учета экранирования:
template<typename L, typename R>
struct length;

template<typename L, typename R>
struct length< type_list<L, R> >
{
  enum { value = 1 + length<R>::value };
};

template<>
struct length< empty_list >
{
  enum { value = 0 };
};

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

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

template<typename L>
struct length_impl<metalist::empty_list, L>
{
  enum { value = 0 };
};

Идея в том, что если не сработают специализации length по fas::type_list или fas::empty_list, то будут задействованы специализации на базе типа metatype, который определен во входном параметре. Если он не определен или не является типом fas::metalist::type_list или fas::metalist::empty_list, то получим ошибку компиляции. Если удалить специализации length< type_list<L, R> > и length< empty_list >, то код будет работоспособным, но компилироваться он будет медленнее. Компилятору (в данном случае 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<bar>::type type;
};

Формируем список типов из всех 26 шаблонных параметров, в голове списка будут явно заданные параметры, а хвост списка будет состоять из множества fas::empty_list — это неправильный список типов в контексте faslib. Операция fas::organize удаляет лишние fas::empty_list и в результате получаем список типов из нужного количества элементов.

Вариант для с++11:
template<typename Head = fas::empty_list, typename ...Args >
struct type_list_n 
{
  typedef typename fas::organize<
    fas::type_list< 
      Head, 
      typename type_list_n<Args...>::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<char> >::type empty;
typedef fas::erase_c< 0, fas::type_list<char> >::type empty;

Список всех доступных операций для списков типов:
  • erase<I,L>::type
    erase_c<int,L>::type
    Удаляет элемент в позиции I из списка L
  • head::type
    Возвращает элемент списка L (голова списка)

    index_of<T,L>::value
    Возвращает позицию первого вхождения типа T в списке L. Если тип не найден, то -1
    length::value
    Определяет длину списка типов L

    merge<L1,L2>::type
    Объединяет два списка L1 и L2 в один список
    organize::type
    Преобразует неправильный список типов L в правильный список.

    normalize::type
    То же что organize, но если L не является списком типов, преобразует его в список из одного элемента

    push_back<T,L>::type
    Добавляет тип T в конец списка L
    push_front<T,L>::type
    Добавляет тип T в начало списка L
    reverse::type
    Меняет порядок следования элементов списка L на противоположный

    split<I,L>::left_list
    split<I,L>::right_list
    split_c<int,L>::left_list
    split_c<int,L>::right_list
    Разделяет список L на два списка в позиции I
    tail::type
    Возвращает хвост списка L (удаляет первый элемент списка)

    type_at<I,L>::type
    type_at_c<int,L>::type
    Возвращает тип в позиции I списка L
    type_count<T,L>::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<typename L>
    struct last
    {
      typedef typename fas::type_at_c<
        fas::length< L >::value-1, 
        L
      >::type type;
    };
    

    Операция set_at будет устанавливать тип в заданной позиции списка типов. Также разработаем set_at_с которая принимает в качестве позиции число. Для минимизации времени компиляции эффективней реализовать эту операцию на специализациях, но мы сделаем проще — используем имеющиеся операции. Для этого:
    1. Разделяем список типов на два списка (fas::split)
    2. Во втором списке отрезаем голову (fas::tail)
    3. Добавляем заданный тип в начало обезглавленного списка (fas::push_front)
    4. Объединяем левый и правый, модифицированный, списки (fas::merge)

    template<int Pos, typename T, typename L>
    struct set_at_c
    {
      typedef fas::split_c<Pos, L> 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<typename Pos, typename T, typename L>
    struct set_at
      : set_at_c< Pos::value, T, L>
    {
    };
    


    Алгоритмы


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

    Все алгоритмы, использующие операции и/или предикаты, имеют версию с суффиксом _t, которая принимает операции и предикаты в виде шаблонных-шаблонных параметров, например:
    template<typename L, template<typename> 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<lst2, fas::inc >::type res; // [2,3,4,5]
    

    В результате получим список интегральных типов, где каждый элемент списка инкрементирован на единицу. Вариант без суффикса предполагает использование placeholder expressions:
    template<typename L, typename F >
    struct transform;
    

    Например:
    typedef fas::transform<lst, fas::inc< fas::_ > >::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<int, 4> который является семантически эквивалентным fas::int_<4>, но это другой тип. Для преобразования fas::integral_c в fas::int_ можно использовать функцию fas::make_int:
    typedef fas::transform<
      lst, 
      fas::make_int< fas::inc< fas::_ > > 
    >::type res2;
    


    Список доступных алгоритмов:
    • accumulate<L, I, F<_,_>=plus >
      Для списка интегральных типов вычисляет сумму значения I и списка L используя операцию F (по умолчанию сложение). Может применяться для любых типов, т.к. для каждого типа T из списка типов L, применяет F<Pred, T>, где Pred на первой итерации это начальный тип I, а на последующих результат предыдущего F
    • count<T, L>
      Определяет количество типов T в списке типов L, аналог fas::type_count, но использует fas::count_if и fas::same_type
    • count_if<L, С<_> >
      Определяет количество типов в списке L, удовлетворяющих условию C<_>
    • erase_if<L, C<_> >
      Удаляет все типы из списка L, удовлетворяющих условию C<_>
    • find_if<L, C<_> >
      Находит тип в списке, удовлетворяющий условию C<_> (первое вхождение)
    • for_<I, C<_>, F<_> >
      Рекурсивно применяет F<_> используя начальный тип I, пока выполняется условие C<_>
    • generator< T, F<_> >
      Генерирует новый тип, используя F
    • generate< N, F >
      Генерирует список типов длинной N, используя генератор типов F (например, fas::generator)
    • index_of_if<L, C<_> >
      Позиция элемента в списке типов, удовлетворяющего условию C<_>
    • is_sorted<L, С<_,_>=less >
      Определяет упорядоченность списка типов L, используя бинарный предикат C
    • random_shuffle<R, L>
      Псевдо-случайно перемешивает список типов L, используя интегральный тип R в качестве зерна
    • select< L, С<_> >
      Извлекает типы из списка L, удовлетворяющих условию C<_>. На выходе список типов.
    • shuffle< L, RL>
      Перемешивает список типов L, используя список интегральных типов RL
    • sort<L, С<_,_>=less >
      Сортирует список типов L
    • transform<L, F<_> >
      Возвращает список типов элементы которого являются результатом F<_>
    • transform2<L1, L2, F<_,_> >
      Возвращает список типов, элементы которого являются результатом F<_1,_2>, где _1 и _2 элементы первого и второго списков соответственно
    • transform_if< L, F<_>, C<_> >
      Возвращает список типов, элементы которого являются результатом F<_>, при условии C<_>. Если условие не выполняется, то тип не изменяется
    • transform_tail<L, F<_> >
      Изменяет хвост списка для каждого элемента (включая сам элемент, в качестве головы списка) используя F<_>
    • transform_tail_if< L, F<_>, C<_> >
      Изменяет хвост списка для каждого элемента (включая сам элемент, в качестве головы списка) используя F<_>, если для текущего элемента выполняется C<_>
    • unique_if<L, С<_,_>=same_type >
      Удаляет элементы, удовлетворяющие С<_,_> оставляя последнее вхождение
    • unique_first_if<L, С<_,_>=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<list1>::type res1; //[1,2,3,3]
    typedef fas::sort<list1>::type res2;   //[1,2,3,3]
    
    typedef fas::sort_t<list1, fas::greater>::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<list2, std::is_base_of >::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<typename L, typename R>
    std::ostream& operator<<(std::ostream& s,  fas::type_list<L, R>) 
    {
      s << L(); // текущая позиция
      int len = fas::length<R>::value; // длина хвоста списка
      if ( len%3 == 0 ) // если длина хвоста кратна трем, то с новой строки
        s << std::endl;
      else if (len != 0) // остальные, если не последний элемент, то пробел
        s <<  " ";
      s << R(); // “рекурсивно” выводим хвост списка
    }
    
    std::ostream& operator<<(std::ostream& s, fas::empty_list) 
    {
      // Конец списка. Ничего не делаем
    }
    

    Результатом “хода” компилятора будет кортеж из трех типов:
    1. Позиция, куда сделан ход. Если позиция равна fas::int_<-1>, значит, ход невозможен (исходная позиция ничейная, либо победа одного из игроков)
    2. Фигура победителя. Если победителя нет, то тип e (пустое поле)
    3. Доска после хода (список типов). Если ход невозможен, то пустой список

    Для вывода результата “хода” компилятора следующая специализация:
    template<typename Pos, typename Fig, typename Board>
    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<typename Pos, typename F, typename S, typename Tail>
    std::ostream& operator<<(std::ostream& s
      ,fas::type_list<fas::tuple< Pos, F, S>, Tail>) 
    {
      s << fas::tuple<Pos, F, S>() << std::endl;
      s << Tail();
    }
    

    Ну а теперь самое интересное. Каждый ход будет делать функция game:
    template<typename R, typename Level, typename Board>
    struct game;
    

    Здесь R — интегральный тип со случайным числом, которое генерирует система сборки, Level — уровень сложности, Board — исходная доска — список типов из девяти элементов (фигур). Результатом игры, как было отмечено выше, кортеж из трех типов: позиция, если ход возможен ( -1 в противном случае), фигура победителя (e — если нет), новая доска с ходом компилятора (empty_list если ход невозможен).

    Алгоритм следующий:
    1. Определяем фигуру (чей ход)
    2. Определяем список возможных ходов в порядке приоритета — это список пар: [позиция, победитель]
    3. В голове списка приоритетный ход, извлекаем его
    4. Извлекаем позицию и победителя
    5. Делаем ход
    6. Формируем результат (кортеж из трех типов)

    template<typename R, typename Level, typename Board>
    struct game
    {
      typedef typename figure<Board>::type fig;
      typedef typename available_moves<R, Level, fig, Board>::type moves;
      typedef typename fas::head<moves>::type result_move;
      typedef typename fas::first<result_move>::type position;
      typedef typename fas::second<result_move>::type win_fig;
      typedef typename do_move<position, fig, Board>::type board;
    
      typedef fas::tuple< position, win_fig, board > type;
    };
    

    Определить, чей ход на текущей доске, просто: если пустых клеток нечетное количество, то ход крестиков, в противном случае — ноликов:
    template<typename Board>
    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 формирует список, используя ряд вспомогательных функций, каждая возвращает список типов из одного или нескольких пар или пустой список:
    1. winner_list — на исходной доске есть победитель, например [-1,x]. Список из одного элемента или пустой список
    2. winning_moves — на исходной доске есть позиция, куда можно сделать ход и победить, например [4,o]. Список из нескольких пар или пустой список
    3. blocking_moves — на исходной доске есть позиция куда можно сделать ход и предотвратить победу соперника, например [7,x]. Список из нескольких пар или пустой список
    4. draw_list — на исходной доске ничья [-1,e] или пустой список
    5. Ход в свободную позицию, например [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<R, Level, Board >::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<typename, typename PairList3>
    struct winner_line
    {
      typedef typename fas::switch_<
        fas::case_c< 
          is_win_line<x, PairList3>::value, 
          fas::pair< fas::int_<-1>, x> 
        >, 
        fas::case_c< 
          is_win_line<o, PairList3>::value, 
          fas::pair< fas::int_<-1>, o> 
        >,
        fas::default_< fas::empty_list >
      >::type type;
    };
    

    Если линия из крестиков (is_win_line<x, PairList3>), то возвращаем [-1,x] — ход невозможен, т.к. крестики победили, если линия из ноликов, то [-1,o]. В противном случае — пустой список.

    Для того, чтобы определить, что линия состоит из одних и тех же фигур, достаточно их посчитать:
    template<typename Fig, typename PairList3>
    struct is_win_line
    {
      enum {
        value = fas::count_if< 
          PairList3 , 
          fas::same_type< Fig, fas::second<fas::_1> > 
        >::value == 3
      };
    };
    

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

    В этой функции value примет значение 1, если на линии ровно одна пустая клетка, а остальные две заняты заданной фигурой.

    Далее разработаем еще одну вспомогательную функцию, которая из входного списка извлекает пары, у которых вторым типом будет e, при условии, если на данной линии возможен победный ход — это всегда список из одного элемента, и пустой список в противном случае:
    template<typename Fig, typename PairList3 >
    struct win_helper
    {
      typedef typename fas::if_c<
        has_win_pos< Fig, PairList3 >::value, 
        typename fas::select< 
          PairList3, 
          fas::same_type< fas::second<fas::_1>, e> 
        >::type, 
        fas::empty_list
      >::type type;
    };
    

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

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

    Если результатом win_helper пустой список, то на выходе также пустой список. В противном случае win_helper вернет список из одного элемента, например [[4,e]] и, в этом случае, нужно заменить тип e на текущую фигуру (Fig). Именно по причине того, что win_helper может вернуть пустой список, мы не можем воспользоваться условной конструкцией fas::if_.

    Итак, с линиями разобрались, далее нам потребуются функции, для конкретной линии. Сделаем одну, но универсальную:
    template<
      template<typename, typename> 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_<P0>, typename fas::type_at_c<P0, Board>::type >, 
        fas::pair< fas::int_<P1>, typename fas::type_at_c<P1, Board>::type >, 
        fas::pair< fas::int_<P2>, typename fas::type_at_c<P2, Board>::type >
      >::type pos_list;
    
      typedef typename Move<Fig, pos_list>::type type;
    };
    

    Параметром Move может передаваться одна из наших вспомогательных функций (winner_line, blocking_move или winning_move). Функция move_t формирует список из трех пар [позиция, фигура], на основе трех целочисленных параметров P0, P1 и P2 и передает их в Move.
    Всевозможные комбинации зададим явно:
    template<
      template<typename, typename> 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<typename Fig, typename Board>
    struct winner_list
      : moves_list_t< winner_line,  Fig, Board>
    {};
    

    Список победных ходов:
    template<typename Fig, typename Board>
    struct winning_moves
      : moves_list_t< winning_move,  Fig, Board>
    {};
    

    Список блокирующих ходов:
    template<typename Fig, typename Board>
    struct blocking_moves
      : moves_list_t< blocking_move,  Fig, Board>
    {};
    

    Итак, мы разобрали три вспомогательные функции для определения доступных ходов (winner_line, blocking_move или winning_move), осталось еще две. Следующая по списку — определение ничьей. Определяем ничью просто — если свободных клеток меньше трех, то это ничья. В общем случае это, конечно же, не верно, однако мы договорились, что используем только голову списка из списка возможных ходов. Поэтому если все предыдущие функции (winner_line, blocking_move или winning_move) вернули пустые списки, то этого достаточно. Разумеется, так мы можем пропустить ничью, которую можно было определить несколько раньше, но этого вполне достаточно, чтобы не делать игру утомительной.
    template<typename Board>
    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 (занятые позиции).

    Для функции, которая возвращает список ходов на пустой доске в порядке приоритета в зависимости от уровня сложности, потребуется псевдослучайное число &reg; и уровень сложности:
    template<typename R, typename Level>
    struct priority_positions;
    

    Нам потребуются три типа:
    1. Центр (позиция 4)
    2. Список углов ([0,2,6,8])
    3. Список крайних позиций ([1,3,5,7])

    typedef fas::int_<4> center;
    
    typedef fas::type_list_n< 
      fas::int_<0>, fas::int_<2>, 
      fas::int_<6>, fas::int_<8> 
    >::type corner_list;
    
    typedef fas::type_list_n< 
      fas::int_<1>, fas::int_<3>, 
      fas::int_<5>, fas::int_<7> 
    >::type edge_list;
    

    Для второго уровня сложности нужно случайно перемешать списки corner_list и edge_list и объединить с центром:
    typedef typename fas::merge<
      center, 
      typename fas::merge<
        typename fas::random_shuffle< R, corner_list>::type, 
        typename fas::random_shuffle< R, side_list>::type
      >::type
    >::type level2_list;
    

    Таким образом на втором уровне сложности приоритеты ходов: центр, угол, крайние позиции. Вместо вложенного fas::merge можно использовать “плоский” fas::type_list_n.
    Как работает random_shuffle?
    Если вы до сих пор читаете эти строки, то, возможно, вас заинтересует то, каким образом перемешиваются списки типов. На самом деле все просто. Допустим, у нас есть список произвольных типов:
    [A,B,C,D]
    

    Для того, чтобы его перемешать, нужно сгенерировать список такой-же длины из произвольных интегральных типов, например:
    [10,2,44,7]
    

    Затем объединить эти два списка в список пар:
    [[10,A],[2,B],[44,C],[7,D]]
    

    Отсортировать его по первому типу каждой пары:
    [[2,B],[7,D],[10,A],[44,C]]
    

    И извлечь второй тип из каждой пары:
    [B,D,A,C]
    

    Для генерации псевдослучайной последовательности нам потребуется генератор, который преобразует исходный тип в некоторый другой. Пример инкрементального генератора:
    typedef fas::generator< 
      fas::int_<1>, 
      fas::inc< fas::_ > 
    >::next_type result; // fas::int_<2>
    

    Для генерации случайного числа:
    typedef fas::generator< 
      fas::int_<1>, 
      fas::rand< fas::_> 
    >::next_type result; // fas::int_<12461757>
    

    Алгоритм fas::generate генерирует последовательность заданной длины используя заданный генератор. Далее fas::random_shuffle использует алгоритм fas::shuffle, который сначала трансформирует список случайных интегральных типов и исходный список типов в список пар (используя fas::transform2), сортирует его, и извлекает второй тип из каждой пары (fas::transform).

    Собственно алгоритм fas::random_shuffle, генерирует псевдослучайную последовательность по заданному зерну и применяет fas::shuffle — все просто. Упрощенная реализация fas::random_shuffle:
    template<typename R, typename L>
    struct random_shuffle
    {
      typedef typename generate_c< 
        length<L>::value,
        generator_t<rand<R>, rand >
      >::type rand_list;
    
      typedef typename shuffle< L, rand_list>::type type;
    };
    

    И fas::shuffle:
    template<typename L, typename RL>
    struct shuffle
    {
      typedef typename transform2_t< RL, L, make_pair >::type pair_list;
      
      typedef typename sort<
        pair_list, 
        less<
          first<_1>,
          first<_2> 
        > 
      >::type sorted_list;
      
      typedef typename transform_t< sorted_list, second >::type type;
    };
    


    Для нулевого уровня сложности просто перемешиваем то, что получили для второго уровня:
    typedef typename fas::random_shuffle< R, level2_list >::type level0_list;
    

    Для первого уровня сложности нужно объединить списки углов и крайних позиций в один список, перемешать его, и в голову поместить центральную позицию:
    typedef typename fas::merge< corner_list, edge_list >::type side_list;
    typedef typename fas::merge<
      center, 
      typename fas::random_shuffle< R, side_list>::type
    >::type level1_list;
    

    Итак мы получили три списка возможных ходов, для каждого уровня сложности, осталось выбрать нужный список:
    typedef typename fas::switch_<
      fas::case_c< Level::value == 0, level0_list >, 
      fas::case_c< Level::value == 1, level1_list >, 
      fas::default_< level2_list >
    >::type type;
    

    Итого:
    template<typename R, typename Level>
    struct priority_positions
    {
      typedef fas::int_<4> center;
    
      typedef fas::type_list_n< 
        fas::int_<0>, fas::int_<2>, 
        fas::int_<6>, fas::int_<8> 
      >::type corner_list;
      
      typedef fas::type_list_n< 
        fas::int_<1>, fas::int_<3>, 
        fas::int_<5>, fas::int_<7> 
      >::type edge_list;
      
      typedef typename fas::merge< corner_list, edge_list >::type side_list;
      
      typedef typename fas::merge<
        center, 
        typename fas::merge<
          typename fas::random_shuffle< R, corner_list>::type, 
          typename fas::random_shuffle< R, side_list>::type
        >::type
      >::type level2_list;
    
      typedef typename fas::merge<
        center, 
        typename fas::random_shuffle< R, side_list>::type
      >::type level1_list;
    
      typedef typename fas::random_shuffle< R, level2_list >::type level0_list;
    
      typedef typename fas::switch_<
        fas::case_c< Level::value == 0, level0_list >, 
        fas::case_c< Level::value == 1, level1_list >, 
        fas::default_< level2_list >
      >::type type;
    };
    

    На выходе priority_positions список интегральных типов — позиции в порядке приоритета в зависимости от уровня сложности. Но на выходе free_moves должен быть список пар, в виде [N,e], а для этого нужно трансформировать список:
      typedef typename fas::transform  <
        typename priority_positions< R, Level >::type,
        fas::pair<
          fas::_1, 
          fas::type_at< fas::_1, Board>
        >
      >::type pair_list;
    

    И извлечь свободные позиции:
      typedef typename fas::select<
        pair_list, 
        fas::same_type< 
          e, 
          fas::second<fas::_>
        >
      >::type type;
    

    Итак, функция, которая делает ход в случайную свободную позицию в зависимости от уровня сложности:
    template<typename R, typename Level, typename Board>
    struct free_moves
    {
      typedef typename fas::transform<
        typename priority_positions< R, Level >::type,
        fas::pair<
          fas::_1, 
          fas::type_at< fas::_1, Board>
        >
      >::type pair_list;
    
      typedef typename fas::select<
        pair_list, 
        fas::same_type< 
          e, 
          fas::second<fas::_>
        >
      >::type type;
    };
    

    Последний пункт в алгоритме game — сделать ход. Если ход возможен, то замещаем тип e, в заданной позиции фигурой, которой сделал ход компилятор. В противном случае возвращаем пустой список (если компилятор не может сделать ход, то доску на экран не выводим):
    template<typename Pos, typename Fig,  typename Board>
    struct do_move
    {
      typedef typename set_at< Pos, Fig, Board >::type type;
    };
    
    template<typename Fig,  typename Board>
    struct do_move< fas::int_<-1>, Fig, Board>
    {
      typedef fas::empty_list type;
    };
    

    Уффф. Вроде, все. Основная программа:
    #include "tictactoe.hpp"
    #include "types.hpp"
    #include "show_board.hpp"
    #include <iostream>
    
    int main()
    {
      typedef game< initial_rand, level, board >::type result;
      std::cout << result() ;
      return 0;
    }
    

    Итак, мы научили компилятор делать один ход на заданной доске. А если можно сделать один ход, то научить играть партию до конца с самим собой — дело техники.

    Крестики-нолики. Партия


    Для этого нам понадобится цикл, который будет применять game, до тех пор, пока не выявится победитель или будет ничья. Изучать циклы будем на примере факториала. Рекурсивная реализация (без проверок):
    int factorial(int n)
    {
       return n > 0 ? n * factorial(n - 1) : 1;
    }
    

    Аналог на этапе компиляции:
    template<int N>
    struct factorial { enum { value = N * factorial<N-1>::value }; };
    
    template<>
    struct factorial<1> { enum { value = 1 };};
    

    В цикле:
    int factorial(int i)
    {
      int result = 1;
      for ( ; i > 0; result*=i, --i);
      return result;
    }
    

    Но для начала совсем простой пример:
    int i=0;
    for (; i<10;i++);
    std::cout << i << std::endl;
    

    С использованием fas::for_:
    typedef fas::for_< 
      fas::int_<0>, 
      fas::less<fas::_, fas::int_<10> >,
      fas::inc<fas::_> 
    >::type result;
    std::cout << result::value << std::endl;
    

    Аналогично классическому оператору for у fas::for_ три элемента: исходный тип, условие и действие. На первой итерации исходный тип передается, как есть, условному выражению, и, если оно истинно, то операции. Далее, результат операции, на вход условию, после опять операции и т.д. до тех пор пока срабатывает условие. Если условие не сработало ни разу, то результатом будет исходный тип. Результатом операции должен быть тип, который корректно обработает условие и который можно заново передать операции.

    Для вычисления факториала с использованием цикла нам потребуется пара типов — счетчик и текущее значение:
    template<int I>
    struct factorial
    {
      typedef typename fas::for_<
        // исходный тип
        fas::pair<
          fas::int_<I>,  // счетчик 
          fas::int_<1>   // текущее значение
        >,
        // условие (пока счетчик больше нуля)
        fas::greater< fas::first< _1 >, int_<0> >,
        // действие (декримент счетчика и умножение текущего значения на счетчик)
        fas::pair<
          fas::dec< fas::first< _1 > >,
          fas::times< fas::second< _1 >, fas::first< _1 > >
        >
      >::type result; 
    
      // результат пара: счетчик (всегда равен нулю) и факториал
      typedef typename fas::second<result>::type type; // int_< I! >
      enum { value = type::value};
    };
    

    Приступим к разработке цикла, который проигрывает партию начиная с заданной позиции и до конца (ничья или победитель). Результатом выполнения цикла будет список кортежей, которые вернет game на каждой итерации. Соответственно все элементы fas::for_ будут манипулировать этим списком. В качестве исходного типа будет список из одного кортежа, в который будет добавляться результат каждого раунда игры до тех пор, позиция очередного хода не будет равна fas::int_<-1>, что будет означать конец игры и условием выхода из цикла. Итак, исходный тип:
    fas::type_list< 
      fas::tuple< 
        fas::empty_type, // ход игрока 
        e,               // фигура победителя
        board            // исходная доска 
      > 
    >
    

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

    Условием выхода из цикла будет первый тип кортежа, который расположен в хвосте списка типов результатов ходов, равный fas::int_<-1> (ход невозможен) или фигура, не равная e (есть победитель):
    fas::and_<
      fas::not_<
        fas::same_type<
          fas::int_<-1>, 
          fas::first< last< fas::_1> >
        >
      >, 
      fas::same_type<
        e, 
        fas::second< last< fas::_1> >
      > 
    >
    

    Действием будет добавление в хвост списка типов результата очередного раунда игры:
    fas::push_back< 
       game< 
         initial_rand, // “случайное” число
         level,        // уровень сложности
         fas::third< last< fas::_1> > // Результат предыдущего раунда 
                                      // (третий элемент последнего кортежа)
       >, 
       fas::_1 // Список результатов предыдущих игр
    >
    

    Далее остается только отрезать голову списка, вывести исходную доску и результаты всех раундов игры (соответствующая специализация << для вывода списка результатов раундов у нас уже есть):
    #include "show_board.hpp"
    #include "tictactoe.hpp"
    #include "types.hpp"
    
    int main()
    {
      typedef fas::for_<
        fas::type_list< 
          fas::tuple< 
            fas::empty_type, 
            e,
            board
          > 
        >, 
        fas::and_<
          fas::not_<
            fas::same_type<
              fas::int_<-1>, 
              fas::first< last< fas::_1> >
            >
          >, 
          fas::same_type<
            e, 
            fas::second< last< fas::_1> >
          > 
        >, 
        fas::push_back< 
          game< 
            initial_rand, 
            level, 
            fas::third< last< fas::_1> > 
          >, 
          fas::_1
        >
      >::type result_list;
    
      typedef fas::tail<result_list>::type game_list;
      
      std::cout << board() << std::endl;
      std::cout << game_list() << std::endl;
      return 0;
    }
    

    Заключение


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

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

    Так же не раскрыта тема экстремального мета-программинга в моей интерпретации. Здесь речь не идет об XP. Это программирование на пределе возможностей, но не человека (хотя и не без этого), а компилятора. Суть достаточно проста. Нужно заставить компилятор разворачивать относительно простую внешне шаблонную конструкцию достаточно долго, так, чтобы можно замерить время компиляции (чем дольше, тем лучше), не сваливаясь в
    error: template instantiation depth exceeds maximum of 900  
    

    Сделать это не так просто, но очень увлекательно, и позволяет наглядно увидеть эффект от оптимизации тех или иных конструкций, с точки зрения времени компиляции. Побочный эффект от подобных экспериментов, это безумные логи ошибок (десятки, а иногда и сотни мегабайт), сваливание компилятора в глубокий своп (зависание системы) и Internal Compiler Error. Например, если в цикле fas::for_, который проигрывает партию крестиков-ноликов, заменить board на, например, fas::empty_type, получите 128 мегабайтный лог ошибок (для gcc-4.8).

    В повседневной практике рассмотренные пакеты в явном виде я использую редко, за исключением fas::type_list_n для формирования списка типов. Эти пакеты разработаны для поддержки пакета fas/aop (в котором реализованы аспектно-ориентированные сущности), который я активно использую в реальных проектах уже более 8 лет. Если эта тема будет интересна, то я о ней тоже с удовольствием расскажу, но это потребует, возможно, целого цикла статей.

+69
21.4k 101
Comments 28
Top of the day