CHINESE CHECKERS – IN
THE LIGHT OF AI
Computer Game Playing
Under the Guidance of Prof.
Pushpak Bhattacharyya
Presented by:
Anwesha Das, Prachi Garg
and Asmita Sharma
1
OUTLINE
1. BACKGROUND
2. HISTORY OF CHINESE CHECKERS
3. INTRODUCTION - GAME
DESCRIPTION
4. AI – PERSPECTIVE
1. MINIMAX ALGORITHM
2. ALPHA – BETA PRUNING
5. HEURISTICS
7. CONCLUSION
8. REFERENCES
Computer Games &
AI
Game playing was one of the earliest researched
AI problems since
games seem to require intelligence (heuristics)
state of games are easy to represent
only a restricted number of actions are allowed
and outcomes are defined by precise rules
It has been studied for a long time
Babbage (tic-tac-toe)
Turing (chess)
Sole Motive is to get a game solved, meaning
that the entire game tree can be built and
outcome of the game can be determined even
before the game is started.
3
Class of Chinese
Checkers
It falls under the category of zero-sum
discrete finite
deterministic games of perfect
information.
Zero-sum: In the outcome of any game, Player
A’s gain
equals player B’s loss.
Discrete: All game states and decisions are
discrete values.
Finite: Only a finite number of states and
decisions.
Deterministic: No chance (no die rolls).
Perfect information: Both players can see 4the
History of Chinese
Checkers
Chinese checker was invented in Germany
under the name of “stern-halma”.
It is a variation of “Halma” which is Greek
for “Jump”, invented by an American
professor from Boston, Dr. George
Howard Monks (1853-1933) between
1883 and 1884
5
History of Chinese
Checkers
Developed by Chinook
Used alpha-beta search
Used a pre computed perfect end
game by means of a database
In 1992 Chinook won the US Open
….. And challenged for the World
Championship
6
History of Chinese
Checkers
Dr Marion Tinsley had been the world
champion for over 40 years
… only losing three games in all that time
Against Chinook he suffered his fourth and
fifth defeat
….. But ultimately won 21.5 to 18.5
In August 1994 there was a re-match but
Marion Tinsley withdrew for health reasons
Chinook became the official world
champion
7
History of Chinese
Checkers
Chinook did not use any learning
mechanism.
Kumar in 2000- Learning was done
using a neural network with the
synapses being changed by an
evolutionary strategy.
The best program beat a commercial
application 6-0
The program was presented at CEC
2000 (San Diego) and remain
undefeated
8
Components of the
The gameGame
can be defined as a kind of
search problem
problem with the following
with the following
components :
1. A finite set of states.
2. The initial state: board position, indication
of whose move it is
3. A set of operators: define the legal moves
that a player can make
4. A terminal test: determines when the
game is over (terminal states)
5. A utility (payoff) function: gives a numeric
9
Introduction – How to
play?
2 to 6 players can play the game ,having 10
same-colored marbles
At the start - player's marbles are in the ten
holes of the star point that has the same color
as his marbles
Goal - move all marbles of one color from
starting point to the star point on the opposite
side of the board
No game pieces are removed from the board.
Introduction - Constraints
marble can move by rolling to a hole next to it
by jumping over one marble, of any color, to a
free hole, along the lines connecting the holes in
a hexagonal pattern
several jumps in a row, but only one roll
cannot both roll the marble and jump
with it at the same turn
Minimax
1944 - John von Neumann outlined a
search method (Minimax) that
maximize your position whilst
minimizing your opponent’s
Minimax searches state-space using the
following assumptions
– your opponent is ‘as clever’ as you
– if your opponent can make things worse for
you, they will take that move
– your opponent won’t make mistake
12
Minimax - Example
1 A
MAX
1 B -3 C
MIN
4 D 1 E 2 F -3 G
MAX
H I J K L M N O
4 -5 -5 1 -7 2 -3 -8
= agent = opponent
13
Minimax to a Fixed Ply-
Depth
Usually not possible to expand a game to
end-game status
have to choose a ply-depth that is
achievable with reasonable time and
resources
absolute ‘win-lose’ values become
heuristic scores
heuristics are devised according to
knowledge of the game
14
Minimax - Example
1 A 8
0
MAX
14 B -3 8 C
0 -3
MIN
43 D 10 E 24 F -3-3 G
MAX
H I J K L M N O
4 -5 -5 1 -7 2 -3 -8
= agent = opponent
15
Alpha-Beta Pruning
Fixed-depth Minimax searches entire
space down to a certain level, in a
breadth-first fashion. Then backs values
up. Some of this is wasteful search
Alpha-Beta pruning identifies paths which
need not be explored any further
16
Alpha-Beta Pruning
Traverse the search tree in depth-first order
At each MAX node n, alpha(n) = maximum
value found so far
At each MIN node n, beta(n) = minimum value
found so far
Note: The alpha values start at -infinity and only
increase, while beta values start at +infinity and only
decrease.
Beta cutoff: Given a MAX node n, cut off the
search below n (i.e., don’t generate or examine
any more of n’s children) if alpha(n) >= beta(i)
for some MIN node ancestor i of n.
Alpha cutoff: stop searching below MIN node n 17
Alpha-beta Pruning
A
MAX
<=6 B C
MIN
6 D >=8 E
MAX
H I J K
6 5 8
= agent = opponent
18
Alpha-beta Pruning
>=6 A
MAX
6 B <=2 C
MIN
6 D >=8 E 2 F G
MAX
H I J K L M
6 5 8 2 1
= agent = opponent
19
Alpha-beta Pruning
>=6 A
MAX
6 B 2 C
MIN
6 D >=8 E 2 F G
MAX
H I J K L M
6 5 8 2 1
= agent = opponent
20
Alpha-beta Pruning
6 A
MAX
6 B 2 C alpha
cutoff
MIN
6 D >=8 E beta 2 F G
cutoff
MAX
H I J K L M
6 5 8 2 1
= agent = opponent
21
We use α-β pruning, which can optimize move. Here
white balls may take 20 & black 22 moves - α-β pruning
chooses the better move.
Heuristics
Chinese Checker, possible heuristics :-
Random- the computer makes a move randomly
without taking into consideration the current board
configuration
Caveat - the random player may not leave its
triangle at all -denying the chance to the opponent
to occupy its winning triangle
Vertical Displacement(VD)- generates all moves with
minimax algorithm & sums up the vertical distance for its
pieces and adds them. Same done for the opponent.
Static Evaluation Function=totalself - totalopponent
Vertical / Horizontal Displacement (HD)- considers
the horizontal pieces as well in deciding the next move.
It is best to play in the middle of the board.
Formula is W.F*VD+HD where W.F=weight factor which
decides how much of importance is to be given to keep
23
the pieces in the middle compared to jumping vertically
Heuristics
Vertical/Horizontal Displacement with
split – move the pieces to the edges of the
destination triangle once they have moved in
Create space for others to come in
Back piece moving strategy – give more
weightage to the moves where the back pieces
move forward than the front pieces
Pieces move in clusters.
Concept of disuse wt.
Optimization
1. Consider those nodes of minimax algorithm
which show some progress
o Speed improves significantly
2. Shortest depth first in case of a win
o Path which takes to the goal faster
3. Expand nodes with maximum value to
improve α β pruning
4. Sort to increase the gain of α β pruning
Tradeoff is O(n2 ) sorting algorithm versus O(n)
best move.
Horizon Effect
When inevitable bad moves are put off
beyond the cutoff on the depth of lookahead,
e.g. stalling moves by pushing an unfavorable
outcome “over the search horizon” to a place
where it cannot be detected
The unavoidable damaging move is thus not
dealt with
Use of singular extensions where one “clearly
better” move is searched beyond the normal
depth limit without incurring more cost
26
Quiescence Search
Always search to limited depth - blind to states
just beyond this boundary
Might chose a path on the basis that it
terminates in a good heuristic … but next
move could be catastrophic
Overcome by quiescence search – positions in
which favourable captures are avoided by
extending search depth to a quiescent
position.
27
Chinese
Checker
How to efficiently move to goal?
Depicting the board
Back piece moving strategy
configuration of a 2 player
– moving in clusters
game.
Make intelligent moves
Preference given to the
Although less powerful ,
backward, edge pieces
push the backends
among the rest
No pieces to leave behind-
Horizon effect
Best to play in the middle,
All possible moves from a particular piece
make the best move
Identify the correct
move
Conclusion
Board Game – a wonderful tool to reinforce
learning
Study done on the Chinese Checker
distance, regular polygons on checker plane,
its variations of the Pythagorean theorem.
Both minimax and alpha-beta pruning
assume perfect play from the opposition.
Increase in processing power will not always
make exhaustive search of game tree
possible – need pruning techniques to
increase the search depth with the same
computing resources
32
References
Reading material from
whitneybabcockmcconnell.com
of CMU.
http://hem.passagen.se/baolan/r
elease/china.pdf
- Master’s thesis by Paula
Ulfhake , Lund University
http://en.wikipedia.org/wiki/Chin
ese_checkers
http://www.cs.northwestern.edu/
33
THANK YOU
