Tristan Cazenave
email: tristan.cazenave@lamsade.dauphine.fr

Yen-Chi Chen

Guan-Wei Chen

Shi-Yu Chen

Xian-Dong Chiu

Julien Dehos
email: dehos@univ-littoral.fr

Maria Elsa

Qucheng Gong

Hengyuan Hu

Vasil Khalidov

Cheng-Ling Li

Hsin-I Lin

Yu-Jin Lin

Xavier Martinet

Vegard Mella

Jeremy Rapin

Baptiste Roziere

Gabriel Synnaeve

Fabien Teytaud
email: oteytaud@fb.com

Olivier Teytaud

Shi-Cheng Ye

Yi-Jun Ye

Shi-Jim Yen
email: sjyen@mail.ndhu.edu.tw

Sergey Zagoruyko

à la diffusion de documents scientifiques de niveau

Keywords:

recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

INTRODUCTION

In spite of AlphaGo [START_REF] Silver | Mastering the Game of Go with Deep Neural Networks and Tree Search[END_REF], some games still resist to computers and for many games the computational requirement is still huge. We present Polygames, our open-source zero learning framework available at https://github.com/facebookincubator/polygames. It is based on Zero learning, combining Monte Carlo Tree Search and Deep Learning. It features a new architecture for accelerating the training and for making it size-invariant (Section 2.1). It allows neuroplasticity i.e. adding neutral layers, adding channels, increasing kernel size (Section 2.2) and warm start. Polygames also features a new tournament mode in order to make training more robust (Section 2.3). The framework provides a single-file API, that is generic enough for implementing many games, and comes with a library of games and many checkpoints. Basically, for adding a game, one must implement the transition function next (gameplay and reward), the mapping s → tensor(s) representing a state as a 3D-tensor, and a mapping for identifying an action to a 3-dimensional location in the 3D output tensor. One can for example duplicate the code in connectfour.h and modify it. Polygames made the first ever win against top level humans at the game of Hex 19x19 (Section 3.1) and Havannah 8x8 (Section 3.3).

1.1. Zero learning AlphaGo and AlphaZero [START_REF] Silver | Mastering the Game of Go with Deep Neural Networks and Tree Search[END_REF][START_REF] Silver | Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm[END_REF] proposed a combination between Monte Carlo Tree Search [START_REF] Coulom | Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search[END_REF] and Deep Learning. The version in [START_REF] Silver | Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm[END_REF] is a simplified and elegant version, learnt end-to-end.

Monte Carlo Tree Search

Monte Carlo consists in approximating values (i.e. expected rewards) by averaging random simulations. MCTS (Monte Carlo Tree Search) consists in biasing these random simulations: using the statistics from previous simulations, we increase the frequency of moves which look good. The most well known variant of MCTS is Upper Confidence Trees (UCT) [START_REF] Kocsis | Bandit based Monte-Carlo planning[END_REF], which uses, for biasing the simulations, a formula inspired from the bandit literature: a move is chosen if it maximises a score as follows:

score uct (s, a) = avg reward(next(s, a)) + k log(num sims(s)) num sims(next(s, a)) (1)
where s stands for a state, a for an action, num sims(s) for the number of simulations in s, and next represents the dynamics of the game. An MCTS rollout consists in doing a simulation from the current board s 0 and playing using the above formula until a final state is reached. We keep from Monte Carlo a random component in MCTS rollouts: in states without any statistics, the selection is simply random move selection. When M MCTS rollouts have been performed starting in the current state s 0 , we choose an action a maximizing e.g. num sims(next(s 0 , a)).

Neural policies

Let us assume that we have a function tensor which maps a state to a tensor tensor(state) (to be used in Eq. 2 below). A neural network (NN) can then be applied. We consider a NN with two outputs:

π NN (state) is a tensor, V NN (state) is a real number.
The NN typically uses convolutional layers, and then two heads for those two outputs; in the original Alpha-Zero, it contains fully connected layers in both heads. If we assume that each possible action has an index in the output tensor, then π NN (s) can be converted into probabilities of actions by (i) multiplying by some temperature T and applying the exp function to each entry in it (ii) setting to zero illegal actions in state s (iii) dividing by the sum:

logit(a) = π NN (s) Proba NN (s, a) = exp(T logit(a)) a exp(T logit(a ))
Let us note Proba NN (s, a) the probability of action a in state s for the neural network NN.

Zero model of play: how the MCTS is modified by adding the NN

The zero-model is then as follows. First, the UCT formula (Eq. 1) is adapted as PUCT [START_REF] Silver | Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm[END_REF], as follows:

score puct (s, a) = Q(s, a) + k × P NN (tensor(s))(a) × n(s) n(next(s, a)) (2)
In Eq. 2, n(s) stands for num sims(s), Q(s, a) = avg reward(next(s, a)), tensor(s) is a tensor representation of the state, P NN (tensor(s)), output of the action head of the neural network, is also a tensor shaped as the output space -e.g. in Go or Hex the output tensor shape is the board size1 . Each action a is identified to a location in the output tensor of the action head, so that Proba NN (tensor(s))(a) is a real number, namely the logit of the probability of choosing action a according to the neural network in state s. Please note that the log has been removed. The parameter k has been multiplied by the probabilities provided by NN.

Second, when a simulation reached a state in which no statistics are available (because no simulation has been performed here), instead of returning the reward of a random rollout until the end of the game, we return the reward estimated by V NN . The NN has therefore the double impact of (i) biasing the tree search (ii) replacing the random part of the rollouts by neural estimates of value.

1.1.4. Zero training: how the NN is modified by the MCTS Let us generate games with a zero-model as above, using e.g. M = 600 simulations per move. Each time a game is over, we have a family of 3-tuples (s, p, r), one per visited state in this game:

• r is the final reward of the game.

• p is the tensor of frequencies in the MCTS simulations at s. More precisely, with a an action identified to a location in the output tensor as above, p(a) = n mcts,s,a /M where n mcts,s,a is the number of the simulations which have chosen action a, among the M simulations starting at s.

These 3-tuples are then used for training the network so that π NN imitates p and V NN approximates the reward. We also use a weight decay as a regularization, so that the overall loss is

Loss(NN) = (s,r,p)
CrossEntropy(p, Proba NN (s, .))

+ ||r -V NN (s)|| 2 + c L2 ||θ|| 2 1.1.

Overall architecture

There is a server (typically for us 8 GPUs) and many clients (tested up to 500 GPUs and 5 000 cores in our experiments):

• The server receives 3-tuples (s, p, r) from the clients. It stores them in a replay buffer (with default size 1 000 000 in our implementation), in a cyclic manner. It trains the NN as in Section 1.1.4, also cycling over the replay buffer. • The clients send data (3-tuples) to the server.

The number of clients should be tuned so that the cycles performed by the trainer are just a bit faster than the speed at which data are provided; Section 2.4 provides a robust solution for ensuring this, in particular for low computational power.

Other open-source frameworks

Many teams have replicated and sometimes improved the Alpha Zero approach for different games.

Elf/OpenGo [START_REF] Tian | ELF OpenGo: An Analysis and Open Reimplementation of AlphaZero[END_REF] is an open-source implementation of AlphaGo Zero for the game of Go. After two weeks of training on 2 000 GPUs it reached superhuman level and beat professional Go players. Compared to Elf/OpenGo, Polygames features a wide library of games, boardsize-invariance, and growing architectures.

Leela Zero [START_REF] Pascutto | Leela Zero[END_REF] is an open-source program that uses a community of contributors who donate GPU time to replicate the Alpha Zero approach. It has been applied with success to Go and Chess. Compared to Polygames, its library of games is smaller, it is not boardsize-invariant and does not support growing architectures.

Crazy Zero by Rémi Coulom is a zero learning framework that has been applied to the game of Go as well as Chess, Shogi, Gomoku, Renju, Othello and Ataxx. With limited hardware it was able to reach superhuman level at Go using large batches in self-play and improvements of the targets to learn such as learning territory in Go. While the predicted final territory information (attribution of each location on the board) is not used by the Zero player, learning territory, as a side information in Go, increases considerably the speed of learning. Polygames does not have this clever use of side information. This is under progress. Polygames, on the other hand, features a large library of games, boardsize invariance, and growing architectures.

KataGo [START_REF] Wu | Accelerating Self-Play Learning in Go[END_REF] is an open-source implementation of AlphaGo Zero that improves learning in many ways. It converges to superhuman level much faster than alternative approaches such as Elf/OpenGo or Leela Zero. It makes use of different optimizations such as using a low number of playouts for most of the moves in a game so as to have more data about the value in a shorter time. It also uses, as a side information for training the neural network, additional training targets so as to regularize the networks. Compared to KataGo, Polygames has a wide library of games, boardsize invariance, diversity of opponents for the training, and growing architectures.

Galvanise Zero [START_REF] Emslie | Galvanise Zero[END_REF]) is an open-source program that is linked to General Game Playing (GGP) [START_REF] Pitrat | Realization of a general game-playing program[END_REF]. It uses rules of different games represented in the Game Description Language (GDL) [START_REF] Love | General game playing: Game description language specification[END_REF], which makes it a truly general zero learning program able to be applied as is to many different games. The current games supported by Galvanise Zero are Chess, Connect6, Hex11, Hex13, Hex19, Reversi8, Reversi10, Amazons, Breakthrough, International Draughts. Contrarily to Galvanise Zero, Polygames is based on compiled C++ game descriptions, and uses growing architectures and boardsize-invariant neural networks.

To the best of our knowledge, besides differences pointed out above, Polygames is the only framework featuring a population of models (the past checkpoints), ranked by an ELO scale and used for sampling sparring partners for the training. It is also the framework in which growing architectures are most systematized. The convolutional layers preserve the spatial coordinates of the shapepossibly not the depth, i.e. the number of feature maps. The number of parameters of those layers, therefore does not depend on the board size, and a same neural network can work in 9x9 Go and 19x19 Go (or Hex, etc). On the other hand, each neuron in the fully connected layers has one weight per location in its input tensor (plus the bias weight), so that a neural network with fully connected layers is not boardsize-independent. This can be solved in two different manners: (1) using only convolutional layers, which is possible when the output tensor has the same spatial shape as the input tensorwhich is the case, for many games, in the case of the action head of the neural network in zero-learning (2) applying global pooling, before the fully connected layers, for reducing the spatial dimensions to (1x1). In Polygames, we apply (1) for the actor head of the neural network and (2) for the critic head, so that our neural networks are boardsize invariant (Section 2.1.2). The resulting architecture is presented in Fig. 2.

Fig. 2. Structure of a boardsize invariant neural network in Polygames. H × W is the board size (spatial coordinates). F i is the number of input channels. F 1 and F 2 are the number of channels in the first and second convolutional layers (in real experiments there are way more layers). The input (more precisely, the tensor representation of the input state) is on the left. The output has two heads: the policy (also known as actor, at the top) and the critic, which approximates the value. The only fully connected layer is for predicting the value: importantly, it is based on the output of a global pooling layer, so that it does not depend on the boardsize. Using global pooling before the fully connected layer and convolutional layers everywhere else, we get a boardsize invariant neural network. F 1 , F 2 , F 3 , F 4 are fixed parameters, independent of the board size.

INNOVATIONS

Some innovations in Polygames consist in using ideas from computer vision inside Zero learning (Section 2.1): global pooling, fully convolutional neural networks. We also use a diverse set of opponents for filling the replay buffer (i.e. the current model plays against previous models sampled according to their ELO rank as described in Section 2.3), and growing architectures (Section 2.2). These elements are detailed in the present section.

2.1. Structured zero learning 2.1.1. Fully convolutional models: taking into account the natural mapping between inputs and outputs

Many zero-learning methods are based on traditional convolutions, followed by fully connected layers. However, policy learning in board games is often closer to image segmentation (i.e. several output values per input pixel) than to classical image classification (fixed output size, independent of the number of pixels) as actions are naturally mapped on boards (a vector of logits for each location on the board). More precisely, for many games:

• The input has various channels, and two dimensions matching the board size (spatial dimensions; see Fig. 1). • Similarly, the output of the network has various channels, corresponding to various possible moves, and two dimensions matching the board size as well.

Therefore, we can apply fully convolutional models -not a single fully connected layer is necessary in the policy part. This contributes to scale invariance (Section 2.1.2) but also takes into account the partial translation invariance of policy learning. Polygames features fully convolutional networks [START_REF] Shelhamer | Fully Convolutional Networks for Semantic Segmentation[END_REF], residual fully convolutional networks [START_REF] He | Deep Residual Learning for Image Recognition[END_REF], including with global pooling [START_REF] Wu | Accelerating Self-Play Learning in Go[END_REF] as detailed below for scale invariance, and U-networks [START_REF] Ronneberger | U-Net: Convolutional Networks for Biomedical Image Segmentation[END_REF].

Scale invariant models

The widely cited [START_REF] Marcus | Innateness, AlphaZero, and Artificial Intelligence[END_REF] pointed out that zero-learning frameworks are not boardsize invariant. In the present section, we point out that Polygames learns in a boardsize invariant manner. As usually in zero learning, our neural network has two heads: one for the policy and one for the value.

The one for the policy is fully convolutional (Section 2.1.1), and therefore it works independently of the input size, i.e. independently of the board size. The value part, however, does not have this property if it is fully connected. We therefore use global pooling as in [START_REF] Wu | Accelerating Self-Play Learning in Go[END_REF]. Global pooling replaces each channel c, of shape possibly boardsize×boardsize×1, by several channels, such as the maximum and the average of c. This maximum and this average are computed over the boardsize × boardsize entries. We therefore get a boardsize-independent representation, of shape 1 × 1 × number o f channels. Our Hex19 model was trained in 13 × 13 and was immediately strong in 19 × 19 -though we needed a bit of fine tuning for the success story presented in Section 3.1.

Neuroplasticity

Several modifications are almost neutral when initialized close to zero:

• addition of residual blocks (i.e. switching from 12 blocks of 3 convolutional layers to 13 or 14 blocks of 3 convolutional layers); • addition of new channels;

• extension of the kernel size (from 3 × 3 to 5 × 5 or 5 × 5 to 7 × 7, etc).

Polygames provides a script "convert" that makes such a growth of the neural network easy. Training can be resumed after such extensions of the neural architectures; we can train, then grow (while preserving the quality of the model as it remains almost equal to the previous model as new weights are close to 0), then resume the training with more degrees of freedom.

Tournament mode

In order to fight catastrophic forgetting [START_REF] Mccloskey | Catastrophic Interference in Connectionist Networks: The Sequential Learning Problem[END_REF] or the red queen effect (oscillations of performance [START_REF] Johansson | Self-learning Robots using Evolutionary and Genetic Algorithms[END_REF])), we add a tournament mode, as follows. Each completed game is used for evaluating the ELO rank of players. Each client, when it must start a new simulated game, randomly draws a checkpoint in the archive. With dev the most recent checkpoint and ELO dev its ELO rank, the probability that a model with ELO rank ELO is drawn is proportional to exp(-ELO dev -ELO

400

). Then the client simulates games between the MCTS using PUCT (Eq. 2) using "dev" and a MCTS using PUCT with that model. We experimentally notice that sometimes old models come back in the race.

Other features

Checkpoints

We provide checkpoints2 for many games: Einstein Würfelt Nicht, Breakthrough, Havannah8, Havan-nah10, MiniShogi, Othello8, Othello10, Hex, and others.

Against overfitting

Heuristically, we consider that an example, in the replay-buffer, should never be seen more than 8 times. When the clients are not fast enough for filling the replay buffer, for example because of preemption of clients or slow game, we artificially add delays in the learning when an example is seen more than 8 times.

Easy addition of games

Adding a new game can be made by writing a new class that inherits from State and overrides a few methods (see the implementation of Connect Four3 as an example).

Stochastic games and some partially observable games

Polygames can handle stochastic games (see e.g. our bot "randototoro" on LittleGolem, playing the game of Einstein Würfelt Nicht), which is not that common in existing frameworks but not conceptually hard: we just need random nodes, instead of only minimization and maximization nodes. The adaptation of MCTS to partial observation is more tricky: we cannot simulate the underlying dynamics from a given state, because players have only a partial observation. Actually, [START_REF] Buffet | Optimistic Heuristics for MineSweeper[END_REF] has presented a class of partially observable games that can be converted to an equivalent stochastic game, and therefore can be handled by MCTS (and, equivalently, by Zero learning as shown by Polygames): all games in which the visible information is the same for all players. This class includes a few two-player games: for example Chinese Dark Chess: there is hidden information, but the observable part is the same for both players. It also includes all one-player games, in particular Minesweeper and Mastermind. In those games, the undecidability results such as [START_REF] Auger | The Frontier of Decidability in Partially Observable Recursive Games[END_REF] do not apply.

For self-containedness, let us explain the reasoning in [START_REF] Buffet | Optimistic Heuristics for MineSweeper[END_REF]. We do not know the state, so instead of a state, s is the history of observations: we must make a decision in a given s. This concept of history of observations is correctly defined because, by assumption, the history of observations is the same for all players. Given an history of observations s (including actions) and an action a, we can solve the transition by simulating next(s, a) by rejection sampling as follows:

(1) Consider r 1 , . . . , r n all sources of randomness up to "state" s.

(2) Randomly draw r 1 , . . . , r n and simulate a game with actions as in s and random outcomes as in r 1 , . . . , r n .

(3) If results are not consistent with the observation in s, go back to step 2. This is fully developed in [START_REF] Buffet | Optimistic Heuristics for MineSweeper[END_REF] in the case of MCTS and implemented inside Polygames for Minesweeper and Mastermind. In the case of Minesweeper, we implemented the more sophisticated method from [START_REF] Buffet | Optimistic Heuristics for MineSweeper[END_REF], faster than the rejection sampling.

SUCCESS STORIES

Results here are obtained using (i) trainings stabilized by the tournament mode (Section 2.3), (ii) architectures growing in order to double the number or parameters each time the ELO rank stagnates (Section 2.2) (iii) boardsize-invariant architectures (Section 2.1), with top performance typically obtained after 9 days with 500 GPUs (usually playing at a very strong level after 3 days).

Beating humans at Hex19

According to [START_REF] Bonnet | On the complexity of connection games[END_REF], "Since its independent inventions in 1942 and 1948 by the poet and mathematician Piet Hein and the economist and mathematician John Nash, the game of Hex has acquired a special spot in the heart of abstract game aficionados. Its purity and depth has lead Jack van Rijswijck to conclude his PhD thesis with the following hyperbole [START_REF] Van Rijswijck | Set colouring games[END_REF]: « Hex has a Platonic existence, independent of human thought. If ever we find an extraterrestrial civilization at all, they will know Hex, without any doubt.» " The rules are simple. Black and white fill an empty cell, in turn (Fig. 3). Black wins if it connects North and South, White wins if it connects West and East.

The game is made more fair by a pie rule: at the second move, the second player can decide to swap colors. The game is hard because, as a connection game, its reward is based on a global criterion (no local criterion to sum). Fig. 3 shows the first win against a top level human.

TAAI competition

At TAAI 2019, Polygames was ranked first in Othello10 (3 programs), Breakthrough (4 programs) and Connect6 (2 programs)4 . For more statistical significance, it was also successfully tested against

• WZebra and Ltbel (Othello8),

• the winner of TAAI 2018 at Connect6, namely Kavalan, and won all games (4 games against Ltbel, 4 games against WZebra 15 games against Kavalan). We show in Fig. 5 one of the games won against Kavalan at Connect6.

Havannah

Havannah was invented specifically for being hard for computers (Fig. 6). It follows the game play of Hex, also with hexagonal cells but now on an hexagonal board, and winning conditions are more diverse:

• Connecting two of the six corners wins (15 possibilities); However (third), the situation in the center is quite complicated and later it turns out that Black can win by one of two possible paths (last: White can not block both H7 and an attack on the left side). Source: LittleGolem. Our bot played multiple games since this win and never lost one, including games against Galvanise-Zero (Fig. 4). We use a single Quadro GP100, 5 minutes per move. • Connecting three of the six sides wins (20 possibilities);

• Realizing a loop (even if it does not contain empty cells) wins.

According to [START_REF] Lorentz | Early Playout Termination in MCTS[END_REF], "The state of Havannah programming is still in its early stages. Though the top programs do play at a reasonable level, about the level of somebody who has played the game for 6 months or a year, they still play with a very unnatural style, and often win their games by virtue of tactical shots missed by the human opponent. Our feeling is that Havannah programs cannot be expected to play at an elite level until they learn to play a more natural, human-like game."

Draws are theoretically possible but very rare. The game is also played with a pie rule. Some decent players have been defeated by computers, but never the best humans until Polygames. On Littlegolem, an early version won 3 games out of 4 against Mirko Rahn (Elo rank 2133), and 2 games out of 2 against tony (Elo rank 2167), who belong to the top four players on this website (see Figure 6 middle and right for examples of games). Then, a new version was trained and won two games out of two against Eobllor (Elo rank 2415): both games were quite short, with excellent opening moves by Polygames (Fig. 7). This bot, our strongest version, was using a single Quadro GP100, 40 minutes per move with a shared GPU (used simultaneously 50% for other applications), whereas the human could use a lot of times as by default on LittleGolem (there were several days per move, using vacation days and the 10 days main time + 24 hours per move -our bot was slowed down as requested by Eobllor just for reducing the overall speed but we did not use the additional thinking time).

CONCLUSIONS

We propose a state-of-the-art framework, called Polygames, that can play to various games. It is based on zero learning, with innovations detailed in Section 2, and had success stories detailed in Section 3. Polygames contains new architectures, allows architecture search thanks to neutral components addition and is stabilized by a tournament mode and an overfitting fighting method. It was widely tested in the TAAI competition and on LittleGolem (www.littlegolem.net). The source code is publicly available under an open-source license. Our plan includes ablation studies and experimenting some of the innovations -e.g. the one-player case, including partial observability as in Section 2.4.4. Eobllor won most games against the previous version of Polygames (Fig. 6), so we retrained it and got the present results. We note that the 3 fastest games lost by Eobllor, who rarely loses a game, are these 2 games and the game he lost against the previous version.

Fig. 1 .

 1 Fig.1. Traditional deep convolutional network. The convolutional layers preserve the spatial coordinates of the shapepossibly not the depth, i.e. the number of feature maps. The number of parameters of those layers, therefore does not depend on the board size, and a same neural network can work in 9x9 Go and 19x19 Go (or Hex, etc). On the other hand, each neuron in the fully connected layers has one weight per location in its input tensor (plus the bias weight), so that a neural network with fully connected layers is not boardsize-independent. This can be solved in two different manners: (1) using only convolutional layers, which is possible when the output tensor has the same spatial shape as the input tensorwhich is the case, for many games, in the case of the action head of the neural network in zero-learning (2) applying global pooling, before the fully connected layers, for reducing the spatial dimensions to (1x1). In Polygames, we apply (1) for the actor head of the neural network and (2) for the critic head, so that our neural networks are boardsize invariant (Section 2.1.2). The resulting architecture is presented in Fig.2.

Fig. 3 .

 3 Fig. 3. Game of Hex 19x19 with Pie rule played by Polygames against Arek Kulczycki, Winner of the last LG tournament, ranked first for the ELO ranking (ELO 2248) on the LittleGolem server. First: opening. Second: at that stage, the human (White) seems to win -two solid groups are connected to East and West respectively, and look close to connect each other.However (third), the situation in the center is quite complicated and later it turns out that Black can win by one of two possible paths (last: White can not block both H7 and an attack on the left side). Source: LittleGolem. Our bot played multiple games since this win and never lost one, including games against Galvanise-Zero (Fig.4). We use a single Quadro GP100, 5 minutes per move.

Fig. 4 .

 4 Fig. 4. Results of our bot Mootwo since its game in Fig. 3.

Fig. 5 .

 5 Fig. 5. Game won by Polygames against Kavalan: move 26 (left), which made the situation excellent for Polygames, and final position (right). Polygames won 15 games out of 15.

Fig. 6 .

 6 Fig. 6. Left: The game of Havannah and the three different ways for winning. Middle: a win by Polygames against Tony, Elo rank 2167. Right: a win against Mirko Rahn, Elo rank 2133, winner of many Havannah tournaments. Sources: wikipedia (left) and LittleGolem (middle and right).

The output of the neural network is actually corrupted by a Dirichlet noise: rather than o = Proba NN (tensor(s)), we use .75o + .25DirichletNoise(1/numMoves), where numMoves is the number of legal moves in s. This is close to what was already done in(Silver et al.,

2017).

http://dl.fbaipublicfiles.com/polygames/checkpoints/list.txt

https://github.com/facebookincubator/polygames/blob/master/games/connectfour.h

https://www.tcga.tw/taai2019/en/

ACKNOWLEDGEMENTS

We are grateful to Wikipedia and LittleGolem as image sources and platforms for running experiments. We are grateful to human players who accepted to play with our bot, in particular Eobllor who beat successive preliminary versions of our bot. This work was supported in part by MOST under contracts 109-2634-F-259-001-through Pervasive Artificial Intelligence Research (PAIR) Labs, Taiwan. Tristan Cazenave is supported by the PRAIRIE institute.


Elie Bouttier
email: elie.bouttier@enseeiht.fr

Riadh Dhaou

Fabrice Arnal
email: fabrice.arnal@thalesaleniaspace.com

Cédric Baudoin
email: cedric.baudoin@thalesaleniaspace.com

Emmanuel Dubois
email: emmanuel.dubois@cnes.fr

André-Luc Beylot
email: beylot@enseeiht.fr

Élie Bouttier

Heterogeneous multipath networks: Flow vs Packet based routing in a size-aware context

come

I. INTRODUCTION

Internet usage is growing very fast, leading to an exponential bandwidth increase. Thereby, internet infrastructures need to be upgraded to face these new requirements. While there is a massive deployment of fiber (FTTH) in some cities, other areas do not evolve. That is the case for rural areas where modernization costs are prohibitive given potential customers. Hence these areas become underserved regarding new bandwidth standards.

Satellite networks allow bringing a high bandwidth internet access at a moderate cost of deployment which provides users with new services they could not or hardly use before like video on demand (VoD), video streaming, geolocation services, photo gallery, etc. However, satellite access suffers from the significant delay introduced by the signal propagation between the Earth and the geostationary orbit leading to a notable negative impact on user Quality of Experience (QoE). Interactive services, like video games or web traffic, suffer particularly badly from this long delay. From this perspective, a hybrid network associated with a smart routing policy may provide better QoE for end users by using the best of both networks.

Several techniques exist, in the literature, to efficiently exploit the diversity of paths. Indeed, multipath networks provide among others a better throughput, robustness to congestion and resilience to breakdown. They can be classified into two classes, flow-based routing schemes, and packetbased routing schemes, the first class being a subset of the second one. Packet-based routing offers new possibilities compared to flow-based routing. For instance, it allows to aggregate the capacity of different paths for the same flow or to balance the load between several paths at a finer scale.

However, heterogeneous networks bring specific issues. Indeed, differences in speed, latency or packet loss reveal several problems to exploit the different links properly. Especially, packet-based routing schemes, associated to paths with differents delays, worsen out-of-order delivery of packets, which is misunderstood by TCP congestion algorithm. Thereby, packet-based routing in heterogeneous environments needs specific mechanisms to work properly.

To avoid the bad effect of out-of-order packets, different solutions have been proposed like reordering buffer at the end side of the heterogeneous networks [START_REF] Piratla | Reordering of packets due to multipath forwarding -an analysis[END_REF] or to voluntarily send packets in disorder in a way to receive them in order [START_REF] Chebrolu | Bandwidth aggregation for real-time applications in heterogeneous wireless networks[END_REF]. Some works [START_REF] Lai | Does it hurt when others prosper?: Exploring the impact of heterogeneous reordering robustness of tcp[END_REF] try to improve TCP reordering robustness to make it suitable for heterogeneous networks. The new transport protocol Multipath-TCP (MP-TCP) [START_REF] Paasch | Multipath tcp in the linux kernel[END_REF] can effectively aggregate path throughputs by using separate TCP sub-flows for each path.

These proposals try to maximize different metrics like link occupancy or aggregate capacity. However, the lack of relevant flow information leads to bad routing decision, especially by sending delay sensitive data on the satellite path, which significantly reduces the end-user QoE. In this paper, we consider a Content Delivery Network (CDN) context. The studied architecture, presented in II, allows accessing the content information, in particular, the flow size. Furthermore, the managed context allows deploying specific hybrid routing mechanisms. In this size-aware context, we aim to study the interest from a QoE point of view of packet-based routing compared to flow-based routing.

After the introduction of the architecture, we present the MinFCT flow-based and size-aware routing scheme introduced in [START_REF] Bouttier | Analysis of content size based routing schemes in hybrid satellite and terrestrial networks[END_REF]. Section IV exhibits different packet-based routing schemes, namely size-aware path aggregation as well as severals complementary mechanisms which aim to improve flow-based routing. Then, we describe the implementation of a simulation framework, to evaluate the performance of the proposed routing schemes. Finally, we conclude on pros and cons of flow-based and packet-based routing schemes in our size-aware and heterogeneous context.

II. ARCHITECTURE

A. Overall architecture

Studied routing schemes operate on a multipath architecture represented in figure 1. This architecture allows a home network to access the Internet through a multipath network composed of a terrestrial and a satellite path. These paths are supposed to be the bottlenecks of the network. The multipath network is operated by a virtual Internet Service Provider (ISP) which manages it through two gateways located on each side and which operate as Layer 7 proxies. We reuse the terminology introduced in [START_REF]CDN Interconnection Metadata[END_REF] with the Intelligent User Gateway (IUG) located on the user side and the Intelligent Network Gateway (ING) located on the network side.

The virtual operator also manages its telco Content Delivery Network (CDN) interconnected with several upstream CDNs through Content Delivery Networks Interconnection (CDNI) protocols [START_REF]Content delivery networks interconnection (cdni) working group[END_REF]. Thereby, the hybrid operator can access flow information, especially the size, for contents hosted on these upstream CDNs by different Content Providers. CDNI provides a specific interface to get this kind of information called the Metadata Interface (MI) [START_REF] Niven-Jenkins | CDN Interconnection Metadata[END_REF].

Each gateway has to choose on which path each flow should be routed. In flow-based routing schemes, each flow is assigned to only one path. Conversely, in packet-based routing schemes, each flow can be routed on both paths simultaneously and/or reassigned from one path to another. We do not consider here the protocol aspects of the architecture, which will be subject of further works.

B. Scheduling choices

Although the Shortest Remaining Processing Time (SRPT) discipline is known to give the best performance in a G/G/1 queue [START_REF] Smith | Technical note-a new proof of the optimality of the shortest remaining processing time discipline[END_REF] and so traditional networks, it is seldom used as it is unfair and causes large flows starvation. To ensure fairness in our multipath context, concurrent flows on the same path are served accordingly to a Fair Flow (FF) scheduler which attempts to emulate the fairness of the Processor Sharing (PS) model. This scheduler ensures an asymptotic equal throughput between flows assigned to the same link. As well as ensuring fairness, this choice allows observing routing schemes performance in a way decorrelated from scheduling effects.

The Fair Flow scheduler is an adaptation of the Fair Queueing (FQ) scheduler [START_REF] Nagle | On packet switches with infinite storage[END_REF] [START_REF] Demers | Analysis and simulation of a fair queueing algorithm[END_REF] which was designed for packet switched router. It is based on the concept of virtual time. This quantity corresponds to the assumed last service time of each flow, if the flows are fairly served. The virtual time is initialized to the flow arrival time. Every time a link is available, the flow to be served is selected according to the following formula:

argmin { virtualtime + ⋅ min ( , payload) }
with the number of flows currently assigned to the link , the remaining amount of bytes of flow , the capacity of the link and payload being the maximum payload size of a packet. The served flow virtual time is then updated as follows:

virtualtime ← virtualtime + ⋅ min ( , payload)

III. FLOW-BASED ROUTING SCHEME: MINFCT

For the remainder of this paper, we compare packet-based routing schemes to the flow-based size-aware MinFCT routing scheme presented in [START_REF] Bouttier | Analysis of content size based routing schemes in hybrid satellite and terrestrial networks[END_REF]. This scheme aims to minimize the average Flow Completion Time (FCT) by choosing the best path for each given flow. The following formula, which takes the content size into account, gives the path to which the flow should be assigned:

argmin { + ( + 1) ⋅ + ∑ =0 min( , )
} It consists in estimating, for each path , the completion time of the considered flow of size and chooses the path which minimizes this quantity. The flow completion time is assessed from the delay and capacity of the path, known or estimated from Management Information Base (MIB), TCP-stack or Throughput Guidance [START_REF] Jain | Mobile Throughput Guidance Inband Signaling Protocol[END_REF] for instance, and the number of flows already assigned to the path . is the remaining amount of data of flow .

The transmission time estimation supposes that each flow receive an equal part of the overall available capacity. However, the number of flows sharing a path varies over time, according to flow arrivals and departures. While departures can be predicted thanks to the knowledge of flows size, arrivals remain unpredictable. Thus, we observed that, instead of predicting flow departures, considering a constant number of competing flows to estimate the Flow Completion Time gives good results.

The fact to assign a flow to a path will slow down other flows already assigned to the same path. This is taken into account by adding, for each flow assigned to the path , an additional transmission time min ( , ) where is the remaining amount of data to be transferred before the flow ends.

IV. PACKET-BASED ROUTING SCHEMES

In this section, we present different routing mechanisms which come out of the flow-based class. This means different packets belonging to the same flow may be routed through different paths.

A. Size-aware aggregation

Aggregation consists in splitting up, for a given flow, the set of packets on both paths, allowing to obtain an increased throughput for the given flow. Although this is beneficial for large flows, short flows suffer from the large satellite propagation delay which may prove to be greater than the flow completion time on the terrestrial path only. For a given flow , the aggregation with the satellite network is useful only if the remaining amount of data to transfer verifies the following inequality:

⋅ + > (1)
where is the number of flows, the capacity of the terrestrial path and (resp. ) the propagation delay of the terrestrial path (resp. of the satellite path). Thereby, the size knowledge prevents performance degradation due to the satellite delay. Let's notice that a large flow can be, first, aggregated on both paths until the remaining amount of data becomes small enough to invalidate the previous inequality. This mechanism allows to synchronize the reception of last bytes on both paths. We call this behavior Tail Sync, and the Aggregation Threshold designates the minimum amount of remaining data necessary to trigger satellite aggregation (which depends on the number of transmitting flows ).

However, we do not expect significant improvements from the aggregation compared to the flow-based routing, as soon as several flows are in competition. Indeed, the terrestrial bandwidth is precious as it is not subject to the long satellite propagation time. Thereby, sending packets of the same flow on both paths is a waste of terrestrial bandwidth because it could be used beneficially to others short flows that we would send on the terrestrial path only. As the terrestrial capacity is lower than the satellite one, the aggregation benefit for large flows does not worth the potential bandwidth savings for short flows.

B. Idle Link Opportunistic Aggregation (ILOA)

Although aggregation is susceptible to degrade the performance with concurrent flows, it can still be used positively under low load. Thereby, the Idle Link Opportunistic Aggregation (ILOA) mechanism aims to be used together with a flow-based routing scheme, for instance MinFCT, and consists in allowing a path to be used for aggregation only if there are no flows currently assigned to this path (idle link). In this case, the served flow is chosen between the flows assigned to other links accordingly to the Fair Flow scheduler. Here again, the size-aware condition on satellite aggregation is used to avoid the degradation of performance due to the large propagation time. This mechanism should allow a single flow to benefit from multiple paths capacities without degrading the performance of the competing flows.

C. Reassignment

The reassignment mechanism is also associated with a flowbased routing scheme like MinFCT. It consists in forgetting all flows assignment and re-playing the allocation scheme according to a given policy discussed in the following. The objective is to favor short flows to be assigned to the terrestrial networks. Therefore, the allocation scheme is replayed on the flows, sorted from the flow having the least remaining bytes to send to the one having the most remaining bytes.

This mechanism is expected to improve the performance by relocating some flows, as networks conditions evolve, to stay close to the optimal allocation. Thereby, some flows can be reassigned from the terrestrial to the satellite path as the terrestrial network becomes congested, for example, due to a burst of short flows. Conversely, some flows can be reassigned from satellite to terrestrial path as this last one becomes available due to previous flow ends.

We consider two possibilities to choose reassignment moments:

• on each flow arrival or flow completion • periodically, with a given period Arrival and departure epochs seem to be the best moments to trigger the reassignment mechanism as they provoke an evolution of the situation. However, these moments can be very close under high traffic networks condition, which can lead to computational issues. Periodic reassignment is a way to make the implementation of the reassignment mechanism scalable so that we will only focus on it.

This mechanism needs to slightly modify the MinFCT allocation scheme. First, we no longer consider the initial flow size but naturally the remaining amount of data to be sent. Secondly, we need to avoid reallocation from satellite to terrestrial path when the benefit from reallocation is smaller than the time for packets in flight on the satellite link to arrive. Thereby, we save terrestrial bandwidth for other short flows. This is accomplished by memorizing the last packet sending time on each link. With this information and an estimation of the path latency, the remaining flight time can be estimated and compared to the estimated flow completion time as computed in the regular MinFCT scheme. We refer to this mechanism as FlightTime.

V. EXPERIMENTATION Finally, we implemented a simulation environment in order to evaluate the performance of proposed routing mechanisms. The simulator framework is composed of a test client which retrieves HTTP objects from a content server through both Intelligent Gateways using SOCKS [START_REF] Leech | Socks protocol version 5[END_REF]. As the IUG always send the content request through the terrestrial path, the ING implements the evaluated routing schemes. The test client implements a pool of users. Each user follows the given cycle:

1) waiting for a random time;

2) sending a request for a given content;

3) waiting for the reception of the last byte of the content. We observe the Flow Completion Time (FCT), which is the elapsed time between the sending of the request and the reception of the last part of the content. This metric is used to evaluate the end-user Quality of Experience, considering that short flows are more delay sensitive (e.g. web traffic) than large flows (e.g. video streaming).

The average waiting time is 1 second. The size of requested contents is equal to a multiple of the payload of a packet, the number of packets follows a Zipf law. The law is shifted to ensure a minimum flow length of 7 packets and truncated to a maximum flow length of 6000 packets; the Zipf law parameter is 1.8. Packets have a payload of 1450 bytes with a header of 50 bytes. Experiments are done using UDP with perfect links (no losses) between Intelligent Gateways, which avoid the side effects of a reliable transport protocol. The terrestrial path has a capacity of 2Mbits/s with a 20 ms delay while the satellite path has a capacity of 8Mbits/s with a 300 ms delay.

A. Size-aware aggregation

Figure 2 shows a comparison in a size-aware context between flow-based routing with MinFCT and packet-based routing with an aggregation mechanism. The curves represent the average Flow Completion Time for different number of users in the system. In most situations, the aggregation significantly deteriorates the performance, confirming our assumption that aggregation is a bad idea as soon as there are several competing flows.

For very few users, the aggregation scheme can slightly outerperform MinFCT due to the aggregation of terrestrial and satellite bandwidths for large flows. However, the observed gain is low, among others due to the large difference between the terrestrial and the satellite capacities which limits the benefit of the aggregation. Moreover, only large flows which exceed the Aggregation Threshold can benefit from aggregation but they are few. Indeed, the flow size follows a Zipf which is characterized by a long-tailed distribution, explaining the low gain on average.

We can compare in figure 3 the terrestrial and satellite link occupancy for the MinFCT and the size-aware aggregation routing schemes. We observe that the terrestrial path is less busy under MinFCT routing scheme compared to the aggregation. In fact, the terrestrial path is reserved for short flows, allowing to obtain better performance as observed in figure 2.

The size-aware aggregation performance, in blue in figure 2, shows two points of inflection corresponding, first, to the saturation of the terrestrial path, then, to the saturation of the satellite path, which can be verified on figure 3. The MinFCT routing scheme avoids the first inflection point by preventing the terrestrial congestion. This is another explanation of the better results obtained with MinFCT.

B. Idle link opportunistic aggregation

As link aggregation is beneficial under low load but harmful under high load, the Idle Link Opportunistic Aggregation (ILOA) mechanism allows aggregation only on idle link. Figure 4 shows a comparison of the average FCT under MinFCT with and without opportunistic aggregation. We observe that Fig. 4. Comparison of MinFCT with and without Idle Link Opportunistic Aggregation. The opportunistic aggregation mechanism fully mitigates the performance degradation obtained with size-aware aggregation. ILOA even allows to improve MinFCT performance but the gain is very small due to the chosen law and the large difference in path capacities. Fig. 5. Gain of ILOA mechanism for different flow lengths. For short flows which do not exceed the Aggregation Threshold, the gain is zero. For large flows, the gain is up to 35%.

MinFCT with opportunistic aggregation slightly improves the performance compared to standard MinFCT, as size-aware aggregation in situations with few users only. However, this gain is present for a large number of users whereas sizeaware aggregation deteriorated the performance. The benefit remains low for the same reasons as stated for size-aware aggregation, namely the large difference in path capacities and the chosen law, which limits the number of large flows. Nonetheless, for closer path capacities or considering an advantageous distribution in large flows, we can expect a better improvement.

Figure 5 represents the gain of the ILOA mechanism under the MinFCT assignment scheme for different flow lengths. Here, there are no concurrent flows so link aggregation can be fully exploited. Path capacities are, here, closer compared to the others experiments. For flows shorter than the Aggre-Fig. 6. Gain brought by reassignment using a 100 ms reassingment period. Reassignment only shows a small performance improvement.

gation Threshold, the gain is obviously zero as the flow is fully sent on the terrestrial path. For flows larger than the Aggregation Threshold, the gain increases with the flow length as the transmission time becomes predominant in front of the propagation time. The gain is up to 35%, close to the optimal, which is 37.5% for given path capacities. For the path capacities usually used in the others experiments -2 Mbits/s vs. 8 Mbits/s -the gain is up to 20% for large flows. As stated before, the expected average gain is strongly dependant of the distribution of short and large flows.

C. Reassignment

Figure 6 shows a comparison of performance obtained with and without reassignment using the MinFCT allocation scheme. The results only show a little improvement in favor of the reassignment mechanism. The experiment is conducted using a 100 ms reassignment period; others period have been tested without observing a better improvement. The reasignment mechanism is also reproducing the Tail Sync behavior: when the remaining amount of data to be sent of a large flow becomes smaller than the Aggregation Threshold, the flow becomes relocated on the terrestrial path. However, the benefit of this reassignment is equal to the loss inflicted to terrestrial flows -current or future -future ones not being taken into account in the reassignment decision. This is part of the explanation of the low improvement brought by this mechanism. While experiments have been realised with a constant law shape and constant path capacities, we can expect a better improvement in a more dynamic environment. As the ILOA mechanism, the gain is strongly dependent of flow size distribution, particularly the distribution of medium flow. Indeed, these are more likely be reassigned from one path to another compared to short or long flows for which the routing decision is unlikely to evolve.

The FlightTime mechanism should prevent reassignment from satellite to terrestrial path if the gain of the operation is void in the light of the need to wait for in-flight packets on the satellite path. Figure 7 allows observing the effect of the FlightTime mechanism. As expected, the reassignment hit ratio from satellite to terrestrial path is significantly reduced. We observe also a small reduction of reassignment hit ratio from terrestrial to satellite path, which corresponding to situation where the gain of the reallocation is very low. However, this mechanism does not significantly affect the average flow completion time. A real implementation of an relocation procedure requiring a synchronization protocol, with a inherent overhead, the FlightTime mechanism is still attractive to reduce reassignments and related overheads.

VI. CONCLUSION

In this paper, flow-based and packet-based routing mechanisms in a size-aware context have been compared. We, first, eliminate path aggregation as it degrades the Flow Completion Time due to an overuse of terrestrial path which is beneficial for short flows. Then, propose differents packet-based mechanisms to improve the behavior of flow-based routing. These proposals do not show any notable improvement apart from few specific cases. Finally, studied flow-based routing give good results without the need for finer scale routing mechanisms in the size-aware considered context.

In our ongoing works, we are testing these routing schemes in a realistic environment with a reliable transport protocol. We are considering differents usage of the TCP transport protocol: a TCP sub-flows per path and per content, a pool of pre-established TCP flows, etc. Proposed improvement mechanisms, like Idle Link Opportunistic Aggregation or Reassignment, need inventive operation to be implemented efficiently. As our results show the low interest in packet-based algorithms, overcoming these implementation difficulties does no seem to be worth it. However, specific advantageous situation like low traffic condition could be identified in order to use specific appropriate mechanisms. Finally, our mechanisms will also be compared to MP-TCP which stands as the new reference for aggregation especially in heterogeneous networks.

Fig. 1 .

 1 Fig. 1. Studied architecture.

Fig. 2 .Fig. 3 .

 23 Fig. 2. Comparison of MinFCT and size-aware aggregation. The flowbased MinFCT scheme shows a better average Flow Completion Time than aggregation.

Fig. 7 .

 7 Fig. 7. Comparison of the percentage of flows subject to reassignment for MinFCT and MinFCT without FlightTime prevention. Path statistics are established on first reassignment only. We observe that taking the FlightTime into account allow to significantly reduce the number of reallocations, especially from satellite to terrestrial path.