Flipper
=========
Flipper is an Othello game that I wrote to play around
with the minimax algorithm for searching game trees.
To play a game against the computer, select New Game from
the File menu. The human player goes first, playing black.
To make the computer go first and play black instead, select
Swap Sides from the Options menu. To make a move, click on
the square where you want your piece. If no moves are
possible, click in the Pass box to the right of the board.
The game can be changed between '1 Player' ( against the
computer), '2 Player', and 'Set Up Board' at any time. The
computer can be forced to play against itself by selecting
Swap Sides after every move.
'1 Player' is for playing against the computer. Selecting
Swap Sides will change colours and scores with the computer
at any time. The parameters for selecting computer moves can
be set by selecting 'Set Search' or 'Set Evaluation'
(described below). Pressing the ESC key when the computer is
searching for a move will force it to take the best one it
has found so far.
'2 Player' is for playing a game between 2 human players.
Swap Sides is disabled in this mode.
'Set Up Board' is for placing and changing pieces on the
board. Clicking on a square will place a piece of the
current player's colour there. To place a piece of the other
colour, select Swap Sides. Pressing the ESC key will clear
the board.
The computer finds moves by using the minimax algorithm.
Roughly, the algorithm generates a list of possible moves,
then considers possible countermoves to each of these, then
possible moves after each countermove, and so on. This
builds up a tree structure with each node being a board
position and moves being branches to the next lower level.
To decide which move to take, the board positions at the
lowest level of the tree are evaluated by a board position
evaluation function that determines how likely a given
position is to lead to a win. These evaluations are passed
up to the previous level where they are used to evaluate the
move at that level. At levels where the computer is moving,
the maximum is used. When the opponent is moving, the
minimum is used. When the top of the tree is reached, the
computer knows which move to make.
'Set Search' brings up a dialog box that lets you enter
the search depth and width. The search depth is the number
of levels of the game tree to generate (number of moves to
look ahead). The search width limits the branching factor of
the tree. It sets the maximum number of new moves that are
generated at each node. Larger depths and widths make the
computer play a better game, but it takes more time for each
move.
'Set Evaluation' brings up a dialog box that lets you
change the parameters for the board evaluation function. The
parameters that can be changed are: how much to add for each
computer's piece, how much to add for each computer's piece
on an edge, how much to add for each computer's piece in a
corner, how much to subtract for each opponent's piece, how
much to subtract for each computer's piece one away from an
edge, and how much to subtract for each computer's piece one
away from a corner. This can be used to fine tune the way
the computer plays.
Greg Lobe