...

среда, 2 июля 2014 г.

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


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

(из поисковой выдачи 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 http://ift.tt/1oncqho
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 > и length, то код будет работоспособным, но компилироваться он будет медленнее. Компилятору (в данном случае g++) гораздо проще отработать специализации без “вскрытия” входных типов.

Кроме того, все операции умеют проверять входные списки типов на валидность. Эта опция по умолчанию отключена, т.к. она увеличивает время компиляции. Если у вас появится желание поэкспериментировать со списками типов, то рекомендую включить FASLIB_TYPE_LIST_CHECK, для этого достаточно раскомментировать строку в CMakeLists.txt:


#add_definitions(-DFASLIB_TYPE_LIST_CHECK)


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


#add_definitions(-DDISABLE_TYPE_LIST_SPEC)






Далее, в комментариях, при описании списка типов, для краткости, указывать empty_list я не буду. Будем работать только с правильными списками типов.

Как работает type_list_n?
Слегка упрощенная, но работающая реализация:

template< typename T1 = empty_list,  typename T2 = empty_list,
          typename T3 = empty_list,  typename T4 = empty_list,
          typename T5 = empty_list,  typename T6 = empty_list,
          typename T7 = empty_list,  typename T8 = empty_list,
          typename T9 = empty_list,  typename T10 = empty_list, 
          typename T11 = empty_list, typename T12 = empty_list,
          typename T13 = empty_list, typename T14 = empty_list, 
          typename T15 = empty_list, typename T16 = empty_list, 
          typename T17 = empty_list, typename T18 = empty_list,
          typename T19 = empty_list, typename T20 = empty_list, 
          typename T21 = empty_list, typename T22 = empty_list, 
          typename T23 = empty_list, typename T24 = empty_list,
          typename T25 = empty_list, typename T26 = empty_list
>
struct type_list_n
{
  typedef 
      type_list< T1,  type_list< T2,  type_list< T3,  type_list< T4,
      type_list< T5,  type_list< T6,  type_list< T7,  type_list< T8,
      type_list< T9,  type_list< T10, type_list< T11, type_list< T12,
      type_list< T13, type_list< T14, type_list< T15, type_list< T16,
      type_list< T17, type_list< T18, type_list< T19, type_list< T20,
      type_list< T21, type_list< T22, type_list< T23, type_list< T24,
      type_list< T25, type_list< T26
      > >
          > > > >
                  > > > > > >
            > >
                  > > > > > >
          > > > >
      > >
  bar;
  
  typedef typename organize<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<L>::type

    Возвращает элемент списка L (голова списка)

  • index_of<T,L>::value

    Возвращает позицию первого вхождения типа T в списке L. Если тип не найден, то -1

  • length<L>::value

    Определяет длину списка типов L

  • merge<L1,L2>::type

    Объединяет два списка L1 и L2 в один список

  • organize<L>::type

    Преобразует неправильный список типов L в правильный список.

  • normalize<L>::type

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

  • push_back<T,L>::type

    Добавляет тип T в конец списка L

  • push_front<T,L>::type

    Добавляет тип T в начало списка L

  • reverse<L>::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<L>::type

    Возвращает хвост списка L (удаляет первый элемент списка)

  • type_at<I,L>::type

    type_at_c<int,L>::type

    Возвращает тип в позиции I списка L

  • type_count<T,L>::value

    Количество типов T в списке типов L

  • unique<L>::type

    Удаляет все дубликаты элементов в списке типов L, оставляя последнее вхождение

  • unique_first<L>::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 (например, 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), то возвращаем [-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_, что будет означать конец игры и условием выхода из цикла. Итак, исходный тип:

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 лет. Если эта тема будет интересна, то я о ней тоже с удовольствием расскажу, но это потребует, возможно, целого цикла статей.


This entry passed through the Full-Text RSS service — if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.


на
Ярлыки: ,

Комментариев нет:

Отправить комментарий

Подписаться на: Комментарии к сообщению (Atom)