Nicolas Jouandeau

Zhi Yan

Patrick Greussay

Beiji Zou
email: bjzou@mail.csu.edu.cn

Yao Xiang
email: yao.xiang@mail.csu.edu.cn

Retinal Vessel Segmentation Based on Adaptive Random Sampling

Keywords: Blood vessel segmentation, unsupervised learning, sampling algorithm, retinal vessels, fundus images

This paper presents a method for the extraction of blood vessels from fundus images. The proposed method is an unsupervised learning method which can automatically segment retinal blood vessels based on an adaptive random sampling algorithm. This algorithm consists in taking an adequate number of random samples in fundus images, and all the samples are contracted to the position of the blood vessels, then the retinal vessels will be revealed. The basic algorithm framework is presented in this paper and several preliminary experiments validate the feasibility and effectiveness of the proposed method.

I. INTRODUCTION

Retinal vessel segmentation refers to extract blood vessels in retinal camera images. This technique is of important significance on screening, diagnosing and treating various ophthalmological and cardiovascular diseases. Manual segmentation of retinal blood vessels can guarantee the accuracy of the segmentation, but it is a long work which also needs some professional trainings. The public desires to achieve automation by means of computers. This paper introduces a new method for automatic retinal vessel segmentation based on an adaptive random sampling algorithm. The basic idea is (see Figure 1): take a random sample (i.e. a random pixel) p in the fundus image, if there exists a pixel q around p which has a lower value (i.e. the color of q is darker than that of p), then p retracts to q and marked as vessel. This method is actually to find the local optimal solutions, then combined into a global optimal solution. The rest of the paper is organized as follows: Section II describes an overview of some related works; Section III describes our adaptive random sampling algorithm; Section IV presents the experimental results obtained with the proposed method; and the paper is concluded in Section V at last.

II. RELATED WORKS

Retinal vessel segmentation is actually an issue of image processing, which has been widely studied since the late 1980s. Existing methods can be generally divided into the following categories [START_REF] Fraz | Blood vessel segmentation methodologies in retinal images -a survey[END_REF]: 1) machine learning (mainly including supervised learning and unsupervised learning), 2) matched filtering, 3) vessel tracking, 4) morphological processing, 5) multi-scale approaches, 6) model based approaches, and 7)parallel hardware based approaches. Experiments show that the accuracy of segmentation can reach up to 97%. However, among the existing works, the development of unsupervised learning methods is relatively small, and the accuracy of segmentation by using these methods is relatively low. [START_REF] Garg | Unsupervised curvature-based retinal vessel segmentation[END_REF] presented an unsupervised method for segmenting the vessel from color retinal images. The vessels are modeled as trenches and the medial lines of the trenches are extracted using the curvature information derived from a novel curvature estimate. The output of this process is in the form of a medial axes map of the vessels. The entire vessel structure is then extracted using a region growing method. Their method achieves an area under the ROC (Receiver Operating Characteristic) curve of 0.9271 and a maximum average accuracy of 0.9361 on the publicly available DRIVE database. [START_REF] Kande | Unsupervised fuzzy based vessel segmentation in pathological digital fundus images[END_REF] presented another unsupervised method by extracting the intensity information from red and green channels of the same retinal image to correct non-uniform illumination in color fundus images. Matched filtering is utilized to enhance the contrast of blood vessels against the background. The enhanced blood vessels are then segmented by employing spatially weighted fuzzy c-means clustering. The evaluation of the method resulted in an area under the ROC curve of 0.9518 and 0.9298, and an average accuracy of 0.8911 and 0.8976, respectively on the DRIVE and STARE databases.

III. OUR METHOD

Our proposed method is inspired by the sampling-based methods in the field of robotics [START_REF] Yan | ACS-PRM: Adaptive cross sampling based probabilistic roadmap for multi-robot motion planning[END_REF]. Sampling-based methods are currently considered state of the art for robot motion planning in high-dimensional spaces, and have been highly successful in solving many complex problems which have dozens or even hundreds of dimensions. These methods can avoid the problem of local minima, but they are probabilistically complete, meaning they cannot guarantee to find a solution if one exists. The fundus image could be considered to be a complex environment. Using a probabilistic method can meet the requirement of high efficiency and low consumption.

Our method for retinal vessel segmentation by using the adaptive random sampling algorithm is illustrated in Algorithm 1.

In Algorithm 1, line 1 means that the program will bee repeated until convergence has been reached. Line 2 indicates that we must take a sufficient number (denoted by m) of sample pixels. In line 4, |p-q| indicates the difference between the two pixel values p and q. Line 6 can actually be regarded as the retraction of the sample p to the location of the pixel q. That is the reason why we call this algorithm the adaptive random sampling. In the current version of the algorithm, n, m and threshold are three variables that have been assigned a value at the beginning of the program. Algorithm 1 Adaptive Random Sampling 1: while a maximum number of pixels n pixels has been marked as blood vessel do 2: for number of sample i = 0 to maximum number m do 3: generate a random sample p in retinal image 4: if q adjacent area α of p : |p -q| > ∃ ∈ threshold then 5: if q < p then 6:

q is labeled as vessel 7: else 8:

p is labeled as vessel 9:

end if 10: end if 11: end for 12: end while This manner of manual setting must be difficult to deal with a large number of images. It will be changed to an automatic manner in the program according to various images in our future implementations.

IV. EXPERIMENTS A. Experimental Setup

Several primary experiments have been conducted to evaluate our proposed method. All experiments reported in this paper were carried out on the Ubuntu 10.044 operating system with an Intel Core 2 Duo T5500 1.66GHz processor, an Intel 945GM Express chipset and two DDR2 800MHz 512MB dual channel memory. Our program is realized with secondary development tools based on libpng library, which can be downloaded from www.ai.univ-paris8.fr/ yz/ARS.tar.gz. ∼

B. Experimental Results

The first stage of the experiment is to transfer a color fundus image to a target image. This step is essential to vessel segmentation because it is meaningful to find an effective objective metric [START_REF] Xiang | Selective color transfer with multi-source images[END_REF]. In our method, the color fundus image is converted to a magenta channel image in CMYK (Cyan, Magenta, Yellow and blacK) color model. In contrast with the green channel image in RGB (Red, Green and Blue) color model, greyscale image, and color image, retinal vessels are more distinct in the magenta channel image in CMYK color model [START_REF] Wang | Detection and classification of thyroid follicular lesions based on nuclear structure from histopathology images[END_REF]. The magenta channel image is also more suitable for our adaptive random sampling algorithm, by reason of the obvious difference between vessels and other areas, thus more sensitive to the threshold. A visual comparison of the different images is given in Figure 2. The experimental fundus image is selected from the ImageRet database [START_REF] Kauppi | DIARETDB1 diabetic retinopathy database and evaluation protocol[END_REF]. Figure 3 shows the experimental results for four critical areas in the image. These four areas are sequentially labeled as area (A), area (B), area (C) and area (D), in accordance with the clockwise direction. Area (A) represents the vessel branch and cross, area (B) represents the blood vessels on optic disc, area (C) represents the central vessel reflex, and area (D) represents the blood capillaries. As can be seen from Figure 3, the current version of our method can identify vessel branch and cross, vessels on optic disc, and central vessel reflex effectively, but it cannot handle blood capillaries very well, because the pixel values of the capillary are too close to the values of the other area. This problem will be improved in our future research. Figure 4 depicts the vessel extracted by using our sampling-based method. The left image (subfigure (a)) represents the initial result. The vessels can be obviously identified from this image, but it still has a lot of noises for reasons of uneven background, macular and exudates. The right image (subfigure (b)) represents the result after preliminary noise reduction. In fact, the noises produced by using the current version of our method are mainly grouped around the macular and the exudates. From another point of view, it can be used in detection of pathology. In this paper, we presented a new retinal vessel segmentation method based on an adaptive random sampling algorithm. The idea is to take an adequate number of random samples in retinal camera images, and all the samples should retract to the location of the vessel so as to present it. A basic algorithm framework and some preliminary experimental results are presented. The experimental results proved the feasibility of our proposed method. The future work will focus on:

• Algorithm need to be improved, especially the determination of the values of n, m and threshold. • Image noise should be reduced effectively.

• More images need to be tested, and experimental results should be quantified with accuracy.

VI. ACKNOLEDGMENTS

This work has partly been supported by the Sino-French scientific project "Xu Guangqi" under contract number PHC 28011WC.

Fig. 1

 1 Fig. 1 An example illustrating the sampling-based method

  (a) Original color image (b) Greyscale image (c) Green channel image (RGB color model) (d) Magenta channel image (CMYK model)

Fig 2 :

 2 Fig 2 : A visual comparison of different models of a fundus image

  (a) Initial result (b) After preliminary noise reduction

Fig 3 :

 3 Fig 3 : Vessel extracted by using the sampling-based method


Lawrence Nderu
email: lnderu@jkuat.ac.ke

Nicolas Jouandeau

Herman Akdag
email: akdag@ai.univ-paris8.fr

Towards Universal Rating of Online multimedia content

Most website classification systems have dealt with the question of classifying websites based on their content, design, usability, layout and such, few have considered website classification based on users experience. The growth of online marketing and advertisement has lead to fierce competition that has resulted in some websites using disguise ways so as to attract users. This may result in cases where a user visits a website and does not get the promised results. The results are a waste of time, energy and sometimes even money for users. In this context, we design an experiment that uses fuzzy linguistic model and data mining techniques to capture users experiences, we then use the k-means clustering algorithm to cluster websites based on a set of feature vectors from the users perspective. The content unity is defined as the distance between the real content and its keywords. We demonstrate the use of bisecting k-means algorithm for this task and demonstrate that the method can incrementally learn from users profile on their experience with these websites.

I. INTRODUCTION

The Internet has become a major source of information. Individuals and organizations depend on the Internet in one way or another. It can be asserted that the web is the largest available repository of data with the largest number of users [START_REF] Herrera-Viedma | Evaluating the Information Quality of Web Sites, A Methodology Based on Fuzzy Computing With Words[END_REF]. Therefore, the web can be viewed as a meeting point of providers of information and services and their consumers.

Since its early days the Internet has seen remarkable growth. This growth is fueled by millions who provide high quality, trustworthy content. However, in this favorable landscape a good number of providers may seek to profit by promising users resources which eventually they cannot or do not provide. This leads to cases whereby a user might end up wasting time, energy and even sometimes money. This situation may also create a disillusioned user. Our goal is to develop a website clustering system that takes into consideration the previous users experiences.

The paper is set out as follows: First, we introduce some literature on web mining and fuzzy linguistic modeling. Secondly, an experiment is proposed to compute the agreement between what a web site claims it provides and what in-fact it provides based on users browsing patterns. Third, a discussion is provided to demonstrate the feasibility and effectiveness of the proposed model. Finally, some conclusions are presented at the end of this paper.

II. WEB MINING AND FUZZY LINGUISTIC MODELING

A. Web Mining

Web mining can be broadly defined as the discovery and analysis of useful information from the World Wide Web. This includes the automatic search of information resources available on-line, i.e. web content mining and discovery of users access patterns from web servers [START_REF] Cooley | Web Mining, Information and Pattern Discovery on the World Wide Web[END_REF].

As information technology grows, users can aggregate and store mass data more easily and efficiently [START_REF] Chen | A preference perception system on website by combining fuzzy set with data mining technology[END_REF]. Data mining can help users analyze and retrieve valuable information from mass data sources available online [START_REF] Fayyad | Data Mining and Knowledge Applications in Astronomy Discovery in Databases[END_REF]. Due to the existence of a variety of websites that claim to provide the information that the users are looking for, users find themselves dealing with the question of identification of sources that deliver what they claim. Web mining can be used to analyze users browsing behavior and provide suitable information for future users of the same websites. Important data can be obtained from web servers or proxy servers such as log files, user profiles, registration data and user sessions or transactions [5]. From these data we can discover valuable information about the websites visited.

B. Fuzzy Linguistic Modeling

Fuzzy linguistic modeling [START_REF] Herrera | Direct approach processes in group decision making using linguistic OWA operators[END_REF] is a very useful kind of fuzzy linguistic approach used for modeling the computing with words process as well as linguistic aspects [START_REF] Xu | Method Based on Fuzzy Linguistic Judgement Matrix and Trapezoidal Fuzzy Induced Ordered Weighted Geometric (TFIOWG) Operator for Multi-Attribute Decision-Making Problems[END_REF]. When collecting details from the users on-line activities some aspects are qualitative while others are quantitative. Fuzzy linguistic modelling has been widely used and has provided very good results, it deals with qualitative aspects that are presented in qualitative terms by means of linguistic variables [START_REF] Herrera-Viedma | Evaluating the Information Quality of Web Sites, A Methodology Based on Fuzzy Computing With Words[END_REF], [START_REF] Xu | Method Based on Fuzzy Linguistic Judgement Matrix and Trapezoidal Fuzzy Induced Ordered Weighted Geometric (TFIOWG) Operator for Multi-Attribute Decision-Making Problems[END_REF], [START_REF] Feng | To Provide Explanatory Semantics for Data Warehouses[END_REF], [START_REF] Herrera | A Model Based on Linguistic 2-Tuples for Dealing with Multigranular Hierarchical Linguistic Contexts[END_REF]. The 2-tuple Fuzzy Linguistic representation model provides the following advantages over classical models [START_REF] Herrera-Viedma | Evaluating the Information Quality of Web Sites, A Methodology Based on Fuzzy Computing With Words[END_REF].

1) The linguistic domain can be treated as continuous, while in the classical models it is treated as discrete.

2) The linguistic computational model based on linguistic 2-tuples carries out processes of computing with words easily and without loss of information.

3) The results of the process of computing with words are always expressed in the initial linguistic domain.

The model used in this paper to evaluate the conformance of what the web site says and what it actually delivers uses a set of quality criteria related to the web sites and a computation instrument of quality assessments. We assume that the quality of a web site is measured through users perceptions on the services offered through its web site [START_REF] Hidalgo | Applying Fuzzy Linguistic Tools to Evaluate the Quality of Airline Web Sites[END_REF], and that users have an objective to achieve when they decide to visit a certain website.

Users are invited to fill in a survey built on a set of quality criteria. To measure quality, conventional measurement tools used by the customers are devised on cardinal or ordinal scales. However, the scores do not necessarily represent user preferences. This is because respondents have to internally convert preference to scores and the conversion may introduce distortion of the preference [START_REF] Chen | A preference perception system on website by combining fuzzy set with data mining technology[END_REF]. For this reason, we use fuzzy linguistic modeling to represent the users' perceptions and tools of computing with words to compute the quality assessments [START_REF] Xu | Method Based on Fuzzy Linguistic Judgement Matrix and Trapezoidal Fuzzy Induced Ordered Weighted Geometric (TFIOWG) Operator for Multi-Attribute Decision-Making Problems[END_REF]. The subjectivity and vagueness in the assessment process is dealt with using the fuzzy logic [START_REF] Zadeh | The concept of a linguistic variable and its application to approximate reasoning[END_REF]. Multiple raters are often preferred rather than a single rater to avoid the bias and to minimize the partiality in the decision process. Fig. 1 shows an example of the way the Fuzzy computation with words was used in the experiment in one of the question to the users. Does the website provide accurate information? The choices are None-N, Very Little-VL, Little-L, Medium-M, High-H, Very High-VH and Perfect-P. By making use of the log files details and analysis of the results obtained from the online questioners, it is possible to adapt the paradigm of clustering. The key effectiveness of the clusters is an intuitive distance function [START_REF] Wang | On fuzzy cluster validity indices[END_REF]. Since the content of each single page p ∈ W can be represented by a feature vector of term frequencies, the whole details measurable properties as seen from the users is represented by set of feature vectors. One assumption made by this approach is that sites that fulfills a user needs as seen from the users pattern mining of related content but varying size will become very similar with respect to the Sum of Minimum Distances (SMD) [START_REF] Sharon | Minimum sum of distances estimator: robustness and stability[END_REF]. Let U 1 , U 2 be two users and let f : P → N d be a feature transformation that returns the feature vector of a users' profile p ∈ P where P is the set of all profiles. The concept of SMD is discussed by Hans et al in [START_REF] Kriegel | Classification of Websites as Sets of Feature Vectors[END_REF]. Using these details we create S 1 , S 2 . . . S 3 as centroids that represent the various log features. Fig. 2 shows the modeling of different websites, based on the fact that users have different expectations when visiting the websites.

IV. EXPERIMENTAL SETUP

An experiment was performed with the aim of collecting data from two sources, log analysis and online questionnaires. Students were used as experimental subjects. It is a known fact that this could lead to results that are artificial, particularly when students are asked to perform tasks which they have little or no experience. After identifying this as a potential problem, a number of websites were selected. The selection criterion was that a specific objective needed to be achieved by the website users. The time users took on this websites was then read from the freely provided Google API. A total of 199 randomly selected samples were collected, this included the time taken in a website and the time it would take to carry out the specific objective on the website.

Several methodologies have been suggested for rating websites [START_REF] Herrera-Viedma | Evaluating the Information Quality of Web Sites, A Methodology Based on Fuzzy Computing With Words[END_REF], [START_REF] Barnes | [END_REF], since our objective was to cluster websites based on what it promises, a new criteria was developed. The criteria developed identified the following as the important features with respect to our objective accuracy(Accur.), believable(Beliv.), relevant, details, value, revisit, and deliverability. These factors were obtained from the literature. Table I shows the online questionnaire, with results from one rater of the websites. The rates were to rate websites using: None-N, Very Little-VL, Little-L, Medium-M, High-H, Very High-VH and Perfect-P. The questionnaire was administered for ten visited URLs for which already the time taken by users while visiting this websites had already been noted. The fact that we had 199 log details for users and only selected 10 URLs to evaluate was dictated by a number of factors, the major one being the evaluation that we had carried out about the nature of the websites that we were to use in the study, but to introduce randomness this information was not available to the users. Table II shows the analyzed results for the 10 URLs. The arithmetic mean for the 2-tuple linguistic aggregation operators was used for the calculation. In this paper, we proposed a new solution to automatic classification of websites based on the level of satisfaction of the previous users'. The experimental results shows that clustering can be used as a way of telling how far a website is from the user's ideal website. The results so far point to an interesting direction in the sense that previous user's experience can be used to rank website and provide a metric for classification of websites. Combinations of these results are key point to developing future websites classification system.

Fig. 1 .

 1 Fig. 1. Linguistic Variable "Accurate"

Fig. 2 .

 2 Fig. 2. The Clustering Model.

Fig. 3 .

 3 Fig. 3. Clusters for the 10 URLS

TABLE I

 I the number of iterations. TableIII, shows the results obtained from the clustering program and Figure3shows the clusters for the 10 URLs. The websites used for this experiment U RL 1 , U RL 2 . . . , U RL 10 were well analyzed with respect to what the websites promised to deliver. Any new website that promises to deliver what these websites were delivering can now be clustered with respect to the created clusters. The entry 59.2 5.3 was an outlier for cluster one.

		TABLE II.	ANALYZED DATA FROM THE QUESTIONNAI.
	URL	Accur.	Beliv.	Relevant	Detail	Value	Revisit	Delivery
	1	8.72	8.33	8.88	7.89	8.33	8.55	8.49
	2	2.39	2.78	3.11	1.45	1.40	1.62	2.17
	3	8.00	8.44	8.22	8.44	8.22	788	8.33
	4	2.72	2.78	3.17	3.67	3.50	4.00	2.33
	5	8.27	7.44	7.22	7.22	7.22	8.11	8.16
	6	3.22	2.95	4.56	2.89	2.33	3.33	3.83
	7	8.55	8.49	6.72	8.16	7.50	9.32	7.33
	8	6.78	8.11	8.33	7.22	8.11	7.77	7.22
	9	3.50	3.67	2.67	4.33	2.83	2.83	3.67
	10	2.89	4.06	2.72	3.50	3.56	3.17	4.17
			V. RESULTS AND ANALYSIS
	The clustering K-means algorithm was used, with K=2
	and 100 as
									.	WEBSITE ONLINE QUESTIONNAIRE EXAMPLE
									N	VL	L	M	H	VH	P
								1.	Accurate information	x
								2.	Believable information	x
								3.	Relevant information	x
								4.	The right detail of information	x
								5.	Value for your time	x
								6.	Would you visit it again	x
								7.	Does it deliver	x

center

TABLE III .

 III CLUSTERING USING K-MEANS.

	Clustered Data: k=2 Maximum count (maxCount)=30
	Cluster	Data Unit	Sum	Time (Seconds)
	1	0	59.2	5.3
		2	57.5	5.2
		4	54.1	5.5
		6	56.1	6.0
		7	53.5	5.6
	2	1	14.9	2.7
		3	22.2	3.0
		5	23.1	3.1
		8	23.5	2.9
		9	24.1	3.6


Lawrence Nderu

Nicolas Jouandeau

Herman Akdag

IMPORTANCE OF THE NEUTRAL CATEGORY IN FUZZY CLUSTERING OF SENTIMENTS

Keywords: Sentiments Analysis, Fuzzy Clustering, Social Media, Neutral Category, Unsupervised Classification

Social media is said to have an impact on the public discourse and communication in the society. It is increasingly being used in the political context. Social networks sites such as Facebook, Twitter and other microblogging services provide an opportunity for public to give opinions about some issues of interest. Twitter is an ideal platform for users to spread not only information in general but also political opinions, whereas Facebook provides the capability for direct dialogs. A lot of studies have shown that a need exists for stakeholders to collect, monitor, analyze, summarize and visualize these social media views. Some authors have tended to categorize these comments as either positive or negative ignoring the neutral category. In this paper, we demonstrate the importance of the neutral category in the clustering of sentiments from the social media. We then demonstrate the use of fuzzy clustering for this kind of task.

Introduction

Clustering is a type of unsupervised learning that automatically forms clusters of similar things [START_REF] Jain | Data clustering: a review[END_REF]. During cluster analysis the aim is to put similar things in one cluster and dissimilar things in a different cluster [START_REF] Wang | On fuzzy cluster validity indices[END_REF]. Several types of clustering have been developed and a lot of literature exists on clustering methods. In fuzzy clustering, data elements can belong to more than one cluster and associated with each of the data points are membership grades which indicate the degree to which a data point belongs to the different clusters [START_REF] Krinidis | A robust fuzzy local information C-Means clustering algorithm[END_REF].

Sentiments found within comments, feedback or critiques provide useful indicators for many different purposes. Sentiment analysis provides policy makers and politicians with an opportunity to estimate the public sentiments with respect to policies, public services or political issues [START_REF] Dzogang | Expressions of graduality for sentiments analysis-A survey[END_REF]. With the massive growth of the social media a lot of outlets for publishing one's opinion (s) exist. A number of authors have considered sentiments analysis as a two class question, i.e. positive or negative [START_REF] Prabowo | Sentiment analysis: A combined approach[END_REF]. We assert the importance of treating neutrals as a fully qualified category.

The rest of the paper is organized as follows: first a discussion of related work on public sentiment analysis or opinion mining is presented followed by a discussion of clustering algorithms. We then present our model in this study and then conclusion and future work.

Related Work

Sentiments Analysis

Sentiment analysis has attracted a lot of interest in the recent past. An increasing number of scientists are tackling the task of automated sentiments detection and classification. This has resulted in a computing domain called effective computing [START_REF] Dzogang | Expressions of graduality for sentiments analysis-A survey[END_REF]. More and more users are posting about products and services they use, or expressing their political and religious views on issues. Such data can be efficiently used for marketing, making political decisions or social studies.

The computational treatment of opinion, sentiment and subjectivity has recently attracted a great deal of attention [START_REF] Ding | A Holistic Lexicon-Based Approach to Opinion Mining[END_REF], [START_REF] Breu | No Title[END_REF]. This is in part due to the potential of application areas [START_REF] Broder | Syntactic clustering of the Web[END_REF] [START_REF] Breu | No Title[END_REF]. In sentiment analysis neutrality is handled in various ways, this depends on the technique that is being used [START_REF] Vryniotis | The importance of Neutral Class in Sentiment Analysis | DatumBox[END_REF]. A number of papers tend to ignore the neutral category under the assumption that neutral texts lie near the boundary of the binary classifier. It is also assumed that not much can be learnt from neutral texts comparing to the ones with clear positive or negative sentiment [START_REF] Vryniotis | The importance of Neutral Class in Sentiment Analysis | DatumBox[END_REF], [START_REF] Dzogang | Expressions of graduality for sentiments analysis-A survey[END_REF]. Sentiment about a subject is the orientation (or polarity of the opinion on the subject that deviates from the neutral state [START_REF] Yi | Sentiment analyzer: extracting sentiments about a given topic using natural language processing techniques[END_REF]. The reasoning behind having the neutral sentiment as a category on its own is based on the fact that some opinions are facts. Thus, the statement "the song was well done" has a positive polarity. The statement "the song fails to impress" has a negative polarity, but the statement "the song is in the higher note" has a neutral polarity and indeed provides further information about the song. It is therefore not uncommon to have statements that are neutral.

Clustering

Clustering is a technique used in unsupervised learning. The aim is to cluster similar data points in one cluster and dissimilar points in a different group. Most clustering algorithms do not rely on assumptions common to conventional statistical methods, such as the underlying statistical distribution of data. This means that clustering algorithms are useful in situations where little prior knowledge about the distribution of the data is known [START_REF] Wang | On fuzzy cluster validity indices[END_REF]. Since clusters can formally be seen as subsets of data set, one possible classification of clustering methods can be according to whether the subsets are fuzzy or hard.

Hard clustering methods are based on classical set theory and require that an object either does or does not belong to a cluster. Hard clustering involves partitioning the data into specified number of mutually exclusive subsets. Fuzzy clustering methods, however allow the objects to belong to several clusters simultaneously, with different degrees of membership. In many situations, fuzzy clustering is more natural than hard clustering. Objects on the boundaries between several classes are not forced to fully belong to one of the classes, but rather are assigned membership degrees 0 and 1 indicating their partial membership [START_REF] Wang | On fuzzy cluster validity indices[END_REF].

The potential of clustering algorithms to reveal the underlying structure in data can be exploited in a wide variety of applications [START_REF] Sharon | Minimum sum of distances estimator: robustness and stability[END_REF]. Clustering techniques can be applied to data that is quantitative (numerical), qualitative (categorical) or a mixture of both. The data is typically observations of some physical process. Each observation consists of n measured variables, grouped into an n-dimensional column vector Zk = [z1k, z2k, …,znk]T , Zk n . A set of N observation is denoted by Z = {Zk | k=1, 2, ..., N } and is represented by an n X N matrix. Various definitions of a cluster can be formulated, depending on the objective of clustering. The discussion on hard clustering is covered by [START_REF] Zass | A Unifying Approach to Hard and Probabilistic Clustering 2 . Clustering and Complete Positivity[END_REF] [START_REF] Sharon | Minimum sum of distances estimator: robustness and stability[END_REF], below we present a discussion of fuzzy clustering.

Fuzzy Clustering

The generalization of the hard partition to the fuzzy case follows directly by allowing µik to attain real values in [0, 1]. Conditions for a fuzzy partition matrix are given by [START_REF] Broder | Syntactic clustering of the Web[END_REF].

µik∊ [0, 1], 1 ≤ i ≤ c, 1 ≤ k ≤ N ∑ µ݅݇ ୀଵ = 1, 1 ≤ k ≤ N 0 <∑ ߤ݅݇ ே ୀଵ < ܰ, 1 ≤ ݅ ≤ ܿ
The ith row of the fuzzy partition matrix U contains values of the ith membership function of the fuzzy subset Ai of Z. The total membership of each zk in Z equals one. Considering the range of values from [0, 1]. A number of fuzzy clustering algorithms exist; below we discuss the fuzzy Cmeans clustering.

Fuzzy C-Means Clustering

Fuzzy C-means (also called C methods) is an example of fuzzy clustering which allows one point to belong to one or more clusters [START_REF] Paper | A FUZZY HIERARCHICAL CLUSTERING METHOD FOR CLUSTERING DOCUMENTS[END_REF]. Fuzzy C-means was developed by Dunn and improved by Bezdek and is frequently used in many areas including pattern recognition [START_REF] Cannon | Efficient Implementation of the Fuzzy c-Means Clustering Algorithms[END_REF].

Neutral class

Neutrality in sentiment analysis is handled differently, by different authors [START_REF] Koppel | The Importance of Neutral Examples for Learning Sentiment[END_REF]. This mostly depends on the technique that is being used. In lexicon-based techniques then eutrality score of the words is taken into account in order to either detect neutral opinions or filter them out and enable algorithms to focus on words with positive and negative sentiment [16][19]. The inclusion of the neutral class in our study is based on the fact that in sentiment analysis we believe that not everything is positive or negative.

From Computing with Words to Computing with Numbers

Computing in its usual sense is centered on manipulation of numbers and symbols. In contrast, computing with words is a methodology in which the objects of computation are words and propositions drawn from a natural language [START_REF] Zadeh | The concept of a linguistic variable and its application to approximate reasoning-I[END_REF]. Computing with words is inspired by the remarkable human capability to perform a wide variety of physical and mental tasks without any measurements and any computations [START_REF] Bordogna | A Fuzzy Linguistic Approach Generalizing Boolean Information Retrieval : A Model and Its Evaluation[END_REF]. The basic difference between perception and measurements is that measurements are crisp (hard), whereas perception is fuzzy [START_REF] Zass | A Unifying Approach to Hard and Probabilistic Clustering 2 . Clustering and Complete Positivity[END_REF]. Many aspects of different activities in the real world cannot be assessed in a quantitative form, but in a qualitative one [START_REF] Decision-Making | A Model Based on Linguistic 2-Tuples for Dealing with Multigranular Hierarchical Linguistic Contexts[END_REF]. Fuzzy linguistic modelling has been widely used and has provided very good results, it deals with qualitative aspects that are presented in qualitative terms by means of linguistic variables [START_REF] Nderu | Towards Universal Rating of Online Multimedia Content[END_REF].

When sentiments are expressed in general as either positive or negative some important information is lost. Since sentiments are expressed using the natural language, we consider the interpretation of those sentiments using a set of seven terms (more could be used) and their semantics. Fig. 1, demonstrates the computing with words interpretation of numerical values [START_REF] Herrera | A 2-tuple fuzzy linguistic representation model for computing with words -Fuzzy Systems[END_REF]. For sentiments to be beneficial, it is important that we extract a lot of information from them. For example, consider the answer to the question "how are people responding to this ad campaign". An answer that says negative could lead us into changing the whole ad campaign and yet maybe if we knew it is at a value of 0.67 (as shown in Figure 1), we could just carry out some improvements and the sentiments could change.

Classifying sentiments as either positive or negative, is very general and some information could be lost, adding the category neutral improves, but still does not capture all the information in the sentiments. Below we demonstrate fuzzy clustering of sentiments.

The Proposed Model

A total of 140 negative tweets on the International Criminal Court (ICC), in Kenya were collected. The aim is to propose a model that provides more information than just telling us that the sentiments were negative. The choice of the tweets was done by a being. The Cohen's Kappa which is used to check for inter-rater reliability [START_REF] Application | Cohen ' s Kappa[END_REF] was used. Generally, a Kappa value > 0.70 was considered to be a satisfactory agreement. Table 1, shows the results of the rating by 2 experts. A value of 0 shows a sentiment that could be considered neutral, while 1 is a sentiment that is highly negative. The two rates agreed on 87 tweets, and this are the ones that were tabulated. A sentiment could have some parts that are positive, negative or even neutral. Our aim in this mode of sentiment analysis is to gain all the necessary information from the sentiment. In a 3 dimension plot this could be as shown in figure 2, where horizontal axis= positivity of the sentiment, width = negativity of the sentiment and vertical shows the neutrality or the sentiment.

Conclusion

Information found in the text data is either: Objective information (facts) or Subjective information (opinions). In this paper we have considered the problem as a three-class classification problem (positive, neutral or negative), with varying levels of positivity, neutrality or negativity rather than a two-class problem (positive or negative). The fuzzy clustering which consistsof optimal grouping of given data points together but in such a way that each data point can be shared by one or more cluster by belonging partially to another has been used. The idea that our model is pursuing here is that in some cases the sentiment holder could be persuaded to change his/her view if for example it is not "a very strong negative" sentiment.

In our future work, we want to implement a sentiment analysis system that is maintained automatically with the exact value of how negative, positive or neutral a sentiment is. Such a system could help opinion leaders for example to know the kind of individual who could be persuaded to change their sentiments over an issue.

Fig. 1 .

 1 Fig.1. How positive is a sentiment

Fig. 2 .

 2 Fig.2. A 3-d plot of the sentiments values

Table 1 .

 1 The results of the Analyzed Tweets

	Numerical	0	0.17	0.33	0.5	0.67	0.83	1
	values
	Count	0	5	3	8	18	24	29


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

Varying Complexity in CHINESE DARK CHESS Stochastic Game

CHINESE DARK CHESS is an interesting stochastic game that combines revealing, positioning and capturing moves. As many variants are possible, we propose a general protocol that allows to play this game as puzzle, competitive or cooperative game, by 1 to multiple players. Varying complexity can be addressed by this variations. A short visualisation of 4 different games are presented.

I. INTRODUCTION

CHINESE DARK CHESS is a popular stochastic two players game in Asia that is often played on 4x8 rectangular board where players do not know flipping moves' payoff. One player is black and the other player is red. The first flipping move defines the first player color. Each player starts with the same set of pieces. Relationship between pieces defines capture possibilities. Pieces evolve on squares and can move vertically and horizontally from one square to an adjacent free square (i.e. up, down, left and right). All pieces can move on adjacent squares except cannons that can jump. Jumping are conditioned by a jumping piece and a target piece. Free spaces can stands in the path, before and after the jumping piece.

Chen et al. [START_REF] Chen | Chinese Dark Chess[END_REF] used alpha-beta algorithm with different revealing policies combined with a initial-depth flipping method to reduce the branching factor. They distinguished opening, middle and endgame to apply different policies.

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. Created databases are done for each first move color, up to 8 revealed pieces. They used 2TB of memory to represent 10 12 positions. Positions status are stored as win, lost or draw.

Yen et al. [START_REF] Yen | The Art of the Chinese Dark Chess Program DIABLE[END_REF] presented a non-deterministic Monte Carlo tree search model by combining chance nodes [START_REF] Lanctot | Monte Carlo *-Minimax Search, 23rd Int. Joint Conf. on Artificial Intelligence (IJCAI-2013)[END_REF] and Monte Carlo Tree Search (MCTS). They create shorter simulation by moderating the three policies named Capture First, Capture Stronger Piece First and Capture and Escape Stronger Piece First. As draw rate decreases, win rate increases and simulations are more meaningful for MCTS.

Chang and Hsu [START_REF] Chang | A Quantitative Study of 24 Chinese Dark Chess[END_REF] solved the 2x4 variant. They created a Oracle variant where every pieces are known. Comparing the Oracle variant and the classical variant shows that the first move is crucial on 2x4 board. Safidine et al. [START_REF] Saffidine | Material Symmetry to Partition Endgame Tables[END_REF] exploit pieces combinations to reduce endgame databases. By combining material symmetry identified by relations between pieces and endgames building with retrograd analysis, winning positions are recorded in databases. This general method has been applied to SKAT, DOMINOES and CHINESE DARK CHESS. Even if relationship between pieces in CHINESE DARK CHESS creates intricate symmetries, they reduced the size of 4 elements endgame tables by 9.92 and the size of 8 elements endgame tables by 3.68.

As many variants are possible in CHINESE DARK CHESS, we propose an new protocol that allows to play different variants of this stochastic game. Varying games should help to understand new tactics and new strategies, from single to multi-players.

The paper is organized as follows. Section II describes a general protocol to play with multiple variants. Section III presents a visualisation of the resulting complexity of 4 different variants before the conclusion.

II. DESCRIPTION OF A GENERAL PROTOCOL

To vary complexity in the CHINESE DARK CHESS stochastic games, we propose a simple modular protocol that defines format messages between programs (i.e. between a server and a client during a game). Multiple clients are allowed and clients do not communicate between themselves. Communications are over TCP. Clients connect to the server using the ports printed out by the server. Messages use symbolic expressions (i.e. S-expressions) as message structure. S-expressions come from Lisp programming language, that allows to easily represent tree structures. S-expressions are strings between parenthesis. They are simple to parse and to extend. Even if they are long, they stay easily readable by humans. To initiate the protocol, each client has to send a first version string '((version 1.0))' (see Tab. III). Expressions presented in Tab. I show server to clients communications. Inside id expression, the value PLAYER ID is varying from 1 to N . In the same time, the server should send the expression (players N ). team expression allows to team-play scoring. teammate expression allows to consider team member and multi-player games. size moves and jumps expressions allow to consider different board's configuration, even non rectangular once. To reduce combinatorial of jumping positions, jump expression contains 3 values that defines origin, first and last target (considering that all positions between first and last target are possible targets). Even if jump expression list possible jump, jumping condition has to be checked while applying a jump on a board. Enumerating all moves and jumps allow to build asymmetric boards and topologies. We believe that it should be interesting to fit game situations to real situations, where topologies are commonly not symmetric. This should also produce games that are closer to classical real-time strategic games. The main variants of CHINESE DARK CHESS are played with 4x8 and 8x16 boards with 2 players. On such symmetric boards with L lines and C columns (with L ≥ 2 and C ≥ 2), the number of moves is equal to 4LC -2L -2C and the number of jumps is equal to

L(C -2)(C -1) + C(L -2)(L -1)
. It makes 104 moves and 216 jumps on 4x8 board, and respectively 464 and 2352 on 8x16 board. By using 3 values inside jumps expression, we reduced the number of jumps expressions needed. As a board should be partially revealed at start, revs list all positions that can be revealed. game expression defines game's type (i.e. traditional or strategic positional for example). pieces expression defines involved pieces. According to CHINESE DARK CHESS games, pieces can be identified by letters as presented in Tab. II. Thus a 2x4 board set should be KPPPkppp. For unrevealed pieces on the board, we introduce a 'X' character. For empty positions, we introduce a '.' character. Thus a 2x4 board expression with 2 unrevealed pieces and 1 empty position should be KPPP.kpXX. Transmitting the board at each step should allow players to request timeout to check their current player. To allow players to put pieces in a empty position, hand expression gives a piece to a player's hand. puts expression lists all possible positions where players can put a piece. turn expression should be sent to the current player whereas info expression should be sent to other players. In a multi-player game, these expressions should be practical to inform other players status. When a player wins, the server should send the win expression to all players. Inside the win expression, 0 values are admitted to express individual and team victory. For example, the expression (win 1 0) indicates player-1 victory whereas the expression (win 0 2) indicates team-2 victory.

Expressions presented in Tab. III show clients to server communications. Inside init expression, each client declares its name and contributes to the server seed. According to the board expression ever presented in Tab. I, clients reminds to the server the initial situation enhanced with one of the five next expressions: rev expression is used to reveal POS position; mov expression is used to move a piece from POS I to POS F; resign allows client to resign the current game; bag and put are useful for a variant where unknown pieces are out of the board and where their placement depends on client's choice. In this variant, the initial board is empty. All pieces are unknown and a player chooses one unknown piece, reveals its status and places it on the board. Then until some unknown pieces exist, each player can move one of their pieces on the board according to traditional rules or pick up a new piece for unknown set, reveal and place it on the board. When all pieces are places on the board, each player must move a piece on the board.

~K K k k Guard } G G g g Bishop | B B b b Knight { N N n n Rook z R R r r Cannon y C C c c Pawn x P P p p
The game ends when one player is not able to move one of its pieces. According to Tab. I and Tab. III expressions, we can defines game types :

• traditional 1 VS 1 game • handicap game where players have different sets according to their level • strategic positional variant where players pick unknown pieces from a bag, reveal them and choose their first position on the board • single player game where the goal is to remove all piece of one color as fast as possible pieces number In the single player strategic positional variant with classical sets, the optimal policy is to put pieces on the board and wisely sort them on the board according to future capturing moves. When all pieces of one color are reveal, N pieces are captured within N moves if N paths exists for N master pieces of N subsets. For the single player traditional game, the optimal policy is also to reveal pieces while one color is completely revealed. Then the goal is the identify short independent paths, combination of blue or red moves, minimizing turn back or maximizing exploitation of cannons' abilities.

(revs (0)(1)(2)(3)(4)(5)(6)(7)) S → C1 ((board XXXXXXXX)(turn 0 1)) S → C2 ((board XXXXXXXX)(info 0 1)) S ← C1 ((board XXXXXXXX)(rev 0)) S → C1 ((board KXXXXXXX)(info 0 2)) S → C2 ((board KXXXXXXX)(turn 0 2)) S ← C2 ((board KXXXXXXX)(rev 1)) S → C1 ((board KPXXXXXX)(turn 1 1)) S → C2 ((board KPXXXXXX)(info 1 1)) S ← C1 ((board KPXXXXXX)(rev 4)) S → C1 ((board KPXXpXXX)(info 1 2)) S → C2 ((board KPXXpXXX)(turn 1 2)) S ← C2 ((board KPXXpXXX)(mov 4 0)) S → C1 ((board pPXX.XXX)(turn 2
As example, Tab. IV and Tab. V present respectively one traditional 1 VS 1 game on 2x4 board and one strategic positional variant 1 VS 1 game on 2x4 board. All other variants are then easy to settle.

III. PRACTICAL VISUALISATION

In this section, we present a visualisation of a single player game and 3 two players games. As games finish when a player has no more move, games are visualized according the number of moves' evolution during the game.

(moves (0 1)(0 4)(1 0)(1 2)(1 5)(2 1)(2 3) (2 6)(3 2)(3 7)( 4
0)(4 5)(5 4)(5 6)(5 1) (6 5)( 62)(6 7)(7 6)(7 3)) (jumps (0 2 3)(1 3 3)(2 0 0)(3 0 1)(4 6 7) (5 7 7)(6 4 4)(7 4 5)) (puts (0 Fig. 1 presents a single player game on 8x4 board. All possible moves (i.e. all pieces of all colors) are represented in blue and free spaces (i.e. captured pieces) in red. The goal is then to remove all pieces of one color as fast as possible while revealing pieces can lead to move both color to make shorter paths.

)(1)(2)(3)(4)(5)(6)(7)) S → C2 ((id 2)(players 2)(game strategic) (size 8)(pieces KPPPkppp) (moves (0 1)(0 4)(1 0)(1 2)(1 5)(2 1)(2 3) (2 6)(3 2)(3 7)(4 0)(4 5)(5 4)(5 6)(5 1) (6 5)(6 2)(6 7)(7 6)(7 3)) (jumps (0 2 3)(1 3 3)(2 0 0)(3 0 1)(4 6
Fig. 2 presents a very short traditional games on 8x4 board that ends in 31 turns (i.e. 62 plies). Fig. 3 presents a more competitive traditional games on 8x4 board that respectively finish in 53 turns (i.e. 105 plies). Fig. 4 presents a strategic variant on 8x4 board that ends in 62 turns(i.e. 124 plies). In two players figures, curves represent the number of possible moves (including moves, jumps and reveals) for each player over turns. Turns are represented on horizontal axis and number of possible moves on vertical axis. Black player is shown in blue and red player in red. In Fig. 4, the green curve shows the number of free positions on the board.

In the first game shown in Fig. 1, the player tries to maximize the coverage of one set of pieces regarding to the other set until one color is fully localized. In a second phase, the goal is to reduce the path to capture all pieces (considered as opponent pieces).

In the second game shown in Fig. 2, a strong first player is facing a weak second player. At the end, the strong player wins. It shows that in traditional variant, the complexity stays the same during most of the time. If it decreases drastically for one player while increasing for the other player, then it raises one player win.

In the third game shown in Fig. 3, players' level are equivalent. It makes a game that is more competitive than the first. During the first 40 plies, the red player takes advantage and keep it until the end by reducing black player's moves thus constraining him to reveal moves. It shows that for the winning player, the number of moves is at least as important as for the other player in most cases. For the winner, the state space remains important until 5 to 10 plies before the end.

In the fourth game shown in Fig. 4, players' level are equivalent. Each player stacks units and try to constraint opponents pieces. If a player gains a material advantage, then the game will probably evolve in a victory for this player. As it appears in the figure, when puts possibilities (in green) increase with one player (blue) moves while the other player's (red) moves decrease, it means that the first player is taking benefit of its position.

IV. CONCLUSION

Varying complexity in games is a way to develop more general algorithms. CHINESE DARK CHESS is an interesting stochastic game that allows to simply vary many parameters, from pieces inside sets to rules to put pieces on the board. We have presented a general protocol that allows to play this game with different degrees of complexity. This protocol allows to play with other players, even with a cooperative mode. We believe that providing variants based on CHINESE DARK CHESS will promote the game and helps researchers to enhance their knowledge in stochastic games.

Fig. 1 .

 1 Fig. 1. Single player 4x8 game.

Fig. 2 .

 2 Fig. 2. Short 4x8 traditional game.

Fig. 3 .

 3 Fig. 3. Competitive 4x8 traditional game.

TABLE II TRADITIONAL

 II CHINESE DARK CHESS PIECES.

		Red Player		Black Player
	Pieces names	Num. Icon	Char	Num Icon	Char
	King


Nicolas Jouandeau

Tristan Cazenave
email: cazenave@lamsade.dauphine.fr

Small and large MCTS playouts applied to Chinese Dark Chess stochastic game

Monte-Carlo tree search is a powerful paradigm for full information games. We present various changes applied to this algorithm to deal with the stochastic game Chinese Dark Chess. We experimented with group-nodes and chance-nodes using various configurations: with different playout policies, with different playout size, with true or evaluated wins. Results show that extending playout size over the real draw condition is beneficial to group-nodes and to chance-nodes. It also shows that using evaluation function can reduce the number of draw games with group-nodes and can be increased with chance-nodes.

Introduction

Chinese Dark Chess (CDC) is a popular stochastic two players game in Asia that is often played on 4x8 rectangular board where players do not know flipping moves' payoff. The two player (called black and red) start with the same set of pieces: one king, two guards, two bishop, two knights, two rooks, two cannons and five pawns (pieces that are similar to Chinese Chess). Before the first move, players do not know their color. The first player move defines the first player color. In classical games, pieces evolve on squares and can move vertically and horizontally from one square to an adjacent free square (i.e up, down, left and right). A piece can capture another piece according to pieces value. Captures are done on vertical and horizontal adjacent squares except for cannons that capture pieces by jumping over another piece. Such jump is done over a piece (called the jumping piece) and to the target piece. Free spaces can stand between its initial position and the jumping piece and between the jumping piece and the target position. Even if flipping moves imply multiple board possibilities, classical moves can lead to similar positions during the game and capturing rules are different for each piece, MonteCarlo Tree Search (MCTS) programs have been recently improved as best. We show in this paper two different MCTS implementations that can be further improved using longer playouts, playing policies playout and heuristic playout.

Section 2 describes related works. Section 3 presents two MCTS implementations. Section 4 shows experimental results achieved with different playout size, playout policies and playout evaluation functions. At the end, section 5 concludes.

Related works

In this section we expose related works on CDC. Even if there are few works on this game, previous works concern alpha-beta, move policies, endgame databases and MCTS.

Chen et al. [START_REF] Chen | Chinese Dark Chess[END_REF] used alpha-beta algorithm with different revealing policies combined with a initial-depth flipping method to reduce the branching factor. They distinguished opening, middle and endgame to apply different policies.

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. Created databases are done for each first move color, up to 8 revealed pieces. They used 2TB of memory to represent 10 12 positions. Positions status are stored as win, lost or draw.

Yen et al. [START_REF] Yen | The Art of the Chinese Dark Chess Program DIABLE[END_REF] presented a non-deterministic Monte Carlo tree search model by combining chance nodes [START_REF] Lanctot | Monte Carlo *-Minimax Search, 23rd Int. Joint Conf. on Artificial Intelligence (IJCAI-2013)[END_REF] and MCTS. They create shorter simulation by moderating the three policies named Capture First, Capture Stronger Piece First and Capture and Escape Stronger Piece First. As draw rate decreases, win rate increases and simulations are more meaningful for MCTS.

Chang and Hsu [START_REF] Chang | A Quantitative Study of 24 Chinese Dark Chess[END_REF] solved the 2x4 variant. They created a Oracle variant where every pieces are known. Comparing the Oracle variant and the classical variant shows that the first move is crucial on 2x4 board.

Chen and Hsu [START_REF] Chen | Automatic Generation of Chinese Dark Chess Opening Books[END_REF] presented a policy-oriented search method to build opening books in case of very large state space as it is in CDC. Attack, defend, claim or discover territory are compared according to player's turn. Results show that player's level is a little stronger with openings. As flipping moves can completely change the game issue, they showed that enhancements provided are probabilistically acquired.

Safidine et al. [START_REF] Saffidine | Material Symmetry to Partition Endgame Tables[END_REF] exploit pieces combinations to reduce endgame databases. By combining material symmetry identified by relations between pieces and endgames building with retrograd analysis, winning positions are recorded in databases. This general method has been applied to Skat, Dominoes and CDC. Even if relationship between pieces in CDC creates intricate symmetries, they reduced the size of 4 elements endgame tables by 9.92 and the size of 8 elements 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.

Move groups have been proposed in [START_REF] Childs | Transpositions and move groups in Monte Carlo tree search[END_REF] to address the problem of MCTS in games with a high branching factor. When there are too many moves, it can be a good heuristic to regroup the statistics of moves that share some properties. For example in the game of Amazons where the branching factor can be of the order of a thousand of moves a natural way to reduce the branching factor is to separate the queen move from the stone placement. In the imperfect information game Dou Di Zhu, Information Set [START_REF] Cowling | Information Set Monte Carlo Tree Search[END_REF] has been combined with move groups: the player first chooses the base move and then the kicker, as two separate consecutive decision nodes in the tree. Move groups have also been analyzed on an abstract game [START_REF] Van Eyck | Revisiting move groups in monte-carlo tree search[END_REF].

Stochastic MCTS

In this section, we present the use of chance-nodes and of group-nodes with MCTS. Group-nodes are used to reduce the branching factor created by flipping moves. In a similar manner to move groups that regroup moves, we define groupnodes to consider all revealing moves at the same position in a single node. Apart from that, chance-nodes are the classical way to manage stochastic information in trees. We present the main loop and the selection function of MCTS with group-nodes and with chance-nodes. Both algorithms are presented as anytime interruptible process, that tend to produce better solution over computing time and that are instantaneously interrupt when time is up or when a winning move is found.

With group-nodes

During the game, applying a flipping move can conduct to different boards. At the beginning of the game, the first player has 32 possible moves that correspond to 4 * 10 36 possibilities. During the game, the number of possible boards linked to flipping moves decreases with the number of unrevealed pieces. For the penultimate flipping move, 2 boards are possible and for the last flipping move, only one board. But as the number of possible boards stays over 120 for more than 5 different pieces, the number of possible boards remains important at most of the time before endgame. To reduce the number of children node produced by flipping moves, all possible boards that arise from a flipping move are gathered in single group-node. Therefore, at the beginning of the game, the root node is followed by 32 children that are group-nodes. Then other actions (moves, jumps and captures) are represented in the tree with classical nodes. The main loop of MCTS with group-nodes is presented in Alg 1. The selection phase (line 2) returns a node q to expand, its corresponding board and L the list of moves to apply for expansion. By default, all nodes inserted in the tree have U N SET winning color. If this node is known as winning position, the process is interrupted (line 3). Otherwise each element of L creates a new child to q and store it in N . For each element of N , the board is modified, a new simulation is applied from the modified board and a new result is backpropagate from the new node up to the root node. At the end, the bestNext function selects the best next node q best of the root node that defines the best next move.

The selection function of MCTS with group-nodes is presented in Alg 2. The process iterates to find the best node q, its corresponding board and its moves M. There are 4 different cases:

q is known as winning position. Then the process is interrupted (line 5).

q is leading a player to a new winning position. Then it returns q with the corresponding board and an empty set (line 7).

Algorithm 1 MCTS with group-nodes 1: while not-interrupted do 2: (q, board, L) ← select ( ) 3:

if q.winning color ! = U N SET then break 4:

N ← expandAll (q, L) 5:

for each e ∈ N do 6:

board ←applyMove (e, board) 7:

simulate (e, board ) 8:

backpropagate (e) 9:

end for 10: end while 11: q ← bestNext (root node) 12: return q q is a new node that has not been extended previously. Then it returns q with the corresponding board and new moves that corresponds to the board (lines 9 to 11). q is a group-node previously evaluated with a different flipping outlet that produces new moves that are not yet considered in q children. Then it returns q with the corresponding board and new moves that corresponds to only previously unconsidered moves in q group-node (line 13 to 15).

The next function (Alg 2 line 6) returns all current next nodes of q. The move function (line 8) returns all next moves of the current board. If M is empty (line 9), the corresponding node is noted as winning node for the opponent player of the current board turn. The test applied line 13, checks if the current situation fits with the current group-node. If it fits, then the best next function is applied to select the best nodes inside M (line 17). If it does not fit, then the selection process is stopped and M becomes a set of previously unconsidered moves (line 14).

With chance-nodes

During the game, moves can conduct to the creation of chance-nodes. As different pieces are unknown, each flipping move is represented with a chance-node. Other board modifications, like moves, jumps and captures, are represented with classical nodes. Chance-nodes are composed of classical nodes. At a chance-node, each flipping possibility corresponds to a new child. The main loop of MCTS with chance-nodes is presented in Alg 3.

According to UCT formulae, this process applies iteratively selection, simulation and backpropagation. From a selected node q, the simulation leads to a new node q new from which the result of the last simulation is backpropagate toward the root node. At the end, the bestNext function selects the best next node q best of the root node that defines the best next move. The selection of a chance node can lead to different boards and the selection of a classical node leads to an expected situation. At the beginning, all nodes are inserted in the Algorithm 2 select ( ) with group-nodes 1: q ← root 2: board ← root board 3: M ← ∅ 4: while not-interrupted do 5:

if q.winning color ! = U N SET then break 6:

N ← next (q) 7:

if size (N ) = 0 then break 8:

M ← moves (board) 9:

if size (M) = 0 then 10:

q.winning color ← opponent (board.turn) 11: break 12:

end if 13:

if ∃ e ∈ M with e / ∈ N then 14:

M ← M -(M ∩ N ) 15: break 16:
end if 17:

(q, board) ← best next (q, M) 18: end while 19: return (q, board, M) Algorithm 3 MCTS with chance-nodes 1: while not-interrupted do 2:

(q, board) ← select ( ) 3:

if qnew.winning color ! = U N SET then break 4:

qnew ← simulate (q, board) 5:

backpropagate (qnew) 6: end while 7: q best ← bestNext (root node) 8: return q best tree without winning color information. If the selected node is a winning node, the process can be immediately interrupted (line 3 Alg 3 and line 4 Alg 4).

Algorithm 4 select ( ) with chance-nodes 1: q ← root 2: board ← root board 3: while not-interrupted do 4:

if q.winning color ! = U N SET then break 5:

M ← moves (board) 6:

if size (M) = 0 then 7:

q.winning color ← opponent (board.turn) 8:

return (q, board) 9:

end if 10:

if (posi, pos f ) ← newMove (q, board, M) then 11:

if (posi = pos f ) then 12:

q ← addChanceNode (q) 13:

qnew ← addNode (q ) 14: else 15:

qnew ← addNode (q) 16:

end if 17:

board ← play (posi, pos f ) 18:

return (qnew, board) 19:

end if 20:

(q, board) ← best (q, board, M) 21: end while

The selection function of MCTS with chance-nodes is presented in Alg 4. The process iterates to find the best node q and its corresponding board. From the root node and the root board, the current board is updated according to the best move. At each iteration, a set of moves M is defined according to the selected board position and its turn. If this set is empty (line 6), the corresponding node is noted as winning node for the opponent player of the current board turn. If the best move is a new flipping move (line 11), a new chance node and a new node are added in the tree. If initial and final positions differ, a simple classical node is added.

Experiments

In this section, we present various experiments to select fastest policies, to reduce draw endgames, with varying playout size, with or without evaluation function.

Fastest policies

In this section, we present various policies used to enhance playouts. We present basic and advanced ones and evaluate them to be useful in MCTS with as fast simulations as possible. The fastest policies are considered as most promising and are selected to continue our study.

We have used 4 basic playout policies, that are natural to use in CDC :

-Random, where players play randomly.

-Capture, where players try to capture opponent pieces.

-Avoid, where players try to avoid opponent's capture.

-Trap, where players try to minimize opponents moves.

According to these basics policies, we settled 4 advanced policies declined from the basics:

-Capture and avoid, where players try first to capture one opponent, try second to avoid opponents and otherwise play randomly. -Avoid and capture, where players try first to avoid opponents, try second to capture one opponent and otherwise play randomly -Capture and trap, where players try first to capture one opponent and otherwise to trap opponents. -Capture avoid and trap, where players try first to capture an opponent, try second to avoid opponents and otherwise to trap opponents.

All these policies have been tested for 2000 playouts at the beginning, the middle and the end of the game. Results are shown in Fig. 1-3 and in Tab. 1.

Fig. 1 show the board at the beginning of the game, when player colors are unknown. Best moves are colored in gray on the board and are bold in Tab. 1. 43.00 (0.00) a8-a7 --100 a8-a7 -100 -Fig. 2 shows the resulting board situation after the following 10 turns. Unknown pieces are represented with white circles. The 10 moves played are (columns are annotated with letters and rows are annotated with numbers. Flipping moves indicate a revealed piece under parenthesis. Moving and capturing moves indicate two coordinates. ) : c4(k) d1(P) ; d2(N) d5(p) ; c2(G) c3(c) ; c5(C) c5-c3 ; c4(p) c6(M) ; b3(r) c6-c5 ; b3-c3 c2-c3 ; c7(C) c5-d5 ; b6(g) d5-c5 ; b6-c6 b7(G) ; It is now first player's turn to play. 19 reveal moves remain. First player is black and its non-flipping possible moves are : b4-b3 ; c6-b6 ; c6-c7 ; c6-c5 ; Second player is white (i.e. red) and its non-flipping possible moves are : b7-b6 ; c5-c4 ; c5-d5 ; c3-b3 ; c3-c2 ; c3-c4 ; d2-c2 ; First player has captured only one C piece and second player has captured 3 pieces that are p c r. Good move for black is c6-c5, or reveal c8 and d7.

Fig. 3 shows an endgame board, where everything is known. Black has clearly lost the game.

As CDC games can end in a draw, we settled an evaluation function that can evaluate a draw board. This evaluation is based on the material that is remaining on the board for one player over its opponent. It allows to assign numerical value to draw endgame boards. As we do not know if playing first is an advantage, we allow this evaluation to reply draw if material are equivalent.

In some specific cases, draw depends on pieces position and then this function gives false win detection. In order, pieces {K G M R N C P} are associated to {0.15, 0.1, 0.07, 0.05, 0.03, 0.05, 0.05}.

Tab. 1 compares the time needed by basic and advanced policies to achieve 2000 playouts. This table also gives the average of remaining pieces and its standard deviation, the average playout size and its standard deviation, best moves with and without evaluation function.

It shows that some policies are too slow (i.e. Avoid, Avoid and capture, Trap, Capture and trap, Capture avoid and trap) to play a significant number of playouts to be simply used in MCTS. Remaining pieces and playout size showed us that longer playout could be interesting.

Reducing draw endgames

In this section, we select the best policies by checking their ability to create as less draw endgames as possible. Results are presented according to various draw conditions.

As some policies are considered as too slow, we only kept Random (i.e. RND), Capture (i.e. CAP RND), Capture and avoid (i.e. CAP AVD RND) and Avoid and Capture (i.e. AVD CAP RND) (where these three last also call random if nothing has been done first). Tab. 2 shows the time used to generate 2000 playouts from the beginning board. Next columns show the draw ratio, the average number of pieces at the end, the playout size according to different draw conditions. In a normal game, the draw condition is equal to 40 moves without capture or reveal. It shows that the number of draw can be reduced significantly by increasing the draw condition. In the same time, the number of remaining pieces are reduced. It shows that CAP RND is really efficient for very important value of draw condition. We decided to eliminate the AVD CAP RND policy that increases the time with fewer draw than simple RND policy.

Group-nodes vs. chance-nodes

In this section, we challenge MCTS players by facing group-nodes against chancenodes, with different playout size, with most promising policies. For each combination, we also checked the evaluation influence in helping MCTS formulae to select better player. All the player are tested against a reference player, that simply plays randomly when pieces are unrevealed and otherwise applies minimax to find the best move. Results are shown in Tab. 3 for 500 games with half as first player and half as second player. Each player has 1 sec to generate a new move. The corresponding number of draw games are shown in Fig. 4 for MCTS with group-nodes and in Fig 5 for MCTS with chance-nodes. The RND policy is now abbreviate with R, the CAP RND policy is abbreviate CR and the CAP AVD RND) policy is abbreviate CAR. C1 stands for group-nodes and C2 stands for chance-nodes. h mentions evaluation function usage and no h means that only true victories are considered inside playouts.

Results shows that chance-nodes are less effective with evaluation function where group-nodes are more effective with evaluation function. It further shows that chance-nodes are more dependant on playout size than group-nodes. Best group-nodes players achieved 182 and 175 victories when chance-nodes achieved 244 and 245 victories.

For each policy, Fig 4 shows that evaluation function reduces the number of draw games with group-nodes. Nonetheless the number of draw games is equal or more important with chance-nodes (see Fig 5). -Between all players, the best is chance-nodes with Capture, without evaluation function and with playout size of 640.

It shows that sophisticated policies are better with group-nodes where the basic Capture policy is the best with chance-nodes. Extending playout size over the real draw condition is beneficial to group-nodes and to chance-nodes.

Conclusion

We have presented different Monte-Carlo tree search that deal with the stochastic game Chinese Dark Chess. We have shown relations with playout size, basic or advanced policies and evaluation function usage. While extending the playout size is useful to create more inform playouts, an evaluation function usage can increase or decrease player's effectiveness through modifying the number of draw possibilities.

Fig. 3 :

 3 Fig. 3: Endgame.

Fig. 4 : 3 Fig. 5 :

 435 Fig. 4: Group-node draw of Tab 3 Fig. 5: Chance-node draw of Tab 3

Table 1 :

 1 Playing 2000 playouts at beginning, middle game and endgame.

	Policy	Time Rem. pieces	Playout size	Without eval. fun. With eval. fun. Best W L D Best W L D
	At beginning
	Random	0.660 12.16 (2.31) 106.37 (9.25)	d7	-	-100	b7 69 30 01
	Capture	0.375 5.67 (2.20) 100.01 (17.69)	c2 25 22 53	b3 52 48	-
	Avoid	5.973 16.78 (2.88) 207.41 (74.49)	b2	-	-100	c8 57 43	-
	Capture and avoid	0.598 7.24 (2.25) 107.27 (18.05)	b1 34 13 53	c8 55 45	-
	Avoid and capture	1.049 7.69 (2.20) 123.02 (20.15)	c4 18 06 76	c6 38 60 02
	Trap	140.457 8.95 (2.15) 579.69 (115.79)	d7	-	-100	d6 86 14	-
	Capture and trap	99.753 15.07 (3.07) 610.96 (111.26)	c3 02	-98	c5 52 48	-
	Capture avoid and trap 39.799 7.12 (2.52) 435.53 (177.59)	d3 31 25 44	d1 64 36	-
	At midlle game
	Random	0.606 12.18 (2.24) 91.89 (9.20)	d8	-	-100 c6-c7 43 57	-
	Capture	0.348 6.91 (2.17) 75.60 (19.26) c6-c7 48 02 50 c6-c7 90 10	-
	Avoid	5.072 16.60 (2.72) 194.68 (87.18)	d4	-	-100	d4 55 44 01
	Capture and avoid	0.585 7.53 (1.96) 89.06 (17.93) c6-c7 34 02 64 c6-c7 84 16	-
	Avoid and capture	0.885 7.55 (2.02) 103.68 (15.79) c6-c7 04 14 82 c6-c7 30 69 01
	Trap	157.911 9.68 (1.86) 704.73 (62.78)	d7	--100	d8 97 03	-
	Capture and trap	123.055 14.49 (2.89) 711.58 (45.01)	b8 01 -99	d4 76 24	-
	Capture avoid and trap 34.201 9.92 (1.59) 370.29 (177.85) c6-c7 54 00 46 c6-c7 100 --
	At endgame
	Random	0.504 8.23 (1.14) 42.72 (1.46) a8-a7	-	-100 a8-a7 -100 -
	Capture	0.469 6.26 (0.94)	41.93 (6.02) a8-a7 00 22 78 a8-a7 -100 -
	Avoid	0.781 10.12 (0.54)	40.66 (1.55) d2-c2	-02 98 d2-c2 -100 -
	Capture and avoid	0.733 8.00 (0.00)	43.00 (0.00) a8-a7	-	-100 a8-a7 -100 -
	Avoid and capture	0.817 9.80 (0.53)	40.34 (4.36) d2-c2	-04 96 d2-c2 -100 -
	Trap	11.138 7.00 (0.00)	44.00 (0.00) d2-c2	-	-100 d2-c2 -100 -
	Capture and trap	7.389 11.00 (0.00)	40.00 (0.00) d2-c2	-	-100 d2-c2 -100 -
	Capture avoid and trap	6.030	8.0 (0.00)

Table 2 :

 2 Applying 2000 playouts from beginning board.

	Policy	time[sec] draw Rem. pieces Playout size Draw condition
	RND	0.630 1.00	12.62	106.07	40
		1.067 0.99	6.03	232.11	160
		1.801 0.67	3.24	622.37	640
	CAP RND	0.376 0.70	5.66	103.71	40
		0.522 0.46	4.59	171.77	160
		0.802 0.31	4.29	335.92	640
	CAP AVD RND	0.598 0.73	7.15	110.45	40
		0.953 0.53	6.07	185.41	160
		2.139 0.43	5.87	403.44	640
	AVD CAP RND	1.012 0.87	7.77	124.29	40
		1.707 0.69	6.19	223.51	160
		4.353 0.59	5.85	550.41	640

Table 3 :

 3 Playing 500 games against reference player.

	playout size	40	160	640	2560
		win lost win lost win lost win lost
	chance-nodes C2-R	0 255	4 298 213 109 164 72
	C2-R-h	9 137 104 64 116 43 135 42
	C2-CR	244 16 242 21 245 15 149 21
	C2-CR-h	131 15 143 14 138 23 129 23
	C2-CAR	199 33 245 27 239 46 159 47
	C2-CAR-h 129 16 125 25 122	9 104 30
	playout size	40	160	640	2560
		win lost win lost win lost win lost
	group-nodes C1-R	10 249 51 185 78 187 64 233
	C1-R-h	60 269 103 231 80 219 85 263
	C1-CR	35 46 101 52 146 61 137 66
	C1-CR-h	120 87 167 98 182 88 147 127
	C1-CAR	41 35 103 52 128 93 72 170
	C1-CAR-h 109 100 167 86 175 97 130 143

Table 4 :

 4 Tournament between UCT players.

		C1-CAR-h-640 C2-CR-40 C2-CR-640 C2-CAR-160
	C1-CR-h-640	268 / 169 282 / 97 176 / 252	287 / 131
	C1-CAR-h-640	228 / 137 156 / 285	236 / 175
	C2-CR-40	149 / 220


Nicolas Jouandeau

Tristan Cazenave
email: cazenave@lamsade.dauphine.fr

Monte-Carlo Tree Reductions for Stochastic Games

Monte-Carlo Tree Search (MCTS) is a powerful paradigm for perfect information games. When considering stochastic games, the tree model that represents the game has to take chance and a huge branching factor into account. As effectiveness of MCTS may decrease in such a setting, tree reductions may be useful. Chance-nodes are a way to deal with random events. Move-groups are another way to deal efficiently with a large branching factor by regrouping nodes. Groupnodes are regrouping only reveal moves and enable a choice between reveal moves and classical moves. We present various policies to use such reductions for the stochastic game Chinese Dark Chess. Move-groups, chance-nodes and group-nodes are compared.

Introduction

Chinese Dark Chess (CDC) is a popular stochastic two player game in Asia that is most commonly played on a 4x8 rectangular board where players do not know payoff of reveal moves. The 2 players (called black and red) start with the same set of pieces. Before the first move, players do not know their colors. The first player move defines the first player color. Then pieces can capture other pieces according to their values and their positions. Even if reveal moves imply a huge number of possible boards, classical moves can lead to similar positions during the game and capturing rules are different for each piece [START_REF] Chen | Chinese Dark Chess[END_REF]. As Monte Carlo Tree Search (MCTS) techniques deal with nodes statistics, blindness goes along with branching factor. MCTS programs seem to be promising in CDC.

In TCGA 2012, one participant was a MCTS program. In TCGA 2013, five participants, including the winner called DarkKnight, were MCTS programs. In TCGA 2014, the alpha-beta program Yahari won the competition ahead of DarkKnight. As CDC has a huge branching due to the revealing moves, we try to reduce the revealing moves dependency by applying different ways of regrouping nodes. In the context of stochastic games, we believe that a better understanding of MCTS behavior is needed. We show in this paper 3 different MCTS implementations, called move-groups, chance-nodes and group-nodes, that are using longer playouts, the same playout policy and no heuristic playouts. Section 2 describes related works. Section 3 presents move-groups, chancenodes and group-nodes principles applied to MCTS algorithms and different regrouping policies. Section 4 shows experimental results. At the end, section 5 concludes.

Related works

In this section we expose related works on creating nodes and regrouping them in CDC and in stochastic games.

Most previous works related to CDC consider openings building [START_REF] Chen | Automatic Generation of Chinese Dark Chess Opening Books, 8th Int. Conf. on Computers and Games (CG[END_REF], endgames building [START_REF] Jr | Design and Implementation of Computer Chinese Dark Chess Endgame Database[END_REF][START_REF] Saffidine | Material Symmetry to Partition Endgame Tables, 8th Int. Conf. on Computers and Games (CG[END_REF][START_REF] Jr | Equivalence Classes in Chinese Dark Chess Endgames[END_REF], sub-problems resolution [START_REF] Chang | A Quantitative Study of 24 Chinese Dark Chess, 8th Int. Conf. on Computers and Games (CG[END_REF]. Due to a long expertise in alpha-beta, most programs use the minimax extension to games of chance called expectimax [START_REF] Chen | Chinese Dark Chess[END_REF] with its common pruning extensions Star1 and Star2 [START_REF] Ballard | The *-minimax search procedure for trees containing chance nodes[END_REF]. It remains that MCTS programs are highly sensitive to their parameters [START_REF] Yen | The Art of the Chinese Dark Chess Program DIABLE[END_REF].

Move-groups have been proposed in [START_REF] Childs | Transpositions and move groups in Monte Carlo tree search[END_REF] to address the problem of MCTS in games with a high branching factor. When there are too many moves, it can be a good heuristic to regroup the statistics of moves that share some properties. For example in the game of Amazons where the branching factor can be of the order of a thousand of moves, a natural way to reduce the branching factor is to separate the queen move from the stone placement. In the imperfect information game Dou Di Zhu, Information Set [START_REF] Cowling | Information Set Monte Carlo Tree Search[END_REF] has been combined with move-groups: the player first chooses the base move and then the kicker, as two separate consecutive decision nodes in the tree. Move-groups have also been analyzed on an abstract game [START_REF] Van Eyck | Revisiting move groups in monte-carlo tree search[END_REF].

Chen et al. [START_REF] Chen | Chinese Dark Chess[END_REF] used alpha-beta algorithm with different revealing policies combined with the initial-depth flipping method to reduce the branching factor.

Yen et al. [START_REF] Yen | The Art of the Chinese Dark Chess Program DIABLE[END_REF] presented a non-deterministic MCTS with chance-nodes [START_REF] Lanctot | Monte Carlo *-Minimax Search, 23rd Int. Joint Conf. on Artificial Intelligence (IJCAI-2013)[END_REF]. They create shorter simulation by moderating the three policies named Capture First, Capture Stronger Piece First and Capture and Escape Stronger Piece First.

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 size, of basic or advanced policies and with heuristic playouts. They studied group constitution related to position's pieces. They showed that relevant playout sizes, policies and heuristic playouts are not equivalent for chance-nodes and group-nodes.

More generally, MCTS has been successfully applied in the past to other multi-player perfect information stochastic games with different regrouping optimizations.

In Backgammon, Monte Carlo playouts have been parallelized to evaluate a position. As playing a position depends on dices, random dices sequences have been also evaluate in parallel. As the number of possible moves increases when dices are doubles, states evaluation can be divided in 2 sub-problems [START_REF] Van Lishout | Monte-Carlo Tree Search in Backgammon[END_REF] : the first without double dices and the second with double dices. In other words, they distinguished states in 2 groups : light states that have small branching factor and heavy states that have huge branching factor.

In Scrabble, simulations are restricted inside a directed acyclic graph to produce existing words [START_REF] Sheppard | World-championship-caliber Scrabble[END_REF].

In Poker, betting strategies depends on the gamestate [START_REF] Billings | The Challenge of Poker[END_REF] (that can be Pre-Flop, Flop, River). During these gamestates, players' hands are consistent with their actions. Thus simulations are limited to special tracks that are defined by players' hands.

These contributions in other stochastic games show that biased sampling according to particular things of gamestates and regrouping possibilities has been used to settle efficient MCTS playouts.

Regrouping nodes

In this section, we present the use of chance-nodes, move-groups and group-nodes principles applied to MCTS. Figure 1 show the differences between representations of a common tree, a tree with chance-nodes and a tree with move-groups. With chance-nodes and move-groups, branching factor reductions can arise. With chance-nodes (related to a game where possible moves are partly defined by rolling a dice), events e1 and e2 are selecting possible next nodes. With move-groups, children are divided between categories (here 3 categories A, B and C ) to perform a smart descent towards the best leaf. When these categories are defined by the moves coordinates in the board, move-groups are called group-nodes.

The main loop of MCTS applied to perfect information games is presented in Alg. 1. It is a statistical search based on 3 steps called selection, expansion and backpropagation, also guided by random games (i.e. playouts). The tree expansion is performed to evaluate the current most promising node. The main loop presented is limited to nbPlayouts iterations but it can be an anytime process. It can start from an empty tree with its root node only or from a tree filled by previous MCTS loops. The use of such procedure is consistent if and only if the root node is not a endgame position (i.e. root is not a solved problem). This process can lead to the insertion of 1 to nbP layouts nodes. The select function takes the current tree T as input and performs descent toward the best node q and returns the move m to produce a new node. Then the expand function applies m to q and produces q new . Starting from this new node q new , a playout helps to collect statistical information of q new . Then backpropagation function insert q new in the tree T as statistically informed node and backpropagates q new results of its parents. If during the descent, this q new node is a winning leaf, this leaf is updated and future tree expansions are expected to perform different descents and select different nodes. According to this exclusion of endgames inside T , the select function detailed in Alg. 2 always selects node q with at most 1 move. It selects the best node q best from all possible moves m from q or it breaks at the first node (q + m) not in T .

input : T the current tree output: T expanded with 1 to nbP layouts nodes

for nbP layouts do ( q , m ) ← select ( T ) ; qnew ← expand ( q , m ) ; res ← playout ( qnew ) ; backpropagate ( qnew , res ) ;
Algorithm 1: Classical MCTS applied to perfect information games.

input : T the current tree output: ( q, m ) where q ∈ T and q to expand by applying a move m q ← root; while true do q best ← {∅} ; foreach move m from q do if (q + m) / ∈ T then return ( q, m ) ; q best ← best ( q best , (q + m) ) ; q ← q best ; Algorithm 2: Select function of classical MCTS.

Considering stochastic games and modifications of tree's representation that are arising with chance-nodes and move-groups usage :

the select function may distinguish types of nodes.

the endgame shortcut assertion is no more true. Thus endgames can be selected inside select function. It implies modifications in main loop and in select function.

input : T the current tree output: T expanded with nbP layouts iterations for nbP layouts do ( q , m ) ← select ( T ) ; if m = {∅} then qnew ← expand ( q , m ) ; res ← playout ( qnew ) ; backpropagate ( qnew , res ) ; else res ← result ( q ) ; backpropagate ( q , res ) ;

Algorithm 3: MCTS applied to stochastic games.

The modified main loop is presented in Alg. 3. Even if a descent can lead to an endgame, stochastic games can lead to different events during the descent, that should lead to unevaluated parts of T . The selection process is guided by nodes scores and by stochastic events. Thus the statistical scoring process can be applied systematically during nbP layouts iterations, to insert 0 to nbP layouts nodes in T . In such games, expansion, playout and backpropagation are applied only if the selected move m differs from {∅}.

The modified select function with chance-nodes is presented in Alg. 4. At each iteration, the state of the node is checked : if it is a chance-node, then the dice function adds an external event to q. If no move is available from q, then {∅} is returned as move m to apply. If q is not in T , then q is inserted and the move returned to apply to q is its first move. Thus each time this node is selected, it will try to add another move from q before looking for the best children of q to descend one more time in T .

The modified select function with move-groups is presented in Alg. 5. The process is divided between 3 cases :

there is no move from q, that is equivalent to no group available. The process breaks and the tuple ( q , {∅} ) is returned. -1 move-group g exists from q, which means that this group contains at least 1 move. In this case, the process tries to evaluate all possible moves of the move-group g. if 2 or more move-groups exists from q, then the process tries to select the first group without a move. If all groups have 1 or more moves, then the best group M best is selected and 1 move from this group is considered. If this move is not in T , then it returns the tuple ( q , m ). This process implies to input : T the current tree output: ( q, m ) where q ∈ T and q to expand by applying a move m q ← root; while true do if no move from q then break ; q best ← {∅} ; foreach possible move m from q do if m is a classical move then if (q + m) / ∈ T then return ( q, m ) ; q best ← best ( q best , (q + m) ) ; else if m is a reveal move then qnew ← revealRandomlyAt ( q, m ); if qnew / ∈ T then return ( q, m ) ; q best ← best ( q best , qnew ) ; q ← q best ; return ( q , {∅} ) ; Algorithm 6: Select function with group-nodes check the intersection between a move-group and T . The one-move function defines the policy to generate and add new moves in T .

The modified select function with group-nodes is presented in Alg. 6. Revealing moves are regrouped by position. Each position to reveal leads to different boards. Thus a board with 3 known pieces with 4 possible moves each and with 10 unrevealed pieces will have 12 children for its known pieces and 10 children for its unrevealed pieces. As revealing positions can leads to different boards, possible moves are always recomputed with group-nodes. The select function returns the first unevaluated classical move or the first unevaluated reveal move from the current best node in the tree. The function revealRandomlyAt applies a random reveal at the position m. As revealed pieces will be different, subgroups will be also different. Thus the group-nodes regrouping policy produced an approximate evaluation of groups.

In this paper, we investigate the way that groups constitution influence MCTS performances in CDC stochastic game. To achieve this, we consider different regrouping policies and different generating policies inside groups:

revealed group or unrevealed group : these 2 groups are simply defined on the board by revealed and unrevealed pieces. Using these 2 groups, we tried to generate randomly new moves (abrev. move-group-random) and to cycle over the considered move-group's elements (abrev. move-group-cycle). revealed pieces or unrevealed group : this is equivalent to group-nodes. Unrevealed pieces are considered randomly inside the unrevealed group and revealed pieces are considered individually (abrev. group-nodes).

Experiments

In the first experiment, we compare the 5 regrouping policies move-groupsrandom, move-groups-cycle-R, move-groups-cycle-M, group-nodes and chancenodes to a random player and to a reference player rand-mm. The policies move-groups-cycle-R and move-groups-cycle-M are respectively starting by reveal moves and by real moves. Thus move-groups-cycle-R is more dependant on the number of revealing possibilities than move-groups-cycle-M. The reference player rand-mm simply plays randomly when pieces are unrevealed and otherwise applies minimax to find the best move. In our experiments, UCT (abrev. Upper Confidence bounds applied to Trees) values are computed with

(v/(v + d)) + K * log(n)/(v + d)
with n simulations, v wins, d losses and K equals to 0.3. As capture has been proven to contribute in better MCTS evaluations [START_REF] Yen | The Art of the Chinese Dark Chess Program DIABLE[END_REF][START_REF] Jouandeau | Small and large MCTS playouts applied to Chinese Dark Chess stochastic game[END_REF], captures are preferred to random moves inside playouts.

As playouts can finish with a draw endgame and are evaluated without heuristic function, we extended the draw rule inside playouts to 640 turns to produce more informed playouts. Results presented in all tables involve 500 games in which half are achieved with one player as first and half are achieved with the other player as first. Games are played with 0.01[sec] per move and with 1[sec] per move. Table 1: Games against random-player and random-minimax player.

Results of table 1 confirm that the move-groups-cycle-R policy of cycling on moves and starting by reveal moves is not a good policy. As similar results are obtained with move-groups-random and move-groups-cycle-M, the knowledge introduced with cycling and starting by known pieces is inefficient to do better than a random selection. Results show that chance-nodes are more effective than others with simple playouts (i.e. no heuristic evaluation function inside playouts). Table 2: Using minimax at the end.

In the second experiment, we enhanced these 5 policies by using minimax as the reference player rand-mm do. When all pieces are revealed, enhanced players apply minimax to find the best move. Policies are used when pieces are unrevealed and otherwise a minimax search is done. These modified players move-groups-random-mm, move-groups-cycle-R-mm, move-groups-cycle-M-mm, group-nodes-mm and chance-nodes-mm are compared to rand-mm player. 2 show that adding minimax search in the perfect information part of games improves all the players. This enhancement makes chance-nodesmm the best player with 0.01[sec] and 1[sec] per move. In case of 1[sec] per move, move-groups-cycle-R-mm and move-groups-cycle-M-mm are closed to chancenodes-mm. In all these experiments, rand-mm obtains quasi null scores.

Results of table

In the third experiment, we evaluate the contribution of chance-nodes by gradually introducing random moves. The figure 2 shows the performance of chance-nodes-mm against himself. The second player is weakened with a random move during X first turns. Players are evaluated in 500 games, with 1[sec] per move, from 0 to 35 random moves. It shows that performances are equal when chance-nodes-mm plays randomly during its 10 first moves. After 10 first random moves, losts increase and draws decrease. It shows chance-nodes contribution while some unrevealed pieces remain. After 20 turns, the game has more chance to be fully revealed. It shows that similar gain is achieved in the perfect information part of the game. As there are 32 unrevealed positions at the beginning of the game, chance-nodes contributes effectively at least in managing 12 unrevealed pieces. Fig. 2: chance-nodes-mm with X random plies against chance-nodes-mm.

Conclusion

Monte-Carlo Tree Search (MCTS) is a powerful paradigm for perfect information games. When considering stochastic games, the tree model that represents the game has to take chance and a huge branching factor into account. We have presented 3 ways to regroup nodes and their consequences to MCTS algorithm and the descent function. We have compared different regrouping policies and different generating policies in Chinese Dark Chess games. Experiments show that without heuristic function evaluation, chance-nodes regrouping policy is the best for the stochastic part of the game and that adding minimax search in the perfect information part of the game improves all players.

Fig. 1 :

 1 Fig. 1: Common, chance-nodes and move-groups representations.

input : T the current tree output: ( q, m ) where q ∈ T and q to expand by applying a move m q ← root; while true do if q is a chance-node then q ← q + dice ( ) ; else if no move from q then break ; if q / ∈ T then insert q in T ; return ( q , first move from q ) ; else q best ← {∅} ; foreach move m from q do if (q + m) / ∈ T then return ( q, m ) ; q best ← best ( q best , (q + m) ) ; q ← q best ; return ( q , {∅} ) ; Algorithm 4: Select function with chance-nodes.

input : T the current tree output: ( q, m ) where q ∈ T and q to expand by applying a move m q ← root; while true do if no move from q then break ; if only 1 move-group g exists from q then q best ← {∅} ; foreach move m of g from q do if (q + m) / ∈ T then return ( q, m ) ; q best ← best ( q best , (q + m) ) ; q ← q best ; else M best ← {∅} ; foreach move-group M from q do if M ∩ T = ∅ then add one-move of M in T ; return ( q , m ) ;

∈ T then return ( q, m ) ; q ← q + m ; return ( q , {∅} ) ; Algorithm 5: Select function with move-groups