Content-Type: application/octet-stream; name="index.html" Content-Transfer-Encoding: quoted-printable Content-Description: index (Netscape Hypertext Document) Content-Disposition: attachment; filename="index.html" Othello, Choosing Sides Othello, Choosing Sides
Lawrence J. Leftin

The Project

In this project we explore the capabilities and behavior of a genetic = programming system through experimentation. The genetic programming software, developed by = K. Kokkonen and=20 extended by E.Eskin provides an environment for evolving machine-learned = Othello game=20 players. Consequently, the Java source code provides all the base = classes for population creation, cross-over and mutation, and fitness selection.

The Othello System

Two opponents, a random Othello player, and Edgar, the Othello master, = are provided. A=20 board-evaluation algorithm, for evaluating moves is provided as well. = The inidividual players are tree-structures created from a set of operators and = 'terminals' (e.g. +, -,=20 *, /, white, black, white_corners, black_corners, white_near_corners, = black_near_corners, white_edges, black_edges, 10). The tree-structures, when parsed by the = move-evaluation algorithm, determine the move, best characterized by the tree.

The Game, Othello

Othello is a board game wherein the objective is to end up with more = pieces than your opponent. One captures pieces by surrounding the opposing pieces on both = sides. The surrounded pieces are then converted to the victor's color (black, or = white). The basic stategy could be called 'Surround, but don't be surrounded.' As a = consequence of the=20 finite size of the board, not all spaces are created equal. For example, = the corners, once obtained, cannot be captured. Also, edge-squares can only be = captured by other edge-squares. Once a corner is obtained, one can threaten the two = attached edge areas and the diagonals. Once an entire edge is captured, it may in turn be used = to threaten the attached rows and columns. Consequently, a good strategy would be to = gain possession of the corners, next gain possession of the edges, then proceed to capture = each row and column.

While hardly an expert player, I know enough about chess to understand = that the white player (who moves first) has an advantage over the black player (who = follows).=20 The white player, then, determines the beginning strategy and thereby = can cause the black player to be reactive or defensive. In fact, in master tournaments, the = white player (barring some blunder) generally wins. These observations apparently = hold for Othello also.

The Approach

I first read the work of our colleagues Juno Suk, Barry Shiffman and = Dave=20 Evans, and Pan and Poricelli. Based on this, I concluded that I, working = alone, probably couldn't improve on their results. I could however, explore the effects = of varying salient parameters, code, and stategies to gain a deeper insight into = the genetic programming world, and perhaps, discover interesting phenomena.=20

Experiments performed varied population size, deme size, restricting = genetic diversity to limit the hypothesis space, and rewarding wins. I also evolved the = populations against=20 different opponents. The various experiments are described in the = following sections.

The original code only allowed evolution against a BLACK random player. = Consquently, I had to change the code to allow evoluation against Edgar or a WHITE = random player. I also modified the code that tests evolved players to accommodate a WHITE = random player.

Experiments

Experiment 1: Varying Population = Size

Case 1a: BLACK Random Opponent

The population was set to 10, 20, 50, then 100 for five distinct runs. = The deme size=20 was set to half the population size to maintain equivalent profiles. The = code played 5 games against each indivdual. In every case, the 'most fit' player's = s-expression was 'white'. While this did generally beat most random players, it = clearly wasn't the best possible, considering previous work. I concluded that subjecting = the players to 5 games against (a generally weak) random opponent is a not tough enough = discriminant. In=20 fact, any player should be able to beat a random player an average of = 2.5 times, and winning five games should happen in approximately 1 in ten runs.

Case 1b: WHITE Random Opponent

Since the role of white and black players are not equivalent, I evolved = another set of players using a WHITE random opponent. Based on the dissappointg 5-game = stategy, I evolved these individuals using 20 games.

Case 1c: WHITE Edgar Opponent

I also evolved a set of players using a WHITE Edgar opponent, using 5 = games. I concluded that 5 games against a strong opponent would not result in = 'false-fitness' as in case 1a.

Case 1d:

I repeated Case 1a using 20 games instead of 5 games. The resulting = individuals were measureably more fit.

Experiment 2: Varying Deme Size

Cases 2a-d: Using a population size of 100, I used deme sizes of 5, 10, = 20, and fifty and a game size of 5 (early experiment, before number of games was changed = to 20). All=20 runs evolved the s-expression 'white'. Not much could be concluded, = other than these runs suffered from the same 'false fitness' observed in Case 1a. I repeated = this experiment using 20 games instead (see Experiment 2 results) but still could not observe = any clear-cut trends.

Experiment 3: Manual Approach

After playing several games against Edgar, and discovering the = corners/edges/all stategy described above, I concluded that a 'good' s-expression should emphasize = corners and de-emphasize near_corners. Consequenly, my imaginary candidate would be: + / black_corners white_near_corners / white_corners black_near_corners I played this against Edgar and actually won:

Experiment 4: Restricting Genetic = Diversity

Having invented one individual that could beat Edgar, I decided to try = to evolve it using the genetic programming system. Since I knew it used only six = primitives, I restricted the node set to these by commenting out the unwanted ones. I = fully expected several viable species to evolve, including the one in Experiment 3.

Case 4a: Restricted to Primitives + / black_corners, = white_corners, black_near_corners white_near_corners

The individual in Experiment 3 never appeared. In fact, the most fit = indivdual was rather complex:

( / ( + ( / ( + black_corners white_corners ) ( / = white_near_corners white_near_corners ))
( / ( / ( + ( / ( + black_corners white_corners ) = white_near_corners )
( / ( / black_near_corners black_corners ) ( + = black_near_corners black_corners )))
( + ( + ( / ( + black_corners white_near_corners ) ( + = black_corners white_corners ))
( / black_corners black_near_corners )) ( / ( / = white_near_corners white_near_corners )
white_near_corners ))) ( + black_near_corners black_corners ))) =
( + ( + ( + black_near_corners white_near_corners )
( + ( + ( + ( / black_corners white_near_corners ) ( / = white_corners black_corners ))
( + white_corners black_near_corners )) ( / ( + ( / ( + = black_corners white_near_corners )
( / white_near_corners black_corners )) ( / ( + = white_near_corners black_near_corners )
( + black_corners white_near_corners ))) white_near_corners )))
( / ( + black_near_corners white_near_corners ) = black_near_corners )))

Case 4b: Restricted to Primitives + - black_corners, = white_corners, black_near_corners, white_near_corners, black_edges, white_edges
I though adding a few terminals would help, but the resulting most fit = individual was still fairly complex:

( / ( / ( + white_edges ( + black_near_corners black_edges ))=20 ( + ( / ( + ( / white_near_corners white_corners )=20 ( + ( / ( / black_edges black_edges ) black_edges )=20 ( + ( / black_corners white_edges ) ( + black_near_corners = white_corners )))) ( + ( / white_corners black_edges ) ( / black_edges = black_near_corners )))=20 ( + ( + white_edges black_edges ) ( / ( + ( / ( + ( + = black_near_corners black_corners ) ( / black_edges white_corners )) ( / ( + black_edges = black_edges )=20 ( / ( + white_edges ( + black_near_corners black_edges )) ( + ( / ( + black_corners black_near_corners ) ( / = black_near_corners white_corners )) ( + ( + white_edges black_edges ) ( / black_edges = white_corners )))))) ( / black_edges black_edges )) ( + ( + black_edges = white_corners ) ( / white_near_corners white_corners ))))))=20 ( / ( + ( + ( / white_near_corners white_corners ) ( / ( + white_corners white_edges ) ( + black_edges = black_edges )))=20 ( + ( + black_edges white_near_corners ) ( + white_near_corners = white_near_corners ))) ( + white_edges white_corners )))

It appears that nature/chance will make up for lack of diversity in = terminals with greater complexity in their arrangement!

Results:

Key: WR -> Opponent is White Random Player, BR -> = Opponent is Black Random Player

Experiment 1:

Case 1a-1,2:
(case 1a1)
(case 1a1)
pop=3D10 demesize=3D5 50 runs 5 games and pop=3D20 demesize=3D10 50 = runs 5 games

white

fitness 0.0

WR BLACK 319 WhiteRandom 281
EDGAR BLACK 15 WHITE 49
BR BLACK 96 WHITE 404

=09 Case 1a-3
(case 1a2)
pop=3D50 demesize=3D 25 50 runs 5 games set trained against black = random player

( + white ( + white ( + white white_corners )))

fitness 0.0

WR BLACK WhiteRandom
EDGAR BLACK 15 WHITE 49
BR BLACK 88 WHITE 412

Case 1b:
(case 1b)
(case 1bs)
pop=3D200 demesize=3D100 31 runs 20 games set trained against white = random player

black_edges

=20 fitness 1.0
WR BLACK 480 WhiteRandom 20 (we win)
EDGAR BLACK 16 WHITE 48
BR BLACK 483 WHITE 17 (BR wins)

Case 1c:
(case 1c)
edgar pop=3D200 demesize=3D100 31 runs 5 games set trained against = EDGAR

( / ( + ( * black_edges black_edges ) ( - 10 white )) ( / = blac k_edges white_corners ))

EDGAR WHITE 12 BLACK 52 (EDGAR loses)
BR BLACK 438 WHITE 62
WR BLACK 452 WHITE 58 (we win!!!)
=20 Case 1d-2:
(case 1d2)
pop=3D100 demesize=3D20 10 runs 20 games set trained against black = random player

( - ( + ( * black_near_corners ( / white black )) ( - ( + ( = * black_near_corners ( + black_near_corners 10 )) ( - white = black_edges )) ( * ( + black_near_corners white ) ( - black white_corners = )))) ( * ( * ( / white_edges black ) ( - black white_corners )) ( - = black w hite_corners )))

fitness 49.0

WR BLACK 180 WhiteRandom 320
EDGAR BLACK 25 WHITE 39
BR 39 WHITE 461

Case 1d-3:
(case 1d3)
pop=3D100 demes=3D50 10 runs 20 games set trained against black random = player

( * ( / ( - ( + white ( - ( + white ( - black_corners = black )) black )) black ) ( + white_corners 10 )) black_near_corners = )

fitness 74.0
WR BLACK 364 WhiteRandom 136
EDGAR BLACK 7 WHITE 57
BR BLACK 135 365

Experiment 2:

Case 2a:
(case 2a)
pop=3D100 demesize=3D50 10 runs 20 games set trained against black = random player

( * ( / ( - ( + white ( - ( + white ( - black_corners = black )) black )) black ) ( + white_corners 10 )) black_near_corners = )

fitness 74.0
WR BLACK 364 WhiteRandom 136
EDGAR BLACK 7 WHITE 57
BR BLACK 135 365

Case 2b:
(case 2b)
pop=3D100 demesize=3D20 10 runs 20 games set trained against black = random player

( - ( + ( * black_near_corners ( / white black )) ( - ( + ( = * black_near_corners ( + black_near_corners 10 )) ( - white = black_edges )) ( * ( + black_near_corners white ) ( - black white_corners = )))) ( * ( * ( / white_edges black ) ( - black white_corners )) ( - = black w hite_corners )))

fitness 49.0

WR BLACK 180 WhiteRandom 320
EDGAR BLACK 25 WHITE 39
BR 39 WHITE 461

Case 2c:
(case 2c)
pop=3D100 demesize=3D10deme 10 runs 20 games set trained against black = random player

( + ( - black_near_corners black_corners ) ( + ( + ( / ( - = white _corners black_edges ) ( + white_near_corners black_corners )) ( = - white ( / white_near_corners ( * 10 10 )))) white_corners )) =

fitness 89.0
WR BLACK 200 WhiteRandom 300
EDGAR BLACK 20 WHITE 20
BR BLACK 58 442

Experiment 3:
Case 3a: Manually Created

+ / black_corners white_near_corners / white_corners = black_near_corners

WR BLACK 474 WHITE 26 (we win!!!)
EDGAR BLACK 26 WHITE 38 (we win!!!)
BR BLACK 58 442

Experiment 4:

Case 4a:
(case 4a)
pop=3D100 demsize=3D20 10 runs 5 games trained against black random = player
used only white_corners, black_corners, white_near_corners, = black_near_corners,
+ / fitness 90.0
EDGAR WHITE 53 BLACK 11
BR WHITE 37 black 13 (BR loses)

Case 4b:
(case 4b)
pop=3D100 demesize=3D20 10 runs 5 games trained against black random = player
used only white_corners, black_corners, white_near_corners, = black_near_corners, black_edges, white, edges, + /
=09 fitness 74.0
BR WHITE 44 BLACK 6 (BR loses)

Experiment 5:
(case 5)
pop=3D100 demesize=3D20 10 runs 20 games set trained against black = random player
=09 gave 20-pt bonus for wins

=09 ( + ( - white ( / ( / ( / black white_near_corners ) ( + = black _edges black )) ( * ( / ( - white ( + black = white_near_corners )) ( + black_edges black )) ( * ( * black_corners 10 ) ( * = white_edges bl ack ))))) ( * white white ))

EDGAR WHITE 49 BLACK 15
BR BLACK 107 WHITE 393

Conclusions

Factors such as population size, opponent selection, and genetic = diversity dramatically effect experimental outcome. For board games such as Othello, there are = distinct white and black stategies that are not symmetrical. This results from the fact = that the white play has a definite advantage in being the first to move and hence = dictate the conduct of the game. In addition, the strength/versatility of the opponent = greatly determines the strength/versatility of the evolved players. Consequently, the very best = results were=20 obtained by evolving against the (formiddable) WHITE Edgar opponent. The = resulting=20 individual also fared well against the WHITE random player but did not = do well against=20 the BLACK random player. Interestingly, the effect of restricting = genetic diversity in was to compensate by producing more complex species. We also must be = aware that we are=20 performing experiments that are statisitcal in nature. Our conclusions = must be =20 tempered considering the number of runs is not very large compared to = the hypothesis space.
------=_NextPart_000_01BF9FBD.7CB5FC80