=Paper=
{{Paper
|id=Vol-1348/maics2013_paper_6
|storemode=property
|title=Fuzzy Patterns Based Approach for Environment Analysis in Adversarial Games
|pdfUrl=https://ceur-ws.org/Vol-1348/maics2013_paper_6a.pdf
|volume=Vol-1348
|dblpUrl=https://dblp.org/rec/conf/maics/Coffman-WolphK13
}}
==Fuzzy Patterns Based Approach for Environment Analysis in Adversarial Games==
https://ceur-ws.org/Vol-1348/maics2013_paper_6a.pdf
Fuzzy Patterns Based Approach for Environment Analysis in
Adversarial Games
Stephany Coffman-Wolph and Dionysios Kountanis
Department of Computer Science, Western Michigan University
1903 West Michigan Avenue, Kalamazoo, Michigan 49008
stephany.s.coffman-wolph@wmich.edu and dionysios.kountanis@wmich.edu
and easier to analyze areas. Patterns contain five essential
Abstract elements: a starting piece (location), an ending piece (loca-
tion), a shortest path between the starting and ending loca-
Adversarial game-playing situations have been commonly tion (the main path), the attacking or blocking pieces to this
studied in both game theory and artificial intelligence since shortest path, and the shortest paths of any attacking or
the 1950s. However, developing strategies for game play-
blocking pieces. The shortest path contains a candidate
ing has been a challenge due to large search tree size – es-
next move for the starting piece and the information to
pecially as the environment size increases. In this work, we
introduce a new concept entitled Fuzzy Patterns that is in-
evaluate the potential impact the move has on the end goal
spired from Stilman’s zone concept and utilizes a combina- of the system. It is important to note that each pattern only
tion of fuzzy logic and division of the environment into contains one valid shortest path and that all larger paths are
mini-goals to prune a large search tree. Our proposed ap- not considered for either the main path or any attack-
proach provides an essential tool to break a large environ- ing/blocking paths.
ment into smaller interest areas to focus, study, and select There are several key terms that need to be defined or
possible moves. Our proposed Fuzzy Patterns approach clarified including: step, reach-ability, attack-ability, and
improves upon the existing zone concept from Stilman’s shortest path. A step, in this context, is a single move
Linguistic Geometry algorithm in two ways: quicker to made by a piece during a turn in the game (assumed to be a
compute and producing significantly smaller number of valid move via the rules of the game in question). Reach-
patterns. Even though our proposed approach is generic ability is the ability of a piece to reach a given location
and can be applied to any adversarial game-playing scenar- within the environment given the rules or physical limita-
io, in this paper we use a standard chessboard as the envi- tions of the piece. Attack-ability is the ability of a piece to
ronment with standard chess pieces and movement to attack/remove a piece in a given location within the envi-
demonstrate the potential benefits of our proposed ap-
ronment given the rules or physical limitations of the piece.
proach (up to 80% reduction in the number of fuzzy pat-
In some situations the reach-ability and attack-ability are
terns that need to be evaluated over the non-fuzzy based
approach). the same – a good example is the queen piece in chess. In
the case of the pawn, the reach-ability and the attack-ability
Analysis of the environment for any adversarial game- are not the same. The shortest path is defined as the mini-
playing situation can be a daunting task. The larger the mum number of moves or steps a piece needs in order to
environment, the greater the number of potential sequences each an ending location assuming that the location is reach-
of moves and the harder the task of choosing among vari- able or attack-able. In many game situations, including
ous strategies. The game of chess has a fairly restricted chess, there are often multiple shortest paths between two
environment of only 8 by 8. Chess is known to have an locations.
average branching factor of 35 with 50 moves per game The Linguistic Geometry (LG) Search Strategy intro-
for each side resulting in searching trees with 35100 nodes duced by Stilman contains 4 layers (from lowest to high-
(Russell and Norvig 1995). Even the extremely simple est): trajectories, zones, translations, and searches (Stilman
game of tic-tac-toe contains a branching factor of 9 at the 2000). The first two layers of the LG are part of the inspi-
first level alone – the same size as the environment (Rus- ration to the patterns based approach presented in this pa-
sell and Norvig 1995). Therefore, it is essential to develop per. The lowest level, trajectories, finds all shortest paths
techniques to eliminate search branches in order to im- between a starting location and ending location (Stilman
prove any viable adversarial game-playing algorithm. 1994). The second lowest level, zones, finds all reachable
A pattern is used to analyze and identify potential moves starting and ending piece combinations and any intersec-
for various pieces within the environment. Patterns are tions. The zone is used to analyze the environment in small
used primarily to sub-divide the environment into smaller focused areas (Stilman 2000).
There are several key differences between the zone and
the pattern concepts. The LG algorithm is written as a se-
Copyright retained by the authors. ries of grammars that are designed to be used with older
rule-based or recursive computer programming languages piece, but from the point of view of the ending location.
(Stilman 2000). Our proposed pattern based algorithm is Like reach-ability, obtain-ability is based on the rules or
designed to be used with modern object-oriented pro- laws of the piece. Basically the obtain-ability is the reverse
gramming languages (java, C#, etc). The LG grammars of the reach-ability starting at the end location.
are recursive in nature (Stilman 2000) while the algorithms Rooks, bishops, and the queen can move any number of
for patterns are not. The storage of a pattern is an object spaces across the chessboard within a single turn. Rooks
while a zone is a complex string that requires complex can only move north, south, east, or west. Therefore, a
processing for interpretation. The pattern is also a compu- rook can reach any space within the chessboard in either 1
tationally less complex algorithm due to restricting the or 2 steps. Every location on the board that is not directly
depth of examination of intersections. Patterns only exam- north, south, east, or west of the rook has a shortest path of
ine the first level of pieces that can attack or block the 2 steps. All locations that are directly north, south, east,
main path while the zones look at all levels in a recursive and west of the rook are 1 step. The reach-ability matrix of
manner. A major difference between zones and patterns is a rook (R) currently located at (4,3) is seen in figure 1.
that patterns differentiate between reach-ability and attack-
ability for each given piece. The grammar of trajectory, a 2 2 2 2 1 2 2 2 8
method for calculating all the shortest paths between two 2 2 2 2 1 2 2 2 7
elements, is used extensively in the pattern generation al- 2 2 2 2 1 2 2 2 6
gorithm but it has been modified from the recursive gram- 2 2 2 2 1 2 2 2 5
mar format to a straightforward procedural algorithm. 2 2 2 2 1 2 2 2 4
This paper presents the algorithm to generate fuzzy pat- 1 1 1 1 R 1 1 1 3
terns. A detailed example is used to illustrate the applica- 2 2 2 2 1 2 2 2 2
bility of our proposed approach to an adversarial game. 2 2 2 2 1 2 2 2 1
Additionally, an in-depth analysis of the efficacy of using 8 7 6 5 4 3 2 1
our proposed fuzzy approach is presented.
Figure 1: Rook
The Problem Description
The environment is the area to which the patterns (fuzzy or The number within each square represents the smallest
non-fuzzy) are applied. For the examples in this paper, the number of steps it would take the rook to make it to the
environment is a chessboard. A standard chessboard is 8 given location. For example, it takes the rook 2 steps to
rows by 8 columns for a total of 64 squares. Each chess- reach location (8,1) and only 1 step to reach location (4,7).
board square is shaded by one of two contrasting colors in A similar reach-ability matrix can be developed for all of
an alternating dark/light color scheme (the color scheme is the other chess pieces. Pawns are a special case because
commonly referred to as black and white, sometimes white pawns have different attack-ability and reach-ability.
and red or even black and red). A standard chess set comes Pawns can only move in a “forward” direction (i.e., to-
with 8 pawns, 2 rooks, 2 bishops, 2 knights, 1 queen, and 1 wards the opposing side). Pawns are also unique in their
king of each of two colors usually white (attack) and black ability to move one or two spaces on their first move but
(defense). only one space on subsequent moves. The pawns have the
most complex reach-ability and attack-ability patterns.
Reach-ability and Attack-ability Pawns have the most restricted movement and cannot reach
all locations within the chessboard.
The reach-ability is the set of locations within the chess-
board that a given piece at a specific location on the board
can reach and the minimum number of steps it takes to get Finding the Shortest Paths
there (ignoring the positions of any other pieces on the A key element in the pattern generation algorithm is find-
board). The attack-ability is the locations within the ing the shortest path between two pieces. The LG Search
chessboard that a given piece (at a specific location) can Strategy introduces an algorithm entitled “Grammar of
remove a piece of the opposing side (assuming that a piece Trajectory”, which finds all the shortest paths between two
is in place to be taken). Each category of pieces has a elements within a defined environment (Stilman 2000).
unique reach-ability and/or attack-ability within the chess- This recursive algorithm extensively uses the overlap of
board determined by the rules of the game. Pieces could reach-ability matrices to identify the shortest path loca-
take longer paths to reach a given location. However, in tions.
this algorithm the focus will exclusively be on shortest A modified non-recursive algorithm inspired by the tra-
paths. jectory approach to find the shortest paths is given as fol-
The obtain-ability matrix is found using a similar pro- lows:
cess to the reach-ability for the starting piece, except it is
centered on the ending piece. In other words, the calcula- 1. Determine the reach-ability matrix for the starting
tion is similar to that of the reach-ability of the starting piece
2. Determine the obtain-ability matrix for the ending 7 Create a pattern
piece 8 Find all intersecting/blocking pieces (I)
3. Add the reach-ability from step 1 and the obtain- 9 For each i piece in I {
ability from step 2 10 Find shortest paths B between (i, locations in s{
11 If B > 1, for each shortest path b in B {
4. Find the minimum values within the combined 12 Create new pattern w/same main path
matrix and eliminate all non-minimum values
13 Add shortest path b to pattern }
5. Generate the list of shortest paths using the loca- 14 Else: Add shortest path b to pattern }}}}}}
tions identified in previous step
The Algorithm for Finding Fuzzy Patterns
Definition of Fuzzy Pattern
Fuzzification of a concept provides for a more abstract
A pattern is defined by a starting element of one side being view of information (Yen and Langari 1998). It can also be
able to reach an ending element of the opposing side, a thought of as a tool that trades abstraction for a less precise
single shortest path between these two elements and all representation of information (Zadeh 1965). A fuzzy pat-
elements from either side that could interact (positively by tern is simply an abstract view of the pattern. The intro-
blocking or negatively by intersecting). Each pattern has a duction of abstraction to the pattern increases the overall
calculated rank, which combines several elements to de- speed of the algorithm by decreasing the algorithm’s com-
termine goodness. The rank is based on the distances be- plexity and storage requirements. The less information
tween the elements, the value of the elements involved, there is to analyze, the faster the information can be inter-
and the number of intersecting or blocking pieces and the preted and used.
values of these pieces. The fuzzy pattern generation algorithm is similar to the
A fuzzy pattern is a fuzzified version of the pattern pattern generation algorithm. There are two major differ-
where (1) distances are replaced with fuzzy values, (2) ences between the algorithms – the removal of two loops.
exact shortest paths are replaced with the environment The first change is the removal of the for-each loop that
locations that could be part of any shortest path between walks through each of the shortest path choices generated
these two elements, and (3) the calculated rank is also re- for the main path and generates a new pattern (line 6). The
placed by a fuzzy value (Coffman-Wolph and Kountanis second change is the removal of the for-each loop that
2013b). The pattern is fully contained within the fuzzy walks through each of the shortest path choices generated
pattern. from the blocking/attacking pieces (line 11).
The fuzzy pattern stores the shortest paths together as a
The Algorithm for Finding Patterns group. In other words, the fuzzy pattern is concerned with
the ability of a piece to get from the starting location to the
The calculation of the shortest path begins by finding the end piece’s location, but not with the exact path that is tak-
reach-abilities and/or attack-abilities for each possible en. The shortest paths within the fuzzy pattern will, there-
combination of starting and ending elements within the fore, be analyzed and evaluated as a group, enabling us to
environment. The starting and the ending elements are achieve a significant speedup factor.
always from different sides. In chess, there are two sides The removal of these two loops decreases the complexity
(generally white and black). Therefore, if the starting ele- of the algorithm. Each fuzzy pattern may contain a larger
ment were white, then the ending element would be the amount of information than the equivalent non-fuzzy pat-
opposite - black. tern because all the shortest paths are stored in a group.
Our patterns extraction algorithm generates all the pat- Further, since there does not need to be a pattern for each
terns for all possible combinations of starting and ending shortest path or intersecting/attacking shortest path the
pieces where the starting and ending pieces are from op- overall number of fuzzy patterns is smaller.
posing sides. The pattern also finds any intersecting or
blocking pieces. After identification of these pieces, the Pseudocode for Finding Fuzzy Patterns
shortest paths from these pieces to the shortest main path
are found. Any time multiple shortest paths are found, a 1 Find the reach-ability/attack-ability for each piece
new pattern is created for each of these shortest paths. 2 For each piece x in the environment {
3 For each piece y in the environment {
4 If(( x != y) && (x.side != y.side)) {
Pseudocode for Finding Patterns 5 Find the shortest paths S between (x, y)
1 Find the reach-ability/attack-ability for each piece 6 Create a fuzzy pattern f (store all shortest paths)
2 For each piece x in the environment { 7 Find any intersecting/blocking pieces (I)
3 For each piece y in the environment { 8 For each i piece in I {
4 If(( x != y) && (x.side != y.side)) { 9 Find the shortest paths B between (i, locations in s)
5 Find the shortest paths S between (x, y) 10 Add to fuzzy pattern f }}}}
6 For each shortest path s in S {
Finding Patterns and Fuzzy Patterns 2 2 2 2 3 4 5 6 8
1 1 1 2 3 4 5 6 7
Figure 2 shows an example scenario of a chessboard con- 1 BQ 1 2 3 4 5 6 6
taining a total of 7 pieces: black king (Bkg), black queen
1 1 1 2 3 4 5 6 5
(BQ), black knight (Bkn), white king (Wkg), white bishop
2 2 2 2 3 4 5 6 4
(WB), white rook (WR), and a white pawn (WP). This
3 3 3 3 3 4 5 6 3
scenario is used to demonstrate the generation of both the
4 4 4 4 4 4 5 6 2
pattern and the fuzzy pattern. It is also used to illustrate
the differences between the resulting patterns and the 5 5 5 5 5 5 5 6 1
fuzzy patterns. For comparison, pattern and fuzzy pattern 8 7 6 5 4 3 2 1
generation algorithms will be reviewed step-by-step. For
simplicity, the pattern and fuzzy pattern generation will Figure 4: Black Queen using
only be for the white pieces going to the location of the King Reach-ability
black pieces. In other words, this is from the white side’s
point of view.
2 1 2 2 2 2 2 2 8
Bkg 8 2 1 2 2 2 2 2 2 7
1 BQ 1 1 1 1 1 1 6
7
2 1 2 2 2 2 2 2 5
BQ 6 2 1 2 2 2 2 2 2 4
2 1 2 2 2 2 2 2 3
WB 5
2 1 2 2 2 2 2 2 2
Bkn 4 2 1 2 2 2 2 2 2 1
8 7 6 5 4 3 2 1
WP 3
2
Figure 5: Black Queen using
WR Wkg 1 Rook Reach-ability
8 7 6 5 4 3 2 1
Finding the Shortest Paths
The current list of potential combinations to check after
Figure 2: Example Scenario eliminating the unreachable pairs are as follows: (white
rook, black knight), (white rook, black queen), (white rook,
The algorithms for both the pattern and fuzzy pattern black king), (white pawn, black queen), (white pawn, black
begin with finding the reach-ability and attack-ability for king), (white bishop, black queen), (white bishop, black
all pieces. Figure 3 illustrates the reach-ability of the bish- king), (white king, black knight), (white king, black
op. queen), and (white king, black king).
2 1 2 2 8
2 2 1 2 7
2 2 1 1 6 1 2 2 2 2 2 2 2 8
2 2 2 WB 5 1 2 2 2 2 2 2 2 7
2 2 1 1 4 1 2 2 2 2 2 2 2 6
2 2 1 2 3 1 2 2 2 2 2 2 2 5
2 1 2 2 2 1 2 2 2 2 2 2 2 4
2 1 2 2 1 1 2 2 2 2 2 2 2 3
8 7 6 5 4 3 2 1 1 2 2 2 2 2 2 2 2
R 1 1 1 1 1 1 1 1
Figure 3: Bishop Reach-Ability 8 7 6 5 4 3 2 1
The next step is to find the obtain-abilities. Since these Figure 6: White Rook Reach-
patterns and fuzzy patterns are from the perspective of the Ability
white side, we will only need to find the obtain-abilities for
the black pieces. Figures 4 and 5 illustrate the obtain- Shortest Path(s) for (white rook, black king)
abilities for the Black Queen using the King and Rook Using the calculations in step 1 of the algorithm, com-
reach-abilities. bine (i.e., add the values at) each location and get the re-
sulting combined reach-ability. Figure 6 illustrates the
reach-ability for the white rook and figure 7 illustrates the • White rook (8,1) → (8,8) → Black king (5,8), length =
obtain-ability for the black king. Figure 8 illustrates the 2, attack: Black queen (7,6) → (8,7), block: White bish-
combined reach-ability. op (2,5) → (5,8)
• White rook (8,1) → (8,8) → Black king (5,8), length =
1 1 1 K 1 1 1 1 8 2, attack: Black queen (7,6) → (8,6), block: White bish-
2 2 2 1 2 2 2 2 7 op (2,5) → (5,8)
2 2 2 1 2 2 2 2 6
• White rook (8,1) → (8,8) → Black king (5,8), length =
2 2 2 1 2 2 2 2 5
2, attack: Black queen (7,6) → (8,5), block: White bish-
2 2 2 1 2 2 2 2 4 op (2,5) → (5,8)
2 2 2 1 2 2 2 2 3
2 2 2 1 2 2 2 2 2 The fuzzy pattern, as stated before, combines the multi-
2 2 2 1 2 2 2 2 1 ple paths of information. Also, the fuzzy pattern ignores
8 7 6 5 4 3 2 1 the specifics of the attack/block locations to decrease com-
putational complexity. Additionally, the lengths have been
fuzzified (see figure 9 for the definitions of the fuzzy
Figure 7: Black King using Rook
Reach-ability lengths used for this example). The above seven (non-
fuzzy) patterns are reduced to the following single fuzzy
pattern:
2 3 3 K,2 3 3 3 3 8 White rook (8,1) → (5,1) or (8,8) → Black king (5,8),
3 4 4 3 4 4 4 4 7 length = very short, attack: Black queen, block: White
3 4 4 3 4 4 4 4 6 bishop
3 4 4 3 4 4 4 4 5
3 4 4 3 4 4 4 4 4 Values Fuzzy Variable
3 4 4 3 4 4 4 4 3 0-2 Very Short
3 4 4 3 4 4 4 4 2 2-4 Short
R,2 3 3 2 3 3 3 3 1 4-6 Long
8 7 6 5 4 3 2 1 6-8 Very Long
Figure 8: Combined Reach-ability for White Rook Figure 9: Definition of Fuzzy
and Black King Length Variables
As seen in figure 8, the minimum cost path is 2. Look- Analysis of Patterns vs. Fuzzy Patterns
ing at only the spaces with a 2 in them, it can be seen that
there are two shortest paths: The following is an analysis of the computational ad-
white rook → (5,1) → black king vantages obtained by using the fuzzy pattern representation
white rook → (8.8) → black king over the pattern representation. Informally from the exam-
Therefore, there will be at least two patterns, one for ple scenario in the last section, it can be observed that the
each of the shortest paths. The black queen could intersect number of patterns is often greater than the number of
the path in 1 step by means of multiple shortest paths. The fuzzy patterns. This section quantifies this observation.
white bishop could also become involved in 1 step, but An approximation of the computational savings for each
only one shortest path. The black queen would take differ- piece can be calculated by looking at the average number
ent shortest paths depending on the main path and there are of patterns required. There is always only one fuzzy pat-
multiple choices for each. Each of these choices generates tern for each starting and ending pair of pieces. In the abso-
a different path. lute worst case (i.e., only one shortest path between a pair
• White rook (8,1) → (5,1) → Black king (5,8), length = of pieces), the number of fuzzy patterns would be equal to
2, attack: Black queen (7,6) → (5,4), block: White bish- the number of patterns. As mentioned before, the patterns
op (2,5) → (5,8) and the fuzzy patterns are similar in structure. An individ-
ual fuzzy pattern may require a slightly larger amount of
• White rook (8,1) → (5,1) → Black king (5,8), length = storage space, as noted earlier, but there are fewer fuzzy
2, attack: Black queen (7,6) → (7,1), block: White bish- patterns overall.
op (2,5) → (5,8) Continuing using the standard chess game as an exam-
• White rook (8,1) → (5,1) → Black king (5,8), length = ple, the following paragraphs demonstrate that statistically
2, attack: Black queen (7,6) → (5,6), block: White bish- there are significantly fewer fuzzy patterns needed than
op (2,5) → (5,8) patterns. Each side in a chess game has 8 pawns, 2 rooks, 2
• White rook (8,1) → (8,8) → Black king (5,8), length = bishops, 2 knights, 1 queen, and 1 king. Pawns are the most
2, attack: Black queen (7,6) → (7,8), block: White bish- restricted in movement and the lowest value pieces within
op (2,5) → (5, 8) the game. Pawns are extremely restrictive in movement
and, therefore, usually have only one shortest path to a n = maximum number of steps a piece could take
destination. The bishops are the next most restricted as
they can only move on the diagonal and each can only Most pieces will have an r-value of 63. (There are 64 loca-
reach 50 percent of the board. Knights and rooks, unlike tions on the chessboard and the piece is sitting on 1 loca-
bishops, can travel to any location on the board. Knights tion so there are 63 locations the piece could visit). The
are restricted to moving in an “L” pattern while rooks are bishop is the only exception with r being equal to 31 since
restricted to moving north, south, east, and west. Kings can it can only visit half of the locations. The value of k is spe-
move in any direction, but can only move one space at a cific to each piece and is partly dependent on the move-
time. The queens are the least restricted pieces as they can ment of the piece. The formulas given above are best ex-
move in any direction and for any number of spaces. plained by use of examples.
Special Case: Pawns Example: Rook
As stated earlier, the pawns are greatly restricted in Due to the unique properties of the rook chess piece, it is
movement and rarely have multiple shortest paths. There- the easiest to analyze. (For the purposes of this analysis we
fore, when calculating the approximation, all patterns and ignore the unique move involving the rook and king known
fuzzy patterns with a pawn starting piece are assumed to as castling). The calculation for the rook begins with the
be equivalent. For analysis purposes it is assumed that the examination of locations on the chessboard reach-able with
pawns will not increase (or decrease) the total number of only one move. Because rooks can move north, south, east,
patterns or fuzzy patterns. or west as many spaces as desired, anything along the
north, south, east, or west of the rook is reachable in one
Rooks, Bishops, Knights, Queens, and Kings move. In figure 10, a rook (R) is located at (6,5) and the
chessboard locations marked with an “X” are the locations
Calculating an approximate number of patterns for a given reachable in only one move.
chess piece is not an easy task. The task begins by exam-
ining the number of spaces that are reachable from a given
X 8
starting location by a specific piece, how many moves are
X 7
required to reach each of these locations, and most im-
X 6
portantly the number of shortest paths. To do these com-
X X R X X X X X 5
plex calculations, each piece (rook, bishop, knight, queen,
and king) must be examined individually with respect to its X 4
reach-ability. To further complicate the calculations for X 3
some pieces, the destination location can play a significant X 2
role in the total number of shortest paths. (The greater the X 1
number of moves required to reach the ending location, the 8 7 6 5 4 3 2 1
greater the number of shortest paths).
Figure 10: Reachable Locations
General Formula for Rook at (6,5) in 1 Move
The general formula for calculating the number of patterns
needed for a single starting point is as follows: A chessboard is 8 by 8 and, therefore, has 64 locations.
[(L1/r * 1) + (L2/r * 2) + (L3/r * 3) + … (Ln/r * n)] The rook is sitting on one location leaving 63 locations that
the rook could move. There are 14 total locations that a
Lj = number of locations reach-able in j steps rook can reach in only one move from location (6,5).
r = number of locations reach-able for a give piece Therefore, for these 14 locations there is only one shortest
n = maximum number of steps a piece could take path. The other 49 locations within the chessboard are
reach-able in two moves. There are always only two short-
Several starting locations are equivalent to each other (in est paths that can be used to reach any of these two-move
terms of the reach-ability). So the general formula for locations. Regardless of the starting position of the rook,
calculating the number of patterns needed for a given chess there are always 14 locations reach-able in 1 step and 49
piece considering all 64 spaces as a starting point is as locations reach-able in 2 steps.
follows: From this information and using the general formula
{[(L1/r * 1) + (L2/r * 2) + (L3/r * 3) + … (Ln/r * n)] * (provided earlier), the value of r equals 63 (total number of
z1/t} + … + {[(L1/r * 1) + (L2/r * 2) + (L3/r * 3) + … reachable locations), the value of n equals 2, the value of k
(Ln/r * n)] * zk/t} equals 1, and the value of t equals 64. The average number
of patterns for a given rook piece to a location on the
Lj and r are the same as above chessboard is calculated using the following general formu-
k = number of different situations for a given piece la:
zk = number of equivalent locations for the kth situation [(L1/63 * 1) + (L2/63 * 2)] * z1/64
t = total number of locations a piece can be placed
the value of 6 is used as the estimate for the knight. In both
Plugging in the numbers for the rook (the value of L1 cases 5 and 6 are an underestimate given the ranges for
equals 14, the value of L2 equals 49, and the value of z1 each piece and selected for consistency purposes (i.e., al-
equals 64): ways selecting the lower bound). Unlike the king, both the
[(14/63 * 1) + (49/63 * 2)] * (64/64) = (14/63) + (98/63) queen and knight are used in long range planning and are
= 112/63 = 1.778 actively used throughout a game of chess.
Therefore, there are on average 1.778 patterns for each Range of Upper Number Average
Number
rook piece using the non-fuzzy pattern generation algo- Piece Bound of Shortest used for Number of
on Board
rithm instead of only one fuzzy pattern. Using a fuzzy Paths Estimate Patterns
pattern provides computational savings of over 40%. Pawn 8 1-2 1 1
Rook 2 2 2 1.778
Further Analysis of the Other Pieces: Bishop 2 2 2 1.718
Knight 2 6-12 6 5.167
A similar analysis can be done for all other chess pieces.
Queen 1 5-12 5 3.681
However, the logic is more complex. For starters, most
King 1 3-125 5 4.475
pieces (except rook and bishop) have the property that the
number of shortest paths is not constant and depends great-
ly on location within the chessboard environment. Calcula- Figure 12: Average Number of Patterns for Each Chess Piece
tions for both the king and the knight are significantly
more complex because reaching any location does not
As can be seen from the table in figure 12, the greatest
happen in one or two moves (a property of the rook, bish-
amount of computational savings involves the knight.
op, and queen). Consequently, the king introduces a new There are on average 5.167 patterns in the non-fuzzy algo-
level of complexity to the analysis: the number of shortest
rithm and only one fuzzy pattern. The knights are active
paths for a king depends on both the starting location and
chess pieces and two per side. By using a fuzzy pattern
the distance to the end location. When the king is farther
there is a computational savings of slightly over 80%. Fig-
away from the end location, the number of shortest paths
ure 13 and previous analysis clearly demonstrates the sav-
increases dramatically.
ings of using fuzzy patterns over patterns.
140
90
120
80
100
70
80 60
60 50
40 40
20 30
0 20
1.5 2 2.5 3 3.5 4 4.5 5 5.5 6 6.5 10
0
Figure 11: Number of Shortest Paths for King as Rook Bishop Queen King Knight
Distance From End Piece Increases
From figure 11 it can be seen that, as the king and the Figure 13: % Savings
end piece get farther apart, the number of possible shortest
paths increases dramatically (nearly exponentially). To
calculate the approximate number of patterns, it was de- Conclusions
cided to use the extremely conservative number of 5. This Our proposed fuzzy patterns approach for adversarial game
number is the average number of shortest paths for the playing provides a far superior time advantage over the
king piece and an end piece at 2 or 3 steps away. It was pattern or zones (from the LG algorithm) approaches. As
selected to reflect the usage of the king in more tight- has been shown, the fuzzy patterns eliminate two loops in
cornered situations, because the king pieces are rarely used the algorithm. Thus, reducing the complexity of the algo-
strategically in long-term attack strategies. rithm by O(n2). Each fuzzy pattern is slightly larger in
Figure 12 contains a table that displays the average storage size, but there are significantly fewer for any given
number of patterns for each chess piece. The value of 5 is scenario. The computational savings are greatest any time
used in the estimate for both the queen and the king, while a knight or king is involved (average of 5 patterns to every
1 fuzzy pattern for knight and 4.5 patterns to every 1 fuzzy the Proceedings of the 43rd Southeastern Confer-
pattern for king). The rooks and bishops save close to half ence on Combinatorics, Graph Theory, & Compu-
with the usage of fuzzy patterns. The queen pieces have ting. Winnipeg: Utilitas Mathematica Pub., Inc.
around a 3.5 to 1 savings. Forthcoming.
Furthermore, the computational saving discussed has 2. Coffman-Wolph, S. and Kountanis, D. 2013. A
been on the main path (i.e., the path between the starting General Framework for the Fuzzification of Algo-
and ending pieces). There is an additional multiplicative rithms. In the Proceedings of MICWIC 2013.
computational saving for all attacking or blocking pieces. Forthcoming.
In the pattern generation algorithm, whenever there is an
3. Cox, E. 2005. Fuzzy Modeling and Genetic Algo-
attacking or blocking piece discovered that had multiple
shortest paths, separate patterns are generated for each of rithms for Data Mining and Exploration. San
Francisco, California: Morgan Kauffman Publish-
these paths. The fuzzy pattern generation algorithm con-
ing.
siders the multiple shortest paths as a set (same as the main
path) providing even further savings than shown in the 4. David-Tabibi, O., Koppel, M., and Netanyahi, N.
above analysis. S. 2010. Optimizing Selective Search in Chess. In
the Proceedings of the ICML Workshop on Ma-
chine Learning and Games. Madison, Wisconsin:
Number Fuzzy Patterns
ICML.
Number of Non-Fuzzy Patterns
6 5. Groen, F. C. A., den Boer, G. A., van Inge, A.,
and Stam, R. 1992. A Chess Playing Robot: Lab
5 Course in Robot Sensor Integration, IEEE Trans-
actions on Instrumentation and Measurement 41:
4 911-914.
6. Ross, T. J. 2004. Fuzzy Logic with Engineering
3 Applications. West Sussex, England: John Wiley
& Sons Ltd.
2 7. Russell, S., and Norvig, P. 1995. Artificial Intelli-
gence: A Modern Approach. Saddle River, New
1 Jersey: Prentice Hall.
8. Si, J., and Tang, R. 1999. Trained Neural Network
0
Play Chess Endgames. In the Proceedings of the
0 1 2 3 4 5 6 7
International Joint Conference on Neural Net-
works (IJCNN ‘99), 3730-3733. Institute of Elec-
trical and Electronics Engineers, Inc.
Figure 14: Number of Fuzzy vs Non-Fuzzy Patterns
9. Stilman, B. 1994. A Formal Model for Heuristic
The fuzzy patterns are just one part of a larger search Search. In the Proceedings of the 22nd Annual
algorithm (Coffman-Wolph and Kountanis 2013a). The ACM Computer Science Conference, 380-389.
patterns and their fuzzy counterparts are used to determine New York, New York: Association for Computing
the possible moves for each chess piece. By representing Machinery.
several related moves as a single entity, the fuzzy patterns 10. Stilman, B. 2000. Lingustic Geometry: From
have a much smaller branching factor and, thus, a signifi- Search to Construction, Norwell, Massachusetts:
cantly smaller search tree. Specifically using the values Kluwer Academic Publishers.
calculated in the results section and weighting for the 11. Wang, J., Dong, L., Gao, X., Xu, C., Wang, F.,
number of each chess piece, the search tree for a chess and Zhang, C. 2009. The Research and Develop-
game would be cut at least in half. ment of Super-Master-Like Chess Playing Robot.
In the Proceedings of the Chinese Control and De-
Acknowledgments cision Conference (CCDC ’09), 1332-1335. Insti-
tute of Electrical and Electronics Engineers, Inc.
The authors would like to thank Dr. Ala Al-Fuqaha for his 12. Yen, J., and Langari, R. 1998. Fuzzy Logic Intel-
careful review and helpful suggestions that were incorpo- ligence, Control, and Information. Upper Saddle
rated into this paper. The authors would like to thank the River, New Jersey: Pearson Education.
reviewers for their suggestions and comments.
13. Zadeh, L.A. 1965. Fuzzy Sets. Information and
Control 8: 338-353.
References
1. Coffman-Wolph, S. and Kountanis, D. 2013.
Fuzzy Process Particle Swarm Optimization. In