Ben May and Anastasiya Lebedev
PLEASE VIEW AT LARGEST SCREEN SIZE POSSIBLE!
Machine Learning HW4
What was done:
1) After playing against the random player for a long time, we found that it only evolved a single strategy, that of “white.” This sort of makes sense, since the best strategy against a random player is simply to choose the move that optimizes for your total number of pieces on the board. But we felt this was somewhat boring, so we decided to test our program against edgar.
2) We added two new primitives to the Othello package. First, a pair of primitives called “old_white_moves” and “old_black_moves” that count the total number of moves yielded to the opponent after the current player’s last move. Second, we added a primitive pair “old_white_corners” and “old_black_corners” that count how many corners were opened up to the opponent after the last move.
3) We had to modify the code a bit, including some modifications to OthelloGPPlayer, OthelloGPTester, OthelloBoard, and GPOthello. These consisted mostly of modifying the evaluation function to include our new primitives and of changing things to allow us to play edgar instead of the random player.
Results:
Following is a table of settings used and the individual resulted, beats refers to whether or not the tree beats edgar:
|
Settings: |
population |
generations |
mutation |
max creation depth |
complexity effects? |
beats? |
Individual |
|
modified |
|
||||||
|
primitives |
|
||||||
|
(oppmoves) |
100 |
50 |
0 |
6 |
Y |
N |
|
|
|
100 |
50 |
5 |
6 |
Y |
N |
|
|
|
100 |
75 |
0 |
6 |
Y |
N |
|
|
|
100 |
75 |
5 |
6 |
Y |
N |
|
|
|
100 |
100 |
0 |
6 |
Y |
N |
|
|
|
100 |
100 |
5 |
6 |
Y |
N |
|
|
|
200 |
50 |
0 |
6 |
Y |
N |
|
|
|
200 |
50 |
5 |
6 |
Y |
N |
|
|
|
200 |
100 |
0 |
6 |
Y |
N |
|
|
|
100 |
25 |
0 |
10 |
N |
N |
|
|
|
100 |
25 |
0 |
14 |
N |
N |
|
|
|
100 |
50 |
0 |
10 |
N |
N |
|
|
|
100 |
50 |
0 |
14 |
N |
N |
|
|
|
|||||||
|
Old |
|
||||||
|
primitives |
|
||||||
|
|
100 |
50 |
0 |
6 |
Y |
N |
|
|
|
100 |
50 |
5 |
6 |
Y |
N |
|
|
|
100 |
75 |
0 |
6 |
Y |
N |
|
|
|
100 |
75 |
5 |
6 |
Y |
N |
|
|
|
100 |
100 |
0 |
6 |
Y |
N |
|
|
|
100 |
100 |
5 |
6 |
Y |
N |
|
|
|
200 |
50 |
0 |
6 |
Y |
N |
|
|
|
200 |
50 |
5 |
6 |
Y |
N |
|
|
|
200 |
75 |
0 |
6 |
Y |
N |
|
|
|
200 |
75 |
5 |
6 |
Y |
N |
|
|
|
|||||||
|
modified |
|
||||||
|
primitives |
|
||||||
|
(old_corners) |
|
||||||
|
|
100 |
50 |
0 |
6 |
y |
N |
|
|
|
100 |
50 |
5 |
6 |
y |
N |
|
|
|
100 |
50 |
0 |
10 |
y |
N |
|
|
|
100 |
50 |
0 |
10 |
n |
N |
|
|
|
100 |
50 |
0 |
14 |
y |
N |
|
|
|
100 |
50 |
0 |
14 |
n |
N |
none |
|
|
100 |
50 |
5 |
10 |
y |
N |
|
|
|
100 |
50 |
5 |
10 |
n |
N |
|
|
|
100 |
50 |
5 |
14 |
y |
N |
|
|
|
100 |
50 |
5 |
14 |
n |
N |
|
|
|
200 |
50 |
0 |
6 |
y |
N |
|
|
|
200 |
50 |
5 |
6 |
y |
N |
|
Individuals generated while training against the random player available here. These were not included because they do terribly against edgar and generally come up with terrible strategies.
After introducing new primitives, we first decided to test them out against the random player. To get a feel for how the genetic player was evolved, we tried to evolve the algorithm for varying population sizes, generation numbers, and amounts of swap mutation. All other variables were kept constant and unchanged from what was originally created. What we found as a result was that the evolved tree settled down to what it was eventually to become fairly quick (anywhere from 3 to 20 generations), and so there was really no sense in running too many generations. We later made the same observation when we evolved our players by having them test fitness against Edgar.
After getting less than exciting results from testing against the random player, we decided to test our new primitives on Edgar. The variations of GPVariables are shown in the table. Several interesting results were observed:
First of all, for the new primitive pair, “old_black_corners” and “old_white_corners”, all but one of the processes where complexity remained an influence on fitness evolved the exact same player—“- white old_white_corners” (with Edgar playing white and our evolved player playing black). Several other trees of varying structure, depth, and complexity, were evolved in the processes where complexity was “turned off” as a measure of fitness. We ran them against Edgar to watch the game progress and uncovered the next exciting result:
Apparently, the addition of new terminals causes all the trees evolved with these terminals to evolve as a "family”—i.e., as a game progresses, there are visible similarities between the strategies of individual players evolved with those particular terminals. In fact, for most of them, the final board configuration is exactly the same. But even in the games where the board structure was different, the same strategic pattern was observed—with the addition of these terminals, the player learned to stay away from the corners of the board, making it impossible for Edgar to acquire them. In several games, Edgar winds up taking one corner, but the rest remain free till the end of the game. In others, Edgar winds up forcing our player to give up a corner, but the corners stay free until the very last. One player seemingly evolved the strategy of protecting not only corners, but also edges.
Here are some board configurations during the games played by the players evolved with the addition of old_white_corners and old_black_corners terminals:
The following game was played by almost all of the players, with the exception of two, which will be described below.
An early configuration Configuration after Edgar gains a corner Mid-game
configuration Final game configuration
The basic strategy seems to be that while the evolved player gives up one corner early in the game, it has learned the concept of importance of a corner and keeps Edgar out of the other three corners. The final score is 49-0 (losing to Edgar).
The two players that play a different game are: 1) population 100, 50 generations, max depth of created tree 14, mutation 5, fitness not affected by complexity and 2) same as 1, but with mutation of 0.
The game played by 1 looks like this:
We see in this game that the evolved genetic player manages to keep Edgar out of the corners till the very last, at which point it is finally forced to give them up. This version loses to Edgar with a score of 57-7, which, compared to the previous score of 49-0, is at least somewhat more favorable, as it manages to keep some pieces on the board. This player was evolved by implementation with a population of 100, 50 generations, maximum depth for created trees equal to 14, swap mutation of 5.0, and complexity not influencing fitness.
The game played by the player evolved with a population of 100, 50 generations, max creation depth of 14, swap mutation of 0, and complexity not influencing fitness looks like this:
The effect here is that the player has learned that edges and corners are both important, but it tries to preserve the edges from falling into Edgar's virtual hands at the cost of giving up corners. This player loses even more favorably at 44-20.
Additionally, when the old_moves-paradigm-generated-trees were used against random player, they were obviously aggressively going for the corner spaces. However, when pitted against edgar they invariably lost. Since edgar’s strategy is based entirely on the high game value of corners, he aggressively persues them. Behavior forced our trees into adapting more defensive moves in order to prevent edgar from taking the corners, instead of attempting to take the corners themselves. Hence, we can conclude that the evolved players learned the value of corners and were able to either attack them when playing against a weaker player or defend them, when playing against Edgar.