CMS E-Mail for Dummies



A Heuristic Approach to Game Playing:

The Game of Othello

by

Keith R. Wannamaker

Submitted in Partial Fulfillment

of the Requirements for

Graduation with Honors from the

South Carolina Honors College

May 1998

Approved:

________________________________________________________________

Dr. Marco Valtorta

Director of Thesis

________________________________________________________________

Dr. John Rose

Second Reader

________________________________________________________________

Peter Sederberg, James Stiver or Douglas Williams

for the South Carolina Honors College

T a b l e O f C o n t e n t s

P r o j e c t S u m m a r y 1

T H E G A M E O F O T H E L L O 2

HISTORY 2

RULES 2

• OBJECT OF THE GAME 2

• A Minute To Learn 2

• Othello Rules 3

O t h e l l o G a m e T r e e 5

S E A R C H I N G T H E G A M E T R E E 6

BACKGROUND TO HEURISTIC EVALUATION 6

THE HEURISTIC FUNCTION 7

ALPHA-BETA PRUNING 8

DEPTH CUT-OFF 9

TIME RESTRICTIONS 9

U S I N G T H E P R O G R A M 10

PROGRAM DESCRIPTION 10

PROGRAM WINDOWS 10

• GAME BOARD 10

• Search Tree Results 10

• Game Information 11

Playing a game 12

S T A T I S T I C S 13

C O N C L U S I O N 15

S O U R C E C O D E 16

OTHELLO.C 17

BOARD.C 20

GAME.C 23

CM.C 24

ENGINE.C 26

MOVELIST.C 31

OTHELLO.H 32

B I B L I O G R A P H Y 34

P R O J E C T S U M M A R Y

THE GOAL OF THIS PROJECT WAS THE CREATION OF A COMPUTER PROGRAM TO PLAY INTELLIGENTLY THE BOARD GAME OTHELLO WITH A HUMAN OPPONENT. THE PROGRAM ALLOWED EXPLORATION OF ARTIFICIAL INTELLIGENCE TECHNIQUES SUCH AS HEURISTIC EVALUATION AND ALPHA-BETA TREE PRUNING, AS WELL AS GRAPHICS PROGRAMMING IN THE WINDOWS ENVIRONMENT.

Every game can be represented in a tree graph[1]. A complete game tree would contain all combinations of moves and its leaves would represent all endgame scenarios. A computer can play Chess, Checkers, Othello, Go, or any other similar game by looking ahead in the appropriate game tree for the best moves. Unfortunately, the size of such a tree grows exponentially, so computers can not entirely enumerate most complete game trees, including the tree of Othello. Heuristic evaluation is a method for selecting a move even when time and resources prevent a computer from searching the entire tree.

Many other programs have been written to play the game of Othello; in fact, the Internet is proliferated with Othello Java applets. The primary reason that computer programs are so successful playing Othello is that human players, even very experienced users, can not visualize the dramatic board changes possible more than just a few moves ahead. Computers do not have such a restriction and regularly search more than 10 moves ahead in the game. Clearly, they have the advantage.

OTHELLO is a Windows-based program that incorporates heuristic evaluation and another technique, known as alpha-beta tree pruning, to play interactively the game of Othello with a human opponent. It allows the user to play either color (black or white), examine the statistics that the program collects about the board, and also at any time prevent the program from playing its preferred move.

The program gathers and saves statistics about each game it plays. I have distributed the program to a number of users and compiled the resulting statistics files to get an indication of how well OTHELLO plays. As the results demonstrate, OTHELLO proved to be a challenging, competent Othello opponent.

T h e G a m e O f O t h e l l o

HISTORY

No one is certain of the origin of the game Othello. In 1880, Lewis Waterman, of London, England marketed a game with similar rules under the name “Reversi”. In 1888, Walter Peel, also of London, wrote the text Handbook of Reversi. Pressman Toy Corporation currently markets the game under the name of Othello, whose current rules were invented by Goro Hasegawa in 1971. The primary difference between Othello and Reversi is that Reversi starts with a blank board, while Othello has a predefined starting position and first player. It is thought that the game’s revised name came from the Shakespeare play known for its sudden and dramatic plot twists.

Rules

The following is a direct transcription of the rules included in the Pressman Toy Corporation version of Othello, marketed in North America.

Object of the Game

The object of the game is to have the majority of your color discs on the board at the end of the game

A Minute To Learn

Each player takes 32 discs and chooses one

color to use throughout the game.

Black places two black discs and White places

two white discs as shown in Figure 1. The game

always begins with this setup.

A move consists of "outflanking" your opponent's disc(s), then flipping the outflanked disc(s) to your color.

To outflank means to place a disc on the board so that your opponent's row (or rows) of disc(s) is bordered at each end by a disc of your color. (A "row" may be made up of one or more discs).

Here's one example: White disc A was already in place on the board. The placement of white disc B outflanks the row of three black discs.

White flips the outflanked discs and now the row looks like this:

Othello Rules

1) Black always moves first.

2) If on your turn you cannot outflank and flip at least one opposing disc, your turn is forfeited and your opponent moves again. However, if a move is available to you, you may not forfeit your turn.

3) A disc may outflank any number of discs in one or more rows in any number of directions at the same time - horizontally, vertically or diagonally. (A row is defined as one or more discs in a continuous straight line ). See Figures 2 and 3.

4) You may not skip over your own color disc to outflank an opposing disc. (See Figure 4).

5) Discs may only be outflanked as a direct result of a move and must fall in the direct line of the disc placed down. (See Figure 5 and 6).

6) All discs outflanked in any one move must be flipped, even if it is to the player's advantage not to flip them at all.

7) A player who flips a disc which should not have been turned may correct the mistake as long as the opponent has not made a subsequent move. If the opponent has already moved, it is too late to change and the disc(s) remain as is.

8) Once a disc is placed on a square, it can never be moved to another square later in the game.

9) If a player runs out of discs, but still has an opportunity to outflank an opposing disc on his or her turn, the opponent must give the player a disc to use. (This can happen as many times as the player needs and can use a disc).

10) When it is no longer possible for either player to move, the game is over. Discs are counted and the player with the majority of his or her color discs on the board is the winner.

NOTE: It is possible for a game to end before all 64 squares are filled.

O t h e l l o G a m e T r e e

THE GAME TREE FOR OTHELLO IS CERTAINLY NON-TRIVIAL, ALTHOUGH IT IS NOT AS LARGE AS THE GAME TREE FOR CHESS. ASSUMING THAT AN AVERAGE GAME HAS 60 MOVES AND THAT MOVES HAVE AN AVERAGE BRANCHING FACTOR OF 7, THE INITIAL UPPER BOUND ON THE GAME TREE SIZE IS 1050. HOWEVER, DUE TO SYMMETRY AND THE FACT THAT MANY GAMES DO NOT TAKE 60 MOVES TO PLAY, ONE CAN ASSUME THE TREE SIZE IS SMALLER. INDEED, THERE ARE ONLY 1029 COMBINATIONS OF DISCS ON AN OTHELLO BOARD, MANY OF WHICH ARE NOT LEGAL. COMPARE THE CHESS TREE SIZE, WHICH HERTZOG ESTIMATES AT 10120.

Table 1 provides the exact count of nodes in the first 10 plies of Othello, obtained by enumeration.

|Level |Nodes |Avgerage Branching Factor |

|1 |4 |3 |

|2 |12 |4.6 |

|3 |56 |4.3 |

|4 |244 |5.7 |

|5 |1,396 |5.8 |

|6 |8,200 |6.7 |

|7 |55,092 |7.1 |

|8 |390,216 |7.2 |

|9 |3,005,264 |8.2 |

|10 |24,571,056 | |

Table 1

The search tree is actually comprised of four smaller symmetric trees, whose roots are joined at the first level. While I can not prove this by exhaustively comparing the subtrees, the hypothesis held true through all ten levels examined. The symmetry of the tree is intuitive and represents the symmetry of the Othello board after different opening moves.

S e a r c h i n g T h e G a m e T r e e

BACKGROUND TO HEURISTIC EVALUATION

Given an enormous tree to represent every possible move sequence in a game, the challenge of searching the tree to determine the best possible move faces the computer program every turn. Until the final few moves of the game, it is clearly impossible to search the entire tree. The program must make decisions based only on portions of the tree. To accomplish this, one first creates a heuristic function to “score” a given arrangement of pieces on the board. The score is an estimate of the program’s chances of winning, given that particular board arrangement.

Associating each node of the game tree with a heuristic score gives the program a metric to evaluate its position at an arbitrary depth. If the program only has time to evaluate ten plies, or moves of the game, it can still search for the highest score in the leaves of that 10-ply section of the game tree.

In fact, the program’s primary goal in life should be twofold: 1) Evaluate as many nodes as possible in the time allowed, and 2) choose the move that maximizes its score for the nodes examined.

The programmer accomplishes the first goal not only by writing a small, quick evaluation function but also by minimizing the number of nodes that need to be evaluated in the first place. One of the most popular algorithms for trimming unnecessary nodes from a tree is Alpha-Beta Pruning, implemented in OTHELLO. By knowing that the best moves do not lie on a particular branch of the tree, Alpha-Beta pruning can “mark” the branch and prevent the program from wasting time by evaluating bad moves.

Combining a heuristic evaluation function with Alpha-Beta Pruning allows the program to make intelligent move decisions after examining only a small portion of the actual game tree.

The Heuristic Function

In writing the heuristic function, speed and accuracy were paramount. Unfortunately, the relationship between an evaluated score and the actual “goodness” of a board arrangement is clearly non-linear. Heuristic function designers must resort to much trial and error, not only concerning what conditions to test, but also with the weight a position has on the final score.

Below are the six conditions and their respective weights that I arrived at after many hours of Othello-playing.

1) Board Corner. Add 200 points for each of the four corner that our pieces occupy. Subtract 200 points for each corner that our opponent occupies. Add 100 points for every corner that the board allows us to move on the next turn. Subtract 400 points for every corner that the board allows the opponent to move to on the next turn. If a corner is empty, add 80 points for each opponent’s piece in the adjacent squares; subtract 80 points for each of our pieces in the adjacent squares.

2) Outer Edge. Add 75 points for each of our pieces on an outside edge. Subtract 75 points for every opponent’s piece on an outside edge.

3) Inner Circle. Add 40 points for every opponent’s piece falling in the shaded area, as long as all three adjacent outside edge squares are empty. Subtract 40 points for each of our pieces meeting the same criteria.

4) Opening Corner. Add 12 points for each of our pieces in a corner of the opening 4 x 4 board, subtract 12 points for every opponent’s piece in the same locations.

5) Inner Edge. Examine every 2 x 2 square on the board. For each square, if the square contains exactly two pieces of the same color, and the pieces are not positioned diagonally, examine the color. If the pieces belong to the opponent, add one point; otherwise subtract one point.

6) Piece Tally. Add one point for every one of our pieces; subtract one point for every one of the opponent’s pieces.

If the heuristic value computed is zero, the function will randomly assign the value either –1 or 1.

Alpha-Beta Pruning

Alpha-Beta Pruning is a complicated algorithm to accomplish a simple and intuitive task. The underlying assumptions are that heuristic scores are available to both players and that if a player is trying to maximize his score, his opponent will always play in a manner to minimize that score. Thus, every level of the game tree can be assigned an alternating designation of a “min” level or a “max” level. The player’s level is a “max” level because he will propagate the maximum score possible for that level up to the parent in the preceding level. Likewise, the preceding level is a “min” level because his opponent will propagate the minimum score possible for that level up to its parent.

Alpha-Beta Pruning will throw away parts of a tree that our opponent will not allow us to reach. In other words, we should not waste time evaluating good moves that our opponent will most likely never let us reach.

The flaw in this approach is that our opponent (human) can not play perfectly (especially based on our arbitrary heuristic!) and will not always minimize our score. Nevertheless, pruning the search tree in this manner allows a dramatic increase in the search size possible, given a fixed amount of time.

Depth Cut-Off

In order to maximize the use of its time on its move, OTHELLO descends once on a random path from the current board arrangement to an endgame, averaging the branching factors along the way. A branching factor represents the number of moves possible for a given board position and, thus, how quickly the game tree expands. With an estimated average branching factor, the program computes a cut-off level, or a level on which it will terminate searches. This allows the program to search deeper at the end of the game when the branching factor is smaller. The depth cut-off is calculated by:

The equations can be derived from this formula which estimates search time:

When OTHELLO starts, it calibrates the search speed of the host machine by timing 1000 iterations of the heuristic function on an initial board configuration. From the timing results, it calculates and displays the time required to search one node.

Time Restrictions

There is an automatic 12 second per move time limit imposed on the program. This prevents the program from getting off on a tangent search and never producing a move. The 12 seconds are divided up between all potential legal moves, so the program may only have one or two seconds to examine the search space for a particular move.

U s i n g T h e P r o g r a m

PROGRAM DESCRIPTION

OTHELLO is a Windows program that allows a human to play against the heuristic evaluation engine described in this document. The program will run under Windows 95 and Windows NT on machines that meet the minimum operating system requirements.

Only one file is needed in the installation, OTHELLO.EXE.

Program Windows

When the program is started, it will display three windows.

Game Board

This 8 x 8 board represents the current status of the game. The title bar indicates the ply (number of moves) of the current game (if one has been started), whose turn it is, and what color they are playing. There are two menu items for this window:

← Game:

New… Summons a dialog box for the user to pick their preferred color. After selecting OK, the board is reset, and play begins immediately.

Reset Resets the board and begins a new game with the color that the user had previously chosen.

Exit Exits the program.

← Help:

About… Summons a dialog box to display program identification and version number.

Search Tree Results

When it is the program’s turn, this window contains all legal moves that the program may make, along with information about each move.

(6,6) V25567 S27528 (W 0:B 0:D 0) –1

This line indicates a move at location (6,6). Moves are notated in coordinate fashion, (x,y), with (1,1) being the upper-left corner of the game board. We also know that the program Visited (evaluated) 25,567 nodes, and Skipped at least 27,528 nodes due to Alpha-Beta pruning (see page 8). In addition, the program saw no wins for White or Black, or any Draws. The overall heuristic score for the move to (6,6) is –1.

Game Information

This window displays information gathered about the current level of the game. The number in the left column of each line indicates the level for which the information is applicable.

Three types of information are presented:

1) Estimated average branching factor and depth cutoff

30 avg BF 8.06= 5 cutoff

This example indicates that on level 30, the branching factor was estimated to be 8.06 (from this position to the end of the game, each player had, on average, a choice of 8 moves each turn). Given the time constraint of 12 seconds, OTHELLO estimated that it could search 5 plies (to level 35) before running out of time.

2) Completeness of search

32 1 /10 searched completely

This example indicates that, for level 32, OTHELLO searched to the depth cutoff on only one of the ten trees (there were ten possible moves for OTHELLO). The remaining searches were forced to terminate prematurely.

3) Piece tally

26 13W/18B

Each time after the user accepts OTHELLO’s move, a piece tally will be given. In this case, for level 26, white had 13 pieces, and black had 18.

Playing a game

First, the user should use the New… menu option to choose a color and begin a new game. Playing alternates between the user and the computer until the game is finished or terminated.

• User’s turn

The game board will highlight the user’s legal moves by bracketing the squares in his color. The user selects his move by clicking on the appropriate square. OTHELLO will flip the appropriate disks, and automatically begin its turn. The cursor will change into an hourglass to indicate the program’s activity.

• Computer’s turn

OTHELLO will present its findings when all move searches have reached the computed search cut-off, or 12 seconds have elapsed, whichever comes first. First, the Search Result window will be updated with the program’s possible legal moves, along with their score. Secondly, the Game Information window will display one line for each move indicating the depth cut-off used. Finally, the game board will have the program’s preferred move bracketed in its color.

The user can examine the other moves by clicking on the appropriate line in the Search Result box.

A program move is accepted by the user when any of these events occur:

1) The user clicks anywhere in the game board.

2) The user double-clicks a line in the Search Result box.

3) The user clicks the “Play Move” button in the Search Result box.

When this happens, OTHELLO will flip the appropriate disks, display a piece tally in the Game Information window, and return play control to the user.

At any time in the game, if either the user or OTHELLO does not have a legal move available, a message box will indicate the situation, and play will resume with the appropriate player.

When the game is over, a message box with piece tally information will appear and the game will stop.

S t a t i s t i c s

OTHELLO APPENDS GAME INFORMATION TO A FILE IN THE CURRENT WORKING DIRECTORY CALLED PLAYLOG.TXT. THE FILE CONTAINS NINE FIELDS:

|Description |Example Text |

|OTHELLO version |1.2 |

|Time of game completion |Thu Apr 02 08:48:05 1998 |

|Color OTHELLO played |B or W |

|Number of endgame white pieces |47 |

|Number of endgame black pieces |17 |

|Number of times user changed OTHELLO’s preferred move |0 to 30 |

|Total OTHELLO decision time, in seconds |254 |

|Total user decision time, in seconds |124 |

|Total number of moves in the game | nb )

strcat( buffer, "White wins!");

else

strcat( buffer, "Black wins!");

}

strcpy( buffer2, ctime( &now ) );

buffer2[ strlen( buffer2 ) - 1] = 0;

io = fopen( "playlog.txt", "a+" );

if( io != NULL ) {

fprintf( io, "2.2:%s\t%c\t%i\t%i\t%i\t%li\t%li\t%i\n", buffer2,

(User==WHITE) ? 'B' : 'W', nw, nb, numForcedMoves,

MyClock, UserClock, Level );

fclose( io );

}

MessageBox( hWnd, buffer, "Game Result", MB_OK );

ShowWhoseMove( hWnd );

}

cm.c

/*---------------------------------------------------------------------*

* Common functions for GUI and Engine - Keith Wannamaker, Spring 1998 *

*---------------------------------------------------------------------*/

#include

#include "othello.h"

extern board gb;

/*---------------------------------------------------------------------*

* Assuming there is a piece at x, y of color opponent(opp), *

* getflankset returns a flank_set containing the set of directions *

* of flanks that this piece would cause. *

*---------------------------------------------------------------------*/

flank_set getflankset( board b, int x, int y, color opp ) {

unsigned int i;

flank_set fs = 0;

for( i = 1; i ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download