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

"- После Мятежа Галактическое Содружество наложило строгие ограничения на метафункции высшего порядка. И не только из соображений этики; их власти опасаются вообще всякого проявления мании величия..."
(из поисковой выдачи 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 (занятые позиции).

    Для функции, которая возвращает список ходов на пустой доске в порядке приоритета в зависимости от уровня сложности, потребуется псевдослучайное число ® и уровень сложности:
    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 лет. Если эта тема будет интересна, то я о ней тоже с удовольствием расскажу, но это потребует, возможно, целого цикла статей.
Share post
AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 28

    +24
    Человек-маньяк, добавьте Вашу замечательную статью в хаб «Ненормальное программирование»!
      +8
      Добавил, хотя и не согласен с Вами
      +3
      Ого! У меня намного проще крестики-нолики, если это можно назвать крестиками-ноликами.
      Так автор faslib, это Вы?

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

      Требую цикл статей!
        0
        Да, faslib мой проект.
        Я начинал писать статью несколько лет назад, но потом забыл (забил) на это, а Ваша статья побудила реанимировать ее
          0
          А почему вы не использовали boost::mpl? на первый взгляд Ваша библиотека реализуют ту же самую функциональность.
            0
            faslib быстрее в плане времени компиляции, и многие конструкции можно реализовать компактнее (меньше кода)
            В свое время я рассматривал boost::mpl, но т.к. я игрался с оптимизацией времени компиляции нужны были свои решения с которыми можно экспериментировать. Кроме того boost::mpl работает с векторами, а faslib со списками. Много других нюансов. Например boost::mpl::lamba< fun<_1,_2> >::apply — это шаблон с большим числом параметров (не помню сейчас точно), а в fas::lamba< fun<_1,_2> >::apply — это шаблон ровно с двумя параметрами. Да и вся мощь boost::mpl в faslib мне не нужна была. А в общем, то конечно, играть в крестики-нолики можно научить и с помощью boost::mpl
              0
              Понятно, спасибо
                0
                Кроме того boost::mpl работает с векторами, а faslib со списками

                Ну почему же? MPL тоже работает со списками и с другими классами и концепциями последовательностей, а также итераторов.

                А получилось здорово, конечно.
                  0
                  С векторами это я дал конечно, совсем другое имел ввиду. Проще на примере:
                    typedef boost::mpl::list<float,double,long double> floats;
                    typedef boost::mpl::push_front<floats,int>::type types;
                    /* types: 
                           boost::mpl::l_item<mpl_::long_<4l>, int, boost::mpl::list3<float, double, long double> >  */
                  

                    typedef fas::type_list_n< float,double,long double>::type floats;
                    typedef fas::push_front< int, floats>::type types;
                    /* types: 
                           fas::type_list<int, fas::type_list<float, fas::type_list<double, fas::type_list<long double, fas::empty_list> > > > */
                  

                  В faslib результатом операции всегда будет список типов — с ним проще работать, а в бусте непонятно что, результат уже на специализациях не отработаешь. В статье я уже писал, что это сильно сокращает время компиляции. Да и вообще монструозно там все как-то, а про препроцессор я вообще молчу
                    0
                    >> В faslib результатом операции всегда будет список типов — с ним проще работать, а в бусте непонятно что

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

                    >> результат уже на специализациях не отработаешь

                    ИМХО, это правильно — позволяет менять внутреннее представление данных без изменений клиентского кода.
                    Буст предоставляет интерфейс доступа аналогичный обычным контейнерав времени выполнения.
                    В данном случае использование явной специализации — это как попытка «привести» std::vector к int *

                    Если вам нужна специализация используйте enable_if
                    1. bool is_empty<Sequence>()
                    2. {
                    3.     return false;
                    4. }
                    5.  
                    6. bool is_empty<Sequence>(typename boost::enable_if<boost::mpl::empty<Sequence>>::type * = 0)
                    7. {
                    8.     return false;
                    9. }


                    >> А про препроцессор я вообще молчу
                    Это плата за то что оно может работать на куче разных компиляторов, включая древние.
                    Все новомодные штуки типа variadic templates приходится оборачивать в макросы, которые «эмулируют» новый стандарт тем или иным образом.

                    p.s.
                    Все-таки синтаксис С++ меня убивает :(
                      0
                      * вторая функция в примере должна конечно же возвращать тру
                        0
                        Я не спорю, boost::mpl прекрасный инструмент, а вы перечислили различие концепций с faslib:
                        ИМХО, это правильно — позволяет менять внутреннее представление данных без изменений клиентского кода. Буст предоставляет интерфейс доступа аналогичный обычным контейнерав времени выполнения.
                        В faslib во главе угла списки типов, могут меняться инструменты, но представление всегда одно. На ранних этапах я пытался скрыть представление, но отказался от этого.
                        Это плата за то что оно может работать на куче разных компиляторов, включая древние.
                        Я не готов за это «платить» )
                        В бусте это специально сделано, чтоб можно было работать со сложными выражениями не упираясь в ограничение компилятора на максимальную вложенность шаблонов
                        Это не спасает от ограничения. Вы можете сколь угодно сложные конструкции, а в ограничение вы упретесь при обработке таких выражений. Опять же пример, строим «вектор» из 1600 элементов:
                        template<int I, typename List >
                        struct push {
                          typedef typename boost::mpl::push_front< List, fas::int_<I> >::type result;
                          typedef typename push< I-1, result>::type type;
                        };
                        
                        template< typename List >
                        struct push<0, List> {  typedef List type; };
                        
                        int main()
                        {
                          typedef boost::mpl::vector<> lst;
                          typedef push<800, lst>::type lst800;
                          typedef push<800, lst800>::type lst1600;
                          std::cout << boost::mpl::size<lst800>::value << std::endl;
                          std::cout << boost::mpl::size<lst1600>::value << std::endl;
                        }
                        

                        Используя этот способ мы не можем построить за раз вектор больше чем 900 элементов (у меня такое ограничение по умолчанию), потому что именно в push мы упремся в это ограничение. Аналогично мы и список типов можем построить такой же длинны:
                        template<int I, typename List >
                        struct push2 {
                          typedef typename fas::push_front< fas::int_<I>, List >::type result;
                          typedef typename push2< I-1, result>::type type;
                        };
                        
                        template< typename List >
                        struct push2<0, List> {  typedef List type; };
                        
                        int main()
                        {
                          typedef fas::empty_list lst;
                          typedef push2<800, lst>::type lst800;
                          typedef push2<800, lst800>::type lst1600;
                          std::cout << fas::length<lst800>::value << std::endl;
                          std::cout << fas::length<lst1600>::value << std::endl;
                        }
                        

                        Кроме того, насколько я помню «вектора» быстрее компилируются обычно (не уверен, т.к. последний раз я в этом копался очень давно).

                        Время компиляции примера на faslib:
                        0m1.027s
                        На boost::mpl:
                        2m16.836s
                        Да-да я сам в шоке (от буста, конечно-же)
                        Дальше, больше 3200 элементов:
                        faslib: 0m1.400s
                        boost: 16m58.397s
                        Вот она сила специализаций. Хотел попробовать сделать крестики-нолики на бусте, чтобы изучить матчасть, но уже больше не хочу
                        0
                        Да, помню, как я раздосадовался, когда хотел красиво специализацией раздиспатчить что-то типа:

                        template <typename V>
                        class C{};
                        
                        template <>
                        class C<mpl::vector<int> >{};
                        


                        Не специфицировано, что может получиться после манимуляций с вектором (получится, конечно, тот же вектор как концепт, но имя у него может быть vector0, vector1 и т.д.). По факту у меня мог прийти mpl::vector1<int> или mpl::vector<int>

                        Пришлось извращаться менее красиво.
                          –1
                          deleted
                            0
                            Для такой задачи есть стандартный механизм:

                            1. template <class V, class Enable = void> 
                            2. class C {};
                            3.  
                            4. template <class C>
                            5. class A<C, typename boost::enable_if<boost::mpl::equal<V, boost::mpl::vector<int> > >::type> {};


                            Делает имеенно то, что вы хотели.

                            Справедливости ради, вместо вектора там вообще может быть все что угодно, например вы можете простенький враппер который позволит boost::mpl принимать конкретно ваши (fas::) списки типов. Все что вам нужно, это привести их к виду www.boost.org/doc/libs/1_55_0/libs/mpl/doc/refmanual/forward-sequence.html
                              0
                              Для такой задачи есть стандартный механизм:
                              Примерно так и работают операции со списками типов (в статье есть пример fas::lenght ), но плюс всегда есть специализация, для ускорения компиляции.
                              Как это реально влияет можно посмотреть в этом ответе выше. А посему я лучше напишу простенький враппер приводящий бустовые последовательности в списки типов
                                0
                                Именно такой подход сразу и пришел мне в голову: через mpl::equal выражать. Это менее красиво, в разы тормознее, но формально правильно по спецификации mpl, ничего тут не поделаешь.

                                Справедливости ради, вместо вектора там вообще может быть все что угодно

                                Я о том же выше и написал, что неспецифицировано. Например, для операции mpl::erase гарантируется лишь, что результат будет «concept-identical» источнику. То есть, с сохранением набора концепций, но фиг знает каким классом.
                                A sequence s1 is said to be concept-identical to a sequence s2 if s1 and s2 model the exact same set of concepts.

                                На практике из mpl::vector[N] будет получаться mpl::vectorN-1, я бы мог забить вторую спецификацию mpl::vector1<int> и, уверен, 100 лет бы проработало, но формально — это ошибка.

                                принимать конкретно ваши (fas::) списки типов

                                К сожалению, fas — не моя, это laphroaig :)
                                Ни сколько не умаляю достоинств mpl. Сам пользуюсь. Ее возможности более широкие. Широченные. А за высокий уровень абстрагирования приходится платить временем компиляции.
                  +10
                  Когда я вижу вот такое:

                  fas::switch_< fas::case_< fas::false_, fas::int_<24> >, fas::case_c< 1, fas::int_<42> >, fas::default_< fas::int_<44> > >::type::value 
                  

                  я понимаю, что значит НЕНОРМАЛЬНОЕ программирование…
                    +9
                    На калькуляторе БЗ-21 как-то попроще эта игра делалась. Наверное я отстал от жизни :)
                      +9
                      Здравствуй, компилятор, я хочу хочу сыграть с тобой в игру…
                        0
                        Более яркие эмоции можно испытать очнувшись прикованным к офисному креслу и услышав это предложение от компилятора
                          +3
                          После многочасового писка глупой ошибки в программе, достаточно сказать ему «Зато хрен ты у меня в крестики-нолики выиграешь» и сразу легче на душе
                            +6
                            Главное чтобы он не предложил посоревноватmся в пересборке мира с -O3
                            +3
                            Постойте, но ведь на офисном кресле можно просто уехать.
                              0
                              До первой лестницы.
                                +2
                                А дальше бобслей
                                  +2
                                  Скелетон тогда уж.
                          +1
                          Полными по Тьюрингу также являются typecheckers Haskell и D. Видел академические доказательства этому, но вот такое прагматичное впервые. Спасибо, интересная статья. Полнота по Тьюрингу кстати означает, что время компиляции теоретически не ограничено.

                          Only users with full accounts can post comments. Log in, please.