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