Yuichiro Sato
email: sato.yuichiro@jaist.ac.jp

Tristan Cazenave
email: cazenave@lamsade.dauphine.fr

Automated Generation of New Concepts from General Game Playing

In this paper, we propose algorithms to extract explicit concepts from general games and these concepts are useful to understand semantics of games using General Game Playing as a research domain. General Game Playing is a research domain to invent game players which are able to play general games without any human intervention. There are many approaches to General Game Playing, for example, UCT, Neural Network, and Simulation-based approaches. Successful knowledge acquisition is reported in these approaches. However, generated knowledge is not explicit in conventional methods. We extract explicit concepts from heuristic functions obtained using a simulation based approach. Concepts to understand the semantics of Tic-tac-toe are generated by our approach. These concepts are also available to understand the semantics of Connect Four. We conclude that our approach is applicable to general games and is able to extract explicit concepts which are able to be understood by humans.

Introduction

An intelligent system is able to adapt itself to its environment. To invent artificial intelligence, it is a good strategy to make a program which learns knowledge from the environment. We can use our living world itself as the environment for a system, e.g., Natural Language Processing. In this study, we focus on artificial environments, i.e., games. A game has concrete rules, and is easy to simulate and evaluate without any human intervention. We tried to discover new concepts from experience in this artificial environment. We use General Game Playing (GGP) as a research domain. GGP is a research domain to invent game players which are able to play general games.

There are many General Game Players. J. Méhat et al. developed a UCT based player [START_REF] Méhat | A Parallel General Game Player[END_REF], and D. Michulke et al. developed a machine learning based player [START_REF] Michulke | Neural Networks for State Evaluation in General Game Playing[END_REF]. Also, simulation and knowledge based approaches are studied. T. Kaneko et al. developed a successful method to learn logical features using a Boolean network approach [START_REF] Kaneko | Automatic Feature Construction and Optimization for General Game Player[END_REF]. P. Skowronski et al. extracted features for selective search extensions [START_REF] Skowronski | Automated Discovery of Search-Control Features[END_REF]. H. Finnsson et al. also extracted knowledge for general games to improve search efficiency of their player [START_REF] Björnsson | CADIAPLAYER: A Simulation-Based General Game Player[END_REF][START_REF] Finnsson | Simulation-Based Approach to General Game Playing[END_REF]. However, generated knowledge is not explicit in this conventional research. In this study, we propose the generation of new concepts which are explicit enough to be understood by humans.

Method

We made our General Game Player using ECLiPSe Prolog and Java. It reads games expressed in the Game Description Language (GDL) [START_REF] Love | General Game Playing: Game Description Language Specification[END_REF] through a parser [START_REF] Schiffel | [END_REF] into a Prolog engine, then the engine is called from Java through a Java-Prolog interface to simulate a game.

We automatically produced heuristics for the game by statistical analysis of simulation results. GDL is convertible to first-order predicate logic, therefore we can write GDL in Prolog [START_REF] Méhat | A Parallel General Game Player[END_REF]. Also, we can write positions of games as Prolog like facts. Thus, we made heuristics out of a set of Prolog rules. For each rule, the body is a subset of a game position, and the argument of head is the evaluation value of the position.

evaluation(value) :

-a subset of position of game.

(

) 1
We used Tic-tac-toe and Connect Four as subject games. In Tic-tac-toe, x player and o player try to make a straight line on a 3x3 two-dimensional board using his/her mark. In Connect Four, white player and red player also try to make a straight line with one's color, but the board size is 7x6. Additionally, it has gravity, so the players need to drop the tokens of their color from the top and pile them up. Therefore, players need to play Connect Four using a different strategy to Tic-tac-toe.

Even though the game rules are different, the representation of the board is shared by both games. In both games, a board is represented by a set of cell terms with arity 3, two arguments are for the coordinate and one is for the mark or color on the cell. This situation is convenient for our purpose.

Automated Generation of Heuristic Functions from Simulations

We tried automated generation of heuristic functions from random simulations of Tic-tac-toe and Connect Four. J. Clune successfully generated heuristic functions for GGP [START_REF] Clune | Heuristic evaluation functions for general game playing[END_REF]. M. Kirci et al. successfully extracted winning positions of general games from playouts [START_REF] Kirci | A GGP Feature Learning Algorithm[END_REF]. We statistically evaluated positions. We simulated Tic-tac-toe games till we got 10,000 playouts with each player as the winner. Then, we counted up what kind of subset of position is included in playouts and calculated the frequency to appear for each player. Finally, we picked the top 10% of frequent subsets and made Prolog rules which have the frequency as its evaluation value as written in Algorithm 1. We cut off Prolog rules in the heuristic functions which have greater body size than a specific size. We made three heuristic functions by using three different cut off sizes, 1, 2 and 3.

The following rules were included in generated heuristic functions. evaluation(0.238...) : -cell(3, 1, o), cell (2, 2, o).

(2) evaluation(0.237...) : -cell (3, 3, o), cell (2, 2, o), cell (1, 3, x).

(3)

These heuristics are appropriate for Tic-tac-toe. An evaluation value of a position is a sum of evaluation values of heuristic functions which match to the position.

We generated heuristic functions in the same way for Connect Four by 1000 simulations for each player. For Connect Four, we used a cut off size of 1 and 2.

We omitted cut off size 3 to reduce simulation time.

We evaluated the performance of each heuristic function by simulation. In the simulation, a 1-depth alpha-beta search player with each heuristic function played against both a random player and a 1-depth alpha-beta search player without heuristics. The 1-depth alpha-beta search player chooses a winning move when it is found by 1-depth search. Otherwise, the player chooses a random move. We did 10,000 simulations for Tic-tac-toe, 1000 simulations for Connect Four. Against a random player, for both games, winning ratios tend to improve when the cut off size gets greater, as can be seen in Table 1. If the cut off size is 0, it means that the player has no heuristic function. The same tendency was seen against an alpha-beta search player in Table 2. These results suggest that this algorithm successfully extracted features of games properly and encoded them as heuristic functions.

Algorithm 1 makeStatisticalHeuristics(playouts)

Automated Generation of New Concepts for Games from Heuristic Functions

We consider that heuristic functions include essential concepts about games. We tried to extract them as explicit new concepts. This is the Predicate Invention, one of the research areas of Inductive Logic Programming [START_REF] Inoue | Abducing Rules with Predicate Invention[END_REF].

First, for all Prolog rules in each heuristic function, we made pairs of terms included in its body. Then we replaced arguments with variables in the pairs if an argument in one of the terms in the pair relates to the corresponding argument in the other term. If an argument was a number, the argument was replaced by a new variable and the other was replaced by the sum of the variable and the difference between the two arguments. If the arguments were the same strings, we replaced them with a new variable. We introduced variables into original terms in this way. After removing duplicates, finally we got explicit new concepts from Prolog like heuristic functions, as written in Algorithm 2.

We extracted new concepts from heuristic functions for Tic-tac-toe generated in section 3. Typical concepts are as follows.

concept1(X 0 , X 1 , X 2 ) : -cell(X 0 , X 1 , X 2 ), cell(X 0 , X 1 + 1, X 2 ). (4) concept11(X 0 , X 1 , X 2 ) : -cell(X 0 , X 1 , X 2 ), cell(X 0 + 2, X 1 + 2, X 2 ). (5) concept20(X 0 , X 1 ) : -cell(X 0 , X 1 , x), cell(X 0 + 2, X 1 + 2, o). ( 6
)
We are able to interpret these concepts as human language. Equation 4 means "a cell and its right cell are marked by the same symbol". Equation 5 means "a cell and its lower right cell are marked by the same symbol". Equation 6means "a cell is marked by x and its lower right cell is marked by o". These are natural concepts for humans to play Tic-tac-toe.

Applying Automated Generated Concepts to Games

We tried to use the generated concepts to reconstruct heuristic functions. We send queries to a Prolog engine whether each generated concept matches to subsets of simulated playouts. If the query matched, we saved the matching result and counted up how many times it matched. Then we assert a Prolog like heuristic rule of which an evaluation value is the ratio of number of matches frequency to number of subsets as written in Algorithm 3. In our experience, reconstructed heuristic functions are made of only binary relations because all of the generated concepts in section 4 are binary relations on terms.

For Tic-tac-toe, we made heuristic functions from 10,000 random game playouts with each player as the winner, then we evaluated performance using 10,000 simulations against both a random game player and a 1-depth alpha-beta search player. In the results, improvements were seen compared to the player who has no heuristic function, for example, winning ratio of x player improved 14%, but not to players whose heuristic function is better than the 1-body size heuristic function as seen in Tables 3 and4. We think this is because they lack 1-body and 3-body Prolog rules as we mentioned above.

We also made heuristic functions for Connect Four in the same way. We made two different heuristic functions, one is made from only 10 simulations and the other is made from 100 simulations. Even though only a few simulations, for white player, the generated heuristic functions have good performance. Only 10 simulations are enough to compete with 1-body heuristic functions. 100 simulations are enough to be competitive with 2-body heuristic functions as seen in Tables 3 and4. This is proof that concepts learned from experience of small games can play bigger games.

We successfully generated new concepts for games from experience of Tic-tactoe. However, for red player, the result is not good. The difference is that white is the first player and red is the second player. From random game simulation results, it is suggested that the second player has a disadvantage compared to the first player. The difference of performance is possibly due to this property.

Algorithm 3 makeStructuredHeuristics(concepts,playouts)

Automated Generation of Ternary Concepts from Binary Concepts

Generated concepts in Algorithm 2 are relationships between a cell and another cell, i.e., binary relationships. We tried to make ternary relationships as a conjunction of binary relationships. If two binary concepts are satisfied at the same time and a cell is shared in both concepts, the situation is a ternary relationship. Therefore, ternary relationships are made by unification of pairs of terms in each binary concept as written in Algorithm 4.

We generated ternary concepts from the binary concepts generated in Section 4. Typical generated concepts are as follows.

concept67(X 1 , X 2 , X 3 ) : -cell(X 1 , X 2 , X 3 ), cell(X 1 , X 2 + 1, X 3 ), cell(X 1 , X 2 + 2, X 3 ). (7) concept155(X 1 , X 2 , X 3 ) : -cell(X 1 , X 2 , X 3 ), cell(X 1 + 1, X 2 + 1, X 3 ), cell(X 1 -1, X 2 -1, X 3 ). (8)
Equation 7 and 8 represent an idea of line in Tic-tac-toe. Important ternary concepts are successfully generated by this algorithm. The same algorithm has a possibility to make more complex concepts.

We also made heuristic functions made of ternary concepts for Connect Four by Algorithm 3. To reduce generation time, we input 10 simulations and ternary Algorithm 4 makeTernaryConcepts(concepts) P ⇐ makePairsOfConcept(concepts) for all pair (c1, c2) in P do for all term t1 in body of c1 do for all term t2 in body of c2 do if t1 is able to unificate to t2 then t3 ⇐ unification result of t1 to t2 b1 ⇐ make new body as like t3 appearing in c1 by unification b2 ⇐ make new body as like t3 appearing in c2 by unification if b1 is not equals to b2 then R ⇐ make new concept by conjunction of b1 and b2 end if end if end for end for end for R ⇐ remove overlap from R return R concepts generated as above to Algorithm 3 and made heuristic functions. Then, we evaluated it using 1,000 simulations against a random game player or a 1depth alpha-beta search player. Results are not good as seen in Table 5 and6. We think this is due to noises from less important concepts. In Algorithm 3, all input concepts are concerned, therefore, not only important concepts like Equation 7 or 8 but also less important concepts affect evaluation values. This result suggests a limitation of Algorithm 3 and a need for better algorithm. A typical concept learned in this study is as follows.

concept(X 0 , X 1 , X 2 ) : -cell(X 0 , X 1 , X 2 ), cell(X 0 , X 1 + 1, X 2 ). ( 9
)
This concept is applicable to all games in which players put a mark or piece on a two-dimensional board. Even more, through appropriate filters, it is possible to apply the concept to computer vision to understand semantics of a picture. If one makes a filter which converts a picture to Prolog like facts, this concept is applicable for recognizing semantics of series of squares with contents. In other words, concepts generated in this study are available to understand semantics of our living world, not only of artificial game worlds.

It is necessary for a human being to input supervised signals when an artificial intelligence learns concepts about our living world. For example, when we do Natural Language Processing to generate ontology, we need to input well written texts which are written by human beings [START_REF] Mohamed | Discovering Relations between Noun Categories[END_REF]. It is impossible to learn ontology from automatically generated strings. However, in this study, we successfully generated concepts about our world without any supervised signals by human beings. This property is due to the special advantage of games, i.e., environments having concrete rules. In other words, human beings do not have to judge a meaning of record of random games because a simulator is able to judge it, i.e., who is the winner according to its game rules. This tremendously desirable advantage is available only in games, not in other fields. In our study, it is proven that we are able to generate essential concepts about our living world from games according to the advantage.

Conclusions

In our study, we automatically generated concepts which were applicable to understand the world of the games for General Game Playing. Obtained concepts were general and useful to understand several games. General Game Playing is a desirable research area for automatically learning concepts of our living world. To apply obtained concepts to more games and to generate more complex concepts are the problems which remain to be solved.

end if end for end for for all

M ⇐ Hash Map for all playout p in playouts do S ⇐ getSubset(p) for all subset s in S do if M contains s then increment counter for s else create hash for s and set the counter as 1 m in M do v ⇐ counter for m / size of playouts add Prolog rule type heuristic, "evaluation(v):-m." into H end for H ⇐ pick up rules which have top 10% of its evaluation value from H return H

Table 1 .

 1 Evaluation of heuristic functions for Tic-tac-toe and Connect Four against a random player.

				cut off size
			0	1	2	3
	game player		win(%)/lose(%)/draw(%)
	Tic-tac	x 80.73/12.32/6.95 93.38/4.53/2.09 90.17/7.45/2.38 96.49/2.76/0.75
	-toe	o 50.57/40.69/8.74 65.64/27.50/6.86 68.10/28.11/3.79 73.65/24.77/1.58
	Connect white	81.4/18.6/0	84.4/15.6/0	90.2/9.8/0	-
	Four	red	71.3/28.6/0.1	70.4/29.6/0	77.4/22.6/0	-

Table 2 .

 2 Evaluation of heuristic functions for Tic-tac-toe and Connect Four against a 1-depth alpha-beta search player.

				cut off size
			0	1	2	3
	game	player		win(%)/lose(%)/draw(%)
	Tic-tac-toe x 67.98/27.51/4.51 85.81/13.57/0.62 74.53/25.47/0 91.42/8.58/0
		o 27.00/68.71/4.29 41.78/55.40/2.82 41.95/57.87/0.18 50.42/49.58/0
	Connect white	57.4/42.6/0	62.2/37.8/0	79.7/20.3/0	-
	Four	red	40.1/59.9/0	40.4/59.6/0	54.4/45.6/0	-

  Concepts which have a variable as the role argument are general concepts which are available for both Tic-tac-toe and Connect Four. Concepts which do not have a variable as the role argument are specialized for Tic-tac-toe and not available for Connect Four because role symbols are different between Tic-tac-toe and Connect Four.

	Algorithm 2 generateNewConcept(prolog rules)
	end if
	end if
	end for
	if generated pair (p1, p2) is not in C then
	add generated pair (p1, p2) to C as a new concept
	end if
	end for
	end for
	return C

for all rule r in prolog rules do P ⇐ all pairs of terms in the body of r for all pair (p1, p2) in P do for i = 0 to arity of p1 do if i-th argument of p1, ai and i-th argument of p2, bi are instances of the same class then if ai is an instance of number then replace ai to a new variable and bi to sum of the variable and bi -ai else if ai equals to bi then replace ai and bi to a new variable

Table 3 .

 3 Evaluation of heuristic functions made of new concepts for Tic-tac-toe and Connect Four against a random player.

	end if
	end if
	increment the number of subsets size
	end for
	end for
	for all m in M do
	v ⇐ the counter for m / size
	add a heuristic, "evaluation(v):-m." into H
	end for
	end for
	return H

for all concept c in concepts do M ⇐ Hash Map for all playout p in playouts do S ⇐ getSubset(p) for all subset s in S do if prolog query of c matches to s then r ⇐ matching result of s if M contains r then increment counter for r else create a hash for r and set the counter as 1

Table 4 .

 4 Evaluation of heuristic functions made of new concepts for Tic-tac-toe and Connect Four against a 1-depth alpha-beta search player.

	game	player simulation size win(%)/lose(%)/draw(%)
	Tic-tac-toe x	10000	89.64/10.36/0
		o	10000	39.16/56.87/3.97
		white	10	74.5/25.5/0
	Connect white	100	78.3/21.7/0
	Four	red	10	29.5/70.5/0
		red	100	44.3/55.7/0

Table 5 .

 5 Evaluation of heuristic functions made of ternary concepts for Connect Four against a random player.

	game	player simulation size win(%)/lose(%)/draw(%)
	Connect Four white	10	72.7/27.3/0
		red	10	71.7/28.3/0
	7 Discussion
	In this study, we successfully extracted the essential concepts included in the
	game automatically. The proposed algorithm is applicable to general games.
	The algorithm learns new concepts without any supervised signals but from
	experience in a certain environment. The generated concepts are fundamental
	features of the environment, and can be used to play some games with different
	rules.

Table 6 .

 6 Evaluation of heuristic functions made of ternary concepts for Connect Four against a 1-depth alpha-beta search player.

	game	player simulation size win(%)/lose(%)/draw(%)
	Connect Four white	10	39.7/60.3/0
		red	10	37.8/62.2/0

Acknowledgments

The authors would like to express their appreciation to Mr. Abdallah Saffidine for his contribution to the stimulating discussions, Prof. Erick Alphonse for his

comments on Inductive Logic Programming, Prof. Hiroyuki Iida and Japan Advanced Institute of Science and Technology for funding and Dr. Kristian Spoerer for proof reading.


Tristan Cazenave

Monte-Carlo Beam Search

Keywords: Nested Monte-Carlo Search, Puzzle, Beam Search. 3

published or not. The documents may come

Monte Carlo Beam Search

INTRODUCTION

Monte-Carlo Tree Search [START_REF] Kocsis | Bandit based monte-carlo planning[END_REF], [START_REF] Cazenave | Nested Monte-Carlo search[END_REF] is very successful in games such as Go [START_REF] Coulom | Efficient selectivity and back-up operators in monte-carlo tree search[END_REF], [START_REF] Gelly | Combining online and offline knowledge in UCT[END_REF], Hex [START_REF] Cazenave | Utilisation de la recherche arborescente Monte-Carlo au Hex[END_REF], [START_REF] Arneson | Monte carlo tree search in hex[END_REF] or General Game Playing [START_REF] Finnsson | Simulation-based approach to general game playing[END_REF], [START_REF] Bj Örnsson | Cadiaplayer: A simulationbased general game player[END_REF], [START_REF] Méhat | Ary, a general game playing program[END_REF]. Building on these successes in two-player games, Monte-Carlo Tree Search algorithms were also recently used in single-player games [START_REF] Cazenave | Reflexive Monte-Carlo search[END_REF], [START_REF] Schadd | Single-player monte-carlo search[END_REF], [START_REF] Cazenave | Nested Monte-Carlo search[END_REF], [START_REF] Méhat | Combining UCT and nested monte-carlo search for single-player general game playing[END_REF].

Nested Monte-Carlo search has been successfully applied to hard puzzles [START_REF] Kendall | A survey of np-complete puzzles[END_REF] such as Morpion Solitaire or SameGame [START_REF] Cazenave | Nested Monte-Carlo search[END_REF]. Beam search is a search algorithm that selects a given number of positions among the children of the current set of positions. It has been succesfully combined with ant colony optimization to solve the travelling salesman problem with time windows for example [START_REF] L Ópez-Ibá Ñez | Beam-aco for the travelling salesman problem with time windows[END_REF]. We propose to improve Nested Monte-Carlo Search combining it with beam search.

The second section deals with Nested Monte-Carlo Search. The third section describes Monte-Carlo Beam Search. The fourth section explains Parallel Monte-Carlo Beam Search. The fifth section details experimental results.

NESTED MONTE-CARLO SEARCH

The basic idea of Nested Monte-Carlo Search is to play a game choosing each move based on • T. Cazenave is at LAMSADE, Université Paris-Dauphine, 75016 Paris, France. email: cazenave@lamsade.dauphine.fr the results of a lower level Nested Monte-Carlo Search [START_REF] Cazenave | Nested Monte-Carlo search[END_REF]. At level 1, the lower level search is simply a playout. A playout is a game where moves are played at random until the game ends.

Figure 1 illustrates a level 1 Nested Monte-Carlo search. Three selections of moves at level 1 are shown. The leftmost tree shows that at the root all possible moves are tried and that for each possible move a playout follows it. Among the three possible moves at the root, the rightmost move has the best result of 20, therefore this is the first move played at level 1. This brings us to the middle tree. After this first move, playouts are performed again for each possible move following the first move. One of the moves has result 30 which is the best playout result among its siblings. So the game continues with this move as shown in the rightmost tree. (shown here with a bold line), an NMC of level 1 performs a playout (shown with wavy lines) for each available move and selects the best one.

The algorithm for higher levels is Algorithm 1. At each move of a playout of level 1 it chooses the move that gives the best score when followed by a single random playout (using the sample function that plays a completely random game). Similarly for a playout of level n it chooses the move that gives the best score when followed by a playout of level n -1.

For a tree of height h and branching factor a, the total number of playout steps of a NMC of level n will be t n (h, a) = a × 0<i<h t n-1 (i, a) with t 0 (h, n) = h. So a NMC of level 1 will perform a×h 2 /2 playout steps. The complexity of a NMC of level n is O(a n h n+1 ).

In Iterative Nested Monte-Carlo Search, searches at the highest level are repeatedly performed until the thinking time is elapsed. Nested Monte-Carlo search has been successful in establishing world records in single player games such as Morpion Solitaire or SameGame. It provides a good balance between exploration and exploitation and it automatically adapts its search behavior to the problem at hand without parameter tuning. At each level, it is important to memorize the best playout found so far in order to play its moves if no better playout is found.

MONTE-CARLO BEAM SEARCH

In this section we describe how we combine beam search with Nested Monte-Carlo Search. The combination consists of memorising a set of best playouts instead of only one best playout at each level. This set is called a beam and all the positions in the set are developed. The size s level of a beam is fixed for each level. Only the s level best playouts are kept at a given level. Figure 2 intuitively explains how a beam search of level 1 and size 2 works. At the root node, there are three possible moves. For each possible move, the move is played and the resulting position is followed by a playout. The position after the move is associated to the score of the following playout. The best two positions are kept and we are now in the second tree. For each of the two positions in the beam there are three possible moves. For each position in the beam the possible moves are played and followed by a playout. Out of the resulting 6 positions, only the 2 positions that have the best playout results are kept. We are now in the third tree. There are again playouts played after each possible move in the positions of the beam, and the process continues until all positions in the beam are terminal.

Algorithm 2 details Monte-Carlo Beam Search. The variable beam is the set of positions in the beam. There are at most s level positions in the beam. The variable nextBeam represents the best positions of the beam after one move. The variable nextBeam is set to the empty set before filling it with new positions. For all positions in the beam the following position of the best playout associated to the position is put into nextBeam so as to keep the best playout if no better playout is found. Then for all possible moves in the position of the beam, the move is played and a nested search is performed on the resulting position. The best playout resulting from the nested search is associated to the position and the position is inserted in the next beam. After all positions in the beam have been developed, only the s level best positions are kept. A position is better than another one if the associated playout has a better score.

Monte-Carlo Beam Search is a generalization of Nested Monte-Carlo Search. When s level = 1 for all levels, Monte-Carlo Beam Search behaves exactly as Nested Monte-Carlo Search.

PARALLEL MONTE-CARLO BEAM SEARCH

Monte-Carlo Tree Search algorithms close to UCT parallelize quite well until 16 cores [START_REF] Cazenave | On the parallelization of UCT[END_REF], [START_REF] Cazenave | A parallel monte-carlo tree search algorithm[END_REF], [START_REF] Chaslot | Parallel monte-carlo tree search[END_REF], [START_REF] Enzenberger | A lock-free multithreaded monte-carlo tree search algorithm[END_REF], while Nested Monte-Carlo Search parallelizes quite well until at least 64 cores [START_REF] Cazenave | Parallel nested montecarlo search[END_REF].

The parallelization of Monte-Carlo Beam Search is even more simple than the parallelization of Nested Monte-Carlo Search. It consists in having a master process that performs the search at the highest level, and some remote processes that perform the search at the lower levels. The master process computes all the positions following the positions in the beam and sends them to the remote processes. The remote processes apply the lower level Monte-Carlo Beam Search to the positions they receive and send back the result to the master process. Once the master process has sent all the following positions, it receives all the searched positions and only keeps the best ones for the beam. The master and the remote processes are given in algorithms 3 and 4.

EXPERIMENTAL RESULTS

Morpion Solitaire is a single player game. The goal of the game is to play as many moves as possible. A move consists of adding a circle and in drawing a line joining five circles that have not been joined before. In the touching version two lines in the same direction can share a circle, while in the disjoint version they cannot. Before playing, a number of circles are drawn in a cross shape.

Nested Monte-Carlo Search has established world records at Morpion Solitaire [START_REF] Cazenave | Nested Monte-Carlo search[END_REF], [START_REF] Rosin | Nested rollout policy adaptation for monte carlo tree search[END_REF]. The current records are 82-move for the disjoint version and 178-move for the touching version. They were achieved by Chris Rosin with Nested Monte-Carlo Search and playout policy learning in August 2011.

More information on Morpion Solitaire can be found on the Morpion Solitaire web site [START_REF] Boyer | Morpion solitaire. web page[END_REF]. The best human record for the touching levels are set to 1 when testing a value for the beam size of a level. We can see that the behavior is slightly different for the different levels.

At level two, doubling the beam size enables the algorithm to get more points than doubling the beam size at levels 1 and 3. The slope of the curve is better at level 2 until a beam of 128: a 1.1 point gain is observed for each doubling, but then it decreases to approximately half a point. Concerning level 1, approximately 0.9 points are gained for each doubling of the beam size. At level 3, approximately 0.7 points are gained for each doubling of the beam size. Doubling the beam approximately doubles the computing time for all levels. Table 1 gives the average scores obtained for different combinations of the beam sizes at level 1 (s 1 ) and at level 2 (s 2 ). The values have been computed over 118 runs of the algorithms, and only for combinations such that s 1 × s 2 ≤ 32. As the running time of the algorithm is proportional to s 1 × s 2 , we can compare algorithms that are equivalent for the computing time, comparing the values along the antidiagonal. For each antidiagonal, the best value is put in bold. We can observe that values that have the same s 1 ×s 2 are quite close to each other.

Figure 5 depicts the evolution of the average score at level 1 for beams of size 1, 16 and 128. The curve for beam size 1 is the curve for the original Nested Monte-Carlo search algorithm. The two other curves are for Monte-Carlo Beam Search. We can see that using a beam much improves the nested Monte-Carlo algorithm. When running for 163 seconds, Monte-Carlo Beam Search with a beam of 16 scores three An 82-move record was obtained using Monte-Carlo Beam Search. It was found by a level 3 search with s 1 = s 2 = s 3 = 4, a beam of size 4 for level 1, 2 and 3. The record is depicted in figure 6.

Since the fastest way to gain points is to use a beam size s 2 = 8 (as can be observed in figure 4), other tests were done with s 1 = 1 and s 2 = s 3 = 8. These searches found multiple 80 moves grids and another 82-move record depicted in figure 7.

Previous to these experiments we ran many searches of Nested Monte-Carlo Search at level 4 using a parallel implementation. These searches achieved two 80-move grids out of many attempts. In contrast Monte-Carlo Beam Search achieved many 80-move grids and two 82-move grids with faster searches and much less time. The time to complete a search at level 3 with s 1 = 1 and s 2 = s 3 = 8 is less than the time to complete a level 4 search and it gives better scores. A Nested Monte-Carlo Search at level n + 1 requires 200 more computational time than a search at level n, while the Monte-Carlo Beam Search we have used only requires 64 more computational time than a Nested Monte-Carlo Search of level 3 and gives better results than a search at level 4.

CONCLUSION

We have defined a new Monte-Carlo Tree Search algorithm that combines Nested Monte-Carlo Search with Beam Search. We have shown that the use of a beam improves Nested Monte-Carlo search at Morpion Solitaire. Monte-Carlo Beam Search has matched the current world record of 82 moves at the disjoint version of Morpion Solitaire with a search faster than Nested Monte-Carlo Search at level 4. Moreover Nested Monte-Carlo Search at level 4 only achieved 80-move grids. When compared at level 1, Monte-Carlo Beam Search gets four more points on average than Nested Monte-Carlo Search. In future work, we intend to apply the algorithm to other puzzles.

Fig. 1 .

 1 Fig. 1. This figure explains three steps of a level 1 search. At each step of the playout of level 1 (shown here with a bold line), an NMC of level 1 performs a playout (shown with wavy lines) for each available move and selects the best one.

Fig. 2 .

 2 Fig.2. Illustration of a beam search with a beam of size two. At each move, the best two positions among all children are kept.

Algorithm 3 Algorithm 4

 34 Master process beamMonteCarlo (position, level) beam ← {position} while true do nextBeam ← ∅ for b in beam do p ← b if there is a move to play in the best playout of p then play (p, move of the best playout) end if add p to nextBeam end for remote ← 1 nbSent ← 0 for b in beam do for move in possible moves of b do p ← b play (p, move) Send (p, remote) remote ← remote + 1 if remote = # of remote CPU then remote ← 1 end if nbSent ← nbSent + 1 end for end for for i from 1 to nbSent do Receive (p) add p to nextBeam end for if beam = nextBeam then break end if keep only the best s level positions in nextBeam beam ← nextBeam end while Remote process remoteProcess (level) while true do Receive(position) beamMonteCarlo (position, level -1) Send(position, 0) end while version is 170 moves. This record by Charles-Henri Bruneau held for 34 years before being beaten by the combination of Nested Monte-Carlo Search and playout policy learning.

Fig. 3 .

 3 Fig. 3. Evolution of the average score of Iterative Nested Monte-Carlo Search with different levels.

Figure 3

 3 Figure 3 gives the evolution of the average score of a regular Nested Monte-Carlo Search at level 0, 1 and 2. We can observe that at level 1, doubling the computation time improves the average score by half a point. At level 2, doubling the computation time improves the average score by 0.7 points. The average score is only given for time settings of which at least one iteration has been completed.

Fig. 4 .

 4 Fig. 4. Evolution of the average score of a search with different levels and beam sizes.

Figure 4

 4 Figure 4 shows the evolution of the average score obtained for different beams and different levels. The sizes of the beams of the underlying

  s1\s2

Fig. 5 .

 5 Fig. 5. Evolution of the average score of a search at level 1 for different beam sizes.

Fig. 6 .

 6 Fig. 6. An 82-move record for Morpion Solitaire disjoint version.

Fig. 7 .

 7 Fig. 7. Another 82-move grid.

TABLE 1

 1 Average score of level 2 searches for different combinations of s 1 and s 2

ACKNOWLEDGMENT

I wish to thank Ed Mertensotto who told me he uses beam search in his evaluation and search based SameGame solver and Nicolas Jouandeau who helped me to run my programs the mime cluster of University Paris 8. I also thank the anonymous reviewers for helping me improve this paper. This work has been supported by the French National Research Agency (ANR) through the COSINUS program (project EXPLO-RA ANR-08-COSI-004)


domain: spi scco

text:
Gilles Haeffelé
email: haeffele<gilles.haeffele@ac-strasbourg.fr>

Sebastien Dubois

Pascal Sire

How to leverage the knowledge spiral and creative meta-rules to train on TRIZ thinking while rescuing the sinking Titanic?

Keywords: TRIZ, education system, teaching method development, knowledge spiral, meta-rules, creative game, innovative evaluation

come

How to Leverage the Knowledge Spiral and Creative Meta-rules to Train on TRIZ Thinking While Rescuing

the Sinking Titanic?

Motivation

In the TRIZ Future Conference 2012 , we presented a first experiment which objective was to teach simultaneously future teachers and students of 2 classes of a technical high school.

Three main ideas were highlighted:

• A three-level knowledge spiral (Expert, teachers, students), to enable teachers to be taught at the same time that they had to teach students. • The context of a "challenge of creativity for innovation" to stimulate learning and motivate students themselves with the Ideal final result that "everybody wins". • The dimension change for a positive evaluation: We introduced a 2D radar with opposed pairs of innovative criteria to evaluate the creativity of the group.

The positive results we obtained with this experiment encouraged us to extend it to a larger group made of 10 colleges, 24 new teachers and about 300 students (compared to 1 college, 6 teachers and 60 students). New contradictions appeared then in this new context: We had less resource in time, and more teachers and students to be taught.

What should be done?

The purpose of this article is not to compare how to teach TRIZ by means of a case study, compared to "classical" or "modern" TRIZ teaching at universities using lectures and also practices with case examples, as there are already many publications on these discussions.

Instead, the authors will try to solve the theoretical contradiction "how to teach a domain without knowing the subject", applying the TRIZ "knowledge spiral" process (like "Russian dolls") to the specific domain of teaching TRIZ to students by teachers without knowing TRIZ. Then the authors will focus on a proposed method of motivation of the teachers and students based on the "Titanic" case example.

State of the art

The authors were facing several problems to propose a way to teach several teachers who will have to apply a new problem resolution method with their groups of students:

• the time to teach the teachers was reduced,

• the teachers had to explore a new discipline,

• the teachers will have to propose a way to transmit "not acquired" knowledge to their students,

• a new pedagogy has to be proposed, when this situation has not been tackled yet in the literature.

The subject of teaching TRIZ has often been tackled, but mainly through the aspect of increasing the efficiency of a trained teacher to teach its students . Another aspect is the building of supports to help teachers in their way to teach TRIZ as the project TETRIS . But the authors have not found any documents related to the previously cited difficulties, in the specific case of training future TRIZ teachers.

To overcome this set of difficulties, the authors made the choice to build a homothetic approach of their first experience, which has been described in . And, even if the results of a new pedagogy can only be judged afterwards, they built their new proposal referring to the "rules for good pedagogy" they found in literature.

The subject is a new domain for teachers

It is always difficult and stressing for teachers to explore new discipline, and to build for their students a relevant "pedagogic platform" covering many disciplines. However, cross-curricular works in schools have been promoted for the benefits they bring out. In (Savage 2012), these benefits have been recognized mainly for dimensions like enterprise, global dimensions and sustainable development, technology and media, and creativity and critical thinking. One of the main benefits of such an approach is that it helps young people to unify areas of learning and to "make sense of the world".

To face the lack of self-confidence of teachers, which is due to the "lack of content knowledge and to the inability to employ a range of teaching and learning approaches appropriate to the theme" it is recommended to adopt a pedagogy with the following characteristics:

• the pedagogy should have an objective and open-minded approach,

• the pedagogy should use concepts as the intellectual building blocks, and uses categorization, organization and analysis of knowledge, • the pedagogy should mainly be based on participatory and experiential teaching style,

• the pedagogy should refer to questions and issues that enable pupils to explore fundamental aspects of our lives.

Another particular aspect of the current project is not only the fact that the study aims at transferring transversal knowledge (know-how about problem resolution) but also that the teachers to be trained -and their students -are disseminated in several colleges, with different perception of what they have to do, and how to do it. One can recognized it at having different teachers from different disciplines. Thus the problem about homogeneity between disciplines occurs even more dramatically.

One approach that can be used, and on which authors built their proposal is the concept of connection in pedagogy to tackle this problem. Dillon, in (Dillon 2006), reminds that "working across and between disciplines are known as cross-curricula or integrative", it means that these topics are the combination of diverse components of perception. Then, Dillon defines these activities, across and between disciplines, to be inherently creative. "In educational terms, making connections between subjects, and working in cross-curricular modes, are recognized routes to teaching creatively and providing opportunities for both learning about creativity and undertaking creative activity".

To summarize, to help the teachers build an approach to teach a new subject to their students, the proposal of the authors have to fit the following set of requirements:

• it should not be too rigid, but should be goal-oriented,

• it should bring elements of knowledge blocks by blocks,

• it should be practical and mainly based on group-activities,

• it should be motivating both for teachers and students, and for this raise "strong questions",

• it should enable to make connections between the different tackled disciplines.

The teacher has to be self-confident with the subject

As one of the main stakes of the project is to propose a pedagogy that enables both teachers to teach, but also teachers to learn about the subject, the objective is to provide an environment in which the teachers could feel self-confident about what they will use and what they will transfer to their students. [START_REF] Gore | Towards better teaching: productive pedagogy as a framework for teacher education[END_REF]) presented a "Productive Pedagogy" as a framework for enhancing teacher education.

Based on the remarks of interviewed teachers about the lack of the system of education, they proposed this framework to focus more on the substance and purposes of teaching.

This framework is based on four principles:

• intellectual quality, which addresses the tackled knowledge, the deep understanding of it, the inherent problematic, and s.o. • relevance, which addresses the integration of knowledge, its connectedness to the world, the problem based curriculum, … • supportive classroom environment, which addresses the student control, the social support, the explicit criteria, self-regulation, … • recognition of difference, which addresses the cultural knowledge, the group identity, … So, to help teachers to be self-confident in their learning and teaching, the authors tried to build an approach which integrates these different dimensions, by clarifying the nature of knowledge, its role in the global context, and trying to build and environment in which exists an equilibrium between rules and self-regulation of students. This need is re-enforced by the concept of self-study, both for teachers and students. The self-study concept "empowers professionals to examine, and be accountable for, their own practice as they articulate and generate knowledge useful to others." (Lunenberg and Samaras 2011) Lunenberg and al. reminded that the creation of an optimal learning environment could be guided by the Vygotskian principles [START_REF] Vygotsky | The genesis of higher mental functions. The concept of activity in Soviet Psychology[END_REF]):

• social and cultural influences shape development,

• learning occurs during situated activity,

• cognition is socially mediated, especially through dialog,

• education leads, or completes, development.

Here also, the importance of the context, of the clarification of the role of teachers is emphasized, and authors tried to help them in this clarification through the proposed approach.

Activity and group-based approach

One of the last dimensions of the proposed pedagogy is the experimental and group work dimension of the proposed pedagogy. In [START_REF] Blatchford | Toward a social pedagogy of classroom group work[END_REF] the benefits of group work is recognized mainly for conceptual development, thinking, reasoning and problem-solving (the topic of this article), where the acquisition of new skills or strategies is associated with practice-based tasks.

The article pointed out the dimensions that can either bring group work as effective either as uselessness. These dimensions are, among others: the quality of materials provided to learners, the incremental aspect of the learning to acquire robust and enduring habits of mind, and the motivation due to the social context in which the learning occurs.

Considering the social context, it appears that the numbers of members in each group, the nature of interaction between members, and the type of learning tasks have to be particularly focused on. To increase efficiency of interactions and also to provide good context by encouraging the motivation, it is recommended to consider students, in group work, as co-learners, and not considering them as students helping other students.

To evaluate the kind of pedagogy proposed in this article, the authors refer to [START_REF] Conole | Mapping pedagogy and tools for effective learning design[END_REF] in which an octahedron model is described to evaluate pedagogies.

This model is built out of 3 axes (see fig. 1):

• individual / social axis: considering either the individual as the focus of learning, or the learning as an explanation through interaction with others; • reflection / non reflection axis:

considering the basis of learning either as a conscious reflection on experience, or an explanation with reference to processes such as conditioning, preconscious learning and memorization; • information / experience axis: considering the basis of learning either as based on a body of information, text, artifacts or body of knowledge, or arising through direct experience, activity and practical application. Based on this model, the authors categorize their proposed approach as being mainly based on information, reflection and experience; as a set of basis body of knowledge is delivered but will be acquired and understood through its application on case studies and by a reflective approach on the method. This categorization refers to reflective learning as described in [START_REF] Dewey | Democracy and education[END_REF]).

Experimental

Compared to the traditional way of teaching (when teachers know the subject) with a whole unit divided into several topics (like Ideal Final Result, Size-Time-Cost operator, Miniatures men, Contradictions, Available resources, Laws of evolution, TRIZ methods, etc), the materials and course content will be discovered by the students and their teachers during the solving process related to the Titanic case.

The pedagogical method used for the teaching flow does not require specific skills (like when the subject is not mastered), as the teachers and their students will discover by themselves what problem analysis and problem solving methods and tools do they need, in such an urgency situation, to save people on the Titanic. Then the course material and TRIZ methodology are incorporated with course teaching and exercising, and the characteristics of such a pedagogy are a mix of the 3 approaches described in chapter 2.

To reach the objectives, the well-known example of TRIZ applied to the rescue of people during the Titanic sinking will be used to develop the creative game. A first session will be directed with teachers, and then the teachers will put it in practice with their students. In order to motivate both the teachers and the students, a kind of competition will be proposed, first between the different teams inside colleges, and then a challenge between the best team of each college. To be relevant this competition will have to fit some pre-defined rules, as nature of problem to be solved, allocated time, team composition, innovative evaluation, and so on. For the evaluation, the already presented "radar" diagram will be used once more.

Proposed process to "rescue the Titanic"

In order to focus on the tools of TRIZ without being limited by a lack of technological culture, the subject of study used in this case remained deliberately general and known to all, "how to save ALL passengers on the Titanic? ".

The transmission of knowledge and skills development is done by following the model of the "knowledge spiral" by expanding the spiral on 4 levels:

• An expert;

• Expert teachers (trained for 3 days on TRIZ at INSA Strasbourg by Denis Cavallucci), but never applied on a creativity project; • Teachers untrained to TRIZ; • Students.

The general organization was held following four steps:

• • •
• Choice of subject of study by the expert in consultation with a teacher, and planning of the different levels of challenge; • • • • Teachers' involvement: they were able to implement the process in almost the same conditions as students with an unknown subject in advance but in a short time, and they were supervised by an expert and a professor already trained; • • • • Students' involvement, supervised by a teacher, possibly with the help of a teacher already trained; at this stage of the process, each school selected a group by an internal jury to participate in the academic final; • • • • Academic final, where the winning group will be chosen by a high-level panel (expert and researchers, with colleges teachers).

For working with students, it was proposed to follow the following steps:

• 2 hours presentation of TRIZ tools that were each illustrated by Ideal Final Result, Size-Time-Cost operator, Miniatures men, Contradictions, Avalable resources, laws of evolution; • 2 hours of research work in groups of 2-3 students, where diversity has been favored in the formation of groups; at that time, a teacher remained available to provide methodological support; • 2 hours formatting media for the oral presentation of their project; • 4 hours devoted to the presentation of the different projects for a class, with for each group: o A presentation time; o Questions and answers on their presentation; o Comments on the use of TRIZ tools in their presentation; o Use of the "radar" evaluation tool [START_REF] Gore | Towards better teaching: productive pedagogy as a framework for teacher education[END_REF]; o The involvement of students in the assessment.

Teachers are playing the students' role!

In order to be efficient during the Titanic exercise, the teachers were asked to read in advance at least 3 French TRIZ-related articles on (1) "A pedagogy of rupture" (4 pages) stating that incremental innovation or rupture result from fundamental research and technological developments (but also creativity) and that TRIZ logically takes place in a technology training; (2) "Duo teaching" (4 pages) claiming that the technical education program disrupts teachers' practices, coming with two new materials: the case study to discover the innovations, and the creativity project to live the process ; and (3) "The relentless pace of innovation..." (25 pages) remembering that the evolution of technical systems has been studied in France in the second half of the twentieth century, with a renewed interest linked in part to the spread of TRIZ which has, among its key concepts, eight laws of the evolution of technical systems.

To highlight the problematic situations to be chosen by the learners themselves and immediately solved in real-time (less than 2-hour workshop to let participants feel like it could be their story to rescue a group of people during the 2-hour sinking of the Titanic) and to make the problem to solve more realistic, 2 videos are shown to the audience (1) the trailer of the Titanic film to see the atmosphere, with the human and material damage; and (2) a Paint animation that schematically shows the problematic situations without heroes and romance.

The problem of the "sinking Titanic" (see figure 3) is certainly quite different from the usual technical items used by the teachers with their students, but the solutions are based on TRIZ tools, so it is a good subject holder. Easy to understand by everyone, it is a perfect tool to stimulate a more creative state of mind to be adopted by the learners of innovation techniques.

The class of 24 teachers was divided into sub-groups of 4-5 participants and separated in different rooms with a paperboard to draw schemas (see figure 2), follow the 4-step method proposed by the TRIZ expert, and write their conclusions. The workshop itself lasted one hour (accelerated compared to the one for students, as teachers are already technical professionals and able to "jump" quicker in the situation to solve), and the feedback to the whole group took another hour to complete.

As a result, the use of the proposed resources and the sequence of tasks to be done helped smoothly to achieve the educational objectives with just a few basic rules for the creative game. Most teachers felt confortable with the workshop, some even agreed that they enjoyed imagining being the captain and possibly saving all passengers (at first they thought it was impossible, because the movie is so impressive that no other solutions could exist), and at least found TRIZ powerful... The next step for these newly trained teachers is to play the game with their students, which is another story...

Results and discussion

At this point, we are still waiting for the results, but a few trends are already clear:

• The approach is accepted by 4 teachers, entirely voluntary and without waiting for against-part, except new skills in both innovation and innovative educational approach; • The spiral extends smoothly, but through teachers who are able to live a risk along with their students. In addition to TRIZ tools, these teachers also teach innovation spirit being live models for their students; • We can rely on these teachers to gradually transfer their behaviour to their colleagues.

On the meta-rules aspect of the experiment, the authors were positively surprised to see how easy it was to explain the "Titanic case" to the audience, who immediately started to think abouth "who they are (officers, crew, passengers)" and "where they are (waiting on the deck, working hard in the machine room, or safe in the lifeboats)". Based on the state of the art (chapter 2), the best rules and characteristics to identify an other "universal" case study are:

• goal-oriented, practical and mainly based on group-activities;

• motivating both for teachers and students, raising"strong questions";

• bringing elements of interdisciplinary knowledge blocks by blocks;

• cultural knowledge, group identity, connectedness to the world;

• situated activity, socially mediated cognition, through dialog;

• approach based on information, reflection and experience.

There are obviously some difficulties of the proposed method, and more studies and experiments need to be done. Learning form experience while teaching seems valuable for teachers willing to "play the game", it means taking the risk to be seen by their students not as "knowing the subject" but more as "mentors". For teachers not interested to be "out of their comfort zone", the classical pedagogy needs a lot of work done in advance, by the education system and the teachers; on the other side, the experimental shown that the students were happy to take their part, in real-time, and contribute to the building blocks of the course.

Step by step, more teachers know, use and teach TRIZ to their students. From 4 teachers in the first experiment, we grown up to 4 different high-schools in the academy this year and TRIZ is now spontaneously quoted by students, teachers and pedagogical inspectors as a solution to solve inventive problems.

We will present complete results during the 2013 TFC in Paris.

Fig. 1 .

 1 Fig. 1. Octahedron model for pedagogy evaluation (Conole, Dyke et al. 2004).

Fig. 2 .

 2 Fig. 2. Titanic teachers' workgroups

Fig. 4 .

 4 Fig. 4. Titanic students' presentations Fig. 5. Titanic challenge winner

Acknowledgements

This experiment was made possible thanks to support of J.J. Ostermeier and D. Pinaud, Regional pedagogical inspectors, C. Buttner, High School Headmaster, and D. Gigant, Technical education manager at Lycée Blaise Pascal, Colmar, France.

Thanks to Ellen Domb for her support to re-use the "Titanic TRIZ" study case [10], and the pictures included in her article.