Ideas for Othello Game Player (Deliverable 2)
• Improved Evaluation functions
variations to weighted difference function, though still static
evaluation functions that are conditioned on board
mobility – incorporate a factor that reflects the number
of move options available to a player (current mobility
is the number of legal moves available to a player;
potential mobility is number of blank squares next to
opponent piece)
edge stability – measure of likelihood that edge squares
can be flipped
Ideas for Othello Game Player (Deliverable 2)
• More efficient searching (Alpha Beta will tend to prune more
moves, when moves are ordered “best” to “worst” (which
can only be “guessed” at ahead of time). Thus, rather than
relying on default ordering, do
static reordering (e.g., order boards based on weights used by
the weighted-diff function, or some other static weighting)
dynamic reordering (e.g., order boards by evaluation
function score)
• Killer Moves – a (opponent) move in one line of play can be
effective (detrimental) in another line of play (e.g., if an
opponent can capture a corner on one line of play,
consider whether the opponent can capture the corner
in another line of play)
Ideas for Othello Game Player (Deliverable 2)
• Improved Memory Management
Rather than dynamically allocating boards, then “throwing
away”, reuse dynamically allocated boards and mitigate
garbage collection
• Anytime search and searching with time limits
• Iterative Deepening (Alpha Beta) pruning (for Othello, with
a average branching factor about 10, searching to level
N+1 will be about 10 times more expensive than N; collect
stats at N, and dynamically determine whether N+1 is
• Forward pruning – don’t search down paths that seem nonpromising
Ideas for Othello Game Player (Deliverable 2)
• Aspiration search or iterative “broadening”
Instead of starting the search with alpha and beta values
of losing(-1) and winning(+1) values initially,
carefully choose a window (e.g., based on the
current board’s value), such as 0-100, and expand
the window only as needed
• Think ahead – keep searching while opponent is moving, based
on one or more guesses of what the opponent will do
• Hash table of book moves, particularly of opening game
(where “the book” can be initialized by playing the program
against itself
Ideas for Othello Game Player (Deliverable 2)
• Different strategy over course of game (e.g., shallower search
in midgame, all out search later)
• Metareasoning – at each point (each search step, is it better
to stop now or keep searching) – manage the clock
“dynamically” rather than “statically (e.g., assume same
time limit per move) – always ask, is search further
cost effective. Another way to think about it – consider
ceasing the search as a “possible move”
• Learning – about opponent and about “one’s self” (e.g., which
evaluation function is best)

similar documents