三目並べ：コンパイラと人間-極端なメタプログラミング

「-反乱の後、銀河連邦は高次のメタ機能に厳しい制限を課しました。そして、倫理的な理由だけでなく、当局は誇大妄想の出現を恐れています...」
（ Google検索結果から ）

git clone https://github.com/migashko/tictactoe.git cd tictactoe/ git submodule init git submodule update 

 ./tictactoe.py 

 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... XOO - X - X - - Move [0..8, a1..c3]: b2 BUSSY Move [0..8, a1..c3]: b1 compiling... XOO OX - X - X X winner (compiler) 

 echo 2 > level.inl 

 e,e,e, x,o,e, e,e,e 

 echo "e,e,e,x,o,e,e,e,e" > board.inl 

 $> make $> ./tictactoe - - - XO - - - X $> make $> ./tictactoe - - X XO - - - - $> make $> ./tictactoe X - - XO - - - - 

 $> ./tictactoe_its - - - XO - - - - X - - XO - - - - X - - XO - O - - X - X XO - O - - XOX XO - O - - XOX XO - OX - Draw 

1. 私たちは勝利に導く立場に行く
2. 敵の勝利を阻止する
3. フォーク
4. 中心へ
5. 相手がコーナーに行った場合、反対側のコーナーに移動します
6. 隅々まで
7. 任意の自由な位置へ

 e> ./tictactoe.py Level [0,1,2]: 2 Figure [X,x,1,O,o,0]: x Move [0..8, a1..c3]: b1 compiling… - - - XO - - - - Move [0..8, a1..c3]: c3 compiling... - - O XO - - - X Move [0..8, a1..c3]: c1 compiling... - - O XO - XOX Move [0..8, a1..c3]: a1 compiling... X - O XO - XOX X winner (you) 

Faslibの概要

 typedef fas::int_<2> level; 

 std::cout << fas::int_<1>::value << std::endl; // 1 std::cout << fas::plus< fas::int_<1>, fas::int_<2> >::value << std::endl; // 3 

 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 

 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; 

 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] 

 typedef fas::type_list_n<A,B,C>::type list; // [A,B,C,empty_list] 

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

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

タイプリストの操作

 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
  リストLから位置Iのアイテムを削除します
• head::type
  リストアイテムL（リストヘッド）を返します
  index_of<T,L>::value
  リストLでタイプTが最初に現れる位置を返します。タイプが見つからない場合は、-1
  length::value
  タイプLのリストの長さを定義します
  merge<L1,L2>::type
  2つのリストL1とL2を1つのリストに結合します
  organize::type
  無効なLタイプのリストを正しいリストに変換します。
  normalize::type
  オーガナイズと同じですが、Lがタイプのリストではない場合、1つの要素のリストに変換します
  push_back<T,L>::type
  タイプTをリストLの最後に追加します
  push_front<T,L>::type
  タイプTをリストLの先頭に追加します
  reverse::type
  リストLの要素の順序を反対に変更します
  split<I,L>::left_list
split<I,L>::right_list
split_c<int,L>::left_list
split_c<int,L>::right_list
  リストLを位置Iで2つのリストに分割します
  tail::type
  リストLの末尾を返します（リストの最初の要素を削除します）
  type_at<I,L>::type
type_at_c<int,L>::type
  リストLの位置Iにある型を返します
  type_count<T,L>::value
  タイプLのリスト内のタイプTの数
  unique::type
  型リストL内のすべての重複要素を削除し、最後の出現を残します
  unique_first::type
  uniqueと同じですが、要素の最初の出現を残します
  
  このリストには、指定されたset_at位置で型を置き換える（移動するために必要です）、型のリストの最後の要素を最後に取得するなど、明らかな操作はありません。 これは、この記事で説明したfaslibパッケージが、メインのfaslibパッケージであるfas / aopパッケージを主にサポートするように設計されているためです。 しかし、これにはset_atのような操作は必要ありません。 さて、この誤解を修正しましょう。
  
  最後の要素を取得するには、型リストの長さ（fas :: length）を計算し、最後から2番目の位置にある型（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_cも開発します。 コンパイル時間を最小限に抑えるには、この操作をスペシャライゼーションに実装する方が効率的ですが、簡単になります-利用可能な操作を使用します。 これを行うには：
  
  1. 型のリストを2つのリストに分割します（fas :: split）
  2. 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はstlアルゴリズムに似た多くのコンパイル時アルゴリズムを実装しています。 操作とは異なり、アルゴリズムは常にメタ関数（タイプタイプが定義されている構造-結果のタイプ）です。 多くのアルゴリズムは、型のリストに加えて、単項または二項演算を受け入れます-これは、1つまたは2つのパラメーターを持つテンプレートメタ関数です。 アルゴリズムが条件付きの場合、単項またはバイナリの述語（メタ関数も）が必要です。 整数型の比較、fas / typemanipパッケージ（same_type、super_subclassなど）またはstl <type_traits>クラス（c ++ 11を使用する場合はstd :: is_base_ofなど）の関数を述部として使用できます。
  
  操作および/または述語を使用するすべてのアルゴリズムには、接尾辞_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] 

  
  結果として、リストの各要素が1ずつ増加する整数型のリストを取得します。 サフィックスのないオプションには、プレースホルダー式の使用が含まれます。
  

   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の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番目は_2などになります。 _以外のプレースホルダーが式で使用されている場合は、後者を完全に放棄することをお勧めします。そうでない場合、式を理解するのが難しくなります。 同時に、単純なバージョンでは非常に便利です。
  
  fas :: transformを使用した例では、関数fas :: incを使用して、整数型を1つ増やしました。 ただし、この関数の結果は、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 >
    整数型のリストの場合、演算F（デフォルトでは加算）を使用して、Iの値とリストLの合計を計算します。 次のように、あらゆるタイプに使用できます タイプLのリストの各タイプTに対して、F <Pred、T>を適用します。最初の反復でのPredは初期タイプIであり、後続の反復では前のFの結果です
  • count<T, L>
    fas :: type_countと同様ですが、fas :: count_ifおよびfas :: same_typeを使用して、Lタイプのリスト内のTタイプの数を決定します
  • count_if<L, <_> >
    リストL内の条件Cを満たす型の数を定義します<_>
  • erase_if<L, C<_> >
    条件C <_>を満たすすべてのタイプをリストLから削除します
  • find_if<L, C<_> >
    リスト内でC <_>（最初の出現）を満たす型を検索します
  • for_<I, C<_>, F<_> >
    条件C <_>で初期型Iを使用してF <_>を再帰的に適用します
  • generator< T, F<_> >
    Fを使用して新しい型を生成します
  • generate< N, F >
    型ジェネレーターF（たとえば、fas :: generator）を使用してlong Nの型のリストを生成します
  • index_of_if<L, C<_> >
    条件Cを満たす型リスト内の要素の位置<_>
  • is_sorted<L, <_,_>=less >
    バイナリー述部Cを使用して、タイプLのリストの順序を決定します
  • random_shuffle<R, L>
    整数型Rを木目として使用して、L型のリストを擬似ランダムにシャッフルします。
  • select< L, <_> >
    条件C <_>を満たすリストLから型を取得します。 出力はタイプのリストです。
  • shuffle< L, RL>
    RLの整数型のリストを使用して、Lの型のリストをシャッフルします
  • sort<L, <_,_>=less >
    タイプLのリストをソートします
  • transform<L, F<_> >
    F <_>の結果が要素である型のリストを返します
  • transform2<L1, L2, F<_,_> >
    要素がF <_1、_2>の結果である型のリストを返します。ここで、_1と_2はそれぞれ最初と2番目のリストの要素です
  • transform_if< L, F<_>, C<_> >
    C <_>が指定された場合、要素がF <_>の結果である型のリストを返します。 条件が満たされない場合、タイプは変更されません
  • transform_tail<L, F<_> >
    F <_>を使用して、各要素（リストの先頭としての要素自体を含む）のリストの末尾を変更します
  • transform_tail_if< L, F<_>, C<_> >
    C <_>が現在の要素に対して実行されている場合、F <_>を使用して、各要素（リスト自体の先頭として要素自体を含む）のリストの末尾を変更します
  • 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. ,
  6. ( )
  
  

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

  
  , , : , , — :
  

   template<typename Board> struct figure { typedef typename fas::if_c< fas::type_count< e, Board>::value % 2 == 1, x, o >::type type; }; 

  
  , , , .. .
  
  (available_moves) : [, ], — . , -1. :
  
  • [-1,e] — ( ), , ( )
  • [-1,x] — ,
  • [N,e] — N
  • [N,x] — , ( )
  
  available_moves , , :
  
  1. winner_list — , [-1,x].
  2. winning_moves — , , [4,o].
  3. blocking_moves — , [7,x].
  4. draw_list — [-1,e]
  5. , [3,e].
  
  , , , :
  

   template< typename R, typename Level, typename Fig, typename Board > struct available_moves { typedef typename fas::type_list_n< typename winner_list< Fig, Board >::type, typename winning_moves< Fig, Board >::type, typename blocking_moves< Fig, Board >::type, typename draw_list< Board >::type, typename free_moves<R, Level, Board >::type >::type type; }; 

  
  : winner_list, winning_moves blocking_moves. , [, ]. : , . , :
  

   x - - 0 x - - - 0 

  
  :
  

   [[0,e],[1,e],[2,e]] [[3,e],[4,e],[5,e]] [[6,e],[7,e],[8,e]] [[0,e],[3,e],[6,e]] [[1,e],[4,e],[7,e]] [[2,e],[5,e],[8,e]] [[0,e],[4,e],[8,e]] [[2,e],[4,e],[6,e]] 

  
  , , :
  

   template<typename, typename PairList3> struct winner_line { typedef typename fas::switch_< fas::case_c< is_win_line<x, PairList3>::value, fas::pair< fas::int_<-1>, x> >, fas::case_c< is_win_line<o, PairList3>::value, fas::pair< fas::int_<-1>, o> >, fas::default_< fas::empty_list > >::type type; }; 

  
  (is_win_line<x, PairList3>), [-1,x] — , .. , , [-1,o]. — .
  
  , , , :
  

   template<typename Fig, typename PairList3> struct is_win_line { enum { value = fas::count_if< PairList3 , fas::same_type< Fig, fas::second<fas::_1> > >::value == 3 }; }; 

  
  ( , ) . , :
  

   template<typename Fig, typename PairList3> struct has_win_pos { enum { value = fas::count_if< PairList3 , fas::same_type< e, fas::second<fas::_1> > >::value == 1 && fas::count_if< PairList3 , fas::same_type< Fig, fas::second<fas::_1> > >::value == 2 }; }; 

  
  value 1, , .
  
  , , e, , — , :
  

   template<typename Fig, typename PairList3 > struct win_helper { typedef typename fas::if_c< has_win_pos< Fig, PairList3 >::value, typename fas::select< PairList3, fas::same_type< fas::second<fas::_1>, e> >::type, fas::empty_list >::type type; }; 

  
  , , ( ) win_helper:
  

   template<typename Fig, typename PairList3 > struct blocking_move { typedef typename fas::if_< fas::same_type<Fig, x>, o, x >::type rev_fig; typedef typename win_helper< rev_fig, PairList3 >::type type; }; 

  
  , ( , e, [8,e]) . transform:
  

   template<typename Fig, typename PairList3> struct winning_move { typedef typename fas::transform< typename win_helper< Fig, PairList3 >::type, fas::pair< fas::first<fas::_1>, Fig > >::type type; }; 

  
  win_helper , . win_helper , [[4,e]] , , e (Fig). , win_helper , fas::if_.
  
  , , , . , :
  

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

  
  Move (winner_line, blocking_move winning_move). move_t [, ], P0, P1 P2 Move.
  :
  

   template< template<typename, typename> class Move, typename Fig, typename Board > struct moves_list_t { typedef typename fas::type_list_n < typename move_t< Move, Fig, Board, 0, 1, 2 >::type, typename move_t< Move, Fig, Board, 3, 4, 5 >::type, typename move_t< Move, Fig, Board, 6, 7, 8 >::type, typename move_t< Move, Fig, Board, 0, 3, 6 >::type, typename move_t< Move, Fig, Board, 1, 4, 7 >::type, typename move_t< Move, Fig, Board, 2, 5, 8 >::type, typename move_t< Move, Fig, Board, 0, 4, 8 >::type, typename move_t< Move, Fig, Board, 2, 4, 6 >::type >::type type; }; 

  
  ( ) .
  
  :
  

   template<typename Fig, typename Board> struct winner_list : moves_list_t< winner_line, Fig, Board> {}; 

  
  :
  

   template<typename Fig, typename Board> struct winning_moves : moves_list_t< winning_move, Fig, Board> {}; 

  
  :
  

   template<typename Fig, typename Board> struct blocking_moves : moves_list_t< blocking_move, Fig, Board> {}; 

  
  , (winner_line, blocking_move winning_move), . — . — , . , , , , . (winner_line, blocking_move winning_move) , . , , , , .
  

   template<typename Board> struct draw_list { typedef typename fas::if_c< fas::type_count< e, Board >::value < 3, fas::pair< fas::int_<-1>, e >, fas::empty_list >::type type; }; 

  
  , , [-1,e] — , .
  
  , , — . , ( ) “ ”, .
  
  free_moves . , , , . [, ] , e ( ).
  
  , , ® :
  

   template<typename R, typename Level> struct priority_positions; 

  
  :
  
  1. ( 4)
  2. ([0,2,6,8])
  3. ([1,3,5,7])
  
  

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

  
  corner_list edge_list :
  

   typedef typename fas::merge< center, typename fas::merge< typename fas::random_shuffle< R, corner_list>::type, typename fas::random_shuffle< R, side_list>::type >::type >::type level2_list; 

  
  : , , . fas::merge “” fas::type_list_n.
  
  random_shuffle?

  , , , , . . , :
  

   [A,B,C,D] 

  
  , , - , :
  

   [10,2,44,7] 

  
  :
  

   [[10,A],[2,B],[44,C],[7,D]] 

  
  :
  

   [[2,B],[7,D],[10,A],[44,C]] 

  
  :
  

   [B,D,A,C] 

  
  , . :
  

   typedef fas::generator< fas::int_<1>, fas::inc< fas::_ > >::next_type result; // fas::int_<2> 

  
  :
  

   typedef fas::generator< fas::int_<1>, fas::rand< fas::_> >::next_type result; // fas::int_<12461757> 

  
  fas::generate . fas::random_shuffle fas::shuffle, ( fas::transform2), , (fas::transform).
  
  fas::random_shuffle, fas::shuffle — . fas::random_shuffle:
  

   template<typename R, typename L> struct random_shuffle { typedef typename generate_c< length<L>::value, generator_t<rand<R>, rand > >::type rand_list; typedef typename shuffle< L, rand_list>::type type; }; 

  
  fas::shuffle:
  

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

  
  
  
  , :
  

   typedef typename fas::random_shuffle< R, level2_list >::type level0_list; 

  
  , , :
  

   typedef typename fas::merge< corner_list, edge_list >::type side_list; typedef typename fas::merge< center, typename fas::random_shuffle< R, side_list>::type >::type level1_list; 

  
  , , :
  

   typedef typename fas::switch_< fas::case_c< Level::value == 0, level0_list >, fas::case_c< Level::value == 1, level1_list >, fas::default_< level2_list > >::type type; 

  
  :
  

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

  
  priority_positions — . free_moves , [N,e], :
  

    typedef typename fas::transform < typename priority_positions< R, Level >::type, fas::pair< fas::_1, fas::type_at< fas::_1, Board> > >::type pair_list; 

  
  :
  

    typedef typename fas::select< pair_list, fas::same_type< e, fas::second<fas::_> > >::type type; 

  
  , , :
  

   template<typename R, typename Level, typename Board> struct free_moves { typedef typename fas::transform< typename priority_positions< R, Level >::type, fas::pair< fas::_1, fas::type_at< fas::_1, Board> > >::type pair_list; typedef typename fas::select< pair_list, fas::same_type< e, fas::second<fas::_> > >::type type; }; 

  
  game — . , e, , . ( , ):
  

   template<typename Pos, typename Fig, typename Board> struct do_move { typedef typename set_at< Pos, Fig, Board >::type type; }; template<typename Fig, typename Board> struct do_move< fas::int_<-1>, Fig, Board> { typedef fas::empty_list type; }; 

  
  . , . :
  

   #include "tictactoe.hpp" #include "types.hpp" #include "show_board.hpp" #include <iostream> int main() { typedef game< initial_rand, level, board >::type result; std::cout << result() ; return 0; } 

  
  , . , — .
  
  

  -.

  
  , game, , . . ( ):
  

   int factorial(int n) { return n > 0 ? n * factorial(n - 1) : 1; } 

  
  :
  

   template<int N> struct factorial { enum { value = N * factorial<N-1>::value }; }; template<> struct factorial<1> { enum { value = 1 };}; 

  
  :
  

   int factorial(int i) { int result = 1; for ( ; i > 0; result*=i, --i); return result; } 

  
  :
  

   int i=0; for (; i<10;i++); std::cout << i << std::endl; 

  
  fas::for_:
  

   typedef fas::for_< fas::int_<0>, fas::less<fas::_, fas::int_<10> >, fas::inc<fas::_> >::type result; std::cout << result::value << std::endl; 

  
  for fas::for_ : , . , , , , , . , , , .. . , . , .
  
  — :
  

   template<int I> struct factorial { typedef typename fas::for_< //   fas::pair< fas::int_<I>, //  fas::int_<1> //   >, //  (   ) fas::greater< fas::first< _1 >, int_<0> >, //  (       ) fas::pair< fas::dec< fas::first< _1 > >, fas::times< fas::second< _1 >, fas::first< _1 > > > >::type result; //  :  (  )   typedef typename fas::second<result>::type type; // int_< I! > enum { value = type::value}; }; 

  
  , ( ). , game . fas::for_ . , , fas::int_<-1>, . , :
  

   fas::type_list< fas::tuple< fas::empty_type, //   e, //   board //   > > 

  
  , , , . , , — .
  
  , , fas::int_<-1> ( ) , e ( ):
  

   fas::and_< fas::not_< fas::same_type< fas::int_<-1>, fas::first< last< fas::_1> > > >, fas::same_type< e, fas::second< last< fas::_1> > > > 

  
  :
  

   fas::push_back< game< initial_rand, // “”  level, //   fas::third< last< fas::_1> > //    // (   ) >, fas::_1 //     > 

  
  , ( << ):
  

   #include "show_board.hpp" #include "tictactoe.hpp" #include "types.hpp" int main() { typedef fas::for_< fas::type_list< fas::tuple< fas::empty_type, e, board > >, fas::and_< fas::not_< fas::same_type< fas::int_<-1>, fas::first< last< fas::_1> > > >, fas::same_type< e, fas::second< last< fas::_1> > > >, fas::push_back< game< initial_rand, level, fas::third< last< fas::_1> > >, fas::_1 > >::type result_list; typedef fas::tail<result_list>::type game_list; std::cout << board() << std::endl; std::cout << game_list() << std::endl; return 0; } 

  
  

  おわりに

  
  -, , . ( ), . , , . , .
  
  , . - — , fas::for_ . -, - - ( - ).
  
  - . XP. , ( ), . . , , ( , ),
  

   error: template instantiation depth exceeds maximum of 900 

  
  , , , . , (, ), ( ) Internal Compiler Error. , fas::for_, -, board , , fas::empty_type, 128 ( gcc-4.8).
  
  , fas::type_list_n . fas/aop ( - ), 8 . , , , , .