Abstract:
Artificial intelligence is the brain behind solving the intelligent games like
chess, lines of action, Chinese chess and many other perfection information
board games. This paper deals with artificial intelligence techniques like searching
and heuristics for the game Lines of Action (LOA). The LOA is a two player game
here coins are moved for a particular cluster arrangement which decides the
winning in the game. The general
algorithm of LOA is much similar in comparison to Othello, Chinese chess few
more board games. The AI techniques for such board games are much sophisticated
in nature and the space complexity here is solved by the tree searching and
heuristics.
Keywords: Lines of Action, Artificial
Intelligence, tree searching,
heuristics.
I.
INTRODUCTION
A line of Action (LOA) is a
two-player connection game in which each player attempts to connect all of
his/her pieces. It is played on a (8x8 grid) chess board with each player
starting with 12 pieces, which to a large amount of possible game states. The solution
to the problem is adapting AI techniques which would solve the game problem.
There are huge collection of game
based tree searching techniques and the heuristics available for the game
development. The choice of tree searching techniques will result in affecting
or efficient space complexity where as the heuristics are responsible for the
game impact and the intelligent move in the game for winning.
In this paper we discuss the
techniques that will allow playing LOA efficiently. The intelligent algorithm
here uses a depth searching technique and the combination of central and quad
heuristics for the efficiency of the game as explained by Winands (2001).
It is considered that Mona and
YL’s (2002) have acquired some success in working the Winand’s theory and
techniques. The discussed techniques are unlikely to be in competition with
others but we try to bring an idea which might be a basic step for research in
future with more sophisticated modifications.
The remaining paper is divided into
following sections: section II is about the literature review, evolution and
history about the LOA. Section III discusses the methods and the techniques.
Section IV is the conclusion to the discussion considering few future
enhancement points.
II.
LITERATURE
REVIEW
Background information which aids
in understanding the problem of discussing the necessary techniques for playing
this game intelligently is provided by this section and offers a Lines of
Action history including information about the game and how it’s played. A
brief discussion about relevant work is also presented with the discussion on
search tree and closing with the comparison of central and quad heuristics.
A. History
A line of Action was created by
Claude Soucie and first publicized in 1969 by Sid Sackson in his book A Gamut of
Games. However, not until the 1990s did its popularity started increasing. In
1997 the first Mind Sports Olympiad was held by the Mind Sports Organization in
London’s Royal Festival Hall which included the Lines of Action world
championship and continues to host the event annually. With 3 computer
contestants the 2000 series of Lines of Action was included in the 5th Computer
Olympiad. A line of Action also continues to be included in this annual event.
B. The
Game
Lines of Action belongs to the
category of zero-sum game which means that losses and gains between opponents
are exactly balanced where there is no hiding of information whatsoever between
the opponents. The games are played on
an 8x8 grid which is similar to a standard chessboard. The game begins 24
pieces divided into 12 black and 12 white equally controlled by 2 players.
There are some rules illustrated
below:
·
Each
12 black coins are set up at top of the board followed by another 6 in the
bottom row while white coins are set up on the left side of board with 6 at top
and 6 in the bottom row. The initial setup arrangement is shown in Fig.
·
Turns
are alternated between players with black having the first move.
·
Coins
can move horizontally, obliquely, or vertically.
·
On
a particular line, the total number of pieces is equal to the number of spaces
it can move along that line (these are the Lines of Action). Fig shows possible
moves along the board. Fig.
·
Same
color coins can jump over coins.
·
Capturing
a coin is possible by directly landing on them but jumping over opponent pieces
is not possible.
·
By
connecting all his/her coins vertically, horizontally, and/or oblique into one
contiguous unit a player can accomplish a win as shown in Fig.
·
In
case of a connected unit established between players, the player having moved
wins.
·
The
player loses if he is out of moves or cannot move.
Fig: Starting Position
Fig: Possible Position
Fig: Winning Situation
C. Relevant
Work
In 2000 Winands submitted a
thesis on LOA the most dedicated and prominent scientist to work exclusively on
LOA. In his thesis he has enlighten the detail techniques that give efficient
solution of the game of LOA.
D. Comparison
As mentioned previously e discuss
here about the depth-limit search for the indentifying the best possible moves.
This is very clear that AI is not only bothered about the current move but it
is also conserved about the future moves and the effect of current move on
future move which eventually will decide the winning of the game. The simplest
techniques are built in consideration with current move and do not care about
the future moves. The depth-limit searching technique and the quad heuristics
are the best considered techniques for efficient game solution.
III.
METHODS
AND TECHNIQUES
A. Game
Tree Searching
The
depth search is most commonly considered for large tree which has to be
examined in LOA that is, the initial branch is recursively expanded to an
immediate next successful node of the current node till the leaf node is
reached. As search process progresses at initial levels remaining branches are
later considered. A modified version of
this technique is commonly used which is called iterative-deepening search
which is a depth search with a depth limit where tree is completely searched up
to the given depth limit. The limit increases and new search is started if the
search is completed. Hence search process is comprised of several search trees
with increasing depth. Iterative deepening search may seem waste as so many
nodes are expanded multiple times. But the overhead of this multiple expansion
is rather small. To make this concrete for LOA, for b = 30 and d =
4, the number of nodes expanded in a depth search is:
The numbers are total expansions
and are iterative
The overhead is about 3.4 %. The
higher the branching factor the lower will be the overhead. We see that the
branching factor of LOA stays high during the game, so we have a little bit of
overhead. But what is the advantage of iterative deepening?
It significantly helps in
controlling time that is spent for a move decision as it is hard to predict
search times for a fixed depth search, because these differ significantly for
specific positions, which is solved by iterative deepening. It is possible to
produce a best move after iterations or during iteration by stopping the
search.
B. Heuristics
In 99% of the cases heuristic can
be detected that the game is definitely not finished and solution lies in the
use of bits.
1) Central
Heuristics
Central Heuristics assign a close
and greater value to the coin. It is considered that the center of the board is
the best place for arranging the coins with intelligent moves. The centre of
the board has the average less distance to all the coins on the board. The
central heuristics have assigned values to each block on the board as shown in
the figure.
Fig: Assigned values on board
Based on these weights a value
could be calculated which decides the position of the coin on the board and
denoted which coin is close enough to the center of the board. This calculation
is performed by the addition of the values on which the player’s coin is
present. The image below shows the example of calculated value.
Fig: Centralized Heuristic with
value = 15
Fig: Central Heuristics with
value = 10
The central heuristics works this
way.
2) Quad
Heuristics
The first quad heuristics was
given by Winands (2001). This generally gives the value of the joint connection
of the coins for one player. Here the board is expected to be broken in 81
pieces with 2x2 blocks each and these blocks are called quads. These are quads
are given a weighted value considering the number of coins present in each
quad. As shown below in the images.
Fig: Quad with 0 coins having Q =
0
Fig: Quad with 1 coin having Q =
¼
Fig: Quad with 2 coins having Q =
0
Fig: Quad with 3 coins having Q =
- ¼
Fig: Quad with 4 coins having Q =
0
Fig: Quad with 2 coins having Q =
- ½
This uses a weighted value for
the calculation of Euler Number which denotes the position of the coins as
advantage position. The higher the Euler Number means the higher non
connectivity of coins for a player. The example shows below.
Fig: Euler Number with White = 4
& Black = 3
Fig: Euler Number with White = 6
& Black = 7
Smaller the Euler number is the
greater the advantage for the player. The Euler number 3 is the advantage for
the player than the one with Euler number 5. Suppose the Euler number are
negative in nature like -3 and -5 in that case the quad heuristics would
suggest -3 as best advantage for the player and high chances of winning.
The AI winning strategy is to
combine both the heuristic techniques to find the weights and calculate the
value based on which the current and future move of the coin is dependent and
there is very minimum chance for the computer to lose the game.
Fig: Combined Heuristics, value =
14
Fig: Individual Contribution
Fig: Combined Heuristics, value =
-5
Fig: Individual Contribution
VI. CONCLUSION
The combination of quad and
central heuristics will limit the depth of the tree and there shall be no much
need for the implementation of whole tree and traverse all the nodes in the
tree for optimum searching. The combined technique will create a game tree with
a pre determined depth value and reduce the space and time complexity of the
game state execution.
REFERENCES
[1] S. Sackson,(1969)A Gamut of
Games Random House.
[2] Unknown author. (2011) Mind
Sports Olympiad [Online]. Retrieved 08 April 2013.Retrieved from: http://www.boardability.com/home.php
[3] M.Winands,(2000) Analysis and
Implementation of Lines of Action, Dept. Computer Science, Maastricht
University.
[4] S.B. Gray, (1971, Vol: 20(5),
Pp:551–561) Local properties of binary images in two dimensions. Computer Science
IEEE Transactions.
[5] Minsky M. (1968) Semantic
Information Processing. M.I.T. Press,USA.
[6] Minsky, M. et al (1988)
Perceptrons- An Introduction to Computational Geometry. M.I.T. Press,USA.
[7] M.H.M. Winands et al.,( 2001,
Vol: 24, Pp: 3-15) The Quad Heuristic in Lines of Action,ICGA
[8] Unknown author. (2002, Nov).
Mona and YL’s Lines of Action page [Online]. Retrieved 10 April 2013.
Available: http://webdocs.cs.ualberta.ca/ darse/LOA/
