Transcript Cilk Pousse

Cilk Pousse
James Process
CS534
Overview
•
•
•
•
•
Introduction to Pousse
Searching
Evaluation Function
Move Ordering
Conclusion
Introduction
1998 ICFP Functional Programming Contest
Write and AI system to play "Pousse"
May be written in any language
Teams had 72 hours to complete the
programming
Almost 50 programs were entered into the
content
Cilk Pousse written by Supercomputing
Technologies Research Group of the MIT LCS
won first place
•
•
•
•
•
Introduction - Pousse
What is Pousse?
•
•
•
•
•
2 player game
tic-tac-toe variant played on n-by-n board, typically 4by-4
players place either X or O, X places first
A marker is placed on the board by sliding it in from
the side(left, right, top, or bottom)
o Results in 4*n possible moves on a given turn
If a marker is inserted where a maker is already
placed, all markers on that row/column are pushed
down one space. If the row/column is full, the last
marker is pushed off the game board and removed
Introduction - Winning
•
Similar to tic-tac-toe you are trying to
create "straights" to win
o
o
•
•
A "straight" is a full row or column of your marker
Making a move that causes the configuration to
contain more straights of your type than your
opponents results in a win
If you make a move that creates a
configuration that is a repeat of a previous
configuration you lose
o
No looping
There are no ties/draws
Searching
•
Alpha-Beta minimax Searching
o
•
We can prune of parts of the tree and save search
time if we know there is already a better move
Iterative deepening
o
For each iteration we start from the best possible
move of the previous iteration. i.e. the depth-9
search places the best move into a hash table
which provides a starting point for the depth-10
search
Cilk and Parallel Searching
•
•
•
Cilk is a C-based language for
multithreaded programming, did a lot of
the work of multithreading/scheduling
Took the approach that either a single child
would be searched or all children would be
(optimal game tree)
Search first child
o Either return, or spawn off all other children to be
searched in parallel
Evaluation Function
•
•
•
•
Piece count
o Each piece is valued at 4
Centrality
o - Each piece gets a bonus equal to the Manhattan distance
from the piece to the nearest corner
Frank-squared
o Derived from file/rank
o Valued at k^2 for each frank having k of your pieces
Connectivity
o Originally was defined as 2 points per piece for adjacency and
1 point for each diagonal
o Was not used in final version
Evaluation Function Cont.
• Sum this for our pieces and subtract
opponents sum at each state
• Optimized by incrementally updating score
for each position rather than computing
from scratch
Move Ordering
Two heuristics used to improve move ordering
First keep a hash table with the best move
information from the previous search
Second keep a table of countermoves.
•
•
o
o
•
previously when the opponent made move x, we
decided move y was a good choice
In the case of Cilk Pousse they saved the last 2
good countermoves for each move
If the best move hash table has a move
start there, else go to the countermoves
table
Conclusion
Even relatively simple problems require a
large amount of thought and optimization to
solve. All of the following were considered
o
o
o
o
o
o
o
Effective search algorithm
Good use of pruning
Iterative Depth
Keeping track of best states
Tweaking evaluation function
Parallelism
…
• No single piece is the key to a perfect Agent
References
Definition of the game Pousse
http://docs.racket-lang.org/games/pousse.html
MIT Cilk Pousse
http://people.csail.mit.edu/pousse/