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

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

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] 

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] 

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’ 

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 }; }; 

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 }; }; 

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

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; }; 

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; }; 

Операции над списками типов

Для манипуляций со списками типов есть набор операций, которые помимо списка типов 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 <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; 

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::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.

[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> 

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; }; 

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