Nicolas Jouandeau
email: n@ai.univ-paris8.fr

Optimal Player Information MCTS applied to Chinese Dark Chess

are two powerful paradigms useful in computer games. When considering imperfect information, the tree that represents the game has to deal with chance. When facing such games that presents increasing branching factor, MCTS may consider, as alpha-beta do, pruning to keep efficiency. We present a modified version of MCTS-Solver algorithm, called OPI-MCTS as Optimal Player Information MCTS, that adds game state information to exploit logical reasoning during backpropagation and that influences selection and expansion. OPI-MCTS is experimented in Chinese Dark Chess, which is a imperfect information game. OPI-MCTS is compared with classical MCTS.

I. INTRODUCTION

Alpha-beta pruning algorithm is a powerful game-tree search successfully applied in many domains. By considering the 2 players as min-player and max-player, it aims to get the best move according to : [START_REF] Browne | A Survey of Monte Carlo Tree Search Methods[END_REF] an evaluation function applied to leaf nodes; [START_REF] Kocsis | Bandit based Monte-Carlo Planning. 17th Euro. Conf. on Machine Learning[END_REF] with the backpropagation of values towards the root; [START_REF] Auer | Finite-time Analysis of the Multiarmed Bandit Problem[END_REF] with cutting possibilities depending on parents and children values. Even if alpha-beta cuts improves Minimax a lot (with a pruning that does not change the final result), their success rate highly depends on the evaluation function accuracy.

Monte Carlo Tree Search (MCTS) is another powerful game-tree search, newer than alpha-beta and also successfully applied in many domains [START_REF] Browne | A Survey of Monte Carlo Tree Search Methods[END_REF]. The first MCTS algorithm is UCT [START_REF] Kocsis | Bandit based Monte-Carlo Planning. 17th Euro. Conf. on Machine Learning[END_REF] that combines UCB formula [START_REF] Auer | Finite-time Analysis of the Multiarmed Bandit Problem[END_REF] with tree search. The great benefit of UCT is to be able of being used without expert domain knowledge.

Chinese Dark Chess (CDC) is a two-players imperfect information game played with a 4x8 rectangular board where players do not know the location of their pieces at the beginning. Even if they have the same initial material, their flipping moves will reveal pieces (own ones or opponent's ones) that will define player's color and pieces positions. Capture are only allowed from a revealed piece to another revealed piece or to an empty position. Pieces of each player are divided between 7 different types, that have to consider different constraints while they are moving. Even if flipping moves imply multiple board possibilities, classical moves can lead to similar positions during the game. CDC tournaments (mainly at Computer Olympiad (CO), Technologies and Applications of Artificial Intelligence (TAAI) and Taiwan Computer Game Association Computer Game Workshop (TCGA)) are using a Swiss system, with rounds of two games per player. The first player unable to play loses. To avoid infinite games, 3-times repetition of a position leads to draw game. When no flipping or capturing move arises within a fixed number of plies, it is also leading to draw game. The number of plies depends on teams involved, commonly 180 plies are considered.

As MCTS deals with statistics without expert knowledge, efficiency remains linked to branching factor. In TCGA and TAAI 2012, the MCTS with chance nodes program Diablo won the competition. In TCGA 2013, the MCTS program Dark-Knight won the competition ahead 4 other MCTS programs. In CO 2013, DarkKnight on again. In TAAI 2013, the alphabeta program Yahari won the competition. In TCGA and TAAI 2014, the alpha-beta program Yahari won the competition, leaving the second place to DarkKnight during TCGA. In CO 2015, DarkKnight returned and won. As CDC has a huge branching due to the revealing moves, chances nodes allow alpha-beta to reduce the branching factor dependency. Even if chance nodes have even been used with MCTS by Diablo, we believe that a better understanding of MCTS behavior and CDC complexity [START_REF] Jouandeau | Varying Complexity in CHINESE DARK CHESS Stochastic Game[END_REF] are needed.

As adding chance nodes seems to reduce the efficiency of MCTS by sealing it in added chance layers, we propose to add game state information that could be exploited by a logical decision process to guide next MCTS iterations, to prune useless evaluations and also to backpropagate this information in the tree. We propose to add a termination status that allows logical backpropagation to define parents termination. In this way, we present a modified version of MCTS-Solver [START_REF] Winands | Monte Carlo Tree Search Slver[END_REF] applied to Chinese Dark Chess, with new selection, expansion and backpropagation functions. These new algorithm is called OPI-MCTS, as Optimal Player Information MCTS. Unlike the initial MCTS-Solver proposal, we modify the statistics of nodes according to their termination status without biasing the formula with expert knowledge. The number of playouts backpropagated differes depending on nodes types. This paper is organized as follows: Section II describes related works in CDC with alpha-beta, MCTS and other improvements. Section III presents our OPI-MCTS algorithm. Section IV shows experimental results. Section V concludes.

II. RELATED WORKS

In this section we expose related works on CDC. Recent works on this game concern alpha-beta pruning, MCTS improvements, openings and endgame databases.

Winands et al. [START_REF] Winands | Monte Carlo Tree Search Slver[END_REF] presented the MCTS variant called MCTS-Solver designed to prove the value of positions in the tree. They applied it to Lines of Action, that is a 2players perfect information game with sudden-death situations. Depending on the rules, positions that validate each players goal can lead to a win or a draw. They used a modified version of UCT formula with Progressive Bias based on precomputed knowledge of the game. Hsueh et al. [START_REF] Hsueh | Strength Improvement and Analysis for an MCTS-Based Chinese Dark Chess Program[END_REF] used MCTS with Early Playout Terminations (EPT), Implicit Minimax Backups (IMB) and Quality-Based Rewards (QBR). They showed that combining these three techniques improves CDC MCTS programs.

Lorentz [START_REF] Lorentz | Early Playout Termination in MCTS[END_REF] presented MCTS improvements with EPT in many games with different characteristics. EPT has been applied successfully to Amazons, Breakthrough and Havannah.

Lanctot et al. [START_REF] Lanctot | Monte Carlo Tree Search with Heuristic Evaluations Using Implicit Minimax Backups[END_REF] proposed a heuristic function to guide MCTS playouts. This principle, called IMB, has been applied successfully to Kalah, Breakthrough and Lines of Action. Pepels et al. [START_REF] Pepels | Quality-Based Rewards for Monte-Carlo Tree Search Simulations[END_REF] proposed to modify playouts rewards with QBR according to playout length and playout termination. QBR has been applied successfully to Amazons, Breakthrough, Cannon, Checkers and Chinese Checkers. Improvements seems to be stuck for some games like Pentalah that blinds the playout length indicator.

Chen et al. [START_REF] Chen | Chinese Dark Chess[END_REF] used alpha-beta algorithm on CDC with policies to deal with revealing pieces. They also present a way to reduce the branching factor by linking flipping moves to depth. Different policies are defined according to the advancement in game. [START_REF] Baier | Monte-Carlo Tree Search and minimax hybrids[END_REF] proposed different modifications of MCTS with minimax-like enhancements during the selection, playout and backpropagation phases to combine minimax short term evaluation and MCTS long term evaluation. Experiments on Connect-4 and Breakthrough show improvements without adding specific game expert knowledge according to depth and choosen enhanced phase. Saffidine et al. [START_REF] Chee | A Principled Approach to the Problem of Chunking in UCT[END_REF] used buffering and reevaluation to solve the problem of chunked data that could come from UCT parallelisation. The buffering hold statistics inside nodes and the reevaluation recalculates nodes statistics before a new selection. Thus nodes statistics are divided between two parts (i.e. unpropagated and propagated values) and the number of playouts considered differes from the real ones when buffering is on.

Baier and Winands

Yen et al. [START_REF] Yen | The Art of the Chinese Dark Chess Program DIABLE[END_REF], [START_REF] Yen | Design and Implementation of Chinese Dark Chess Programs[END_REF] proposed a way to combine MCTS and chance nodes [START_REF] Lanctot | Monte Carlo *-Minimax Search. 23rd Int. Joint Conf. on Artificial Intelligence (IJCAI-2013)[END_REF]. They shown useful policies called Capture First, Capture Stronger Piece First and Capture and Escape Stronger Piece First, that improved the program's level.

Jouandeau and Cazenave [START_REF] Jouandeau | Small and Large MCTS Playouts Applied to Chinese Dark Chess Stochastic Game[END_REF] presented MCTS influence of various playout length, playout policy with heuristic board evaluation. They studied group constitution related to pieces position. They compared MCTS with chance-nodes and with group-nodes. It shows that playout lengths, policies and heuristic values are dependant to these MCTS variants.

Jouandeau and Cazenave [START_REF] Jouandeau | Monte-Carlo Tree Reductions for Stochastic Games[END_REF] compared tree reduction issues for games with large branching factor. They compared different regrouping policies and nodes selection in CDC. It shows that chance-nodes regrouping policy is better without heuristic evaluation and with Minimax termination.

Chang and Hsu [START_REF] Chang | A Quantitative Study of 24 Chinese Dark Chess[END_REF] solved the 2x4 variant and demonstrate that the first move is crucial on 2x4 board. They used a Oracle variant where every pieces are known to compare solutions with optimal moves. Chen and Hsu [START_REF] Chen | Automatic Generation of Chinese Dark Chess Opening Books[END_REF] built opening databases. As flipping moves can reverse the situation, they showed that enhancements provided are probabilistically acquired.

Chen et al. [START_REF] Jr | Design and Implementation of Computer Chinese Dark Chess Endgame Database[END_REF] built an endgame databases with retrograd analysis, up to 8 revealed pieces, using 2TB of memory to represent 10 12 positions. Positions status are stored as win, lost or draw.

Saffidine et al. [START_REF] Saffidine | Material Symmetry to Partition Endgame Tables[END_REF] built endgame databases with retrograd analysis and pieces combinations pieces exploitation. By combining material, identified symmetries reduce the size of 4 pieces endgame tables by 9.92 and the size of 8 pieces endgame tables by 3.68.

Chen et al. [START_REF] Jr | Equivalence Classes in Chinese Dark Chess Endgames[END_REF] present equivalence classes computation for endgames with unrevealed pieces. Boards are identified by threats and pieces' positions that are compared in a multiple steps algorithm. Compression rates of material has been studied from 3 to 32 pieces. Endgames database has been computed with 3 to 8 pieces and its number of element is reduced by 17.20.

III. PRUNING IN MCTS

In this section, we present OPI-MCTS algorithm that combines classical MCTS with a full expansion phase, add states to prooved nodes and at last, apply different UCT formula to these nodes with virtual numbers of playouts.

A. Classical MCTS with a full expansion

Fig. 1 presents the main loop of classical MCTS algorithm. It consists in iteratively applying the 3 phases called selection, expansion and backpropagation, illustrated here respectively by the 3 functions select, expand and backpropagate. This main loop tries to get the best next move from the current board. The search is initialized with the current board that defines the root node of the tree. At each iteration, the selection phase returns the best sequence S to start with. Then the expansion phase applies S to find the part of the tree that will grow, getting new results that will be backpropagated towards shallowest nodes, hoping of getting a more promising S during next call. The number of new nodes created during an expansion phase depends on the state of the last element of S and on its number of children. If the last element of S is terminal (Fig. 3 lines 2 to 4) then a single win, draw or lost is added to statistics of q i node. Otherwise, one playout is played for each next move (Fig. 3 line 7). Thus the number of new nodes added in the tree corresponds to the number of children of q i . To improve the confidence in values in the tree, we choose to develop all children at each iteration. It allows us to get more accurate estimates of parent nodes. At the end, the best next node of the root node defines the best move. (q, w, d, l) ← expand (S) 6:

backpropagate (q, w, d, l) 7: end while 8: q ← best (root) 9: return q Fig. 1. Classical MCTS algorithm main loop that returns a node q with the best move from a current board.

select (S)

1: q ← last(S) 2: if q has no child then return S 3: q best ← bestChild (q) 4: return select (S + q best ) Fig. 2. Classical MCTS select function.

Fig. 3 presents a full MCTS expansion function. Usually, the selection is applied until positions of the tree are selected and then only one node is added. To improve the confidence in values in the tree, our expandion phase develop all children of the current node q i , to get an accurate estimates of q i . It starts with retrieving the node q i that corresponds to following the sequence S from the current board. Then it checks the state of the game, and breaks if it is a win, a draw or a lost. A new result is also added to the current node (Fig. 3 lines 2 to 4). Otherwise new moves are considered from q i , to add new nodes in the tree and to return sums of wins, draws and loses of all q i children (Fig. 3 line 13). The playout function should distinguish issues of a random game. Then res should take its values in {win, draw, lost}. As presented in related works, the playout function can be enhanced with EPT and end-game databases. q f scores that are always set to 1 here, can be enhanced with QBR.

expand (S)

1: q i ← apply (current board , S) 2: if q i is a win then return (q i , 1, 0, 0) 3: if q i is a draw then return (q i , 0, 1, 0) 4: if q i is a lost then return (q i , 0, 0, 1) 5: for each move m from q i do 6:

new board ← apply (q i , m)

7:
res ← playout (new board)

8:
if res is a win then q f ← (m, 1, 0, 0)

9:
if res is a draw then q f ← (m, 0, 1, 0) 10:

if res is a lost then q f ← (m, 0, 0, 1)

11: add q f as child of q i 12: end for 13: return (q i , win, draw, lost)

Fig. 3. Classical MCTS expand function.

Fig. 4 presents the classical MCTS backpropagation function. As playout simulations have been achieved in children, N value is truly set to allow children to update their UCT value with the setUctVal function. The upper confidence bounds (Eq. ( 1)) is mostly used to define UCT values with win i winning playouts at node i, N i playouts at node i and N playouts at the parent. As presented in related works, this formula can be enhanced with IMB.

argmax i   win i N i + C log(N ) N i   (1)
At last, the best function (Fig. 1 line 8) defines the child of root that maximizes win i /N i . backpropagate (q, w, d, l)

1: q.N += w + d + l 2: q.win += w 3: q.draw += d 4: q.lost += l 5: for each child e of q do 6:

setUctVal (e) 7: end for 8: if q.parent = ∅ then 9:

backpropagate (q.parent, q.win, q.draw, q.lost) 10: end if To store more information in nodes, we added a game state information that contains the outcome of the game for optimal players. Corresponding to the common results of twoplayers games, we defined 3 values that are WIN, DRAW and LOST. The game tree is then composed with classical nodes and with nodes that hold game outcome information. As this information defines the optimal player outcome, our OPI-MCTS algorithm is carrying OPI-nodes. This allows us to settle an UCT improvements that will certainly play the optimal move according to the number of iterations performed from the current state. Improvements consist in exploiting OPInodes during selection, modifying UCT formula for OPI-nodes and taking into account OPI-nodes during backpropagation. Therefore, the main loop of our improved MCTS algorithm stops as soon as the root node is an OPI-node. In the whole process, the goal is to avoid the selection of OPI-nodes, to overestimate UCT values of WIN OPI-nodes, to underestimate UCT values of DRAW and LOST OPI-nodes.

B. Exploiting OPI-nodes

One way to exploit OPI information should be to add virtual win, draw or lost to these nodes. Such issue is not easy due to the UCT formula that contains an exploitation part and an exploration part, where OPI concerns only the exploitation part. On the other way, we choose to keep statistics as they are and just remove these nodes from the MCTS selection phase. Fig. 5 presents the OPI-MCTS selection function. This function recursively selects the bestNonOpiChild node according to statistics while nodes have children. As a node with only OPI-nodes children must be an OPI-node, we are free to select nodes without checking children existence as in the classical MCTS selection function. Fig. 6 presents the OPI-MCTS expansion function. As in the OPI selection function, we can retrieve q i without checking that it corresponds to a terminal game state. Compared to the classical selection function, this one is thus slightly simplified.

select (S)

1: q ← last(S) 2: q best ← bestNonOpiChild (q) 3: return select (S + q best ) Fig. 5. OPI-MCTS select function that avoids OPI-nodes encountered.

expand (S) 1: q i ← apply (current board , S) 2: for each move m from q i do 3:

new board ← apply (q i , m)

4:
res ← playout (new board)

5:
if res is a win then q f ← (m, 1, 0, 0)

6:
if res is a draw then q f ← (m, 0, 1, 0)

7:
if res is a lost then q f ← (m, 0, 0, 1)

8: add q f as child of q i 9: end for 10: return (q i , win, draw, lost)

Fig. 6. OPI-MCTS expand function with OPI-nodes.

C. OPI-nodes UCT values

According to the fact that OPI-nodes are not fairly considered in the selection phase, their final UCT-value is different at the end. As they are no more selected as soon as they are known as OPI-node, their exploration term is more important than their siblings. To fix it, we defined modifications of UCT formula to compute their final UCT value:

• For WIN OPI-nodes, we used Eq. ( 2). Their exploitation term is overestimated 100% wins that ranked them first.

• For DRAW OPI-nodes, we used Eq. ( 3). It corresponds to the average of the number of playout performed in their siblings. As we do not want to promote moves that lead to draw games, we restrict their UCT value to an exploration term, to make as much as undefined nodes more interesting than these nodes, even if they have low success rate.

• For LOST OPI-nodes, we used Eq. ( 4). Their previous DRAW OPI-nodes value is reduced by a constant factor that corresponds to a minimum success rate of classical nodes before behind worst than DRAW OPInodes.

1.0 + C log(N ) N i (2) C log(N -N i + N -Ni T -1 ) N -Ni T -1 (3)
C C 1 log(N -N i + N -Ni T -1 ) N -Ni T -1 (4)
In Eq. ( 2), ( 3) and ( 4), T defines the number of siblings of the node i. Fig. 7 presents UCT-values for classical nodes, 1), ( 3) and ( 4) for nodes with 10 siblings (i.e. T = 10) and various number of playouts. x-axis defines the number of playouts of the visualized node and y-axis shows the resulting UCT-value. Classical nodes (Eq. ( 1)) with a win success rate of 10% are in green, Classical nodes (Eq. ( 1)) with a win success rate of 0% are in red, DRAW OPI-nodes (Eq. ( 3)) are in blue * signs and LOST OPI-nodes (Eq. ( 4)) are in blue + signs. C 1 equals 0.33 in this case.

DRAW OPI-nodes, LOST OPI-nodes in similar situation. Their number of siblings is 10 and the number of playouts of their parent is 200 (that makes an average of 20 playouts per child). Green nodes are classical nodes with a success rate of 10% and red nodes are without win. Before the average of playouts per sibling, classical nodes are always better than OPI-nodes. LOST OPI-nodes are worst than DRAW OPI-nodes according to C 1 constant value.

D. OPI-node backpropagation

As we always develop all the children of a node during the expansion phase, it allows us to define the parent status by analysing children status. According to Eq. ( 2), ( 3) and (4), we backpropagate a virtual number of playouts from DRAW and LOST OPI-nodes that tries to avoid these nodes. As defined in Eq. ( 5), this virtual number of playouts is the maximum between the number of playouts N i and the average number of playouts achieved in T sibling nodes. This number of virtual simulations is backpropagate until the root node.

max N i , N -N i T -1 (5)
Fig. 8 presents the OPI-MCTS backpropagation function for w wins, d draws and l losts at a node q . Even if UCT-values are backpropagated towards parent, OPI-value can be backpropagated to parent depending on logical conditions (lines 11 to 18):

• If one child is an WIN OPI-node, then the parent is also a WIN OPI-node (line 11).

• If all children are LOST OPI-nodes, then the parent is also a LOST OPI-node (line 13).

• If all children are DRAW OPI-nodes, then the parent is also a DRAW OPI-node (line 15).

• If all children are LOST and DRAW OPI-nodes, then the parent is also a DRAW OPI-node (line 17).

backpropagate (q, w, d, l) 1: q.N += w + d + l 2: q.win += w 3: q.draw += d 4: q.lost += l 5: E ← ∅ 6: for each child e of q do 7:

setUctVal

E ← E + e 9: end for 10: if q.parent = ∅ then q.parent ← DRAW OPI-node 19: backpropagate (q.parent, q.win, q.draw, q.lost) 20: end if

IV. EXPERIMENTS

To compare MCTS and OPI-MCTS on CDC, we present results with four boards (Fig. 9) and with classical statistics of tournament between algorithms. All the pieces used are ~, }, |, {, z, y, x, , , , , , , where it corresponds respectively to pawn, cannon, knight, rook, minister, guard and king for each color (e.g. ~is white pawn and x is white king). H represents any unrevealed piece. For all these experiments, we used an exploration constant K of 0.3. In the first board (Fig. 9a), we have limited the classical MCTS with the number of iterations used by OPI-MCTS to get a result. Usually the classical MCTS algorithm is always spending all allocated iterations. In the second board (Fig. 9b), we allowed 10[sec.] to give the best move. This query has been achieved for each color. In the third board (Fig. 9c), we allowed 10k iterations for each algorithm and in the fourth board (Fig. 9d), we allowed 20k iterations for each algorithm. At last, we performed classic games between MCTS and OPI-MCTS. We played 200 games and we allowed 300[sec.] per game. While playing in these games, we allowed to spend 3% of the remaining time, thereby varying from 9 to a little less than 1[sec.].

The first board (Fig. 9a) is holding 2 pieces (one y for the red-player and one for the black-player). The starting position of the black piece is fixed on the top right corner at d -8 and the starting position of the red piece is varying between positions annoted p1 to p14. The only position recorded in the game is the starting position. Then pieces can move everywhere on the board, according to the rules (including 3-cycle restriction). Each position has been tested for red-player turn with MCTS and OPI-MCTS. Results are respectively presented in Fig. 10 and Fig. 11. According to positions, columns of Fig. 10 and Fig. 11 give the number of iterations needed, the number of nodes added in the tree, the final best red-player move, the corresponding value, the depth of the tree and the length of the best sequence after this move. In the first, MCTS corresponding value is the classical UCT-value. In the second board (Fig. 9b) , OPI-MCTS corresponding value is the game outcome or the modified UCT-value. On this first board, Fig. 10 and Fig. 11 shows that even if positions are close, their endings greatly differ in depth and in the outcome (that oscillates between WIN and LOST). Beyond giving guaranted termination, OPI-MCTS explores more nodes than classical MCTS. It shows that MCTS results are better for winning situations than for losing onces. MCTS tree depth is smaller than OPI-MCTS tree depth. Sizes of the sequence that correspond to best moves are shorter in MCTS than in OPI-MCTS. It could explain the failures of MCTS to find the optimal move. The second board (Fig. 9b) is holding move pieces, for both sides and also with some unrevealed pieces (that are |). Results are presented in Fig. 12 for each color. The difference between Red and Black comes from initial situations that are different for the two players. Black has less moves at the beginning due to the number of unrevealed pieces and more limited moves due to the position of its cannon (piece in the middle) and its guard (piece on top right corner). Results are similar for MCTS and OPI-MCTS, even in the number of iterations and nodes.

Third and fourth boards (Fig. 9c and9d) are boards that can be solved with backtracking captures. In the third, the remaining piece is y and black is to play. In the fourth, the remaining pieces are ~~~~~and black is to play. Results of MCTS and OPI-MCTS are presented in Fig. 13. It shows that OPI-MCTS gets the right moves (and knows that it is a winning move) where MCTS gets a non-optimal move (In Fig. 9c, this move will allow to play one time more than a6-b6 for example) and where MCTS gets the right move with a rating success of 70%. As presented in the last column of Fig. 13, after playing the suggested move a6 -b6 on the third board, a possible winning sequence of length 4 should be a8; d2-c2; d1-d2; d5-d2; and black wins as white has only one cannon y without possible move.

At last, we achieved matches of MCTS-OPI agains MCTS. Results are presented in Fig 14 . Independently of who is the first player, OPI-MCTS wins 63% against MCTS and lost 30% in average. The number of lost are reduced to get draw games when OPI-MCTS is the first player.

V. CONCLUSION

We have presented a new algorithm called OPI-MCTS that exploit termination information to guide MCTS selection and expansion. It comes from adding game state information to nodes and to apply a logical backpropagation of this game state information. As selection avoids known termination nodes, the expansion is fairly turned towards promising nodes and OPInodes are pruned during MCTS playouts. As possible, OPInodes are exploited to provide the final best move. As OPI-MCTS is general, it could be applied to many other games. OPI-MCTS improves classical MCTS as it wins 63% against a classical MCTS with common CDC tournament settings. It should provide better results by combining it with other improvements like EPT.

Fig. 2

 2 Fig.2presents the classical MCTS selection function. This function recursively selects the bestChild node according to statistics while nodes have children.

Fig. 4 .

 4 Fig. 4. Classical MCTS backpropagate function.

Fig. 7 .

 7 Fig. 7. Visualization of UCT values defined by Eq. (1), (3) and (4) for nodes with 10 siblings (i.e. T = 10) and various number of playouts. x-axis defines the number of playouts of the visualized node and y-axis shows the resulting UCT-value. Classical nodes (Eq. (1)) with a win success rate of 10% are in green, Classical nodes (Eq. (1)) with a win success rate of 0% are in red, DRAW OPI-nodes (Eq. (3)) are in blue * signs and LOST OPI-nodes (Eq. (4)) are in blue + signs. C 1 equals 0.33 in this case.

11 :

 11 if ∃e, e ∈ E ∧ e is a WIN OPI-node 12: q.parent ← LOST OPI-node 13: if ∀e ∈ E, e is a LOST OPI-node 14: q.parent ← WIN OPI-node 15: if ∀e ∈ E, e is a DRAW OPI-node 16: q.parent ← DRAW OPI-node 17: if ∀e ∈ E, e is a LOST or DRAW OPI-node 18:

Fig. 8 .

 8 Fig. 8. OPI-MCTS backpropagate function with OPI-nodes.

Fig. 9 .

 9 Fig. 9. Board examples for performance analysis from different positions with few pieces. Unrevealed pieces of board (b) are |. Unrevealed piece of board (c) is a y. Unrevealed pieces of (d) are five red pawns ~.

Fig. 13 .

 13 Fig. 13. MCTS and OPI-MCTS evaluates of Fig. 9c and Fig. 9d for black player.

Fig. 14 .

 14 Fig. 14. OPI-MCTS results against classical MCTS in 400 games of 300[sec.].


Aline Hufschmitt
email: alinehuf@ai.univ-paris8.fr

Jean-Noël Vittaut

Nicolas Jouandeau

Statistical GGP Game Decomposition

Keywords: General Game Playing, decomposition, Game Description Langage, causality, compound moves, serial games

This paper presents a statistical approach for the decomposition of games in the General Game Playing framework. General game players can drastically decrease game search cost if they hold a decomposed version of the game. Previous works on decomposition rely on syntactical structures, which can be missing from the game description, or on the disjunctive normal form of the rules, which is very costly to compute. We offer an approach to decompose single or multi-player games which can handle the different classes of compound games described in Game Description Language (parallel games, serial games, multiple games). Our method is based on a statistical analysis of relations between actions and fluents. We tested our program on 597 games. Given a timeout of 1 hour and few playouts (1k), our method successfully provides an expert-like decomposition for 521 of them. With a 1 minute timeout and 5k playouts, it provides a decomposition for 434 of them.

Introduction

Solving smaller sub-problems individually and synthesizing the resulting solutions can greatly reduce the cost of search for a general game player. Previous works on compound games show this and propose some approaches to solve predecomposed single games [START_REF] Cerexhe | A Systematic Solution to the (De-)Composition Problem in General Game Playing[END_REF][START_REF] Günther | Decomposition of Single Player Games[END_REF] or multi-player games [START_REF] Zhao | Decomposition of Multi-Player Games[END_REF]. Sum of games has been widely studied to solve games with specific complete decomposition [START_REF] Berlekamp | Winning Ways for your Mathematical Plays[END_REF]. However, identifying such sub-problems is an essential prerequisite. In this paper we focus on the decomposition of games described in Game Description Language(GDL).

We identify different classes of compound games [START_REF] Hufschmitt | A General Approach of Game Description Decomposition for General Game Playing[END_REF] which raise specific issues for decomposition : games using a stepper like Asteroids1 , synchronous or asynchronous [START_REF] Cerexhe | A Systematic Solution to the (De-)Composition Problem in General Game Playing[END_REF] parallel games respectively like Chinook 2 or Double Tictactoe Dengji 3 , synchronous parallel games with compound moves like Snake-Parallel 4 , serial games like Factoring-Turtle-Brain 5 , multiple games like Multiple-Sukoshi 6 and impartial games starting with several piles of objects like Nim 7 . Some characteristics of these games represent specific difficulties for decomposition. Serial games are games with sequential subgames: when a subgame terminates, another subgame starts. The second game is strongly linked to the first one as the start of the second game depends on the first game state. Compound moves are single actions that are responsible of effects related to different subgames ; the separation of these effects is critical to separate the subgames.

The Game Description Language used to described general games is a logic language similar to Prolog which uses the closed world assumption and uses negation as failure. The logical rules used to infer fluents that will be true in the next state, given a partial description of the current state and a joint move of the players, do not explicitly describe action effects. In the premises of these rules, with head predicate next, some fluents describe some aspect of the current state necessary for the rule head to be entailed but not a complete state. Therefore the exploration of each game state from initial state is necessary to know exactly in which state these rules can be entailed and what is the effect of actions. For example, frame axioms indicate fluents that keep a true value from one state to another given some specific actions: actions not present in these frame rules are those susceptible to have a negative effect. However, among those, some may be illegal when the rule applies. To identify these illegal actions, it is necessary to acquire high level knowledge on the game to know that premises necessary for action legality are incompatible with a premise of the preceding rules. However, like it has been demonstrated with STRIPS-descriptions in planning domain [START_REF] Blum | Fast planning through planning graph analysis[END_REF], a complete inference of all mutually exclusive fluents is intractable for complex games.

In this paper we propose a statistical approach based on simulation to identify the action effects and to decompose the different classes of compound games mentioned above. We first present the previous works on decomposition ( §2) then define what is a correct decomposition of a game ( §3). We present the different aspects of our method to handle the different types of compound games ( §4). We present experimental results on 597 games ( §5). Finally, we conclude and present future work ( §6). 3 At each turn a player chooses a Tictactoe grid from two to place one of his marks.

The goal is to win in both grids. 4 The goal of Snake is to move, for 50 steps, a snake that grows steadily without biting its tail. 5 Factoring Turtle Brain is a series of LightsOn games where the player has to turn on 4 lights: each lamp goes out gradually while he lights up the others. 6 Sukoshi is about creating a path by aligning ordered integers. In the multiple version only one grid counts for the score, the others are useless. 7 In Nim each player takes in turn any number of matches in one of 4 stacks. Whoever no longer has a match to pick loses.

Previous works

We assume familiarity of the reader with General Game Playing [START_REF] Genesereth | General Game Playing: Overview of the AAAI Competition[END_REF] as well as with the Game Description Language (GDL) [START_REF] Love | General Game Playing: Game Description Language Specification[END_REF]. A GDL game description takes the form of a set of assertions and logical rules. A set of keywords allows to describe the game. Figure 1 To quickly evaluate the rules and carry out simulations of the game (playouts), Vittaut et al. [START_REF] Vittaut | Fast instantiation of GGP game descriptions using prolog with tabling[END_REF] propose a fast instantiation using Prolog with tabling that builds a rule graph similar to a propnet [START_REF] Schkufza | Propositional Automata and Cell Automata: Representational Frameworks for Discrete Dynamic Systems[END_REF]. This rule graph is transformed into a logic circuit [START_REF] Vittaut | LeJoueur : un programme de General Game Playing pour les jeux information incomplète et/ou imparfaite[END_REF] which can be quickly evaluated using binary operators. This circuit uses the head of legal, next, goal or terminal rules as outputs, and fluents (true) and actions (does) as inputs.

Günther et al. [START_REF] Günther | Factoring General Games[END_REF] propose a decomposition approach for single player games by building a dependency graph between uninstantiated fluents and actions nodes: the connected components of the graph represent the different subgames. Edges are potential preconditions, positive and negative effects between fluents and actions while action-independent fluents are isolated in a separate subgame to prevent them from joining all subgames. Their program is tested on the game Incredible.

Zhao et al. [START_REF] Zhao | Decomposition of Multi-Player Games[END_REF] present an extension of this approach to multi-player games using partially instantiated fluents and actions in the dependency graph. Serial games and compound move games are treated separately [START_REF] Zhao | Decomposition of Multi-Player Games[END_REF] and their detection heavily rely on game description syntactic structures : rewriting some GDL rules can prevent decomposition. For serial games, they use a separate specific detection: a predicate like game1over in Tictactoe Serial which is false in the legal rules of the first subgame and true in the legal rules of the second one is used to split the game. Results are presented on the games Nim, Double CrissCross2 and several variants of Tictactoe (Double, Serial, Parallel ).

In [START_REF] Hufschmitt | A General Approach of Game Description Decomposition for General Game Playing[END_REF], we propose an approach which is more general but also off-line like the aforementioned ones. It relies on weak heuristics to identify the effects of actions: effects not explicitly described are ignored and can induce over-decomposition. To solve the problem of the compound moves, we identify meta-actions sets which represent a single effect of a compound move: a compound move with N effects is part of N meta-action sets and actions with a single effect are metaaction singletons. These meta-actions are sets of actions which have an identical effect on a fluent of a particular subgame in the same conditions i.e. with the same preconditions in the rules describing the next state and with at least one fluent in common to precondition their legality. However this detection requires the costly calculation of completely developed disjunctive normal form (DNFD) of the game rules. The detection of serial games is limited to two subgames. To separate them, this approach looks for expressions capable of partitioning the legality of actions into two groups. The approach also detect useless subgames i.e. with no influence on score, game termination and, in the case of serial subgames, not allowing another usefull subgame to start. We consider actions of these games as noop actions that can receive the same evaluation during the game exploration. This decomposition is tested on 40 games : 7 games from trivial (Tictactoe) to complex (Hex ) and 33 compound games representative of the different classes presented.

To limit the computation time, another version uses partially developed disjunctive normal form (DNF) : auxiliary predicates are preserved as atoms and are not completely developed. The decomposition using the DNF is quicker: for some games, time decreases from one hour with DNFD to one second with DNF (fig. 8). However this version is less robust: depending on the rules formulation, meta-action detection can fail as well as decomposition. Note that both versions fail to correctly decompose Chomp and Blocker Parallel is not decomposed after a one-hour timeout.

In this paper, we propose a more robust detection of action effects based on statistical information collected during playouts. We use a circuit encoding the game rules to perform fast simulations and collect information on the correlation between fluent value changes and actions played. This circuit is also used to infer preconditions relations using propagation and back-propagation of different signals. We propose a concept of crosspoint which allows to detect junctions between independent parts of a game played sequentially and allows to decompose serial games with any number of subgames. Our approach does not require the use of DNF. We tested our approach on significantly more games than previous works (597 against 1,4 and 40).

Game, subgame and correct decomposition

A game is described by a finite state machine the structure of which is a directed acyclic graph. Let F be the set of the fluents. A state is a set s ⊂ F . A transition is a couple (s, s ) ⊂ F 2 .

A decomposition is a tuple F 1 , ...F n where n i=1 F i = F and ∀i, j, i = j :

F i ∩ F j = ∅.
In a subgame i a state is a set s i ⊂ F i and a transition is a couple (s i , s i ) ⊂ F 2 i such that there exists a transition (s, s ) ⊂ F 2 in the global game where

s i = s ∩ F i and s i = s ∩ F i .
Definition 1 (free choice of a transition) Given a state s = s 1 ∪ s 2 of a global game where s 1 is a state of the first subgame and s 2 a state of the second subgame, we can freely choose a transition (s 1 , s 1 ) in the first subgame and (s 2 , s 2 ) in the second one, if, in the global game, there exists a transition (s 1 ∪ s 2 , s 1 ∪ s 2 ) or a sequence of transitions (s 1 ∪ s 2 , s 1 ∪ s 2 ) followed by (s 1 ∪ s 2 , s 1 ∪ s 2 ).

Definition 2 (compatible decomposition)

The decomposition of a game in two subgames is compatible with the global game if in any subgame it is possible to choose freely a transition from a state to a distinct one.

The extension of definitions 1 et 2 to more than two subgames is straightforward.

Definition 3 (correct decomposition)

A decomposition is correct if it is compatible with the global game and there exists independent victory conditions (evaluation function) in the subgames such that winning every subgames implies winning the global game.

In the example given in figure 1, each lamp can be placed in a separate subgame: a transition can be freely chosen to switch on one of the lamps and independent evaluation functions are identifiable because each lamp involved in the calculation of the score provides a portion of the points.

In games with a binary score (win or loose), like Nonogram, evaluation functions can nevertheless be identified as the condition of victory is composed of distinct subgoals.

Given the aforementioned definitions, we however consider that a game like Nine Board Tictactoe is not decomposable. In this game consisting of 9 Tictactoe board arranged in 3 rows by 3 columns, each mark of a player in the cell of index i of a given board determines the following board i where the opponent will have to replicate, the aim being to align 3 marks in one of the board. Transitions depend on previous moves and can not be chosen freely if each board is a subgame. A game like Blocker is also non-decomposable. In this game, played on a 4 × 4 board, Crosser must put his mark in the cells to build a bridge across the board while Blocker tries to block the road with its own marks. Even though it is possible to freely choose the transitions in the 16 subgames consisting of only one cell of the global game, there do not exist independent victory conditions allowing to evaluate the score in one cell subgames. A single marked cell can be part of a winning state as well as a loosing one.

Method

To identify the different subgames we create a dependency graph; nodes are meta-action sets (see def.8 and §4.4) and completely instantiated fluents; edges represent effect or precondition relationships between them. We compute edge weights to allow the identification of lightly connected parts of the graph ( §4.7). Construction of this graph is detailed in section 4.6. The identified connected components represent the subgames.

For the analysis of relations between fluents and actions, we use the following definitions:

Definition 4 (premises) Let F be the set of all the instantiated fluents and f ∈ F a given positive or negative fluent. Let R be the set of all roles r. Let A be the set of all instantiated players actions a =(does r o). Let h be the head of

a variable free GDL rule. g ∈ F ∪ A is a premise of h if:
g is in the body of this rule, or g is in the body of a variable free GDL rule of head i and i is a premise of h.

g is an non-conflicting precondition of h if no conflict exists between g and another premise of h i.e. if h is satisfiable when g is true.

g is an exclusive precondition of h if g ⇒ h i.e. if h is true when g is true whatever the value of the other premises of h.

As action effects are not explicitly described in GDL rules, we define an effect as a phenomenon the cause of which is not known a priori and observed during a transition: Definition 5 A positive effect f + (resp. negative effect f -) is the value change of a fluent f from false (resp. true) in a state, to true (resp. false) in the next state. Let f * represents a given effect (positive or negative) on f ∈ F . Some effects always happen simultaneously with other effects; we distinguish between two sorts of co-occurring effects: Definition 6 (Globally co-occurring effects (GCE)) GCE(f * ), the set of globally co-occurring effects of f * consists of effects that always occur together with f * regardless the actions that caused this effect on f . Let |GCE(f * )| be the number of times this co-occurrence is observed during the playouts.

Definition 7 (Action co-occurring effects (ACE)) ACE(a, f * ), the set of co-occurring effects of f * for an action a, consists of effects occurring always together with f * when the action a is played. Let |ACE(a, f * ))| be the number of times this co-occurrence is observed during the playouts.

A meta-action is a set M of actions responsible for the same effects f * in the same circumstances. These circumstances correspond to fluents necessary for the actions legality, i.e. the premises of the legal rule for each a ∈ M , but also to the premises used in conjunction with theses actions a ∈ M in the body of the rules of head (next f). These rules indicate whether the conditions are met for the action to have an effect. Identifying the actions occurring with the same set of preconditions in the different clauses of a rule of head (next f) requires the calculation of the disjunctive normal form of this rule. However, by a comparison of all sets of actions occurring with each precondition taken separately, it is also possible to identify these actions.

Actions with no effect on f * but used in conjunction with the same fluent g in the premises of (next f), correspond to a set A = A -(M ∪ I) with A given at the definition 4, M a meta-action set with an implicit effect f * and I a set of illegal actions under the same conditions. These illegal actions may belong to another subgame than f : in this case, the meta-action sets that have an effect on the fluents of the other subgame are included in I. The comparison of actions sets with a same effect, with actions sets with a same precondition in a next rule, and with actions sets with a same precondition in their legal rule, allows to identify meta-action sets even if the effects are not explicitly described in the GDL rules.

We therefore propose the following definition of meta-action sets which does not require rule DNF : Definition 8 A meta-action set M (r, E, N , L) is a set of actions of role r such that all the following conditions are verified:

-E = ∅ and for each f * ∈ E, f * is an effect of each a ∈ M (r, E, N , L).

for each fluent g ∈ N and for each action a ∈ M (r, E, N , L), g is used in conjunction with a in the premises of (next f ) with f * ∈ E, and a is not an exclusive precondition of (next f ).

for each fluent h ∈ L and for each action (does r o) ∈ M (r, E, N , L), h is a non-conflicting precondition of (legal r o). L = ∅ if (legal r o) is always true for each action (does r o) ∈ M (r, E, N , L).

there does not exist A M (r, E, N , L) such that for each a ∈ A , a fluent g is used in conjunction with a in the premises of (next f ), a is not an exclusive precondition of (next f ) and a has no effect on f .

To decompose serial games, we are looking for a state or group of states that are necessarily visited during the game. No action sequence allows to reach the rest of the game without going through one of these states. They can be characterized by the presence of a crosspoint: one specific fluent or a conjunction of fluents. For example, in Blocker Serial composed of two games of Blocker played one after the other, the fluent game1overlock signals the end of the first subgame and conditions the legality of the actions of the second subgame. In Asteroids Serial, composed of two games of Asteroids, the first subgame ends when the spaceship stops, which is represented by the conjunction of fluents there exists at least one edge to the node x, and there exists at least one edge from x to an action node, and x is not in the initial state of the game.

Let a crosspoint X be a set of at least one crosspoint component.

Simulation based detection of action effects

Our approach uses a statistical estimation of the number of action effects during random playouts. Thus our playouts are gathering information to build the decomposition. At each step of the game, each player indicates its move; the set of all of these actions constitutes a joint move. In an alternate move game, only one player has the choice between multiple legal moves while the other player actions have no effect (often named noop). For each transition in a playout, the joint move is associated with state changes. After a given number of simulations, for each action a that occurs in |J(a)| distinct joint moves, we estimate the probability P(a, f + ) that a positive effect on fluent f follows action a:

P(a, f + ) = ( 0<i<|J(a)| E(J(a)i,f + ) O(J(a)i) )/|J(a)|
with J(a) the set of joint moves containing action a, O(J(a) i ) the number of occurrences of a given joint move of this set during playouts and E(J(a) i , f + ) the number of times a positive effect on f has been implied by this joint move. The probability that a negative effect f -follows the action a, is defined similarly.

P indicates the probability to observe a change when an action is played. However the change of some fluents like step or control does not depend on actions and some actions like noop have no effect on any fluents. The formulation of the rules does not always make it possible to detect them. For example, the presence of a noop action in the premises of the rules describing the next state of a control or step fluent can prevent detection.

Filtering action effects

A positive value of P(a, f * ) does not indicate if there is an effect of a on f or a simple correlation. A second step in identifying action effects is therefore needed to check each potential effect suggested by a positive value of P(a, f * ) to filter effects and eliminate correlations.

We first detect alternate moves: our purpose is to detect noop actions with no effects and action-independent control fluent. A n-player game is a sequential game when for each state n -1 players have only one legal action which is therefore considered as noop. The fluent that most frequently change when a noop action is played is the corresponding control fluent, which allows to detect it. If the only actions present in the premise of some fluents are noop actions then these fluents are considered action-independent.

For each action a, we then check each potential positive or negative effect given by the probability P(a, f * ) to confirm or deny the link between a and f * . By observing the rules of the game, it is possible to decide if a rule describes an explicit action effect or if it implies a possible effect. If no such rule is present in the GDL description of the game, we can assume that the action cannot have a positive effect on the fluent: we then set the probability to zero.

For example, an explicit positive effect of an action (does r o) on the fluent f is described by a GDL rule like (<= (next f) (does r o) (not (true f))) where f changes from false in the premises to true when action (does r o) is chosen. A rule like (<= (next f) (not (does r x)) (not (true f))) can suggest that action (does r o) has an implicit positive effect. Rules like (<= (next f) (does r o)) or (<= (next f) (not (does r x))) which both do not indicate if the fluent f is supposed to be true or not in the current state, can also implies a positive effect of (does r o). Similarly, the absence of certain rule patterns can be checked to eliminate negative effects.

By examining the co-occurring effects, we can also filter effects which cannot be the result of some actions. We reconsider the different co-occurring effects of each eliminated effect to detect erroneously assigned ones until no more is filtered. An action a cannot be the cause of an effect f * if P(a, g * ) = 0 with g * ∈ GCE(f * ). On the contrary, the effect f * of a is confirmed if there exists a g * with P(a, g * ) > 0 and either g * ∈ GCE(f * ) with |GCE(f * )| > Ψ or g * ∈ ACE(a, f * ) with |ACE(a, f * )| > Θ, where Ψ and Θ are thresholds necessary to only consider true co-occurring effects (sufficiently tested during playouts) and eliminate false positives. If an effect f * can be confirmed for some actions a but not for the other actions, we consider that other actions are not the cause of this effect.

For multi-player games we also compare the probabilities of the effect attributed to the different actions of a joint move. If an action a of a joint move has a probability Φ times greater than another action b to be followed by the effect f * then the cause of the effect is a and we update P(b, f * ) to a zero value. If the same change occurs for any transition from initial state and never in any other transition, it is considered independent of actions. When no more effect can be eliminated, if no action is the cause of a fluent change, this fluent is flagged as action-independent.

Action independent fluents

We use the circuit, to identify the preconditions of action independent fluents. We back-propagate 4 possible states (undefined, true, false or both) from each A. Hufschmitt et al.

(next f ) output where f is an action-independent fluent to flag its different premises. Then, for each activated positive or negative fluent input, we check if the fluent can change f from false to true (in this case, it is really a precondition, not a conflicting one) or if it can force f to remain true: then the inverse value of the fluent has a negative effect on f . To identify the meta-action sets according to definition 8, we use the previous detection of action effects and consider that P(a, f * ) > 0 denotes an effect of a on f . We detect action preconditions in legal and next rules using the logic circuit built from the rules.

Compound moves and meta-action sets

To find each fluent h that is a premise of a legal rule of head (legal r o), we set the output (legal r o) to true and back-propagate the signal into the circuit with four possible states in tha same way as in §4.3. We then check that each of these fluents actually allows the action to be legal using a three state propagation in the circuit i.e. it is a non-conflicting precondition (def. 4).

To find each fluent g used in conjunction with an action a in the premises of (next f), we set the input (does r o) to true and propagate the signal through the circuit without taking care of the logic gates to label each gate depending on this action including some next outputs. Then we back-propagate the signal from the (next f) output using different flags to specifically label the gates representing a conjunction between the action and another input (according De Morgan law it can be an or gate inside a negation) and mark the fluent inputs used in these conjunctions.

Then we compare the different action sets with a same effect, with a same precondition in a next rule or with a same precondition in their legal rule and recursively split each set until we find the meta-action sets (fig. 2). Fig. 3: Extremely simplified causal graph for the game Tictactoe Serial. m1, m2, po and px stand respectively for mark1, mark2, playero and playerx. A set of terms with variable arguments is represented using wildcards *. Some links are omitted to clarify the graph. Game1overLock is identified as a crosspoint.

Serial games and crosspoints identification

To identify the crosspoints from the crosspoint components set as defined in definition 9, we build a causal graph G where nodes are actions, positive or negative fluents. As the logical relations between nodes are represented by directed edges, we add an edge y → z in G if:

(1) y is an action and z is the result of an effect of y;

(2) y is a fluent (maybe action-independent) premise of (legal r p) with z = (does r p);

(3) y is a fluent, z is an action and y ∧ z are premises of (next f) where f * is an effect of z;

(4) y is a premise of (next z) where z is an action-independent fluent.

A single crosspoint component x is a crosspoint if there do not exist two edges x → y and y → x in C(G). For example, figure 3 shows a very simplified version of the causal graph obtained for the game Tictactoe Serial. The fluent game1overLock marks a clear boundary between two distinct parts of the game and is a crosspoint. Given X c the set of identified crosspoint components, a set X i ⊂ X c is a crosspoint candidate in C(G), if there exists a set of nodes Q such that, forall x ∈ X i and forall q ∈ Q, there exists an edge x → q. each X i which is a crosspoint candidate, we add a node o i in G. Then we use the circuit to identify the logical relations between each node o i and other nodes. In G, we add an edge y → o i for each edge y → x with x ∈ X i and we add an edge o i → y if :

(1) an action y =(does r p) is legal when all x ∈ X i are true and there exist

x ∈ X i where x is a premise of (legal r p); (2) (next f) is possibly true when all x ∈ X i are true and there exist x ∧ y premises of (next f) where f * is an effect of the action y;

(3) y is an action independent fluent and y * is entailed when all x ∈ X i are true.

X i is a crosspoint if there do not exist two edges o i → y and y → o i in C(G).

A crosspoint is discarded if it has another crosspoint or a fluent of the initial state has a unique precondition or if it includes another crosspoint.

Building the dependency graph

We use all previously collected information to build the dependency graph necessary to identify subgames. We add a node for each identified meta-action M and for each fluent f8 .

We add an edge between each meta-action M (r, E, N , L) and fluent f if :

(1) f ∈ L\C where C is the set of the detected control fluents (to avoid linking them with actions from different subgames); (2) f ∈ N \C where C is the set of the detected control fluents or, failing that, the set of all action-independent fluents; (3) f * ∈ E.

Edges (1) and ( 2) receive a weight of 1. The weight W of edges (3) is the mean of the action effect probabilities:

W = 0<i<N P(ai,f * ) N
with a i ∈ M (r, E, N , L). We also add an edge for each precondition of an action-independent fluent. To separate the serial subgames, we remove the links between each fluent present in a crosspoint and the fluents or actions that are preconditioned by this crosspoint. Some actions may not have been tested and some fluents change may have never been observed during playouts. These actions and fluents are considered to belong to all subgames until additional playouts provide more information.

Subgoals to fix under-or over-decomposition

In some games, there does not exist a relationship between some internal structures outside of the game goals. It is the case for cells in Tictactoe, columns in Connect Four9 or colored regions in Rainbow10 . Conversely, in a game like Lights On Parallel11 , we would like to separate the four groups of lamps as lighting one of them is sufficient to achieve victory. But, as each action of lighting a lamp has a negative collateral effect on all other lamps (they gradually go dark), a logical link exists in our dependency graph that connects subgames.

To solve these two problems, we collect subgoals using the circuit. The logic gates of the goal sub-circuit are sorted such that if the output of a gate is used as an input of another one it is examined first.

Each logic gate p of the sub-circuit is activated independently of the others with a value o ∈ {true, false} and, using a three state logic to broadcast the signal, the state of the goal outputs is examined. If an output with the maximum score for one of the players is activated, then the value o of the gate p represent a victory condition. Otherwise, if a non-zero score can nevertheless be obtained (the score 0 is false, a score greater than 0 is true or the value ¬o makes the maximum score impossible to achieve), then the value o of the gate p represents a subgoal. Each gate, the output value of which depends on a previously detected subgoal, is removed from the subgoal search: this allows to collect only the minimal conditions necessary to obtain a non zero score. We proceed similarly for victory conditions.

If several action-dependent subgames are detected, i.e. if the dependency graph presents several subgraphs containing action nodes, we check if the game is not over-decomposed. We verify that each detected subgoal or victory condition does not depends on fluents which are in different subgames. If this happens, the subgames are combined into one. It also allows us to verify that a subgame, if its fluents are involved in the calculation of the score, makes it possible to obtain at least a portion of the points.

If only one action dependent subgame is detected, it can group several subgames each allowing to obtain a maximum score but joined by collateral effects of the actions. To check if such subgames exist, we remove all effects links the weight of which is less than the threshold Ω from our dependency graph and then the victory conditions are used as before to join the parts of the game forming subgames guaranteeing the victory.

Experiments

There is no expert data specifying what the expected decomposition is for each of the game descriptions in the repositories. According to the definitions in section 3, we have therefore established for 597 games found in the Base, Stanford and Dresden repositories of http://games.ggp.org/ 12 , the expected number of action-dependent and action-independent subgames with the number of useless ones 13 . But as it is possible to separate a game into N parts in different ways, in each of our experiments, we manually checked each decomposition with more than 1 subgame to ensure that it agrees with definitions 1 to 3 14 .

The experiments are performed on one core of an Intel Core i7 2,7GHz with 8Go of 1.6GHz DDR3. The value for the ratio and thresholds are empirically set to the following values: Ψ = 3, Θ = 5, Φ = 1.5 and Ω = 0.1. These parameters are not sensitive to slight variations. For example, the value of Ψ leads to ignoring co-occurring effects during the first Ψ observations: the value of Ψ must be high enough to rule out coincidences but paranoid value will just require a larger number of playouts to achieve the same result.

For each game, we measure the time necessary to build the circuit, execute 5k playouts and process the decomposition. Figure 4 shows that 70% of the games can be decomposed in less than 1 minute, a time compatible with GGP competitions setup. Most of the time is used for the creation of the circuit. For example, once the circuit is created, 35 seconds are sufficient to collect initial information, execute 5k playouts and decompose Blocker Parallel that was not decomposed by previous works. 40 games are not decomposed before the 1 hour timeout, among them 32 are decomposable (fig. 6). The decomposition time and the grounding time are not correlated i.e. a game description producing a lot of grounded rules do not take necessarily more time to decompose. However, if the game tree is more complex, all actions and their effects may not be tested during the 5k playouts used to collect information therefore the decomposition is less reliable.

The decomposition process can be reiterated when more simulations have been performed. In Figure 5, we evaluate the number of correct decompositions obtained after each group of 1k playouts. We find that 1k playouts are enough to properly decompose 87% of the games. The only under-decomposed game after 10k playouts (fig. 6) is Simultaneous Win 2 for which no subgoal (evaluation function) could be identified for the subgames. The result of the decomposition after 10k playouts is presented for compound and single games separately (fig. 6). The over-decomposition is, in a majority of cases, due to the lack of information; more playouts would allow a proper decomposition. For example, in Snake or Tron, a part of the game board is not explored during playouts and constitutes a separate subgame.

Other cases of over-decomposition are observed for games that consist in surviving for a number of steps (Queens, Max-Knights 15 ): a wrong move ends the game and the score depends on the current step. In this case, the role of the main game is poorly detected: only the stepper is considered usefull. In some games with simultaneous moves like Point Grab 16 or Smallest 17 , each player is placed in a separate subgame : the identified subgoals do not link the actions of both players. Some games are more problematic : in Roshambo 18 or Beat Mania 19 , an effect of actions is to increment a counter composed of several fluents. The effect on each separate fluent is not significant and action effects are not correctly detected. A concept of meta-effect on a set of fluents would be necessary to handle such games.

All the decomposable games for which the decomposition could not be obtained in less than an hour, consist of a stepper associated with an actiondependent subgame. The time required to create the circuit leaves almost no time for decomposition. For these games, an ad-hoc detection of a stepper could allow to obtain a decomposition more rapidly.

Interesting decompositions are obtained for games of Nonogram (5 × 5 and 10×10) the status of several cells can be decided independently of the others and fluents and actions related to these cells are isolated in independent subgames (fig. 7). The remaining part of the board is decomposed in several subgames if the mark to be placed in cells does not depend on the rest of the game. These decompositions would allow to solve the game much more rapidly. We have compared the result of our decomposition with previous works [START_REF] Günther | Factoring General Games[END_REF][START_REF] Zhao | Decomposition of Multi-Player Games[END_REF][START_REF] Hufschmitt | A General Approach of Game Description Decomposition for General Game Playing[END_REF]: we obtain a correct decomposition for all the game tested in the aforementioned papers 20 . No measure of decomposition time is indicated by Günther et al. [START_REF] Günther | Factoring General Games[END_REF] and Zhao et al. [START_REF] Zhao | Decomposition of Multi-Player Games[END_REF]. Figure 8 parallels the results obtained in [START_REF] Hufschmitt | A General Approach of Game Description Decomposition for General Game Playing[END_REF] with the results obtained for the statistical approach presented in this article; it should be noted that the DNF approach, although faster than the DNFD, is much less reliable and heuristics used to detect causal links with both approaches are very weak. Unlike this previous approach, we obtain a correct decomposition for Chomp and Blocker Parallel within less than 1 hour.

19 Beat Mania is a 2 player game. The first player loose blocks from 3 different positions and the other must catch them. Each missed or caught block earns points to the corresponding player. 20 We do not test Double Crisscross 2 which is not available in repositories.

Fig. 8: Comparison of results from [START_REF] Hufschmitt | A General Approach of Game Description Decomposition for General Game Playing[END_REF] (DNFD, DNF) with those obtained with our statistical approach (stats) for 32 games among the 40 they tested. Results of the 3 approaches are identical for the 8 remaining games. A. Hufschmitt et al.

Conclusion and future work

We presented a simulation based game decomposition approach we tested on a large set of games. This approach provides a solution to the problem of identifying the effects of actions. The analysis of information collected during playouts allows to identify the explicit and implicit actions effects. It also allows to detect alternate moves or steppers when the rule formulation tries to hide them. We proposed an approach for the decomposition of serial games based on the identification of some crosspoints inside the game. We show also that it is possible to identify meta-actions without resorting to the disjunctive normal form of rules, which is very costly to compute. We can then decompose a game like Breakthrough which was not decomposed in less than 1 hour in previous works.

We tested our approach on 597 games from http://games.ggp.org/. Our results demonstrate that it is possible to transform the GDL rules into a logic circuit, execute 5k playouts and process the decomposition in less than 1 minute for 70% of the games. We also show that 1k playouts are sufficient to obtain a correct decomposition for 87% of the games.

Decompositions presented here are computed from the initial state of the game. As a decomposition can be enhanced when more information is available (more playouts are done), it is possible to detect fluents the value of which changes once and for all in each new state, to use this information to remove some links in the dependency graph and to discover new decompositions while playing.

We have seen that some games present specific difficulties: games where action effects on each fluent is not significant like in Roshambo or Beat Mania or in which the goal is to survive N steps like in Queens or Max-Knights. Our decomposition approach cannot handle games with fluents or actions shared between several subgames like Tic-Block or Factoring-Mutually-Assured-Destruction. We will investigate in the future how to handle these games without significantly increasing computational cost for all games.

Approaches that synthesize subgame solutions to better solve a global game are restricted to certain types of games that can easily be decomposed in an ad-hoc way (puzzles or 2-player synchronous parallel games). As our approach allows to obtain a decomposition sufficiently robust on a wide range of games in a time compatible with the General Game Playing competition setup, our first objective is to develop a player using the result of this decomposition to increase its strength.

Fig. 1 :

 1 Fig. 1: Minimalist game represented in GDL. The player can light 4 lamps. Turn on a ends the game. It only gets the maximum score if b and c are lit at the end.

(

  north-speed1 0)∧(east-speed1 0) indicating a zero speed on the 2 cardinal A. Hufschmitt et al. axes. These crosspoint can be identified from a causal graph representing the causal relationships between actions and fluents. Each fluent inside a crosspoint is a crosspoint component: Definition 9 Let G be a causal graph i.e. a directed graph representing the causal relationships between the actions and the fluents (positive or negative) of a game. Given C(G) the transitive closure of G, a fluent node x is a crosspoint component if in C(G):

Fig. 2 :

 2 Fig.2: Graphic representation of meta-actions identification. Fluents with cell1 predicate belong to the first subgame, those with predicate cell2 belong to the second one. The identification of meta-actions allows to remove the links between fluents of both subgames.

Fig. 4 :

 4 Fig. 4: Number of games for which the stage of the decomposition is reached in the given time (for 5k playouts).

Fig. 5 :Fig. 6 :

 56 Fig. 5: Number of games correctly decomposed after 1k to 10k playouts.

Fig. 7 :

 7 Fig. 7: Graphic representation of the decomposition obtained for the game Nonogram 5 × 5. The number in each cell represents the subgame to which it belongs.

In Asteroids the player must drive a small spaceship (in up to 50 steps) to an asteroid and stop on it. If the ship stops before reaching the destination, the game ends with the score 0.

Chinook is composed of two games of Checkers disputed on the white cells and the black cells of the same board.

Positive fluent (true f) and negative fluent (not (true f)) are represented by the same node in the dependency graph.

In Connect Four players drop colored tokens from the top into a seven-column, six-row vertically suspended grid. The goal is to align 4 tokens.

Rainbow is a puzzle that consists in coloring a map such that no adjacent regions have the same color.

Four game of LightsOn are played in parallel by a single player who chooses in which subgame he wishes to act on each turn. The player gets 100 points if he wins any of the 4 subgames.

We excluded GDL-II descriptions using the sees predicate.

These data are available upon request to the main author.

Note that an expert-like decomposition may not equal a correct decomposition. For example, a human expert would like to decompose Nine Board Tictactoe. However such a decomposed game would be difficult to solve.

The goal of Queens or Max-Knights is to place a given number of queens or knights on a chessboard so that no chessman threatens another.

Point Grab is played in 30 steps. At each step, 2 players have the choice between different useless actions or grab a point a or a point b. If both player choose the same point, nobody wins.

Smallest is a game played in a maximum of 25 steps. At each step, four player choose simultaneously a number. The player with the strictly smallest one wins 5 points.

Jeu

DNFD DNF stats Blocker Parallel >1hr >1hr ≈48min Asteroids <1sec <1sec <2sec EightPuzzle <2sec <2sec ≈3sec Checkers >1hr <12min ≈28min Breakthrough <16min <16min ≈14sec Sheep and wolf >1hr <5sec ≈6sec Tictactoe ≈1sec <1sec <1sec Nineboardtictactoe >1hr <2sec <17sec Tictactoex9 >1hr <5sec ≈11sec Chomp <1sec <1sec <2sec Multiplehamilton <1sec <1sec <2sec Multipletictactoe <10sec <1sec ≈1sec Blockerserial <20min <10min ≈3sec Dualrainbow ≈1min <8sec ≈6sec Asteroidsparallel <1sec <1sec ≈2sec Dualhamilton <1sec <1sec <2sec Dualhunter <2sec <2sec <3sec Asteroidsserial <1sec <1sec <4sec LightsOnParallel <8min <1sec <1sec LightsOnSimul4 <8min <1sec ≈3sec LightsOnSimultaneous <8min <1sec ≈3sec Nim3 <2sec <2sec <2sec Chinook <14sec <14sec ≈21sec Double tictactoe dengji >1hr <1sec <1sec SnakeParallel >1hr <2sec <7sec TicTacToeParallel >1hr ≈2sec <2sec Doubletictactoe >1hr <1sec <1sec TicTacHeaven >1hr <2sec ≈17sec TicTacToeSerial >1hr <1sec <1sec ConnectFourSimultaneous >1hr <1sec <2sec DualConnect4 >1hr <1sec <2sec Jointconnectfour >1hr <1sec <2sec