# Mining Experiential Patterns from Game-Logs of Board Game

Authors: Liang Wang; Yu Wang; Yan Li
Journal: International Journal of Computer Games Technology
 (2015)

---

## Abstract

In board games, game-logs record past game processes, which can be regarded as an accumulation of experience. Similar to a real person, a computer player can gradually increase its skill by learning from game-logs. Therefore, the game becomes more interesting. This paper proposes an extensible approach to mine experiential patterns from increasing game-logs. The computer player improves its strategies by utilizing these growing patterns, just as it acquires experience. To evaluate the effect and performance of the approach, we designed a sample board game as a test platform and elaborated an experiment consisting of a series of tests. Experimental results show that our approach is effective and efficient.


---

## Body

## 1. Introduction

Gaming is one of the main intellections in our daily life. To some extent, gaming shows the wisdom of humankind more directly. Artificial intelligence for games (Game AI) is an important subfield of AI research. The current generations of computer games offer an interesting testbed for Game AI [1]. Meanwhile, applying AI techniques to game design will make the games more interesting. The research of Game AI plays an important role in promoting the development of the computer game industry.Board game is one of the earliest objects that AI focused on [2, 3]. By contrast with other types of games, board games reflect human’s intelligence more purely and thus attract the interest of AI researchers [4, 5]. At first, researchers concentrated on the algorithm design about the chess road searching and the chess manual matching and made some important progresses. John von Neumann presented the Minimax algorithm in 1920s [6]. Shannon [2] proposed the game tree searching algorithm with his chess program in 1950. Knuth and Moore deeply analyzed the alpha-beta pruning algorithm in 1958 [7]. Then, studies on AI in board games were widely launched [8–13]. Many contests of board games between machines and real persons showed the advances in AI research [14–16]. Recently, researchers find that game-logs (game records) cover a lot of important and interesting knowledge. Chen et al. [17] proposed an approach to abstract expert knowledge from annotated Chinese chess game records. GO game records are used for the life and death predicting, the pattern acquisition, and the pattern matching [18–20]. Esaki and Hashiyama [21] carried out some experiments to extract human players’ strategies from the game records of Shogi. Weber and Mateas [22] used a data mining approach to process game-logs for the strategy prediction. Takeuchi et al. [23] presented a way of evaluating game tree search methods by game records. Moreover, Wender [24] expounded how to use data mining and machine learning techniques to analyze the game-logs in his project.The common design of board games is to factitiously set the difficulty level on an invincible computer player, but this way is just a simulation. However, human players often expect a computer player to act and think as a real person rather than a superman. Game-logs in a board game are considered as cumulative experience, which will become richer and more effective with the increase of game times. With the accumulation of the experience, computer players can gradually enhance their intelligence level, just like human beings. Data mining techniques can be used to extract experience from game-logs. Nevertheless, there are few works on this topic.In this paper, an approach is presented to mine experiential patterns from the growing game-logs of a sample board game. The computer player can learn from these patterns to improve its intelligence naturally. Firstly, a Chinese checkers game was designed as a test platform for collecting game-logs and launching empirical studies. Then, series of algorithms based on a sequence-tree were proposed to mine experiential patterns from game-logs. These patterns included Experience Rules, Key States, and Checker Usage. Finally, the mined patterns were applied back to the test platform, and then a series of experimental tests was elaborated to verify the effectiveness and performance of our approach.Experimental results demonstrate that our approach is effective and efficient and easy to be transplanted to fit for other types of games.


## 2. Methods

The application of the experiential pattern mining requires two basic conditions listed below.(i)
The computer players of a game have the minimum ability to play the game correctly without any experiential pattern.
Doing so ensures that the game can run properly in the initial stage.
(ii)
There are sufficient and valid game-logs to make the pattern mining task runnable.
Only when the number of game-logs reaches a certain size can the regularity hidden in them appear. In addition, our purpose is to make computer players learn from human players’ strategies. So, these game-logs should be from human players’ games.To satisfy the above conditions, we designed a simplified Chinese checkers game as a test platform to provide the basic move algorithms and collect the game-logs. Subsequent sections cover the following topics in detail:(a)
the concepts concerned with the game and the mining algorithms;
(b)
the algorithms for mining experiential patterns;
(c)
the methods for applying experiential patterns to the game.


### 2.1. Key Concepts

The traditional Chinese checkers game has flexible gameplay (see [25] for more details). In this work, the game was simplified to be more convenient for experimenting (the design details are provided in Appendix). The key concepts used in the following sections are briefly explained below.(i) Checker. The checker means the position used to put pieces on the chessboard. Each checker has its own coordinate.(ii) Checkers-State. The checkers-state describes all the checkers on the chessboard and can be traversed to get or update the information of every checker.(iii) Piece. Each player holds ten pieces. The coordinate of a piece is dependent on the current position of the piece.(iv) Pieces-State. Pieces-states are used to store the coordinates of pieces. A pieces-state is a set that consists of several subsets. The number of the subsets depends on how many players are there in the game. Each subset contains ten elements, which correspond to the ten pieces of a player. For 2-player mode, there are two subsets, called the active side (SAS) and the passive side (SPS), respectively.(v) Game-Log. During gaming, once a piece moves a step, the test platform will save the corresponding pieces-state to a game-log. The pieces-states in a game-log are sorted by their creation time. Hence, a game-log is a sequence of pieces-states. Separate XML files are used to store the game-logs.(vi) Experiential Pattern. Experiential patterns are mined from game-logs and easily used by computer players. In this work, we considered three kinds of experiential patterns, including Experience Rule, Key State, and Checker Usage.An Experience Rule is similar to an if-then rule. If pieces-stateP
S
a appears, then the player should achieve the pieces-state P
S
b by moving a piece. The rule can be represented as P
S
a
→
P
S
b, where P
S
a is called last state and P
S
b next state.Key States are a group of particular pieces-states. They appear in victor games frequently and thus indicate some good game situation. By algorithm designing, one can help the computer player in approaching these Key States. Furthermore, approaching the Key States may also promote the applying of some Experience Rules, because some Key States may just be the last states or the next states.Checker Usage describes the usage of a checker and is denoted byC
U. The C
U of a checker can be calculated by
(1)
C
U
C
=
F
C
_
C
o
u
n
t
C
N
,
N
>
0
1
,
N
=
0
,
where C
U
C represents the C
U of checker C,  F
C
_
C
o
u
n
t
C holds the times that C has been used as the falling checker, and N stores the number of game-logs in database.


### 2.2. Mining Experiential Patterns

By using some traditional move algorithms, the computer player may figure out the best move within several rounds. However, being subject to the computing capability of the computer and the requirement of game runtime, the computer player is hard to make more skillful moves or longer layouts. Humans improve their chess skill by accumulating the playing experience. A computer player can simulate this process to study experience from humans’ excellent games and thus make the moves more strategic. The three experiential patterns introduced in Section2.1 are mined from the game-logs generated in the games of human-human mode. The data mining process is run in server-side, and its workflow is shown in Figure 1.Figure 1
Workflow of the data mining process.As shown in Figure1, the data mining process consists of three phases, including data extraction, data mining, and data representation.


#### 2.2.1. Data Extraction

Each game makes a single game-log file, and this will generate lots of XML files stored in server-side. These XML files are not suitable to be the direct data source of data mining. Therefore, the sequential data with consistent format needs to be extracted from game-logs and stored in database first.Three data entities,PiecesState,PiecesStateSequence, andCheckerUsage, are used to format the game-logs. Their attributes are, respectively, shown in Tables 1, 2, and 3. The pieces-states inPiecesState are distinct, and each of them has a unique ID. The sequences inPiecesStateSequence are repeatable, and each of them corresponds to a game-log. The tuples inCheckerUsage have the same number as the checkers on the chessboard.Table 1
Attributes of thePiecesState.
Attribute name
Description
Data type
Restrictions
ID
The ID of pieces-state.
Big integer
Unique, nonnull
SAS_0
The coordinate of the first piece in active side.
Coordinate
Nonnull
SAS_1
The coordinate of the second piece in active side.
Coordinate
Nonnull
⋮
⋮
⋮
⋮
SAS_9
The coordinate of the tenth piece in active side.
Coordinate
Nonnull
SPS_0
The coordinate of the first piece in passive side.
Coordinate
Nonnull
SPS_1
The coordinate of the second piece in passive side.
Coordinate
Nonnull
⋮
⋮
⋮
⋮
SPS_9
The coordinate of the tenth piece in passive side.
Coordinate
Nonnull
Count
The times this pieces-state appeared in victor games.
Big integer
NonnullTable 2
Attributes of thePiecesStateSequence.
Attribute name
Description
Data type
Restrictions
ID
The ID of the sequence.
Big integer
Unique, nonnull
SequenceStr
Sequential string.
Long text
NonnullTable 3
Attributes of theCheckerUsage.
Attribute name
Description
Data type
Restrictions
ID
Serialized ID
Big integer
Unique, nonnull
c
The coordinate of the falling checker
Coordinate
Nonnull
Times
The usage of the falling checker
Big integer
NonnullAlgorithm1 describes the process of data extraction.Algorithm 1:
DataExtraction.
Procedure  DataExtraction
Input:
statesD, the data table of PiecesState in database.
files: the XML files of game-logs.
Output: Non.
Method:
(01)let  stateIdsbe the set of PiecesState ids;
(02)let  file be a file of game-log;
(03)let  statesF be the set of the pieces-states extracted from game-logs;
(04)let  newStateId be the new PiecesState id;
(05)while  files.empty == false  do
(06)file = files.getOne(); //Read a game-log.
(07) Extract the pieces-states fromfile, and save them to statesF;
(08) Extract the game result fromfile, and save it to result;
(09)for  i = 0 to  statesF.length − 1 do
(10)  //Get the sequence of ids of PiecesState.
(11)ifFound = false;
(12)  Update thetimes field of CheckerUsage with statesF[i].
(13)for  j = 0 to  statesD.length − 1 do
(14)ifequal(statesF[i], statesD[j].state) then
(15)stateIds.add(statesD[j].id);
(16)isFound = true;
(17)count += result;
(18)
break;
(19)endif
(20)endfor
(21)if  isFound == false  then
(22)   InsertstatesF[i] into PiecesState;
(23)   count = result;
(24)   Save the new id tonewStateId.
(25)stateIds.add(newStateId);
(26)statesD.add(newStateId, statesF[i]);
(27)endif
(28)endfor
(29)if  result != 0 then
(30)k = 1;
(31)if  result == -
1  then
(32)k = 0;
(33)endif
(34)for  n = 0 to  stateIds.length − 1 do
(35)stateIds[n] *= (−1) ∧ ((i
-
k) % 2);
(36)endfor
(37)endif
(38)sequenceString = stateIds[0];
(39)for  p = 0 to  stateIds.length − 1 do
(40)sequenceString += (“:” + stateIds[p]);
(41)endfor
(42) InsertsequenceString into PiecesStateSequence;
(43)delete(file); //Delete the current game-log.
(44)endwhileIn Algorithm1, lines (29)–(37) add a win/loss mark to the nondraw game and use minus to mark the pieces-states created by the loss player. Lines (38)–(41) combine all the PiecesState IDs from the same game into a single sequential string.


#### 2.2.2. Data Mining

Experiential pattern mining means finding useful patterns from a large number of sequences composed of pieces-states. The types of these patterns include but are not limited to those mentioned in Section2.1. Mining the Experience Rules, which are the most important experiential patterns in this work, is an objective of sequential pattern mining. Sequential pattern mining is a topic of data mining concerned with finding statistically relevant patterns between data examples where the values are delivered in a sequence [26]. In this field, many efforts of mining sequential patterns have been devoted to developing efficient algorithms, such asGSP [27],SPADE [28],CloSpan [29],PrefixSpan [30], andMEMISP [31]. In recent years, researchers have paid more attention to the applied research of sequential pattern mining as discussed elsewhere [32–36].In this section, we describe the methods for mining the three kinds of experiential patterns explained in Section2.1.Experience Rule. Experience Rules describe the experience of the human players most directly. The problem of mining Experience Rules can be described as follows. Let S be a set of items, where each item is a sequence of pieces-states. Given a minimum support thresholdminSupport, the aim is to find out all the consecutive binary subsequences (CBSSs) whose frequency is not less thanminSupport. Each CBSS consists of two pieces-states that are consecutive in the original sequence, and this can be regarded as a constraint in data mining. In this paper, an algorithm based on pattern-growth is proposed for mining CBSSs. This algorithm uses a sequence-tree (see Figure 2) as the data structure to load all the sequences in database. The sequence-tree is different from the FP-tree [37] of frequent pattern mining, and we do not have to scan database previously to obtain the supports of every pieces-state. Algorithm 2 describes the procedure of creating a sequence-tree.Algorithm 2:
SequenceTreeCreation.
Procedure
SequenceTreeCreation
Input: sequencesD, the data table of PiecesStateSequence in database.
Output: root, the root node of the sequence-tree.
Method:
(01) let  stateIds save the ids of PiecesState;
(02) root = new
Node(value = 0, branches = null);
(03) for  i = 0 to
sequencesD.length − 1 do
(04) stateIds = sequencesD[i].sequenceStr.split(“:”);
(05) //Eliminate redundant pieces-state of stateIds.
(06) for
j = stateIds.length − 1 to 2 do
(07)  for
k = j − 2 to 0 by 2 do
(08)   if
stateIds[j] ==stateIds[k]then
(09)    stateIds.delete(k + 1, j);
(1
0)    j = k;
(1
1)   endif
(1
2)  endfor
(1
3) endfor
(1
4) node = root;
(1
5) for  m = 1 to
stateIds.length − 1 do
(1
6)  if
node.value == 0 then
(1
7)   node.value = s
t
a
t
e
I
d
s
[
0
];
(1
8)  endif
(1
9)  isFound = false;
(20)  if
node.branches != null
then
(21)   for
n = 0 to
node.branches.length − 1 do
(22)    if
node.branches[n].next.value == s
t
a
t
e
I
d
s
[
m
]
then
(23)     node.branches[n].weight += (stateIds[m]/s
t
a
t
e
I
d
s
[
m
]);
(24)     node = node.branches[n].next;
(25)     isFound = true;
(26)     break;
(27)    endif
(28)   endfor
(29)  endif
(30)  if
isFound == false
then
(31)   branch = new
Branch(
(32)    weight = stateIds[m]/s
t
a
t
e
I
d
s
[
m
],
(33)    next = new
Node(value = s
t
a
t
e
I
d
s
[
m
], branches = null)
(34)   );
(35)   node.branches.add(branch);
(36)   node = node.branches[node.branches.length − 1].next;
(37)  endif
(38)  //Merge the nodes of same values.
(39)  BranchShifting(root, node);
(40) endfor
(41) endfor
(42) return
root;Figure 2
Data structure of a node on the sequence-tree.In Figure2,value stores the ID of the pieces-state,weight represents the support of the related CBSS, andnext stores the linkage pointing to the next node.On a certain player’s perspective, if two same pieces-states appear, the moves between the two pieces-states will become noneffective interference data. Eliminating these data will reduce the unnecessary data analyses and improve the reliability of mining results (see lines (05)–(13) in Algorithm2).Not all the frequent CBSSs are good, since some of them may be from losing games. The support count of a CBSS denoted bysuppCount can be calculated by
(2)
s
u
p
p
C
o
u
n
t
=
p
o
s
S
u
p
p
C
o
u
n
t
-
n
e
g
S
u
p
p
C
o
u
n
t
,
whereposSuppCount is the support count of the CBSS generated in winning games andnegSuppCount in losing games.By means of the win/loss mark, thesuppCount of each CBSS has been calculated during the process of creating the sequence-tree. Hence, the weight of each branch is equal to thesuppCount of the relevant CBSS. Moreover, the same pairs of nodes are not allowed to appear on the same sequence-tree; otherwise thesuppCountvalues will be incomputable (as illustrated in Figure 3). To solve this problem, the algorithm for shifting branches is designed (see Algorithm 3).Algorithm 3:
BranchShifting.
Procedure  BranchShifting
Input:
root, the root node of the sequence-tree.
node, the pointer that points to the current node.
Output:
Updatednode.
isShifted, the result of shifting.
Method:
(01)if  node.value == root.value then
(02)node = root;
(03)return
true;
(04)else
(05)if  root.branches == null
then
(06)return false;
(07)else
(08)for  i
=
0  to  root.branches.length − 1  do
(09)if
BranchShifting(root.branches[i].next, node) == true
then
(10)return true;
(11)endif
(12)endfor
(13)return false;
(14)endif
(15)endifFigure 3
Branch shifting. The two pairs of nodes B-C marked with dotted circles on the left tree should be merged together, and their branch weights should be added up too. The right tree is the result of this branch shifting.To obtain the frequent CBSSs, the following formula is given:(3)
s
u
p
p
=
s
u
p
p
C
o
u
n
t
t
o
t
a
l
S
e
q
s
×
100
%
,
wheresupp denotes the support of a CBSS andtotalSeqs denotes the total number of the sequences in database. Given aminSupport, the frequent CBSSs are those whose supports are not less thanminSupport. All the frequent CBSSs can be found out by traversing the sequence-tree only once, and the script to do so is shown in Algorithm 4.Algorithm 4:
CBSSFinding.
Procedure
CBSSFinding
Input:
minSupport, the minimum support threshold.
root, the root node of the sequence-tree.
total: the total number of sequences.
sps, the set of the found CBSSs.
Output:
Updatedsps.
Method:
(01)let
supp be the support of a CBSS;
(02)let
sp be the instance of SequentialPattern;
(03)if
root.branches == null
then
(04)return;
(05)endif
(06)for
i
=
0
to
root.branches.length − 1do
(07)supp = root.branches[i].weight/total;
(08)if
supp≥minSupport
then
(09)sp = new
SequentialPattern();
(10)sp.premise = root.value;
(11)sp.result = root.branches[i].next.value;
(12)sp.support = supp;
(13)sps.add(sp);
(14)endif
(15)CBSSFinding(minSupport, root.branches[i].next, total, sps);
(16)endforIn Algorithm4, the structure of the object SequentialPattern is shown in Figure 4. The found CBSSs will serve as the data source for selecting Experience Rules.Figure 4
The structure of SequentialPattern.Key State. Given a threshold percentageminFreq, Key States are those pieces-states of the frequencies not less thanminFreq. The frequency (denoted byfreq) of a pieces-state can be calculated by
(4)
f
r
e
q
=
c
o
u
n
t
N
×
100
%
,
where N stores the total number of sequences in database andcount denotes the occurrence number of the pieces-state in the net winning games. The value ofcount is figured out during the process of data extraction (see lines (17) and (23) in Algorithm 1).In respect of threshold selection, adjustingminFreqdynamically in accordance with the number of Experience Rules can make the Key States more efficient.Checker Usage. This pattern can be calculated by formula (1), in which the F
C
_
C
o
u
n
t
C is figured out during the process of data extraction (see line (12) in Algorithm 1).


#### 2.2.3. Data Representation

In this phase, the main task is to make the mined experiential patterns recognizable to the computer player. The experiential pattern here mainly refers to Experience Rule. The following format is used to represent an Experience Rule:(5)
p
r
e
m
i
s
e
⟶
r
e
s
u
l
t
:
s
u
p
p
o
r
t
.According to the data structure of the Experience Rule, the process of data representation can be described as follows. Replace the IDs, which denote the last states or next states of Experience Rules, with the corresponding pieces-states, and then write these pieces-states to an XML file in server-side.However, the mined patterns may not be all reliable. For example, given aminSupport, the obtained Experience Rules are as follows:
(6)
P
S
a
⟶
P
S
b
:
15
%
P
S
a
⟶
P
S
c
:
13
%
P
S
a
⟶
P
S
d
:
17
%
.
That is, one last state has multiple next states. When pieces-state P
S
a appears, it is clearly reliable to select the pieces-state P
S
d, which is of the highestsupport. Hence, the reliability selection should be done before data presentation. Algorithm 5 shows this process.Algorithm 5:
ReliabilitySelection.
Procedure ReliabilitySelection
Input:
minSupport, the minimum support threshold.
total: the total number of sequences.
sequencesD, the data table of PiecesStateSequence in database.
Output:
sps, the set of reliable Experience Rules.
Method:
(01)root = CreatSequenceTree(sequencesD);
(02)CBSSFinding(minSupport, root, total, sps);
(03)for
i
=
0
to
sps.length – 2 do
(04)for
j
=
i
+
1
to
sps.length − 1 do
(05)if
sps[i].premise == sps[j].premisethen
(06)if
sps[i].support < sps[j].supportthen
(07)sps.delete(i);
(08)i−−;
(09)break;
(10)else
(11)sps.delete(j);
(12)j−−;
(13)endif
(14)endif
(15)endfor
(16)endfor


### 2.3. Applying Experiential Patterns

The way of applying experiential patterns depends on the specific gameplay. In this section, we give a computer player’s strategy as shown in Figure5 and then explain how to apply the mined experiential patterns to the actual game.Figure 5
Strategy of the computer player.In the course of the game, the computer player uses Experience Rules first. Algorithm6 demonstrates the procedure of matching Experience Rules.Algorithm 6:
ExperienceRuleMatching.
Procedure
ExperienceRuleMatching
Input:
PS, the current pieces-state.
ERs: the set of Experience Rules.
Output:
nextPS, the next pieces-state.
Method:
(01)for each
er
in
ERs
do
(02)if
PS == er.lastthen
(03)nextPS = er.next;
(04)break;
(05)else
(06)nextPS = null;
(07)endif
(08)endforWhen there are no available Experience Rules, the computer player will automatically approximate a certain Key State. Doing so can promote the formation of some good game situation and may activate some Experience Rules. Obviously, the approached Key State is the nearest pieces-state after the current one. So, all of the Key States are sorted by their occurrence time. LetP
S
a and P
S
b be two different pieces-states. Their order is defined below.Definition 1.
Assume thatP
S
a
≠
P
S
b. If P
S
a
·
SAS
≥
P
S
b
·
SAS and P
S
a
·
SPS
≥
P
S
b
·
SPS, then P
S
a is behind P
S
b, which can be expressed as P
S
a
≥
P
S
b.The concept of dissimilarity (denoted byDiss) is used to represent the closeness between two pieces-states. TheDiss between P
S
a and P
S
b is equal to the least moves from P
S
a to P
S
b. The less the value ofDiss, the closer the two pieces-states. For calculatingDiss, the following definitions are given.Definition 2.
LetP be a piece and let P
S be a set of pieces-states. If the coordinate of P is included in P
S, then P belongs to P
S, which can be expressed as P
∈
P
S.Definition 3.
LetC
a and C
b be two checkers, (
x
a
,
y
a
) and (
x
b
,
y
b
) their coordinates, respectively, and x
a
+
y
a
≥
x
b
+
y
b. Then, the minimal number of steps for a move from C
a to C
b is called move distance from C
a to C
b and denoted by M
D
a
b, which can be calculated by
(7)
M
D
a
b
=
φ
x
a
-
x
b
+
φ
y
a
-
y
b
,
where the function φ is defined as
(8)
φ
x
=
x
,
x
≥
0
0
,
x
<
0
.Definition 4.
LetP
a and P
b be two pieces, C
a and C
b their checkers, respectively, P
S
a and P
S
b two pieces-states, P
a
∈
P
S
a
·
SIS, and P
b
∈
P
S
b
·
SIS. Then, the minimal number of steps for a move from C
a to C
b is called the Distance in Active Side between P
a and P
b, which is denoted by DAS
a
b. Similarly, one can define the Distance in Passive Side between P
a and P
b, which is denoted by DP
S
a
b.Algorithm7 demonstrates the calculation of the distance between two pieces.Algorithm 7:
PiecesDistanceCalculation.
Procedure
PiecesDistanceCalculation
Input:
PS, the current pieces-state.
P
a, piece P
a.
P
b, piece P
b.
Output:
Dab, the distance between P
a and P
b.
Method:
(01)let
CS be the checkers-state;
(02) let
vAllFC be a vector to store the falling checkers of every layer.
(03) //The maximum distance between P
a and P
b.
(04) Calculate the move distance MDab;
(05) if
MDab == 0 or
MDab == 1 or
MDab == 2 then
(06) //If MDab is less than 3, there is no less distance.
(07)  return
MDab;
(08) endif
(09) for
i = 0 to 9 do
(10) CS[PS⋅SAS[i]⋅x][PS⋅SAS[i]⋅y] = 1;
(11) CS[PS⋅SPS[i]⋅x][PS⋅SPS[i]⋅y] = −1;
(12) endfor
(13) FindVirtualFallingCheckers(0, CS, P
a
⋅
x, P
a
⋅
y, true, vAllFC, 0);
(14) isBreak = false; //Denotes the end of searching.
(15) Dab = MDab; //The distance in the worst case.
(16) for
each
allFC
in
vAllFC
do
(17) for
each
c
in
allFC
do
(18)  if
allFC.index == (MDab−1) then
(19)   isBreak = true; break;
(20)  endif
(21)  if
c
⋅
x == P
b
⋅
x
and
c
⋅
y == P
b
⋅
y
then
(22)   Dab = allFC.index + 1; isBreak = true;
(23)   break;
(24)  endif
(25)  if
allFC.index == (MDab−2) then break; endif
(26)
FindVirtualFallingCheckers(0, CS, c
⋅
x, c
⋅
y, true, vAllFC, allFC.index + 1);
(27) endfor
(28) if
isBreak == true
then break; endif
(29) endfor
(30) return
Dab;
(31) //Search the virtual falling checkers of specified checkers.
(32) Function
FindVirtualFallingCheckers(d, CS, x, y, isFirstStep, vAllFC, index)
(33) begin
(34) for
i = 3to−3 do
(35)  if
i == −d  then continue; endif
(36)  if
i == 0 then continue; endif
(37)  Search the next jumping falling checker (x
′, y
′) in direction i of checker (x, y).
(38)  if (x
′, y
′) exists then
(39)   vAllFC[index].add(new
Coordinate(x
′, y
′));
(40)   FindVirtualFallingCheckers(3, CS, x
′, y
′, false, vAllFC, index);
(41)  else if the piece on (x
′, y
′) is of own side then
(42)   FindVirtualFallingCheckers(3, CS, x
′, y
′, true, vAllFC, index + 1);
(43)  else
(44)   if
isFirstStep == true
then
(45)     vAllFC[index].add(new
Coordinate(x
′, y
′));
(46)   endif
(47)  endif
(48) endfor
(49)endLetP
S
a and P
S
b be two pieces-states. According to Definitions 2–4, the dissimilarity matrices between P
S
a and P
S
b are defined as follows:
(9)
D
i
s
s
M
a
t
r
i
x
A
S
=
DAS
00
⋯
DAS
09
⋮
⋱
⋮
DAS
90
⋯
DAS
99
D
i
s
s
M
a
t
r
i
x
P
S
=
DPS
00
⋯
DPS
09
⋮
⋱
⋮
DPS
90
⋯
DPS
99
,
whereDissMatrixAS is defined on the active side andDissMatrixPS on the passive side. Then, theDiss between two pieces can be calculated by
(10)
D
i
s
s
=
min
⁡
⁡
∑
a
=
0
9
∑
b
=
0
9
DAS
a
b
X
a
b
+
∑
a
=
0
9
∑
b
=
0
9
DPS
a
b
Y
a
b
,
where X
a
b and Y
a
b satisfy the following conditions, respectively:
(11)
∑
a
=
0
9
X
a
b
=
1
∑
b
=
0
9
X
a
b
=
1
a
,
b
=
0,1
,
2
,
…
,
9
X
a
b
=
0,1
,
∑
a
=
0
9
Y
a
b
=
1
∑
b
=
0
9
Y
a
b
=
1
a
,
b
=
0,1
,
2
,
…
,
9
Y
a
b
=
0,1
.It follows that the calculation of theDiss between pieces is a typical assignment problem in linear programming. This problem can be solved byHungarian algorithm as discussed by Edmonds [38].When there are no Key States behind the current pieces-state or theDiss between the nearest Key State and the current pieces-state is more than a given threshold, the computer player will execute a tentative move algorithm namedTentativeMove, which was designed based on the traditional alpha-beta pruning algorithm [7] (see Appendix for more details). Moreover, the pattern Checker Usage is one of the parameters ofTentativeMove.


## 2.1. Key Concepts

The traditional Chinese checkers game has flexible gameplay (see [25] for more details). In this work, the game was simplified to be more convenient for experimenting (the design details are provided in Appendix). The key concepts used in the following sections are briefly explained below.(i) Checker. The checker means the position used to put pieces on the chessboard. Each checker has its own coordinate.(ii) Checkers-State. The checkers-state describes all the checkers on the chessboard and can be traversed to get or update the information of every checker.(iii) Piece. Each player holds ten pieces. The coordinate of a piece is dependent on the current position of the piece.(iv) Pieces-State. Pieces-states are used to store the coordinates of pieces. A pieces-state is a set that consists of several subsets. The number of the subsets depends on how many players are there in the game. Each subset contains ten elements, which correspond to the ten pieces of a player. For 2-player mode, there are two subsets, called the active side (SAS) and the passive side (SPS), respectively.(v) Game-Log. During gaming, once a piece moves a step, the test platform will save the corresponding pieces-state to a game-log. The pieces-states in a game-log are sorted by their creation time. Hence, a game-log is a sequence of pieces-states. Separate XML files are used to store the game-logs.(vi) Experiential Pattern. Experiential patterns are mined from game-logs and easily used by computer players. In this work, we considered three kinds of experiential patterns, including Experience Rule, Key State, and Checker Usage.An Experience Rule is similar to an if-then rule. If pieces-stateP
S
a appears, then the player should achieve the pieces-state P
S
b by moving a piece. The rule can be represented as P
S
a
→
P
S
b, where P
S
a is called last state and P
S
b next state.Key States are a group of particular pieces-states. They appear in victor games frequently and thus indicate some good game situation. By algorithm designing, one can help the computer player in approaching these Key States. Furthermore, approaching the Key States may also promote the applying of some Experience Rules, because some Key States may just be the last states or the next states.Checker Usage describes the usage of a checker and is denoted byC
U. The C
U of a checker can be calculated by
(1)
C
U
C
=
F
C
_
C
o
u
n
t
C
N
,
N
>
0
1
,
N
=
0
,
where C
U
C represents the C
U of checker C,  F
C
_
C
o
u
n
t
C holds the times that C has been used as the falling checker, and N stores the number of game-logs in database.


## 2.2. Mining Experiential Patterns

By using some traditional move algorithms, the computer player may figure out the best move within several rounds. However, being subject to the computing capability of the computer and the requirement of game runtime, the computer player is hard to make more skillful moves or longer layouts. Humans improve their chess skill by accumulating the playing experience. A computer player can simulate this process to study experience from humans’ excellent games and thus make the moves more strategic. The three experiential patterns introduced in Section2.1 are mined from the game-logs generated in the games of human-human mode. The data mining process is run in server-side, and its workflow is shown in Figure 1.Figure 1
Workflow of the data mining process.As shown in Figure1, the data mining process consists of three phases, including data extraction, data mining, and data representation.


### 2.2.1. Data Extraction

Each game makes a single game-log file, and this will generate lots of XML files stored in server-side. These XML files are not suitable to be the direct data source of data mining. Therefore, the sequential data with consistent format needs to be extracted from game-logs and stored in database first.Three data entities,PiecesState,PiecesStateSequence, andCheckerUsage, are used to format the game-logs. Their attributes are, respectively, shown in Tables 1, 2, and 3. The pieces-states inPiecesState are distinct, and each of them has a unique ID. The sequences inPiecesStateSequence are repeatable, and each of them corresponds to a game-log. The tuples inCheckerUsage have the same number as the checkers on the chessboard.Table 1
Attributes of thePiecesState.
Attribute name
Description
Data type
Restrictions
ID
The ID of pieces-state.
Big integer
Unique, nonnull
SAS_0
The coordinate of the first piece in active side.
Coordinate
Nonnull
SAS_1
The coordinate of the second piece in active side.
Coordinate
Nonnull
⋮
⋮
⋮
⋮
SAS_9
The coordinate of the tenth piece in active side.
Coordinate
Nonnull
SPS_0
The coordinate of the first piece in passive side.
Coordinate
Nonnull
SPS_1
The coordinate of the second piece in passive side.
Coordinate
Nonnull
⋮
⋮
⋮
⋮
SPS_9
The coordinate of the tenth piece in passive side.
Coordinate
Nonnull
Count
The times this pieces-state appeared in victor games.
Big integer
NonnullTable 2
Attributes of thePiecesStateSequence.
Attribute name
Description
Data type
Restrictions
ID
The ID of the sequence.
Big integer
Unique, nonnull
SequenceStr
Sequential string.
Long text
NonnullTable 3
Attributes of theCheckerUsage.
Attribute name
Description
Data type
Restrictions
ID
Serialized ID
Big integer
Unique, nonnull
c
The coordinate of the falling checker
Coordinate
Nonnull
Times
The usage of the falling checker
Big integer
NonnullAlgorithm1 describes the process of data extraction.Algorithm 1:
DataExtraction.
Procedure  DataExtraction
Input:
statesD, the data table of PiecesState in database.
files: the XML files of game-logs.
Output: Non.
Method:
(01)let  stateIdsbe the set of PiecesState ids;
(02)let  file be a file of game-log;
(03)let  statesF be the set of the pieces-states extracted from game-logs;
(04)let  newStateId be the new PiecesState id;
(05)while  files.empty == false  do
(06)file = files.getOne(); //Read a game-log.
(07) Extract the pieces-states fromfile, and save them to statesF;
(08) Extract the game result fromfile, and save it to result;
(09)for  i = 0 to  statesF.length − 1 do
(10)  //Get the sequence of ids of PiecesState.
(11)ifFound = false;
(12)  Update thetimes field of CheckerUsage with statesF[i].
(13)for  j = 0 to  statesD.length − 1 do
(14)ifequal(statesF[i], statesD[j].state) then
(15)stateIds.add(statesD[j].id);
(16)isFound = true;
(17)count += result;
(18)
break;
(19)endif
(20)endfor
(21)if  isFound == false  then
(22)   InsertstatesF[i] into PiecesState;
(23)   count = result;
(24)   Save the new id tonewStateId.
(25)stateIds.add(newStateId);
(26)statesD.add(newStateId, statesF[i]);
(27)endif
(28)endfor
(29)if  result != 0 then
(30)k = 1;
(31)if  result == -
1  then
(32)k = 0;
(33)endif
(34)for  n = 0 to  stateIds.length − 1 do
(35)stateIds[n] *= (−1) ∧ ((i
-
k) % 2);
(36)endfor
(37)endif
(38)sequenceString = stateIds[0];
(39)for  p = 0 to  stateIds.length − 1 do
(40)sequenceString += (“:” + stateIds[p]);
(41)endfor
(42) InsertsequenceString into PiecesStateSequence;
(43)delete(file); //Delete the current game-log.
(44)endwhileIn Algorithm1, lines (29)–(37) add a win/loss mark to the nondraw game and use minus to mark the pieces-states created by the loss player. Lines (38)–(41) combine all the PiecesState IDs from the same game into a single sequential string.


### 2.2.2. Data Mining

Experiential pattern mining means finding useful patterns from a large number of sequences composed of pieces-states. The types of these patterns include but are not limited to those mentioned in Section2.1. Mining the Experience Rules, which are the most important experiential patterns in this work, is an objective of sequential pattern mining. Sequential pattern mining is a topic of data mining concerned with finding statistically relevant patterns between data examples where the values are delivered in a sequence [26]. In this field, many efforts of mining sequential patterns have been devoted to developing efficient algorithms, such asGSP [27],SPADE [28],CloSpan [29],PrefixSpan [30], andMEMISP [31]. In recent years, researchers have paid more attention to the applied research of sequential pattern mining as discussed elsewhere [32–36].In this section, we describe the methods for mining the three kinds of experiential patterns explained in Section2.1.Experience Rule. Experience Rules describe the experience of the human players most directly. The problem of mining Experience Rules can be described as follows. Let S be a set of items, where each item is a sequence of pieces-states. Given a minimum support thresholdminSupport, the aim is to find out all the consecutive binary subsequences (CBSSs) whose frequency is not less thanminSupport. Each CBSS consists of two pieces-states that are consecutive in the original sequence, and this can be regarded as a constraint in data mining. In this paper, an algorithm based on pattern-growth is proposed for mining CBSSs. This algorithm uses a sequence-tree (see Figure 2) as the data structure to load all the sequences in database. The sequence-tree is different from the FP-tree [37] of frequent pattern mining, and we do not have to scan database previously to obtain the supports of every pieces-state. Algorithm 2 describes the procedure of creating a sequence-tree.Algorithm 2:
SequenceTreeCreation.
Procedure
SequenceTreeCreation
Input: sequencesD, the data table of PiecesStateSequence in database.
Output: root, the root node of the sequence-tree.
Method:
(01) let  stateIds save the ids of PiecesState;
(02) root = new
Node(value = 0, branches = null);
(03) for  i = 0 to
sequencesD.length − 1 do
(04) stateIds = sequencesD[i].sequenceStr.split(“:”);
(05) //Eliminate redundant pieces-state of stateIds.
(06) for
j = stateIds.length − 1 to 2 do
(07)  for
k = j − 2 to 0 by 2 do
(08)   if
stateIds[j] ==stateIds[k]then
(09)    stateIds.delete(k + 1, j);
(1
0)    j = k;
(1
1)   endif
(1
2)  endfor
(1
3) endfor
(1
4) node = root;
(1
5) for  m = 1 to
stateIds.length − 1 do
(1
6)  if
node.value == 0 then
(1
7)   node.value = s
t
a
t
e
I
d
s
[
0
];
(1
8)  endif
(1
9)  isFound = false;
(20)  if
node.branches != null
then
(21)   for
n = 0 to
node.branches.length − 1 do
(22)    if
node.branches[n].next.value == s
t
a
t
e
I
d
s
[
m
]
then
(23)     node.branches[n].weight += (stateIds[m]/s
t
a
t
e
I
d
s
[
m
]);
(24)     node = node.branches[n].next;
(25)     isFound = true;
(26)     break;
(27)    endif
(28)   endfor
(29)  endif
(30)  if
isFound == false
then
(31)   branch = new
Branch(
(32)    weight = stateIds[m]/s
t
a
t
e
I
d
s
[
m
],
(33)    next = new
Node(value = s
t
a
t
e
I
d
s
[
m
], branches = null)
(34)   );
(35)   node.branches.add(branch);
(36)   node = node.branches[node.branches.length − 1].next;
(37)  endif
(38)  //Merge the nodes of same values.
(39)  BranchShifting(root, node);
(40) endfor
(41) endfor
(42) return
root;Figure 2
Data structure of a node on the sequence-tree.In Figure2,value stores the ID of the pieces-state,weight represents the support of the related CBSS, andnext stores the linkage pointing to the next node.On a certain player’s perspective, if two same pieces-states appear, the moves between the two pieces-states will become noneffective interference data. Eliminating these data will reduce the unnecessary data analyses and improve the reliability of mining results (see lines (05)–(13) in Algorithm2).Not all the frequent CBSSs are good, since some of them may be from losing games. The support count of a CBSS denoted bysuppCount can be calculated by
(2)
s
u
p
p
C
o
u
n
t
=
p
o
s
S
u
p
p
C
o
u
n
t
-
n
e
g
S
u
p
p
C
o
u
n
t
,
whereposSuppCount is the support count of the CBSS generated in winning games andnegSuppCount in losing games.By means of the win/loss mark, thesuppCount of each CBSS has been calculated during the process of creating the sequence-tree. Hence, the weight of each branch is equal to thesuppCount of the relevant CBSS. Moreover, the same pairs of nodes are not allowed to appear on the same sequence-tree; otherwise thesuppCountvalues will be incomputable (as illustrated in Figure 3). To solve this problem, the algorithm for shifting branches is designed (see Algorithm 3).Algorithm 3:
BranchShifting.
Procedure  BranchShifting
Input:
root, the root node of the sequence-tree.
node, the pointer that points to the current node.
Output:
Updatednode.
isShifted, the result of shifting.
Method:
(01)if  node.value == root.value then
(02)node = root;
(03)return
true;
(04)else
(05)if  root.branches == null
then
(06)return false;
(07)else
(08)for  i
=
0  to  root.branches.length − 1  do
(09)if
BranchShifting(root.branches[i].next, node) == true
then
(10)return true;
(11)endif
(12)endfor
(13)return false;
(14)endif
(15)endifFigure 3
Branch shifting. The two pairs of nodes B-C marked with dotted circles on the left tree should be merged together, and their branch weights should be added up too. The right tree is the result of this branch shifting.To obtain the frequent CBSSs, the following formula is given:(3)
s
u
p
p
=
s
u
p
p
C
o
u
n
t
t
o
t
a
l
S
e
q
s
×
100
%
,
wheresupp denotes the support of a CBSS andtotalSeqs denotes the total number of the sequences in database. Given aminSupport, the frequent CBSSs are those whose supports are not less thanminSupport. All the frequent CBSSs can be found out by traversing the sequence-tree only once, and the script to do so is shown in Algorithm 4.Algorithm 4:
CBSSFinding.
Procedure
CBSSFinding
Input:
minSupport, the minimum support threshold.
root, the root node of the sequence-tree.
total: the total number of sequences.
sps, the set of the found CBSSs.
Output:
Updatedsps.
Method:
(01)let
supp be the support of a CBSS;
(02)let
sp be the instance of SequentialPattern;
(03)if
root.branches == null
then
(04)return;
(05)endif
(06)for
i
=
0
to
root.branches.length − 1do
(07)supp = root.branches[i].weight/total;
(08)if
supp≥minSupport
then
(09)sp = new
SequentialPattern();
(10)sp.premise = root.value;
(11)sp.result = root.branches[i].next.value;
(12)sp.support = supp;
(13)sps.add(sp);
(14)endif
(15)CBSSFinding(minSupport, root.branches[i].next, total, sps);
(16)endforIn Algorithm4, the structure of the object SequentialPattern is shown in Figure 4. The found CBSSs will serve as the data source for selecting Experience Rules.Figure 4
The structure of SequentialPattern.Key State. Given a threshold percentageminFreq, Key States are those pieces-states of the frequencies not less thanminFreq. The frequency (denoted byfreq) of a pieces-state can be calculated by
(4)
f
r
e
q
=
c
o
u
n
t
N
×
100
%
,
where N stores the total number of sequences in database andcount denotes the occurrence number of the pieces-state in the net winning games. The value ofcount is figured out during the process of data extraction (see lines (17) and (23) in Algorithm 1).In respect of threshold selection, adjustingminFreqdynamically in accordance with the number of Experience Rules can make the Key States more efficient.Checker Usage. This pattern can be calculated by formula (1), in which the F
C
_
C
o
u
n
t
C is figured out during the process of data extraction (see line (12) in Algorithm 1).


### 2.2.3. Data Representation

In this phase, the main task is to make the mined experiential patterns recognizable to the computer player. The experiential pattern here mainly refers to Experience Rule. The following format is used to represent an Experience Rule:(5)
p
r
e
m
i
s
e
⟶
r
e
s
u
l
t
:
s
u
p
p
o
r
t
.According to the data structure of the Experience Rule, the process of data representation can be described as follows. Replace the IDs, which denote the last states or next states of Experience Rules, with the corresponding pieces-states, and then write these pieces-states to an XML file in server-side.However, the mined patterns may not be all reliable. For example, given aminSupport, the obtained Experience Rules are as follows:
(6)
P
S
a
⟶
P
S
b
:
15
%
P
S
a
⟶
P
S
c
:
13
%
P
S
a
⟶
P
S
d
:
17
%
.
That is, one last state has multiple next states. When pieces-state P
S
a appears, it is clearly reliable to select the pieces-state P
S
d, which is of the highestsupport. Hence, the reliability selection should be done before data presentation. Algorithm 5 shows this process.Algorithm 5:
ReliabilitySelection.
Procedure ReliabilitySelection
Input:
minSupport, the minimum support threshold.
total: the total number of sequences.
sequencesD, the data table of PiecesStateSequence in database.
Output:
sps, the set of reliable Experience Rules.
Method:
(01)root = CreatSequenceTree(sequencesD);
(02)CBSSFinding(minSupport, root, total, sps);
(03)for
i
=
0
to
sps.length – 2 do
(04)for
j
=
i
+
1
to
sps.length − 1 do
(05)if
sps[i].premise == sps[j].premisethen
(06)if
sps[i].support < sps[j].supportthen
(07)sps.delete(i);
(08)i−−;
(09)break;
(10)else
(11)sps.delete(j);
(12)j−−;
(13)endif
(14)endif
(15)endfor
(16)endfor


## 2.2.1. Data Extraction

Each game makes a single game-log file, and this will generate lots of XML files stored in server-side. These XML files are not suitable to be the direct data source of data mining. Therefore, the sequential data with consistent format needs to be extracted from game-logs and stored in database first.Three data entities,PiecesState,PiecesStateSequence, andCheckerUsage, are used to format the game-logs. Their attributes are, respectively, shown in Tables 1, 2, and 3. The pieces-states inPiecesState are distinct, and each of them has a unique ID. The sequences inPiecesStateSequence are repeatable, and each of them corresponds to a game-log. The tuples inCheckerUsage have the same number as the checkers on the chessboard.Table 1
Attributes of thePiecesState.
Attribute name
Description
Data type
Restrictions
ID
The ID of pieces-state.
Big integer
Unique, nonnull
SAS_0
The coordinate of the first piece in active side.
Coordinate
Nonnull
SAS_1
The coordinate of the second piece in active side.
Coordinate
Nonnull
⋮
⋮
⋮
⋮
SAS_9
The coordinate of the tenth piece in active side.
Coordinate
Nonnull
SPS_0
The coordinate of the first piece in passive side.
Coordinate
Nonnull
SPS_1
The coordinate of the second piece in passive side.
Coordinate
Nonnull
⋮
⋮
⋮
⋮
SPS_9
The coordinate of the tenth piece in passive side.
Coordinate
Nonnull
Count
The times this pieces-state appeared in victor games.
Big integer
NonnullTable 2
Attributes of thePiecesStateSequence.
Attribute name
Description
Data type
Restrictions
ID
The ID of the sequence.
Big integer
Unique, nonnull
SequenceStr
Sequential string.
Long text
NonnullTable 3
Attributes of theCheckerUsage.
Attribute name
Description
Data type
Restrictions
ID
Serialized ID
Big integer
Unique, nonnull
c
The coordinate of the falling checker
Coordinate
Nonnull
Times
The usage of the falling checker
Big integer
NonnullAlgorithm1 describes the process of data extraction.Algorithm 1:
DataExtraction.
Procedure  DataExtraction
Input:
statesD, the data table of PiecesState in database.
files: the XML files of game-logs.
Output: Non.
Method:
(01)let  stateIdsbe the set of PiecesState ids;
(02)let  file be a file of game-log;
(03)let  statesF be the set of the pieces-states extracted from game-logs;
(04)let  newStateId be the new PiecesState id;
(05)while  files.empty == false  do
(06)file = files.getOne(); //Read a game-log.
(07) Extract the pieces-states fromfile, and save them to statesF;
(08) Extract the game result fromfile, and save it to result;
(09)for  i = 0 to  statesF.length − 1 do
(10)  //Get the sequence of ids of PiecesState.
(11)ifFound = false;
(12)  Update thetimes field of CheckerUsage with statesF[i].
(13)for  j = 0 to  statesD.length − 1 do
(14)ifequal(statesF[i], statesD[j].state) then
(15)stateIds.add(statesD[j].id);
(16)isFound = true;
(17)count += result;
(18)
break;
(19)endif
(20)endfor
(21)if  isFound == false  then
(22)   InsertstatesF[i] into PiecesState;
(23)   count = result;
(24)   Save the new id tonewStateId.
(25)stateIds.add(newStateId);
(26)statesD.add(newStateId, statesF[i]);
(27)endif
(28)endfor
(29)if  result != 0 then
(30)k = 1;
(31)if  result == -
1  then
(32)k = 0;
(33)endif
(34)for  n = 0 to  stateIds.length − 1 do
(35)stateIds[n] *= (−1) ∧ ((i
-
k) % 2);
(36)endfor
(37)endif
(38)sequenceString = stateIds[0];
(39)for  p = 0 to  stateIds.length − 1 do
(40)sequenceString += (“:” + stateIds[p]);
(41)endfor
(42) InsertsequenceString into PiecesStateSequence;
(43)delete(file); //Delete the current game-log.
(44)endwhileIn Algorithm1, lines (29)–(37) add a win/loss mark to the nondraw game and use minus to mark the pieces-states created by the loss player. Lines (38)–(41) combine all the PiecesState IDs from the same game into a single sequential string.


## 2.2.2. Data Mining

Experiential pattern mining means finding useful patterns from a large number of sequences composed of pieces-states. The types of these patterns include but are not limited to those mentioned in Section2.1. Mining the Experience Rules, which are the most important experiential patterns in this work, is an objective of sequential pattern mining. Sequential pattern mining is a topic of data mining concerned with finding statistically relevant patterns between data examples where the values are delivered in a sequence [26]. In this field, many efforts of mining sequential patterns have been devoted to developing efficient algorithms, such asGSP [27],SPADE [28],CloSpan [29],PrefixSpan [30], andMEMISP [31]. In recent years, researchers have paid more attention to the applied research of sequential pattern mining as discussed elsewhere [32–36].In this section, we describe the methods for mining the three kinds of experiential patterns explained in Section2.1.Experience Rule. Experience Rules describe the experience of the human players most directly. The problem of mining Experience Rules can be described as follows. Let S be a set of items, where each item is a sequence of pieces-states. Given a minimum support thresholdminSupport, the aim is to find out all the consecutive binary subsequences (CBSSs) whose frequency is not less thanminSupport. Each CBSS consists of two pieces-states that are consecutive in the original sequence, and this can be regarded as a constraint in data mining. In this paper, an algorithm based on pattern-growth is proposed for mining CBSSs. This algorithm uses a sequence-tree (see Figure 2) as the data structure to load all the sequences in database. The sequence-tree is different from the FP-tree [37] of frequent pattern mining, and we do not have to scan database previously to obtain the supports of every pieces-state. Algorithm 2 describes the procedure of creating a sequence-tree.Algorithm 2:
SequenceTreeCreation.
Procedure
SequenceTreeCreation
Input: sequencesD, the data table of PiecesStateSequence in database.
Output: root, the root node of the sequence-tree.
Method:
(01) let  stateIds save the ids of PiecesState;
(02) root = new
Node(value = 0, branches = null);
(03) for  i = 0 to
sequencesD.length − 1 do
(04) stateIds = sequencesD[i].sequenceStr.split(“:”);
(05) //Eliminate redundant pieces-state of stateIds.
(06) for
j = stateIds.length − 1 to 2 do
(07)  for
k = j − 2 to 0 by 2 do
(08)   if
stateIds[j] ==stateIds[k]then
(09)    stateIds.delete(k + 1, j);
(1
0)    j = k;
(1
1)   endif
(1
2)  endfor
(1
3) endfor
(1
4) node = root;
(1
5) for  m = 1 to
stateIds.length − 1 do
(1
6)  if
node.value == 0 then
(1
7)   node.value = s
t
a
t
e
I
d
s
[
0
];
(1
8)  endif
(1
9)  isFound = false;
(20)  if
node.branches != null
then
(21)   for
n = 0 to
node.branches.length − 1 do
(22)    if
node.branches[n].next.value == s
t
a
t
e
I
d
s
[
m
]
then
(23)     node.branches[n].weight += (stateIds[m]/s
t
a
t
e
I
d
s
[
m
]);
(24)     node = node.branches[n].next;
(25)     isFound = true;
(26)     break;
(27)    endif
(28)   endfor
(29)  endif
(30)  if
isFound == false
then
(31)   branch = new
Branch(
(32)    weight = stateIds[m]/s
t
a
t
e
I
d
s
[
m
],
(33)    next = new
Node(value = s
t
a
t
e
I
d
s
[
m
], branches = null)
(34)   );
(35)   node.branches.add(branch);
(36)   node = node.branches[node.branches.length − 1].next;
(37)  endif
(38)  //Merge the nodes of same values.
(39)  BranchShifting(root, node);
(40) endfor
(41) endfor
(42) return
root;Figure 2
Data structure of a node on the sequence-tree.In Figure2,value stores the ID of the pieces-state,weight represents the support of the related CBSS, andnext stores the linkage pointing to the next node.On a certain player’s perspective, if two same pieces-states appear, the moves between the two pieces-states will become noneffective interference data. Eliminating these data will reduce the unnecessary data analyses and improve the reliability of mining results (see lines (05)–(13) in Algorithm2).Not all the frequent CBSSs are good, since some of them may be from losing games. The support count of a CBSS denoted bysuppCount can be calculated by
(2)
s
u
p
p
C
o
u
n
t
=
p
o
s
S
u
p
p
C
o
u
n
t
-
n
e
g
S
u
p
p
C
o
u
n
t
,
whereposSuppCount is the support count of the CBSS generated in winning games andnegSuppCount in losing games.By means of the win/loss mark, thesuppCount of each CBSS has been calculated during the process of creating the sequence-tree. Hence, the weight of each branch is equal to thesuppCount of the relevant CBSS. Moreover, the same pairs of nodes are not allowed to appear on the same sequence-tree; otherwise thesuppCountvalues will be incomputable (as illustrated in Figure 3). To solve this problem, the algorithm for shifting branches is designed (see Algorithm 3).Algorithm 3:
BranchShifting.
Procedure  BranchShifting
Input:
root, the root node of the sequence-tree.
node, the pointer that points to the current node.
Output:
Updatednode.
isShifted, the result of shifting.
Method:
(01)if  node.value == root.value then
(02)node = root;
(03)return
true;
(04)else
(05)if  root.branches == null
then
(06)return false;
(07)else
(08)for  i
=
0  to  root.branches.length − 1  do
(09)if
BranchShifting(root.branches[i].next, node) == true
then
(10)return true;
(11)endif
(12)endfor
(13)return false;
(14)endif
(15)endifFigure 3
Branch shifting. The two pairs of nodes B-C marked with dotted circles on the left tree should be merged together, and their branch weights should be added up too. The right tree is the result of this branch shifting.To obtain the frequent CBSSs, the following formula is given:(3)
s
u
p
p
=
s
u
p
p
C
o
u
n
t
t
o
t
a
l
S
e
q
s
×
100
%
,
wheresupp denotes the support of a CBSS andtotalSeqs denotes the total number of the sequences in database. Given aminSupport, the frequent CBSSs are those whose supports are not less thanminSupport. All the frequent CBSSs can be found out by traversing the sequence-tree only once, and the script to do so is shown in Algorithm 4.Algorithm 4:
CBSSFinding.
Procedure
CBSSFinding
Input:
minSupport, the minimum support threshold.
root, the root node of the sequence-tree.
total: the total number of sequences.
sps, the set of the found CBSSs.
Output:
Updatedsps.
Method:
(01)let
supp be the support of a CBSS;
(02)let
sp be the instance of SequentialPattern;
(03)if
root.branches == null
then
(04)return;
(05)endif
(06)for
i
=
0
to
root.branches.length − 1do
(07)supp = root.branches[i].weight/total;
(08)if
supp≥minSupport
then
(09)sp = new
SequentialPattern();
(10)sp.premise = root.value;
(11)sp.result = root.branches[i].next.value;
(12)sp.support = supp;
(13)sps.add(sp);
(14)endif
(15)CBSSFinding(minSupport, root.branches[i].next, total, sps);
(16)endforIn Algorithm4, the structure of the object SequentialPattern is shown in Figure 4. The found CBSSs will serve as the data source for selecting Experience Rules.Figure 4
The structure of SequentialPattern.Key State. Given a threshold percentageminFreq, Key States are those pieces-states of the frequencies not less thanminFreq. The frequency (denoted byfreq) of a pieces-state can be calculated by
(4)
f
r
e
q
=
c
o
u
n
t
N
×
100
%
,
where N stores the total number of sequences in database andcount denotes the occurrence number of the pieces-state in the net winning games. The value ofcount is figured out during the process of data extraction (see lines (17) and (23) in Algorithm 1).In respect of threshold selection, adjustingminFreqdynamically in accordance with the number of Experience Rules can make the Key States more efficient.Checker Usage. This pattern can be calculated by formula (1), in which the F
C
_
C
o
u
n
t
C is figured out during the process of data extraction (see line (12) in Algorithm 1).


## 2.2.3. Data Representation

In this phase, the main task is to make the mined experiential patterns recognizable to the computer player. The experiential pattern here mainly refers to Experience Rule. The following format is used to represent an Experience Rule:(5)
p
r
e
m
i
s
e
⟶
r
e
s
u
l
t
:
s
u
p
p
o
r
t
.According to the data structure of the Experience Rule, the process of data representation can be described as follows. Replace the IDs, which denote the last states or next states of Experience Rules, with the corresponding pieces-states, and then write these pieces-states to an XML file in server-side.However, the mined patterns may not be all reliable. For example, given aminSupport, the obtained Experience Rules are as follows:
(6)
P
S
a
⟶
P
S
b
:
15
%
P
S
a
⟶
P
S
c
:
13
%
P
S
a
⟶
P
S
d
:
17
%
.
That is, one last state has multiple next states. When pieces-state P
S
a appears, it is clearly reliable to select the pieces-state P
S
d, which is of the highestsupport. Hence, the reliability selection should be done before data presentation. Algorithm 5 shows this process.Algorithm 5:
ReliabilitySelection.
Procedure ReliabilitySelection
Input:
minSupport, the minimum support threshold.
total: the total number of sequences.
sequencesD, the data table of PiecesStateSequence in database.
Output:
sps, the set of reliable Experience Rules.
Method:
(01)root = CreatSequenceTree(sequencesD);
(02)CBSSFinding(minSupport, root, total, sps);
(03)for
i
=
0
to
sps.length – 2 do
(04)for
j
=
i
+
1
to
sps.length − 1 do
(05)if
sps[i].premise == sps[j].premisethen
(06)if
sps[i].support < sps[j].supportthen
(07)sps.delete(i);
(08)i−−;
(09)break;
(10)else
(11)sps.delete(j);
(12)j−−;
(13)endif
(14)endif
(15)endfor
(16)endfor


## 2.3. Applying Experiential Patterns

The way of applying experiential patterns depends on the specific gameplay. In this section, we give a computer player’s strategy as shown in Figure5 and then explain how to apply the mined experiential patterns to the actual game.Figure 5
Strategy of the computer player.In the course of the game, the computer player uses Experience Rules first. Algorithm6 demonstrates the procedure of matching Experience Rules.Algorithm 6:
ExperienceRuleMatching.
Procedure
ExperienceRuleMatching
Input:
PS, the current pieces-state.
ERs: the set of Experience Rules.
Output:
nextPS, the next pieces-state.
Method:
(01)for each
er
in
ERs
do
(02)if
PS == er.lastthen
(03)nextPS = er.next;
(04)break;
(05)else
(06)nextPS = null;
(07)endif
(08)endforWhen there are no available Experience Rules, the computer player will automatically approximate a certain Key State. Doing so can promote the formation of some good game situation and may activate some Experience Rules. Obviously, the approached Key State is the nearest pieces-state after the current one. So, all of the Key States are sorted by their occurrence time. LetP
S
a and P
S
b be two different pieces-states. Their order is defined below.Definition 1.
Assume thatP
S
a
≠
P
S
b. If P
S
a
·
SAS
≥
P
S
b
·
SAS and P
S
a
·
SPS
≥
P
S
b
·
SPS, then P
S
a is behind P
S
b, which can be expressed as P
S
a
≥
P
S
b.The concept of dissimilarity (denoted byDiss) is used to represent the closeness between two pieces-states. TheDiss between P
S
a and P
S
b is equal to the least moves from P
S
a to P
S
b. The less the value ofDiss, the closer the two pieces-states. For calculatingDiss, the following definitions are given.Definition 2.
LetP be a piece and let P
S be a set of pieces-states. If the coordinate of P is included in P
S, then P belongs to P
S, which can be expressed as P
∈
P
S.Definition 3.
LetC
a and C
b be two checkers, (
x
a
,
y
a
) and (
x
b
,
y
b
) their coordinates, respectively, and x
a
+
y
a
≥
x
b
+
y
b. Then, the minimal number of steps for a move from C
a to C
b is called move distance from C
a to C
b and denoted by M
D
a
b, which can be calculated by
(7)
M
D
a
b
=
φ
x
a
-
x
b
+
φ
y
a
-
y
b
,
where the function φ is defined as
(8)
φ
x
=
x
,
x
≥
0
0
,
x
<
0
.Definition 4.
LetP
a and P
b be two pieces, C
a and C
b their checkers, respectively, P
S
a and P
S
b two pieces-states, P
a
∈
P
S
a
·
SIS, and P
b
∈
P
S
b
·
SIS. Then, the minimal number of steps for a move from C
a to C
b is called the Distance in Active Side between P
a and P
b, which is denoted by DAS
a
b. Similarly, one can define the Distance in Passive Side between P
a and P
b, which is denoted by DP
S
a
b.Algorithm7 demonstrates the calculation of the distance between two pieces.Algorithm 7:
PiecesDistanceCalculation.
Procedure
PiecesDistanceCalculation
Input:
PS, the current pieces-state.
P
a, piece P
a.
P
b, piece P
b.
Output:
Dab, the distance between P
a and P
b.
Method:
(01)let
CS be the checkers-state;
(02) let
vAllFC be a vector to store the falling checkers of every layer.
(03) //The maximum distance between P
a and P
b.
(04) Calculate the move distance MDab;
(05) if
MDab == 0 or
MDab == 1 or
MDab == 2 then
(06) //If MDab is less than 3, there is no less distance.
(07)  return
MDab;
(08) endif
(09) for
i = 0 to 9 do
(10) CS[PS⋅SAS[i]⋅x][PS⋅SAS[i]⋅y] = 1;
(11) CS[PS⋅SPS[i]⋅x][PS⋅SPS[i]⋅y] = −1;
(12) endfor
(13) FindVirtualFallingCheckers(0, CS, P
a
⋅
x, P
a
⋅
y, true, vAllFC, 0);
(14) isBreak = false; //Denotes the end of searching.
(15) Dab = MDab; //The distance in the worst case.
(16) for
each
allFC
in
vAllFC
do
(17) for
each
c
in
allFC
do
(18)  if
allFC.index == (MDab−1) then
(19)   isBreak = true; break;
(20)  endif
(21)  if
c
⋅
x == P
b
⋅
x
and
c
⋅
y == P
b
⋅
y
then
(22)   Dab = allFC.index + 1; isBreak = true;
(23)   break;
(24)  endif
(25)  if
allFC.index == (MDab−2) then break; endif
(26)
FindVirtualFallingCheckers(0, CS, c
⋅
x, c
⋅
y, true, vAllFC, allFC.index + 1);
(27) endfor
(28) if
isBreak == true
then break; endif
(29) endfor
(30) return
Dab;
(31) //Search the virtual falling checkers of specified checkers.
(32) Function
FindVirtualFallingCheckers(d, CS, x, y, isFirstStep, vAllFC, index)
(33) begin
(34) for
i = 3to−3 do
(35)  if
i == −d  then continue; endif
(36)  if
i == 0 then continue; endif
(37)  Search the next jumping falling checker (x
′, y
′) in direction i of checker (x, y).
(38)  if (x
′, y
′) exists then
(39)   vAllFC[index].add(new
Coordinate(x
′, y
′));
(40)   FindVirtualFallingCheckers(3, CS, x
′, y
′, false, vAllFC, index);
(41)  else if the piece on (x
′, y
′) is of own side then
(42)   FindVirtualFallingCheckers(3, CS, x
′, y
′, true, vAllFC, index + 1);
(43)  else
(44)   if
isFirstStep == true
then
(45)     vAllFC[index].add(new
Coordinate(x
′, y
′));
(46)   endif
(47)  endif
(48) endfor
(49)endLetP
S
a and P
S
b be two pieces-states. According to Definitions 2–4, the dissimilarity matrices between P
S
a and P
S
b are defined as follows:
(9)
D
i
s
s
M
a
t
r
i
x
A
S
=
DAS
00
⋯
DAS
09
⋮
⋱
⋮
DAS
90
⋯
DAS
99
D
i
s
s
M
a
t
r
i
x
P
S
=
DPS
00
⋯
DPS
09
⋮
⋱
⋮
DPS
90
⋯
DPS
99
,
whereDissMatrixAS is defined on the active side andDissMatrixPS on the passive side. Then, theDiss between two pieces can be calculated by
(10)
D
i
s
s
=
min
⁡
⁡
∑
a
=
0
9
∑
b
=
0
9
DAS
a
b
X
a
b
+
∑
a
=
0
9
∑
b
=
0
9
DPS
a
b
Y
a
b
,
where X
a
b and Y
a
b satisfy the following conditions, respectively:
(11)
∑
a
=
0
9
X
a
b
=
1
∑
b
=
0
9
X
a
b
=
1
a
,
b
=
0,1
,
2
,
…
,
9
X
a
b
=
0,1
,
∑
a
=
0
9
Y
a
b
=
1
∑
b
=
0
9
Y
a
b
=
1
a
,
b
=
0,1
,
2
,
…
,
9
Y
a
b
=
0,1
.It follows that the calculation of theDiss between pieces is a typical assignment problem in linear programming. This problem can be solved byHungarian algorithm as discussed by Edmonds [38].When there are no Key States behind the current pieces-state or theDiss between the nearest Key State and the current pieces-state is more than a given threshold, the computer player will execute a tentative move algorithm namedTentativeMove, which was designed based on the traditional alpha-beta pruning algorithm [7] (see Appendix for more details). Moreover, the pattern Checker Usage is one of the parameters ofTentativeMove.


## 3. Results and Discussions

In order to evaluate the effect and performance of our proposed approach, we conducted an experiment on our designed test platform mentioned in Section2. The experiment contains a series of tests. To maintain the objectivity of the experiment, we chose the same group of testers, who are ten experienced human players.


### 3.1. Test in Human-Computer Mode without any Experiential Patterns

Each tester played against the computer player for 30 games, serving as offensive player (OffP) and defensive player (DefP) alternately. The computer player was only allowed to useTentativeMove using a default value of Checker Usage as the parameter. A total of 300 game-logs in this test were recorded. The test results are shown in Table 4.Table 4
Data records of the test in human-computer mode without any experiential pattern.
Tester
Gts
Role
Wts
Anrs
Wr (%)
00
15
OffP
5
45
33.33
00
15
DefP
4
42
26.67
01
15
OffP
5
47
33.33
01
15
DefP
3
45
20.00
02
15
OffP
4
44
26.67
02
15
DefP
1
40
6.67
03
15
OffP
3
45
20.00
03
15
DefP
2
41
13.33
04
15
OffP
4
42
26.67
04
15
DefP
4
47
26.67
05
15
OffP
4
44
26.67
05
15
DefP
1
40
6.67
06
15
OffP
6
49
40.00
06
15
DefP
4
42
26.67
07
15
OffP
2
37
13.33
07
15
DefP
2
36
13.33
08
15
OffP
6
45
40.00
08
15
DefP
3
45
20.00
09
15
OffP
5
45
33.33
09
15
DefP
2
40
13.33
Note: Gts: game times; Role: role of the computer player; Wts: winning times of the computer player; Anrs: average number of the rounds per game; and Wr: winning rate of the computer player.Furthermore, we observed the performance of our algorithms by using the parameter ATMC (the average time for each move of the computer player). A script embedded into the program was used to calculate the response time of the computer player during testing and give the value of ATMC in the end. In this test, the value of ATMC was 5.85 s (s = seconds).Descriptions of Effects. (a) The computer player has the ability to play correctly; (b) the winning rate of the computer player in competition with every tester is not more than a half; (c) the computer player spends a little long time to move a piece.Discussions. (a) Condition (i) mentioned at the beginning of Section 2 is satisfied by the TentativeMove algorithm; (b) the moves driven by TentativeMove may not be optimal due to the error of its evaluation function and the restraint of searching depth, which affects the winning rate of the computer player; (c) TentativeMove has a deeper recursion depth. As the game goes on, the checkers to be searched in each recursive layer will increase rapidly, which degrades the performance of TentativeMove.


### 3.2. Test in Human-Human Mode for Collecting Game-Logs

Each tester played with all the others for 30 games, serving as OffP and DefP alternately. A total of 1350 game-logs in this test were recorded. This satisfied condition (ii) mentioned at the beginning of Section2. Subsequently, additional tests in human-computer mode were performed to select the appropriateminSupport andminFreq. These tests were similar to those in Section 3.1, and the results are shown in Table 5. Finally, the experiential pattern mining program was executed with the selectedminSupport andminFreq. As a result, we gained 528 Experience Rules and 575 Key States, and the Checker Usage of every checker was updated in real time.Table 5
Data records of the additional tests for selecting thresholds. A total of 1650 game-logs were used as the data source.
Gts
Ms (%)
Mf (%)
Ner
Nks
Anep
Auep (%)
15
10
5
113
160
4
1.47
15
8
4
275
323
11
1.84
15
6
3
386
421
15
1.86
15
4
2
460
512
19
1.95
15
2
1
528
575
26
2.36
15
1
0.5
582
649
26
2.11
15
0.5
0.25
638
691
27
2.03
15
0.25
0.125
690
743
28
1.95
Note: Gts: game times; Ms: minSupport; Mf: minFreq; Ner: number of Experience Rules; Nks: number of Key States; Anep: average number of experiential patterns used in each game; and Auep: average usage of experiential patterns per game.As shown in Table5, whenminSupport was 2% andminFreq was 1%, the crest value ofAuep was reached, which meant the mined experiential patterns were better utilized.


### 3.3. Test in Human-Computer Mode with Experiential Patterns

The test plan here was the same as that in Section3.1, except for the applying of the experiential patterns obtained in the test mentioned in Section 3.2. The results are shown in Table 6, and the comparison with the test results in Section 3.1 is illustrated in Figure 6. In this test, the value of ATMC was 0.93 s.Table 6
Data records of the test in human-computer mode with experiential patterns.
Tester
Gts
Role
Wts
Anrs
Wr (%)
00
15
OffP
9
51
60.00
00
15
DefP
7
51
46.67
01
15
OffP
8
52
53.33
01
15
DefP
4
54
26.67
02
15
OffP
4
56
26.67
02
15
DefP
3
50
20.00
03
15
OffP
8
51
53.33
03
15
DefP
5
49
33.33
04
15
OffP
9
54
60.00
04
15
DefP
7
52
46.67
05
15
OffP
8
52
53.33
05
15
DefP
5
48
33.33
06
15
OffP
10
56
66.67
06
15
DefP
6
50
40.00
07
15
OffP
4
48
26.67
07
15
DefP
2
51
13.33
08
15
OffP
11
52
73.33
08
15
DefP
7
52
46.67
09
15
OffP
9
52
60.00
09
15
DefP
5
50
33.33
Note: Gts: game times; Role: role of the computer player; Wts: winning times of the computer player; Anrs: average number of the rounds per game; and Wr: winning rate of the computer player.Figure 6
Comparison of the winning rates of the computer player.Descriptions of Effects. (a) Figure 6 shows that, by using experiential patterns, the computer player has increased its winning rates in most of the games at different degrees; (b) the average number of the rounds per game has increased; (c) the value of ATMC has declined dramatically.Discussions. (a) The effectiveness of experiential patterns will become more obvious with the increase of game-logs, and this will give the human players an impression that the computer player is learning from the experience; (b) in a few games such as 02-OffP and 07-DefP shown in Figure 6, although the computer player’s winning rates are not increased, the average number of the rounds per game is greatly raised (see the lines with bold font shown in Table 6). The testers obviously feel the improvement of the computer player’s chess skill; (c) if the Experience Rules exist, the computer player will match and use them first. Compared with TentativeMove, the pattern matching algorithm is of linear complexity and consumes less time (see Algorithm 6).


### 3.4. Test in Computer-Computer Mode

In this test, we set two computer players. One could use the experiential patterns and the other could not. They took turns to serve as OffP and played with each other for 30 games. The results are shown in Table7.Table 7
Data records of the test in computer-computer mode. The computer player using experience patterns is denoted by CP1 and the other by CP2.
Player
Wts
Anep
ATMC (s)
Wr (%)
CP1
56
26
0.91
93.33
CP2
4
0
5.77
6.67
Note: Wts: winning times; Anep: average number of experiential patterns used in each game; ATMC: value of ATMC; and Wr: winning rate.Description of the Effect. The computer player using experience patterns has a great advantage in winning rate and ATMC.Discussion. Experiential patterns can help the computer player in making more strategic moves; still, we are aware of four losing games of CP1 (as shown in Table 7). This indicates that some of the experiential patterns may not be really good. However, the invalid patterns will die out with the growth of game-logs.


### 3.5. Comparative Analysis on the Algorithms of Pattern Mining

A sequence database consists of sequences of ordered elements, and these elements contain some unordered items. The common objectives of the previous works [27–31] are to find the interesting relations between these items. In this work, however, the pattern mining algorithms aim at finding only the frequent CBSSs in the game-logs. This can be considered as a special case of the sequential pattern mining on a sequence database. For ease of comparison, we implemented the traditional algorithmPrefixSpan and added some restraints to make it fit for mining in our game-logs. These restraints were (a) setting length of each subsequence to 2 and (b) setting size of each element to 1. The comparative results are shown in Figure 7.Figure 7
Performance of the two algorithms on a given data set.ErsMining denotes the set of algorithms, includingSequenceTreeCreation,BranchShifting,CBSSFinding, andReliabilitySelection, for mining Experience Rules.Here the minSupport was set to 2%, and the given data set contained 1,650 sequences (i.e., game-logs), 155,100 elements (i.e., pieces-states). Figure7 indicates that our algorithms compared withPrefixSpan are more efficient.


### 3.6. Discussion on the Using of Game-Logs

Previous works [17–24] mainly discuss the methods of extracting expert knowledge from game records. The extracted knowledge is commonly used to construct a game agent of high intelligence. Differently, our work aims at helping a computer player in learning from growing game-logs, acquiring human’s experience, and gradually becoming more skillful. It is a practical approach to make the game more fascinating. Furthermore, by satisfying the two conditions mentioned at the beginning of Section 2, any board game can utilize this approach after a minor adjustment. And this shows the extensibility of our approach.


## 3.1. Test in Human-Computer Mode without any Experiential Patterns

Each tester played against the computer player for 30 games, serving as offensive player (OffP) and defensive player (DefP) alternately. The computer player was only allowed to useTentativeMove using a default value of Checker Usage as the parameter. A total of 300 game-logs in this test were recorded. The test results are shown in Table 4.Table 4
Data records of the test in human-computer mode without any experiential pattern.
Tester
Gts
Role
Wts
Anrs
Wr (%)
00
15
OffP
5
45
33.33
00
15
DefP
4
42
26.67
01
15
OffP
5
47
33.33
01
15
DefP
3
45
20.00
02
15
OffP
4
44
26.67
02
15
DefP
1
40
6.67
03
15
OffP
3
45
20.00
03
15
DefP
2
41
13.33
04
15
OffP
4
42
26.67
04
15
DefP
4
47
26.67
05
15
OffP
4
44
26.67
05
15
DefP
1
40
6.67
06
15
OffP
6
49
40.00
06
15
DefP
4
42
26.67
07
15
OffP
2
37
13.33
07
15
DefP
2
36
13.33
08
15
OffP
6
45
40.00
08
15
DefP
3
45
20.00
09
15
OffP
5
45
33.33
09
15
DefP
2
40
13.33
Note: Gts: game times; Role: role of the computer player; Wts: winning times of the computer player; Anrs: average number of the rounds per game; and Wr: winning rate of the computer player.Furthermore, we observed the performance of our algorithms by using the parameter ATMC (the average time for each move of the computer player). A script embedded into the program was used to calculate the response time of the computer player during testing and give the value of ATMC in the end. In this test, the value of ATMC was 5.85 s (s = seconds).Descriptions of Effects. (a) The computer player has the ability to play correctly; (b) the winning rate of the computer player in competition with every tester is not more than a half; (c) the computer player spends a little long time to move a piece.Discussions. (a) Condition (i) mentioned at the beginning of Section 2 is satisfied by the TentativeMove algorithm; (b) the moves driven by TentativeMove may not be optimal due to the error of its evaluation function and the restraint of searching depth, which affects the winning rate of the computer player; (c) TentativeMove has a deeper recursion depth. As the game goes on, the checkers to be searched in each recursive layer will increase rapidly, which degrades the performance of TentativeMove.


## 3.2. Test in Human-Human Mode for Collecting Game-Logs

Each tester played with all the others for 30 games, serving as OffP and DefP alternately. A total of 1350 game-logs in this test were recorded. This satisfied condition (ii) mentioned at the beginning of Section2. Subsequently, additional tests in human-computer mode were performed to select the appropriateminSupport andminFreq. These tests were similar to those in Section 3.1, and the results are shown in Table 5. Finally, the experiential pattern mining program was executed with the selectedminSupport andminFreq. As a result, we gained 528 Experience Rules and 575 Key States, and the Checker Usage of every checker was updated in real time.Table 5
Data records of the additional tests for selecting thresholds. A total of 1650 game-logs were used as the data source.
Gts
Ms (%)
Mf (%)
Ner
Nks
Anep
Auep (%)
15
10
5
113
160
4
1.47
15
8
4
275
323
11
1.84
15
6
3
386
421
15
1.86
15
4
2
460
512
19
1.95
15
2
1
528
575
26
2.36
15
1
0.5
582
649
26
2.11
15
0.5
0.25
638
691
27
2.03
15
0.25
0.125
690
743
28
1.95
Note: Gts: game times; Ms: minSupport; Mf: minFreq; Ner: number of Experience Rules; Nks: number of Key States; Anep: average number of experiential patterns used in each game; and Auep: average usage of experiential patterns per game.As shown in Table5, whenminSupport was 2% andminFreq was 1%, the crest value ofAuep was reached, which meant the mined experiential patterns were better utilized.


## 3.3. Test in Human-Computer Mode with Experiential Patterns

The test plan here was the same as that in Section3.1, except for the applying of the experiential patterns obtained in the test mentioned in Section 3.2. The results are shown in Table 6, and the comparison with the test results in Section 3.1 is illustrated in Figure 6. In this test, the value of ATMC was 0.93 s.Table 6
Data records of the test in human-computer mode with experiential patterns.
Tester
Gts
Role
Wts
Anrs
Wr (%)
00
15
OffP
9
51
60.00
00
15
DefP
7
51
46.67
01
15
OffP
8
52
53.33
01
15
DefP
4
54
26.67
02
15
OffP
4
56
26.67
02
15
DefP
3
50
20.00
03
15
OffP
8
51
53.33
03
15
DefP
5
49
33.33
04
15
OffP
9
54
60.00
04
15
DefP
7
52
46.67
05
15
OffP
8
52
53.33
05
15
DefP
5
48
33.33
06
15
OffP
10
56
66.67
06
15
DefP
6
50
40.00
07
15
OffP
4
48
26.67
07
15
DefP
2
51
13.33
08
15
OffP
11
52
73.33
08
15
DefP
7
52
46.67
09
15
OffP
9
52
60.00
09
15
DefP
5
50
33.33
Note: Gts: game times; Role: role of the computer player; Wts: winning times of the computer player; Anrs: average number of the rounds per game; and Wr: winning rate of the computer player.Figure 6
Comparison of the winning rates of the computer player.Descriptions of Effects. (a) Figure 6 shows that, by using experiential patterns, the computer player has increased its winning rates in most of the games at different degrees; (b) the average number of the rounds per game has increased; (c) the value of ATMC has declined dramatically.Discussions. (a) The effectiveness of experiential patterns will become more obvious with the increase of game-logs, and this will give the human players an impression that the computer player is learning from the experience; (b) in a few games such as 02-OffP and 07-DefP shown in Figure 6, although the computer player’s winning rates are not increased, the average number of the rounds per game is greatly raised (see the lines with bold font shown in Table 6). The testers obviously feel the improvement of the computer player’s chess skill; (c) if the Experience Rules exist, the computer player will match and use them first. Compared with TentativeMove, the pattern matching algorithm is of linear complexity and consumes less time (see Algorithm 6).


## 3.4. Test in Computer-Computer Mode

In this test, we set two computer players. One could use the experiential patterns and the other could not. They took turns to serve as OffP and played with each other for 30 games. The results are shown in Table7.Table 7
Data records of the test in computer-computer mode. The computer player using experience patterns is denoted by CP1 and the other by CP2.
Player
Wts
Anep
ATMC (s)
Wr (%)
CP1
56
26
0.91
93.33
CP2
4
0
5.77
6.67
Note: Wts: winning times; Anep: average number of experiential patterns used in each game; ATMC: value of ATMC; and Wr: winning rate.Description of the Effect. The computer player using experience patterns has a great advantage in winning rate and ATMC.Discussion. Experiential patterns can help the computer player in making more strategic moves; still, we are aware of four losing games of CP1 (as shown in Table 7). This indicates that some of the experiential patterns may not be really good. However, the invalid patterns will die out with the growth of game-logs.


## 3.5. Comparative Analysis on the Algorithms of Pattern Mining

A sequence database consists of sequences of ordered elements, and these elements contain some unordered items. The common objectives of the previous works [27–31] are to find the interesting relations between these items. In this work, however, the pattern mining algorithms aim at finding only the frequent CBSSs in the game-logs. This can be considered as a special case of the sequential pattern mining on a sequence database. For ease of comparison, we implemented the traditional algorithmPrefixSpan and added some restraints to make it fit for mining in our game-logs. These restraints were (a) setting length of each subsequence to 2 and (b) setting size of each element to 1. The comparative results are shown in Figure 7.Figure 7
Performance of the two algorithms on a given data set.ErsMining denotes the set of algorithms, includingSequenceTreeCreation,BranchShifting,CBSSFinding, andReliabilitySelection, for mining Experience Rules.Here the minSupport was set to 2%, and the given data set contained 1,650 sequences (i.e., game-logs), 155,100 elements (i.e., pieces-states). Figure7 indicates that our algorithms compared withPrefixSpan are more efficient.


## 3.6. Discussion on the Using of Game-Logs

Previous works [17–24] mainly discuss the methods of extracting expert knowledge from game records. The extracted knowledge is commonly used to construct a game agent of high intelligence. Differently, our work aims at helping a computer player in learning from growing game-logs, acquiring human’s experience, and gradually becoming more skillful. It is a practical approach to make the game more fascinating. Furthermore, by satisfying the two conditions mentioned at the beginning of Section 2, any board game can utilize this approach after a minor adjustment. And this shows the extensibility of our approach.


## 4. Conclusions

In this paper, a novel approach is proposed to mine experiential patterns from the game-logs of board game. Those experiential patterns can be utilized to improve the intelligence of a computer player. This approach makes computer players learn from human’s experience progressively during gaming and become more experienced with the increase of game-logs. This will make the game more interesting. We conducted an experiment on our designed test platform of Chinese checkers game, and the results demonstrate that our approach is effective, efficient, and extensible.Nevertheless, our approach still needs improvements from several aspects, such as the following:(i)
designing algorithms to automatically adjust the parametersminSupport andminFreq;
(ii)
optimizing the related algorithms to improve their access performance for a huge sequence-tree;
(iii)
researching the fast matching problem in massive experiential patterns;
(iv)
developing the approach for online analysis of game-logs;
(v)
looking for more experiential patterns making games interesting.



---

*Source: 576201-2015-01-22.xml*