assignment9_part1.html

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
  "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">

<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
<meta http-equiv="Content-Style-Type" content="text/css" />
<style>
    body {
        font-family: sans-serif;
        max-width: 800px;
        margin-top: -21px;
        margin-left: 66px;
        border-left: 1px solid gray;
        padding-left: 24px;
        margin-bottom: -15px;
    }

    div.content {
        padding-top: 21px;
        padding-bottom: 15px;
    }

    h1 {

    }

    hr {
        color: gray;
        background-color: gray;
        height: 1px;
        margin-left: -24px;
        margin-right: -24px;
        border: 0px solid gray;
    }

    .draft {
        color: #008080;
    }
    div.attention {
        background: #ffcccc;
        border: 2px dashed red;
        padding: 11px 21px 11px 21px;
    }
    div.hint {
        background: lightgreen;
        border: 2px dashed green;
        padding: 0 21px 0 21px;
    }

    table {
        padding: 0;
        border-bottom: 1px solid grey;
        border-right: 1px solid grey;
    }

    tr {
        margin: 0;
        padding: 2px;
    }
    td {
        border-left: 1px solid grey;
        border-top: 1px solid grey;
        margin: 0;
        padding: 2px;
    }
    th {
        border-left: 1px solid grey;
        border-top: 1px solid grey;
        margin: 0;
        padding: 2px;
    }


    span.keyword {
        font-weight: bold;
    }
    span.emph {
        font-style: italic;
    }
    span.hilite {
        text-decoration: underline;
    }

    a {
        text-decoration: none;
    }

    div.author {
        float: right;
        margin-top: 27px;
        color: grey;
    }

    .code {
        font-family: monospace;
    }
    div.code {
        border: 1px dashed grey;
        padding-top: 11px;
        padding-bottom: 11px;
        padding-right: 21px;
        padding-left: 21px;
        white-space: pre;
        overflow-x: auto;
        background: #fff;
    }
    div.points {
        float: left;
        text-align: right;
        margin-left: -88px;
        min-width: 50px;
    }
    li div.points {
        margin-left: -128px;
    }
    div.points.easy {
        color: #008000;
    }
    div.points.hard {
        color: #800000;
        font-weight: bold;
    }

    table.board {
        border: 1px solid #000;
        border-right: 0;
        border-top: 0;
        border-spacing: 0;
    }
    table.board.highlight {
        border: 5px solid #f00;
    }

    table.board tr {
        border: 0;
    }
    table.board td {
        border: 1px solid #000;
        border-bottom: 0;
        border-left: 0;
        padding: 0;
        width: 25px;
        height: 25px;
        background: #0a0;
        vertical-align: middle;
    }

    table.small td {
        width: 15px;
        height: 15px;
    }

    table.board div {
        -webkit-border-radius: 999px;
        -moz-border-radius: 999px;
        border-radius: 999px;
        behavior: url(PIE.htc);
        border: 0;
        width: 20px;
        height: 20px;
        margin-left: auto;
        margin-right: auto;
    }

    table.board div.W {
        background: #fff;
    }
    table.board div.B {
        background: #000;
    }
    table.board div.S {
        border: 2px solid #f00;
    }

    table.small div {
        width: 10px;
        height: 10px;
    }

    #minimaxTable {
        border: 0;
        font-weight: bold;
    }
    #minimaxTable > tbody > tr > td {
        border: 0;
        text-align: center;
    }
    #minimaxTable td > table {
        margin: auto;
    }
    #minimaxTable .bracket {
        margin: 10px auto 10px auto;
        border: 3px solid #000;
        border-bottom: 0;
        width: 50%;
        height: 25px;
    }
</style>
<title>CS2 Assignment 9: Othello - Part 1</title>

<script>
function print_board(s, small, highlight) {
    var classes = "board";
    if (small) classes += " small";
    if (highlight) classes += " highlight";

    document.write('<table class="' + classes + '">');
    s.replace(/\s+/g, ' ');
    for (var i = 0; i < 8; i++) {
        document.write('<tr>');
        for (var j = 0; j < 8; j++) {
            document.write('<td>');
            var c = s.charAt(i*8 + j);
            if (c == 'o') {
                document.write('<div class="W"></div>');
            } else if (c == 'x') {
                document.write('<div class="B"></div>');
            } else if (c == 'O') {
                document.write('<div class="W S"></div>');
            } else if (c == 'X') {
                document.write('<div class="B S"></div>');
            }
            document.write('</td>');
        }
        document.write('</tr>\n');
    }
    document.write('</table>');
}
</script>

</head>

<body>
<div class="content">

<div class="author">Author: Kevin Chen</div>
<h1>CS2 Assignment 9: Othello - Part 1</h1>
<h2>Due Tuesday, March 6, 2018, at 17:00 PST</h2>

<hr />

<h2>Introduction</h2>

<p>This is <b>Part 1</b> of a two-part CS2 assignment on Othello.
<a href="assignment9_part2.html">For <b>Part 2</b>, click here.</a></p>
<p><b>A note on late tokens for the final project</b>: You may use tokens on the Othello project; you can use the minimum of the number of tokens you both have. (if you have 1 token and your partner has 2, then you can turn either assignment 9 or 10 in 1 day late).</p>

<p>However, you are highly discouraged from using late tokens on assignment 10, since you can not participate in the tournament then.</p>

<p>In addition, you must turn in ALL assignments by Friday March 16, 5 pm. Remember that you must turn in every assignment with a reasonable attempt to pass, even if you have achieved the minimum number of points required to pass this course!</p>
<hr />

<h2>Assignment Background</h2>


<h3>Othello Rules</h3>

<p>Othello (also known as Reversi) is a board game played on an 8x8 board between two sides: White and Black. The board starts out with the four centermost squares populated in an alternating pattern, like so:</p>

<div align="center">
<script>
print_board('\
--------\
--------\
--------\
---ox---\
---xo---\
--------\
--------\
--------\
');
</script>
</div>

<p>On every move, a player must play a stone such that one or more of their opponent's stones are located contiguously between the stone placed and some other stone of the same color in the horizontal, vertical, or diagonal directions. All such stones belonging to an opponent are then flipped to the player's own color.</p>

<p>To make this more clear, consider what happens when black plays the following move (highlighted in red).
Notice that the white stone is flipped because it is between the the stone that was just put down
and another black stone.</p>

<div align="center">
<div style="display: inline-block">
<script>
print_board('\
--------\
--------\
---X----\
---ox---\
---xo---\
--------\
--------\
--------\
');
</script>
</div>
<div style="display: inline-block; margin-left: 20px">
<script>
print_board('\
--------\
--------\
---x----\
---xx---\
---xo---\
--------\
--------\
--------\
');
</script>
</div>
</div>

<p>If a player cannot make any moves, play continues with the other player. The game ends when there are no legal moves remaining, and <span class="keyword">the player with the most stones of their own color wins.</span> For example, the following board shows a finished game that black won 34-29. Note that even though there
is an empty square, there are no more valid moves for either player:</p>

<div align="center">
<script>
print_board('\
o-xxxxxx\
ooxxxxxx\
oooxxxxx\
ooxoxxxx\
oooxoxxx\
ooxoxoxx\
ooxxoxox\
oooooooo\
');
</script>
</div>

<p>Now that you know the rules of Othello, your team's task is to create an AI program
capable of playing the game! Your AI will be graded based on its performance
versus a force of bots codenamed SimplePlayer, ConstantTimePlayer,
BetterPlayer, OogeePlayer, and DeepKwok. In addition, we'll pit your team's AI against
those of your classmates in a (hopefully) epic tournament for honor and glory.</p>

<p>This is a difficult task, no doubt. In fact, 8x8 Othello is not yet
"solved", which means that we still cannot determine, computationally or
otherwise, the outcome of a game where both players play perfectly (as a side
note, 8x8 checkers <span class="emph">is</span> weakly solved). Don't worry
though: we'll take steps one at a time.  For this week, your goals are to
create an AI that can <span class="keyword"> (1) play valid moves</span>, <span
class="keyword">(2) beat SimplePlayer</span> (which just plays randomly), and
<span class="keyword">(3) build and use a minimax decision tree</span>.
</p>


<br/>
<h3>Heuristic Functions</h3>

<p>Any good Othello AI needs a method of ranking different moves in order to
choose the best one. This is generally done in terms of the board position;
a good move will (eventually) result in a favorable board position
for the AI, while a bad move will in an unfavorable one. To determine which
board states are favorable and which are not, you will want to develop
a <span class="keyword">heuristic</span> that takes a board position and
returns a numeric "score". This score describes how far in your favor the
board position is (usually a heuristic is set up so that a higher score is
better).</p>

<p>Because Othello is won by having the greater number of stones by the end
of the game, one simple heuristic might be the difference between the
number of stones you have and the number of stones your opponent has:</p>

    <div class="code">board position score = (# stones you have) - (# stones your opponent has)</div>

<p>However, we can think of more strategic considerations. For example,
notice that a piece in the corner of the board can never be captured, and
a piece on the edge of the board can only be captured by other edge stones.
These spaces, then, are quite valuable. Spaces that grant access to the
corners, though, are a terrible idea to play a piece in, since then the
opponent can often play a piece in the corner.</p>

<p>We can incorporate these observations into our heuristic as modifiers.
For example, we could multiply the value of a play in the corner by 3, causing
such plays preferred over others; or, we could multiply a play in a square
adjacent to the corner by -3, causing such plays to be considered only if
the alternatives are truly unfavorable.</p>

<p>Now we can now play the move that results in a board position with the
highest score. This is much better than playing randomly! However, there is
still a problem with this approach. Because a heuristic is simply an
estimate, a board position that may look good early in the game might actually
be terrible in the long run. This is particularly true in the early and mid
stages of an Othello game; it is not uncommon for a player to recover
from having only 1 piece left to retake the whole board by the end.</p>


<br/>
<h3>Minimax Decision Trees</h3>

<p>One standard way to solve this problem is the use a <span
    class="keyword">decision tree</span> - a tree of all possible moves down to
a certain depth. Then, you can choose the branch that leads to the best
outcome. A decision tree essentially lets you look a number of steps into the
future, where your heuristic will hopefully be more accurate. While a tree is
almost certainly required to defeat more difficult opponents, one is not
necessarily required to beat SimplePlayer.</p>

<p>
For simple games like tic-tac-toe, this can be done for the depth
of the entire game; for complicated games like chess, where the decision
tree branches quickly, it is only feasible to construct a decision tree for a
limited depth (e.g. 10 moves ahead). For games with an especially high
"branching factor", e.g. Go, constructing the entire decision tree is entirely
impractical, so programs must decide intelligently which parts of the
decision tree to explore. This is also true in environments where time is a
real constraint, e.g. an AI playing a casual game against a human, or an AI
playing in a tournament setting where each side is allotted a maximum total
time. </p>

<a name="minimax_example"></a>
<p>
Let's consider a simple Othello decision tree with 2-ply depth
(ie. a turn by white followed by a turn by black):
</p>

<table id="minimaxTable" border="0" cellpadding="0" cellspacing="0">
<tr>
<td colspan="5">
<script>
print_board('\
--------\
--------\
-x------\
xoxxxx--\
--------\
--------\
--------\
--------\
');
</script>
<div class="bracket"></div>
</td>
</tr>

<tr>
<td colspan="2" width="400">
<script>
print_board('\
--------\
-O------\
-o------\
xoxxxx--\
--------\
--------\
--------\
--------\
', true, true);
</script>
<div class="bracket"></div>
</td>

<td colspan="3">
<script>
print_board('\
--------\
--------\
-x------\
xoooooO-\
--------\
--------\
--------\
--------\
', true);
</script>
<div class="bracket" style="width: 66%">
    <div class="bracket" style="width: 1px; border-left: 0; border-top: 0; margin: auto"></div>
</div>
</td>
</tr>

<tr>
<td>
<script>
print_board('\
--------\
Xo------\
-x------\
xoxxxx--\
--------\
--------\
--------\
--------\
', true);
</script>
score = -5
</td>

<td>
<script>
print_board('\
--------\
-oX-----\
-x------\
xoxxxx--\
--------\
--------\
--------\
--------\
', true);
</script>
score = -5
</td>

<td>
<script>
print_board('\
--------\
--------\
-x------\
xxxxxxxX\
--------\
--------\
--------\
--------\
', true);
</script>
score = -9
</td>

<td>
<script>
print_board('\
--------\
--------\
-x------\
xxooooo-\
-X------\
--------\
--------\
--------\
', true);
</script>
score = +1
</td>

<td>
<script>
print_board('\
--------\
--------\
-x------\
xoxoooo-\
---X----\
--------\
--------\
--------\
', true);
</script>
score = +1
</td>

</tr>
</table>

<p>
Starting from the initial board state, we see that white can play 2
potential moves; the board states after these 2 moves are shown in
the 2nd layer of the tree. The 3rd layer of the tree shows the board
states for the possible moves for black, starting from one of the boards
in layer 2. If we wanted to generate a 4th layer, we would enumerate all
the moves for white starting from the boards in layer 3; and so on.
The score in the last layer is just using the simple heuristic
described previously (difference in piece count).
</p>

<p>To use the tree, we want to make the choice that
<span class="hilite">maximizes our minimum gain</span> (this idea is also
referred to as <span class="keyword"> minimax</span>). That is, we want to
make the choice that maximizes our eventual score, given that our opponent
is also intelligent and consistently makes choices that minimize our future
score. We do this because making the choice that simply maximizes our current
score is often not the best option. There are situations where we could take a
large number of stones from our opponent, only to have them retaken by a series
of clever moves in the future. Maximizing our minimum gain ensures that we are
not so vulnerable to such "critical hits".</p>

<p>
The above tree is a simple example of how minimax is better than a greedy
approach. It initially seems like white's move on the right is good, since
it capture 4 of black's stones (for a heuristic score of +4).
However, minimizing white's score, black will play a move that recaptures
these stones. This results in a terrible heuristic score of -9 (and game over)
for white in the end.
</p>

<p>
On the left branch, we see that white initally only captures 1 piece for a
score of -2. However, the best black can do in the next turn is to minimize
white's score to -5 (either of the two moves does this).
Since white obviously wants to maximize its score at each step, it should
choose the left move (highlighted in red), which leads to a score of -5,
versus the right move, which leads to a worse score of -9.
</p>

<p>
So we could simply generate a decision tree down to a practical depth and
use minimax to choose the branch that maximizes our minimum score. However,
this is an inefficient approach, since we spend a lot of time considering
branches that will end up being worse than branches we have already considered
or that our opponent would never let us reach. If we could stop ourselves from
tracing too far into these, we could save time, allowing us to look deeper with
the time we have.  We will deal with solutions to this inefficiency next week.
<a href="assignment9_part2.html">Feel free to look ahead though!</a>
</p>

<hr />

<h2>Prerequisites</h2>

<p>These are the prerequisites for getting this assignment to compile
(ubuntu package names):
    <ul>
    <li>g++ 4.6.x+</li>
    <li>openjdk-6-jre</li>
    <li>openjdk-6-jdk (optional - only if you want to use Java)
    </ul>
Ask a TA if you need help retrieving these packages, or if these packages appear
to be missing from the CS cluster.</p>
<hr />

<h2>Assignment (20 points)</h2>

<h3>Using Github and Git</h3>
<p>In past weeks, you have pulled the assignment directories using Git, but have
turned your code in via Moodle. For this project, to encourage you to take
advantage of Git's version control functionality, you will be required to use Git
to turn in your assignments as well.</p>

<p>Since this project is optionally a team project, we are also encouraging you
to use Git as a software development tool. Using Git will help you keep your
group's code synchronized and help your group reconcile changes.</p>

Each member of your group should create a Github account. Then, one member of
your group should do the following:

<ul>
    <li>Use the Github web interface to create a new public repository. You can
        name the repository whatever you'd like, such as a team name or just
        "othello". </li>
    <li>In the directory for this assignment, run "<span class="code">git remote set-url origin https://github.com/USER/REPO.git</span>".
        Replace <span class="code">USER</span> with your
        Github username, and
        replace <span class="code">REPO</span> with the repository
        name that you chose in the previous step.</li>
    <li>Run <span class="code">git push</span>. Now, if you refresh your
        repository's Github webpage, you should see the code for this assignment.</li>
    <li>Click "Settings" on your repository's Github webpage, then click
        "Collaborators". Add your teammate as a collaborator. This will allow
        them to <span class="code">git push</span> to your repository.</li>
</ul>

Your teammate should now clone your repository by running <span class="code">git clone https://github.com/USER/REPO.git</span>.
If they have already retrieved the assignment by running <span class="code">git clone https://github.com/caltechcs2/othello.git</span>,
then, instead of running <span class="code">git clone</span> again,
they can run <span class="code">git remote set-url origin https://github.com/USER/REPO.git</span>
from inside the assignment's directory.

<p>Now, practice the basic version-control operations
you'll need to perform during the course of this assignment:</p>

<ul>
    <li>Each group member should make some small changes to the
    <span class="code">player.cpp</span> file. Then, each group member
    should commit their changes locally using
    <span class="code">git commit -a</span>.</li>
    <li>Each group should now also create a file called
    <span class="code">README.txt</span>. The file need not contain anything
    of substance just yet; it'll be populated next week. The person creating
    the file should now <span class="code">git add README.txt</span> at the
    command line, then commit the added file using
    <span class="code">git commit</span>.</li>
    <li>Each group member should now <span class="code">git push</span>
    their changes. Each group member should <span class="code">git pull</span>
    before pushing to avoid throwing an error.</li>
    <li>In the event that a merge conflict is generated, open up the problem
    file in a text editor and resolve the conflict by hand; then commit and
    push.</li>
</ul>

<p><div class="points easy">5</div>
<div class="hint"><p>
As an incentive for getting familiar with Git
early (and starting early!), there's a small bonus if every member of your group
has committed at least one change by <span class="keyword">Sunday, March 5, at
23:59 PDT</span>.</p></div></p>

<h3>Writing Your AI</h3>

<p>In this assignment, we have provided you with a framework that will simulate
the tournament setup. While the actual framework code is in Java (hence the
Java runtime requirement), we have provided you with some wrapper classes so
that you can code in C++. If you would like to use a language other than C++,
check out the <a href="#other_languages">section at the end</a>.
</p>

<p>To get started, check out <span class="code">player.cpp</span>. You'll
notice that it includes one function definition, <span class="code">doMove()</span>.
The framework will call this function with your opponent's last move as well as
the time you have left for the game. Your AI will be expected to return a valid
move (or <span class="code">nullptr</span> if there are none). Of course, to figure
out which moves are valid or not, your AI will need to keep track of the Othello
board state for itself. To help get you started, we have provided an Othello board
class in <span class="code">board.cpp</span>.</p>

<p>As you can see, it has a bunch of useful functions, such as
<span class="code">checkMove()</span>, <span class="code">doMove()</span>,
and <span class="code">hasMoves()</span>. You are free to use and modify this
class as you wish. Be aware though; while it does the job, it is definitely not
the most efficient. We expect that the highest-performing AI's will end up rolling
their own board-state implementations.</p>

<p>The makefile is set up to build <span class="code">player.cpp</span> into the executable
<span class="code">player</span>. <span class="keyword">
You should rename your AI something more unique by setting the PLAYERNAME
variable in the Makefile (the name should reflect your team name)</span>:</p>

    <div class="code">PLAYERNAME  = bestplayerever</div>


<p>To test your AI, run the
<span class="code">testgame</span> program. To use it, simply pass it the
names of two AI programs as arguments (the first program will play as black,
the second as white). The testgame program will also accept the names of the
three easier precoded AIs ("SimplePlayer", "ConstantTimePlayer", "BetterPlayer")
as well as "Human", which lets you play one of the sides. For example, to play
your AI as black against SimplePlayer, you would run:</p>

    <div class="code">./testgame player SimplePlayer</div>

<p>This should invoke a Java application that will render the game to a
separate window. To play against SimplePlayer yourself:</p>

    <div class="code">./testgame Human SimplePlayer</div>

<p><span class="code">testgame</span> also takes an optional 3rd argument, which is the time allotted to
each player in milliseconds. If it is not provided, both players are given
unlimited time. For example, to give each player 5 minutes each (the time limit that will be used in the tournament):</p>

    <div class="code">./testgame player SimplePlayer 300000</div>
<br />

<p><div class="points easy">5</div>
Now, it's up to you to actually implement a working AI. Use player as a base
and fill in the appropriate functions:
<ul>
    <li><span class="code">Player()</span> (constructor) - should do all of your
        initialization, such as setting up any variables (like your board object).</li>
    <li><span class="code">Move *doMove(Move *opponentsMove, int msLeft)</span> -
        should update your internal board state based on the given opponent's
        move and then calculate and return a valid move.</li>
</ul>
Feel free to add helper functions or even new classes. Remember, you can use the
provided Board class to get started.</p>

<p>
By "working AI", we mean one that can successfully play games to completion
within the tournament framework (no invalid moves, passes when it should, etc).
For these points, your AI does not have to be good; it simply has to
<span class="hilite">work</span>. A good starting point is to write an AI that
just randomly plays valid moves.
</p>

<div class="attention" style="padding-top: 0">
<p><span class="keyword">IMPORTANT:</span> Because the C++ wrapper communicates with
the Java framework using <span class="code">stdin</span> and
<span class="code">stdout</span>, you should <span class="keyword">NOT</span>
use <span class="code">stdout</span> when debugging. Instead, use
<span class="code">stderr</span>; this is as simple as replacing
<span class="code">cout</span> with <span class="code">cerr</span>:</p>
    <div class="code">std::cerr << "blah" << std::endl;</div>
<p>If you want to use <span class="code">printf()</span>, you can do:</p>
    <div class="code">fprintf(stderr, "%d\n", "123");</div>
</div>


<p><div class="points easy">9</div> The next step is to make your AI good
enough to beat SimplePlayer. Remember, SimplePlayer just plays randomly, so
this shouldn't be too difficult. A good heuristic function should be enough to
beat it consistently without implementing the next step. </p>

<p><div class="points easy">6</div> Now, you'll want to make your AI implement
a <span class="keyword">minimax</span> algorithm so it can look ahead into
the future and make even better decisions!
</p>

<p>We have provided a <span class="code">testminimax.cpp</span> file to
help test your implementation for correctness. Starting from the example
board used in the background section, your player should play the following
move. For the test, your player should use a 2-ply depth minimax and the heuristic
of the difference in number of stones on the board, just like the
<a href="#minimax_example">example</a>.

<div align="center">
<div style="display: inline-block">
<script>
print_board('\
--------\
--------\
-x------\
xoxxxx--\
--------\
--------\
--------\
--------\
');
</script>
</div>
<div style="display:inline-block; margin-left: 20px">
<script>
print_board('\
--------\
-O------\
-o------\
xoxxxx--\
--------\
--------\
--------\
--------\
');
</script>
</div>
</div>


<p>
The <span class="code">testminimax.cpp</span> file already creates a
<span class="code">Board</span> object with the initial state that you can use;
however, <span class="keyword">it is up to you to update your player's internal board state
appropriately</span> (since this will likely be different for everyone).
If you are using the provided Board class, this might be
as simple as setting your player's board to the created board.
</p>

<p>To compile/run the test:</p>
<div class="code">make testminimax
./testminimax
</div>

<p>
<div class="hint">
<p>We are aware that you will likely want to use a better heuristic or
search to a depth greater than 2 with your minimax. However, this could potentially
lead to a different result for the minimax test.</p>

<p>
To get around this, the <span class="code">Player</span> class includes a
boolean flag as a member variable:
</p>
<div class="code">bool testingMinimax;</div>
<p>
This will be set to <span class="code">true</span> in the
<span class="code">testminimax</span> program, and
<span class="code">false</span> otherwise. You can use this boolean to switch
between using the 2-ply minimax and naive heuristic for the minimax test and using a
different approach for actual competitive play.
</p>
</div>
</p>


<div class="attention" style="padding-top: 0">
<p>Finally, when writing your AI, you should keep in mind a few rules for the tournament:
<ul>
    <li>Your final executable program should have a unique name related to your team name.</li>
    <li>During the tournament, each side is allowed up to 5 minutes total per game; this is
    subject to change, so make sure to pay attention to <span class="code">msLeft</span>.</li>
    <li>The constructor for your AI must return within 30 seconds.</li>
    <li>Your AI must not try to steal resources from the other player (such as memory). During
    the tournament, you will be limited to 768M of memory (the tournament manager marks a loss for AIs that go over this limit).
    </li>
    <li>Your AI may be permitted to read from and write to files with filename beginning with your team name (or some other name unique to you). The data files will be in the same folder as your executable. Remember that there will be multiple copies of your AI running at the same time. This rule may be subject to change if it is found infeasible.</li>
</ul>
</p>
</div>

<hr />
<a name="other_languages">
<h3>Using Other Languages</h3>
</a>
While we only provide framework code for C++, you can actually use any language
you want to write your AI, <span class="keyword"> as long as it runs on the
cluster computers</span>. In addition, you must implement an equivalent testsuite
for testing your AI's minimax algorithm. If your team is planning to use a different
language, please make sure to let the TAs know.</p>

<p>If you take a look at <span class="code">java/WrapperPlayer.java</span>, you will see
that it simply runs an external program and communicates with it using
<span class="code">stdin</span> and <span class="code">stdout</span>.
After your AI is done initializing, the wrapper expects a single newline (\n) delimited
line. Then, for moves the wrapper sends lines of the form:</p>
    <div class="code">x y msLeft</div>
<p>where <span class="code">x</span> and <span class="code">y</span> represent
your opponent's move (both -1 to indicate a pass), and <span class="code">msLeft</span>
is the time you have left in milliseconds. The wrapper expects lines of the form:</p>
    <div class="code">x y</div>
<p>where <span class="code">x</span> and <span class="code">y</span> represent
your move (both -1 for a pass). Look at <span class="code">wrapper.cpp</span>
for a concrete example of how your program should communicate.</p>


If you want to use <span class="keyword">Java</span>, it's slightly simpler
since the framework is also in Java. Check out <span class="code">java/ExamplePlayer.java</span>
and <span class="code">java/OthelloBoard.java</span>; they are equivalent to
the C++ starting classes we give you. In addition, there are makefile targets
for building/cleaning the Java files if you want to use them:</p>
    <div class="code">make java
make cleanjava</div>
<p>You will want to modify <span class="code">java/TestGame.java</span> to test
your Java AI.  NOTE: If you are building the java files on the cluster, change the java/Makefile first line to the following:</p>
<div class="code"> JAVAC = gcj -C </div>

<p>Just remember - using a higher level language like Java or Python will
likely put you at a disadvantage in terms of pure speed versus using C++
(which means you probably won't be able to use your allotted time as efficiently).</p>

<hr />

<div class="hint">If you have any questions about this week's assignment,
please contact cs2-c-tas@caltech.edu, or show up at any TA's office
hours.</div>

</div>


</body>

</html>