Paramorph your DSL: C++

Two months back, we went over the process of building a DSL for arithmetic operations and we introduced the concept of Catamorphism as a way to decouple the traversal of an AST from the operations we want to perform on it.

We saw how it could help us compose operations before traversing the AST of our DSL, leading to more efficient composition and better testability.

We did this exercise in Haskell, introducing the concept of Catamorphism through its wonderful type system. Then we tried it in Clojure only to see it was a simple post-walk tree traversal. We ended up by exploring the limits of its applicability in C++.

The full series of post is available below for reference:

This post will build on top of the Catamorph your DSL: C++ Port post. We will introduce, through a motivated use case, another very close and useful recursion scheme, Paramorphisms, and try to implement them in C++.

 

Reminder: Our Arithmetic DSL


Our Arithmetic DSL allows to build expression composed of operations like addition and multiplication of integer constants and integers variables. An arithmetic expression is one of the following:

  • A constant value (and integer for simplicity)
  • A variable (identified by a string for simplicity)
  • An addition of a vector of sub-expressions
  • A multiplication of a vector of sub-expressions

Because an AST alone is not very useful, we added several interpreters on our DSL to play with it. We implemented each of them in in the Catamorph your DSL: C++ Port post:

  • prn to pretty print our Arithmetic expressions
  • eval to compute the value of an expression, given the value of all variables
  • optimize to simplify and optimize our expression
  • partial to partially evaluate our expression, given the value of some variables
  • dependencies to retrieve not yet resolved variables from our expression

 

Reminder: Recursion Schemes


Looking at our interpreters, we noticed in our previous post that they all had in common the need to traverse the full AST. We used Catamorphisms to factorize this concern out of our interpreters.

This section is a short overview of what Catamorphism are for and how we implemented them in C++. You can skip it if you feel comfortable with the notion already.

 

Open recursion on types

To use Catamorphisms, we first need to generalize our Arithmetic expression and make it an open recursive data type: expression_r templated on a parameter type R, which represents the type of the sub-expressions.

 
An expression of our DSL is then defined such as the template parameter R is itself an expression. In more formal terms, expression is the fixed point of the expression_r type. We can compute it using CRTP and boost::recursive_wrapper.

 

Functor instance

We made our expression_r type an instance of a Functor by implementing a fmap function for our type. Note that by Functor here, we mean the mathematical construct, and not function objects.

The transformation map given to fmap applies on the template parameter of the expression_r and may modify its type. In other words, fmap allows to transform the sub-expressions.

Note: because the function provided to fmap can have different types as input and output, the type of the template parameter of expression_r can change under fmap, and with it, the nature of the recursion.

 

Generic tree traversal

We then defined the cata function, which implements the Catamorphism recursion scheme. It takes what we will call an algebra as parameter, and returns a transformation on a whole AST.

The algebra is a function that takes an expression_r templated on Out, and outputs an Out value.

The result of cata on the algebra (curried) is a function that applies on a full expression and returns an Out value:

For instance, the following print_alg algebra transforms an expression_r templated on string into a string. Its goal is to implement a “pretty print” of the expression at one stage of the expression alone.

Given to cata, it will become an function that transforms a complete expression into a string, basically being promoted to operate on all stages of the expression.

 

The use case that breaks the pattern


Every single technique we use in Software Engineering has its limits. Outside of these limits, the technique will either not apply or might not be the best tool for the job. Catamorphisms are no exception to this rule.

Because Catamorphisms are a way to factorize a particular recursion scheme, it cannot apply for recursions that do not follow the given pattern. We will now explore one use case that demonstrates these limits.

 

Infix notation

Let us imagine that the client of our arithmetic DSL does not like the prefix notation of our pretty print function. Instead, he would like the arithmetic expressions to be pretty printed in infix notation. For example, 1 + y + x * 3 instead of (+ 1 y (* x 3)).

Now, and contrary to the prefix notation which follows a pretty simple parenthesizing scheme, pretty printing in infix notation requires us to be careful. A wrong use of parentheses could change the meaning of the expression.

 

A first attempt

As a first approximation, we could use the following strategy for the placement of the parentheses in our infix notation:

  • Systematically surround the arguments of a multiplication with parentheses
  • Never surround the arguments of an addition with parentheses

Implementing the pretty printer that follows this strategy can be done using Catamorphisms. We use Boost to make the code simpler:

 
We can try this first implementation on our test arithmetic expression:

What we get is is a correct result: the pretty printed expression has indeed the right meaning. But there are so much unneeded parentheses that the expression is really hard to read. We have to do much better.

 

Improving parenthesizing

To get better results, we need our infix notation to avoid adding useless pairs of parentheses. We know how to fix this: a multiplication only needs to add parentheses around sub-expressions that correspond to additions.

Unfortunately, Catamorphisms are not a powerful enough recursion scheme to implement this logic. The algebra given to the Catamorphism has no access to the sub-expressions, only their resulting string.

As a consequence, there is no way to know whether the expression was previously an addition (except by parsing it, which would truly be awful). The Catamorphism has failed us here: we need to turn to a different recursion scheme.

 

From Catamorphism to Paramorphism


The previous use case demonstrated us that we need the information on whether a sub-expression is an addition when dealing with the multiplication.

We will turn to the recursion scheme known as Paramorphism, which is like a Catamorphism but with added contextual information.

 

Paramorphisms

Paramorphisms are pretty close to Catamorphisms. The goal is identical: it turns a local transformation on an open recursive data structure into a global transformation on the fixed point of this data structure.

The difference is the prototype of the algebra given as parameter to the recursion scheme. Instead of taking the open recursive type parameterized on the output type of the transformation, the algebra takes a an open recursive type parameterized on a pair:

  • The first element of the pair is the output of the sub-expression transformation
  • The second element of the pair is the sub-expression before the transformation

In more concrete terms, and applied to our arithmetic expression, here are the prototypes for the algebra of catamorphism and paramorphism:

The second element of the pair is the contextual information. In our specific case, it will provide us with the information about the sub-expression needed to make the right parenthesizing choice.

 

Paramorphism implementation

We will now implement the para function, whose goal is to transform a local algebra into a global transformation on an arithmetic expression.

The implementation is very similar to the one of the Catamorphism. The only modification concerns the lambda provided to the fmap function, which needs to return a pair instead of a single value:

 

Implementing the infix notation

We now have enough contextual information to implement our infix notation properly. For each sub-expression of addition and multiplication, our algebra has access to:

  • The pretty printed sub-expression (first argument of the pair)
  • The sub-expression itself (second argument of the pair)

We can therefore implement the pretty printing of the multiplication such that it adds parentheses around addition sub-expressions only.

 
We can try this second implementation on our test arithmetic expression. This result is clearly much better. The resulting infix notation has no unnecessary parentheses left:

 

Conclusion


This was the second post dedicated to the implementation of the recursion schemes often used in Haskell into C++.

Through a motivating use case, we discovered the limits of the Catamorphism recursion scheme, and learned about a new strictly more powerful one: Paramorphism.

Although typically unused in C++, we managed to provide a concise implementation of it. The result is clearly not as short and beautiful than in Haskell, but has the merit to show that it is not outside of the expressiveness range of C++.

You can access the full code of the DSL, along with all its associated interpreters, in this Gist or alternatively in Ideone.

Building a Clojurescript game: AI

This post is the sixth in the series of posts focused on the design and implementation of a port in ClojureScript of the game named Tribolo. You can try the game at the following address.

Our first post described the game and identified the following responsibilities, each of them will be developed in a different post:

  1. Game logic: the rules governing transitions between game states
  2. Rendering: transforming the current game state into HTML and SVG
  3. Store: the in-memory data-base holding the application state
  4. Game loop: coordinates and control of the different aspects
  5. AI logic: selection of the best next move for an AI player

Among these different parts, we already implemented the game logic as well as the rendering and the game loop. The goal of this post will be to implement a decent artificial intelligence for our Tribolo game.

 

Reminder on the target architecture


Our different responsibilities are interconnected through the following high level architecture (you can refer to our first post for more details):

   Store ----------------> Rendering ---------------> Reagent
     ^      (reaction)         ^      (send hiccup)
     |                         |
     |                         | (listen)
     |       (update)          |
     \-------------------- Game loop
                               |
                               |
     ,-------------------------| (use to update store)
     |                         |
     v                         v
 Game logic <-------------- AI logic

The last missing piece to complete the game is our AI. Until now, we assumed the existence of a function find-best-move that would implement this AI.

This function takes as input a game and returns what it believes to be the best coordinate for the current player to play at.

The goal of today is to find a satisfying implementation for this function.

 

Designing our AI


Before diving in the implementation, we will start by thinking a bit about what we want the achieve, and how we want to achieve it.

 

Choice of the weapon

There are many different types of games. Some games naturally encourage specific pattern for the development of their associated AI. Our game follows a structure such that it is easily possible to build a Game Tree for it.

A Game Tree is defined as a directed graph whose nodes are positions in a game and whose edges are moves in Wikipedia. This is pretty much the structure followed by our Game Logic API:

  • A turn represents a valid point in time in a complete game
  • A transition is a valid progression from one turn a next turn

One overall good strategy to explore a Game Tree is to use the Minimax algorithm. This algorithm was originally created to deal with two player games, so we will need to adapt it to make it work for the 3 players of Tribolo.

 

No Alpha – No Beta

The issue with the Minimax algorithm is the combinatorial explosion due to the high branching factor of the Game Tree. One good complement that allows to reduce the search tree is to use Alpha Beta pruning.

As for the Minimax, this algorithm was originally developed to deal with two player games. But unlike the Minimax, the Alpha Beta pruning is pretty hard to adapt to deal with three player games. You can check this paper for more details.

In addition to this, the rules of Tribolo are such that there is no clear alternating sequence of players. A transition might make another player unable to play, skipping his turn.

This means the next turns might not have the same player. Since the player drives whether we should minimize or maximise, this in turn means that there is no guarantied interleaving of min and max phases.

All these concerns conspire to make it really hard to come up with an implementation of Alpha-Beta pruning for Tribolo. So we will have to be do with a Minimax implementation, adapted for three players, without branch pruning.

 

High level AI

Our Minimax algorithm will not be able to go very deep in the Game Tree. But we might be able to offset this by choosing good evaluation functions. An evaluation function is defined in Wikipedia as a function used by game-playing programs to estimate the value or goodness of a position in the minimax algorithm.

In general though, there is no single evaluation function that will fit all situations best. One common approach is to select different evaluation functions depending on the stage of the game.

  • Are we in in the early game? Or in the late game?
  • Is the AI in a specific dangerous situation?
  • Is the opponent in a specific dangerous situation?
  • Is the AI loosing? Or is it winning?

Our AI will try to adopt different evaluation functions to deal with some specific situations. We will call these AI strategies. Selecting the right strategy can have a big impact on how good the AI performs.

 

AI Strategies

One obvious evaluation function for Tribolo is to use the score of the game. Namely, we could optimize for the number of cells owned by the player. This is a good strategy for the late game especially, in which we only care about winning.

Among the specific situation, there are cases in which a player is in great danger of not being able to play a single move in the following turns. We will call this situation being trapped. We might change the evaluation function to maximize the number of available transitions when such a situation seems to come at horizon. This strategy is very useful in early or middle game, but much less useful in late game.

Last but not least, we can make the AI more aggressive against the winning player. To compensate for the lack of pruning in our Minimax implementation, the AIs will both ally against the player (to ruin his score) when the player is winning. This strategy is valid in all stages of the game.

These three strategies are the ones we will implement for our Tribolo game. Our design will need to support them (and an easy way to add more in general).

 

Minimax implementation


We determined that our algorithm of choice will be a variation on Minimax. We need to adapt the simple Minimax to include the support for:

  • Three players instead of two players
  • Non standard alternation of players
  • Different evaluation functions

 

AI Strategy Protocol

Based on the fact players might alternate in different patterns, and based on the fact we want to support AI alliance against the player, the MIN and MAX parts of the Minimax algorithm will need to be parameterized.

In addition, we have to support different kind of evaluation functions. This leads us to define a protocol for an evaluation strategy that contains two methods:

  • eval-turn represents the minimax evaluation function for a turn
  • maximizing? indicates whether or not we want to min or max the scores

We call this protocol AIStrategy:

For instance, a strategy where both AI play against the human player would provide an implementation of maximizing? that would return true for turns played by the AI and false otherwise. It would naturally lead to both AI helping each other.

 

Minimax

Our next task is to implement a variant of a fixed depth Minimax implementation, parameterized by an implementation of the AIStrategy protocol we defined in the previous section.

This algorithm can be described by a nice recursion. The base case is when we reach a leaf of a search tree (the maximum depth we want to search for, or the end of the game), in which case we apply the eval-turn to give a score to the turn. Otherwise, we recur and apply a min or a max on the scores returned by each of the sub-trees.

This can be summarized with the following piece of code, which makes use of the function minimax-step to implement the recursion (which we will see after):

 
The implementation of minimax-step follows the open recursion technic. Instead of having minimax calling itself directly, we provide to minimax-step the function to call to recur. Thanks to this, we will be able to reuse this open recursive definition to implement our AI Strategies later.

Our minimax-step function will also be parameterizable with different min and max implementations. This flexibility will also help us a lot later.

 
Note 1: We do not need to worry about blowing the stack with such recursions. The search tree grows exponentially with the search depth, so we will never be able to search very deep anyway.

Note 2: If you are curious about open recursion and its different usage, you can read more about it in this previous article in which we used it to help with the implementation memoization.

 

Top level search

Our minimax function attributes a score to an turn by looking at the game tree starting from it. To find our best move, we need to call our minimax function for each reachable turn from our initial turn.

We should be able to re-use our minimax-step with one twist. As we need to keep track of the coordinate to play, we want to return tuples containing both a move and a score and maximize by score alone.

To customize the comparison, we create a variant minimax-step-by that accepts a projection for the comparison:

 
Using this minimax-step-by, we can implement our top search game-tree-search function. It takes an AIStrategy, a turn from which to start the search, and a maximum depth search. It returns what it believes to be the best move to play.

 

High level AI


Our Minimax-based AI algorithm is now ready and implemented by game-tree-search. Our next job is to implement useful AIStrategies to use in this game tree search.

 

Optimizing scores

Our first AIStrategy consists in optimizing the score of a chosen player. Because our turns contains the transitions to the next turns, we can be clever and use this data to go one level deeper in the search.

We will use our open recursive minimax-step function, but instead of calling our minimax recursively, we provide it with a function that computes the scores taking into account the transition. This computation is much cheaper than accounting for the whole transition.

We extract this logic inside the eval-next-score-of function, that takes as input the players whose scores should be summed and optimized for.

 
Based on this previous function, we can easily derive the implementations of our two AI that care about the scores:

  • The optimize-own-score-ai which optimize the score of the playing AI
  • The optmize-ai-scores-ai which optimize the scores of both AI (allied)

 

Avoiding traps

Our second family of AIStrategy is about avoiding being trapped with no move left to play. The corresponding evaluation function will maximize the number of available transition instead of the score. This is pretty simple to implement:

 

Assembling the pieces


Both our Minimax algorithm and our AI evaluation functions are ready. We only need to plug these parts together.

 
We first implement a High Level AI that will select the appropriate AI strategy to use depending on the game configuration.

Note: the details of the different predicates used in the function above are available in the following GitHub Gist.

 
Our last task is to complete our find-best-move function, which was the goal of this post. This functions is the only public function of the whole AI namespace and does:

  • Select the appropriate AI strategy using the high-level-ai function
  • Run a game tree search using game-tree-search and the selected AI

 
Note: The resulting search is performed with a depth of 2 which is quite low. In reality, because our score evaluation function also looks ahead, we get a search tree of depth 3. This strikes a balance between the need for the AI to run on the Web browser of low power devices (tablets or smart phones) and the difficulty.

We could have chosen different depth for different devices, but it would make the game harder on PC than on smartphones. Apart from being annoying to implement, it is not quite fair. To go deeper, we would instead need to add pruning to our game tree.

 

Conclusion


With this last post focusing on the implementation of the artificial intelligence, our Tribolo game is now fully complete. You can check the source code in the following GitHub repository.

I hope you did enjoy the series and the game that we built through it. I hope it did give you some ideas, made you discover at least one thing, or was as much fun as it was for me to implement it.

 

Special thanks


I would like to thank Manwe56 for our discussions on how to build an smart enough AI. His great insights helped me in designing my first ever artificial intelligence. In particular, I owe him the concept of high level AI, which helped me tremendously.

Manwe56 is regularly present in the top 1% of some of the major competitive programming contests. He is also the author of the competitive-programming GitHub repository that contains some generic implementation of the most common AI algorithms for both Java and C++.