Geekly Articles each Day
📜 ⬆️ ⬇️

Tic-tac-toe: compiler against man - extreme metaprogramming

"- After the Revolt, the Galactic Commonwealth imposed strict restrictions on higher-order metafunctions . And not only for ethical reasons; their authorities fear in general any manifestation of delusions of grandeur ..."
( from google search results )
I suggest you play tic-tac-toe with a compiler. For the game, knowledge of c ++ is not required, it is enough to have cmake, python and the c ++ compiler itself (it will pull even as ancient as gcc-3.3). Python is used only to enter user data, run the compiler after each turn, and the compiled program to get the result. All calculations (the next move, determination of the winner or statement of a draw) are made at the compilation stage, at run-time only the output of the result.

For those who have a desire to understand how it works: everything will be fair, no tricky tricks, hacks and code generation by the script (well, almost). At the output of the script, two files, one with the initial position, is a string of the form e, x, e, o, e, e, e, e, x, where e is an empty field, and in the second file the number 0.1 or 2 is level of difficulty. There will be 3 levels of difficulty, and the compiler's moves will be random depending on this level. We will also teach the compiler to play with itself at different levels of complexity.

There will be a bit of code - we will use what has already been implemented in the faslib library. This library is designed to implement aspect-oriented concepts using patterns based on type lists. The topics of AOP , this time we will not touch, and use the packages to work with lists of types and meta-algorithms.

To play, we load the project from github (faslib is connected as a submodule):
git clone https://github.com/migashko/tictactoe.git cd tictactoe/ git submodule init git submodule update

Make sure that cmake and c ++ are available, and run the game:
 ./tictactoe.py

When you first start the script itself will create the build directory and run cmake. If something went wrong, do it manually:
 mkdir build cd ./build cmake .. make tictactoe

Example of one round of the game
 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)


The script at the beginning of the game writes the number entered by the user to the level.inl file, which sets the level of difficulty, and after each move to the board.inl file, a new arrangement of figures (crosses or zeros), analyzing which, the compiler makes a move. These actions can be done manually, run the compiler and see the result. As an example, write a second level of difficulty in level.inl:
 echo 2 > level.inl

and in board.inl, set the initial positions using a text editor (you can insert line breaks):
 e,e,e, x,o,e, e,e,e

or so:
 echo "e,e,e,x,o,e,e,e,e" > board.inl

go to build and run make, then ./tictactoe.
Multiple compilation example
 $> make $> ./tictactoe - - - XO - - - X $> make $> ./tictactoe - - X XO - - - - $> make $> ./tictactoe X - - XO - - - -


In addition to tictactoe, there is a program tictactoe_its, which loses the game to the end (also at the compilation stage). For the initial location of the figures used board.inl. If you want to play the game from the beginning, just delete this file.
Example for a starting position with two moves
 $> ./tictactoe_its - - - XO - - - - X - - XO - - - - X - - XO - O - - X - X XO - O - - XOX XO - O - - XOX XO - OX - Draw


The algorithm used by the compiler is not perfect, so for a given location, even for the second level of complexity, no one’s death is guaranteed.
')
Win-win algorithm:
  1. We go to the position leading to the victory
  2. We block the victory of the enemy
  3. Fork
  4. To the center
  5. If the opponent went to the corner, move to the opposite corner.
  6. To any angle
  7. In any free position

In the current implementation, at the second level of complexity, the compiler ignores points 3 and 5. If you follow this algorithm yourself, even taking into account points 3 and 5, the compiler will reduce the game to a draw. At the first level, the fourth point is not taken into account, but at the simplest, zero, sixth.

To get a chance to win the compiler on the second level of difficulty, you need to make the first move to the “wrong” position - in the side cage. The progress of the compiler will be in the center. Your next turn should be at one of the opposite corners, relative to your first turn. The compiler, following the algorithm, will make a move to any of the free corners, and if he chooses a corner not near your first move, then you are guaranteed to put the fork and win.
Fork compiler on the second level of complexity
 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)


At this game we finish and get down to the most interesting. Next, you need a good knowledge of C ++, especially all that concerns templates. At the beginning I will give a brief overview of faslib (only those packages that we need to implement the game), then we will teach the compiler to make one move, identify the winner and determine the draw. And finally, we will teach him to play the whole game with himself.

Faslib overview


Orientation in the library is simple - each design (even the simplest) in a separate file. It is enough to look through the list of files to determine the available functionality. faslib is a meta-library, there is practically no run-time code, therefore, by functions and algorithms we will mean meta-functions and meta-algorithms.

The design of faslib was influenced by several libraries. Type lists ( fas / type_list ), as well as various types of operations on types ( fas / typemanip ) are, of course, Loki . Many constructions from typemanip can be replaced by analogs of <type_traits> in c ++ 11. The ideas for the fas / mp package (placeholder expressions and lambda meta-functions) and fas / integral (wrappers over integral types and operations on them) are taken from boost :: mpl. I tried to make interfaces for meta-algorithms similar to STL algorithms.

Let's start with integral types. When working with templates, it is not always convenient to use numbers; for this purpose, special wrappers are more convenient, for example:
 typedef fas::int_<2> level;

The definition of this construction, as well as for other integral types in the package fas / integral. You can also find basic operations there, for example, additions:
 std::cout << fas::int_<1>::value << std::endl; // 1 std::cout << fas::plus< fas::int_<1>, fas::int_<2> >::value << std::endl; // 3

An example of how to find the smallest common multiple at compile time can be explored here .

The fas / typemanip package contains a set of constructions for working with various data types. We will need the same_type to determine if the two types are the same:
 std::cout << fas::same_type<int, long>::value; // 0 std::cout << fas::same_type<int, int>::value; // 1

Couples and tuples of types and functions of getting the type from a certain position
 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

A tuple can take up to five types. If more is needed, it is more convenient to use type lists. Functions for getting the fourth and fifth types: fourth and fifth.

Conditional operations:
 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

Type Lists. I will not describe in detail the concept, I will only indicate the features of the implementation. So, the basic structures:
 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; };

List of four types:
 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]

Incorrect list:
 typedef fas::type_list<A, B > list2_ab_invalid;

In faslib, in contrast to Loki, the type list should always end with the type fas :: empty_list. If this rule is not observed, then this list is called unorganized. The function of fas :: organize will help to correct the situation, for example like this:
 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]

I sincerely do not understand why Alexandrescu and followers use #define to form a list of types, can be much more elegant, for example:
 typedef fas::type_list_n<A,B,C>::type list; // [A,B,C,empty_list]

Up to c ++ 11 type_list_n accepts up to 26 parameters, after it is unlimited (variadic templates).
More about type lists
In addition to building type lists, type_list_n can organize them using fas :: organize, removing the restriction on the number of parameters, for example:
 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]

The following remarkable feature of typelists in faslib is the possibility of their shielding by structures, for example, like this:
 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]

All operations and algorithms that work with type lists are designed to detect shielding and, if possible, not rebuild them. Let me explain with the example of combining lists:
 typedef fas::merge< list_bc, // [B,C,empty_list] list_abc // [A,list_bc] >::type list; // [B,C,A,list_bc]

A trivial implementation of this operation would rearrange the list in [B, C, A, B, C, empty_list]. Implementation in faslib is not much more complicated, but it does not provide a real profit in terms of optimizing compile time and practical reduction of the log in case of errors when screening the tail of the list. But the very possibility of screening can be useful for the formation of a list, for example, like this:
 template<int A, int B, int C> struct list123: fas::type_list_n< fas::int_<A>, fas::int_<B>, fas::int_<C> >::type {};

In addition, the screened list, when passed as a template parameter to any class, allows you to make the error log more readable:
 #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(); }

In this embodiment, the compiler will produce something like this:
 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'

and for list2:
 error: 'class test<list2>' has no member named 'doit'

You will feel the difference if there are a dozen or more items on the list. So, let's reveal the secret of how screening works, using the example of defining a function that determines the length of a list. Implementation without screening:
 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 }; };

If a shielded list comes to the input of the length function, in this implementation, we get an error at the compilation stage. In order to distinguish the list of types from other constructions, we use the magic metatype defined in the structures fas :: type_list and fas :: empty_list, declaring additionally:
 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 }; };

The idea is that if the specializations of length on fas :: type_list or fas :: empty_list do not work, then specializations based on the type metatype, which is defined in the input parameter, will be involved. If it is not defined or is not the type fas :: metalist :: type_list or fas :: metalist :: empty_list, then we get a compilation error. If you delete the specialization length <type_list <L, R>> and length <empty_list>, then the code will work, but it will be compiled slower. It is much easier for a compiler (in this case, g ++) to work out specializations without “opening” input types.

In addition, all operations are able to check the input type lists for validity. This option is disabled by default, because it increases compile time. If you want to experiment with type lists, I recommend that you enable FASLIB_TYPE_LIST_CHECK, for this you just uncomment the line in CMakeLists.txt:

#add_definitions (-DFASLIB_TYPE_LIST_CHECK)

You can also disable the specialization of operations and algorithms by type_list, leaving only the specialization on the meta type, and evaluate the effect in terms of compile time:

#add_definitions (-DDISABLE_TYPE_LIST_SPEC)

Further, in the comments, when describing the type list, for brevity, I will not specify empty_list. We will work only with the correct type lists.
How does type_list_n work?
Slightly simplified, but working implementation:
 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; };

We form a list of types from all 26 template parameters, in the head of the list there will be explicitly specified parameters, and the tail of the list will consist of a set of fas :: empty_list - this is an incorrect list of types in the context of faslib. The operation fas :: organize removes unnecessary fas :: empty_list and as a result we get a list of types from the required number of elements.

Option for c ++ 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; };

Also, a simplified implementation - fas :: organize is applied to the list at each stage of its formation. In an amicable way, you first need to create a list and then organize it once. Here, fas :: organize is needed in order to be able to pass type lists in the parameters of fas :: type_list_n.


Type list operations


For manipulations with type lists, there is a set of operations that, in addition to the type list L, can take type T and index I, an integral type. For operations with an index, there is an alternative with the suffix _c, in which the index is given by a number, for example:
 typedef fas::erase< fas::int_<0>, fas::type_list<char> >::type empty; typedef fas::erase_c< 0, fas::type_list<char> >::type empty;

List of all available operations for type lists:

Source: https://habr.com/ru/post/228367/

More articles:


All Articles