For this assignment, hardcopies (only) of the first Part are required, and both hardcopies and electronic submissions of Part II are required. See Part II below on details of what to submit, which includes a README file. Hardcopies are also due in class. The course web page provides directions for electronic submission.
The rest of the readings are from "Invitation to Computer Science". The following parts of Chapter 13 are on artificial intelligence, and are therefore abstractly related to Part II below, but are not needed before you start Part II below. Read Sections 13.1, 13.2, 13.3, 13.5 (only to the end of the paragraph at the top of page 614), 13.6. This will provide a conceptual framework of some artificial intelligence concepts, which includes the relative capabilities of humans versus machines, and how knowledge can be represented in a machine. This topic includes decision trees (a la "guess the animal" learned decision tree as shown in class) and search through possible moves of a game (a la Part II below).
The following parts of Chapter 10 are on theoretical models of computation -- they will prepare you for Part I below. Read sections 10.1, 10.2, 10.3.1, 10.3.2 (only skim this section to get a sense of Turing machines - you are not responsible for the details), 10.6, 10.7 (also just skim, since it is pretty technical -- we will go over the halting problem with less technical details in class), 10.8
Chapter 14 through Section 14.3. You will not be tested on these concepts, but now that you have learned so many fundamental concepts behind computer science, I highly recommend you read this introduction to the responsibilities that come with:
Next, consider that these aspects of Java are indeed powerful enough to implement any Turing machine (this has been proven already -- you don't have to). Now, citing the Church-Turing thesis, provide a couple sentences giving another argument that any non-physical algorithm can be implemented with these aspects of Java. Note that you don't need to know any details of Turing machines to create this argument.
For this assignment you will use Java to program the intelligent "brain" part of an on-line, web-based Othello player. In a word, this brain is a "move-chooser" to select what move the computer makes next. You or your friends can go to your web page and play against the Othello nemesis you create.
Next, you will slightly alter your strategy to make it play differently. And then, we will tell you a Unix command that will automatically run a tournament between these two Othello brains that you have created to see which one is better (that is, which wins more frequently).
Finally, you will pit your creation against the ultimate Othello-playing arch-nemesis, Edgar. Edgar is bad, badder than Darth Vader; meaner than a junkyard dog. This will be another simple Unix command. Edgar will beat your Othello brain, I am afraid, since the Othello brain you create will have some intrinsic limitations. But, how badly will your brain be slaughtered? Stayed tuned for more!
Othello is played on an 8-by-8 board (i.e., a chess board). The pieces are discs that are black on one side and white on the other. When you play, the goal is to dominate the board with your color. Each move, you put one new piece on the board. If the new piece you just added "surrounds" a row, column or diagonal sequence of your opponent's pieces, you get to flip those pieces to your color.
The rules become clear when you actually play the game. Try playing a game of Othello now, at http://www.cs.cmu.edu/~astro/ (follow the links to "Exegesus" and then "Beat Edgar"). At this web page, you are actually playing against Edgar, so plan to be creamed.
If you are interested, you can learn about how Edgar was programmed at www.cs.columbia.edu/~evs/ml/hw4EDGAR.html. Edgar, an intelligent computer program, is one of two leading fictional characters (the other is a human) in the novel, "Exegesis", by Astro Teller. Find out more about this novel from Astro's home page. Edgar is also a non-fictional, intelligent Othello player developed by the same Astro Teller. Edgar's programming used advanced techniques in artificial intelligence which are beyond the scope of this course. Edgar sits patiently as part of an advertisement for "Exegesis" at www.randomhouse.com/vintage/exegesis.
cd public_html mkdir othello
cd othelloand copy all the Java source code and a couple other files from ~es66/public_html/othello/ by typing (actually, you can just cut and paste the following into the window with the $ prompt):
cp -r ~es66/public_html/othello/audio . cp -r ~es66/public_html/othello/images . cp -r ~es66/public_html/othello/*.java . cp -r ~es66/public_html/othello/othello.html . cp -r ~es66/public_html/othello/FinalWeights . cp -r ~es66/public_html/othello/traindata .(the -r makes it copy all subdirectories, "recursively".) Don't forget those periods at the end, each after a space.
It will give you one warning -- ignore it. Didya know that a compiler warning is not nearly as bad as a compiler error, but they should not be ignored unless the instructor or a law enforcement officer tell you to do so.
chmod a+r * chmod a+r . chmod a+x . chmod a+x audio/ images/ chmod a+r audio/* images/*
In general, with regard to this type of problem, it is always best to do the homework during a TA's office hours so you can ask when you encounter unanticipated technical "gotchas" and obstacles.
However, we can not use such complicated strategies this semester. Instead, the strategy to be used in your version of Othello is as follows. When it's the computers turn to move, it will generate a list of all its possible, legal moves. The rules of the game Othello stipulate that you can only go somewhere that will cause some of your opponent's pieces to be flipped (if there is no such option, your move is skipped and your opponent takes another move). Creating the list of legal moves has already been programmed for you. It will go through that list and give a rating to each possible move. This rating will be determined by some code THAT YOU WILL WRITE which will look at the result of the move and give a numerical rating. After all the boards are evaluated, the computer will pick the best board which has the highest rank and make the move that will produce that board. If there is a tie, it will pick one randomly.
In a word, your code is a "move-chooser" to select what move the computer makes next.
To do this, you only need to modify the file MyPlayer.java, in between the "**********"s -- take a look at that file now (with pico or emacs). You will see a portion of the code marked with *****. This is the only place you will have to modify anything. You will insert code that will go through a board, e.g., with nested loops, and come up with a score for that board.
The board is a two dimensional array called "board.board". (We thought just calling it "board" was too "boring" -- get it?) Basically, it is a grid. Usually, arrays start from 0, yet for this project, the gameBoard will be starting from 1. So the top left corner is board.board[1][1] and the bottom right is board.board[8][8]. Note that you put TWO SETS OF SQUARE BRACKETS when you give the coordinate of a location -- don't use a comma.
You really don't have to do very much to get this to happen. The board "situation" in the two-dimensional array is not the current state of the game -- it is a candidate ("hypothetical") situation corresponding to one of the moves the computer is considering. It the situation that would result if the computer chose that move. The computer has to decide if it wants to be in that situation. Your code will "rate" how good that situation is.
Again, for emphasis, the contents of the "board.board" 2-dimensional array represents a hypothetical board state that your code will give a rating to. It does not represent the current actual board state in the game being played. Of these possible next-move hypothetical board states, the one that YOUR CODE gives the highest rating to will be selected as the next move the computer makes.
The rating will go in the variable called "rank". Therefore, your goal is to scan the board's contents and rate how good a situation that would be in. The rating must end up as a value in variable "rank".
One simple strategy would be to count up the number of pieces of your color are on the board and assigning "rank" to that value. This makes sense since the goal is to have as many pieces of your color as possible.
Before you change MyPlayer.java at all, it doesn't look at the board at all, and the "rank" variable always ends up with the value zero (0). This means it is giving the result of each possible move the same value, so it has no basis for selecting. In this case, since it is a tie, it selects one of the moves randomly. This is why you were playing against a random player, above, when you tried out the web page.
COLOR: What color are you? Well the way Himani (Fall 1998 TA) set set up for you is that the computer is always white and the user is always black. But, when it plays computer-versus-computer, the same strategy will be used to play black. Therefore, you must program it to be able to play black or white.
This is easy to do because Himani set up a variable called "color" corresponding to the color the computer is controlling (think of the variable as "my color"). You use this variable to compare against individual board locations. So when you write your function, and you want to see if the piece located at (5,3) is your color you would do something like "if (board.board[5][3] == color)" (of course, that if-statement is missing the "then"-part). Also, you can test if a spot on the board is empty by comparing it to "OthelloBoard.EMPTY", as in, "if (board.board[5][3] == OthelloBoard.EMPTY)" (capitalization matters). You can also test if the piece on the board is the opponent's color, if you want. Yet I will leave you to figure that one out. (Hint: each position on the board has either your color, the opponent's color, or is empty.)
COMMENTS: Be sure to comment your code. Comments are done using //. This will help YOU debug your code and it will also help the TA in figuring out what your code is meant to do.
Play a few games against Edgar and against the random player to get a feel for the game and a sense of tactics and strategy. In addition to counting up the number of positions with your color, there are several other possible strategies that can be added on top of this. In fact, simply counting these pieces is a pretty "greedy" algorithm, and does not result with a very effective Othello player -- a random player will often beat that strategy!
Possible strategies include:
Please feel free to add in any bells or whistles you choose to make your player "smarter". Use your imagination -- but recognize that some of the strategies you can think of might be too difficult to program right now. For example, in principle you could program it to look ahead a few moves, but that would be really rough! If you have a brilliant idea that you'd like to implement but don't know where to start, please feel free to contact a TA.
Your minimal requirements are to include a nested loop to count the number of pieces of your color on the board, and the addition of another strategy on top of that such as giving an extra bonus for having a corner location.
You will probably have lots of errors your first couple of time around. Don't get discouraged! And I would suggest spending some time to figure out what's wrong before asking for help (but also recognize when you are "stuck").
Use compiler errors as guidelines. Each error will have a line number. Go to the first line number that you have an error on and see whats wrong. Maybe you forgot to close a parenthesis or forgot a semicolon or attempting to use a variable that is not defined. Also remember, that fixing up one error may clear up a lot of other errors. Also be sure you to use the features of emacs or pico. After you write each line, press the TAB key. If the line doesn't align up the way you think it should, something is probably wrong in your parenthesis or bracket count. See also the list of debugging hints in the previous homework assignment.
NOTE: The TA's will often ask you if you tried to solve the problem before coming to them first and they will ask you to try explain what you think the problem is.
JAVA CONSOLE: While the game is playing, you may not be fast enough to catch whats going on. Thus, there is a feature in every browser called the console. You should be able to bring it up using the Netscape (or Internet Explorer) options. As you play the game, the moves and a grid of the gameboard will be displayed to help you figure out whats going on -- it will show you the rating given to each move it is considering, and which move it actually chose. Also, this is where you will see output if you put in System.out.println()'s to debug your code.
Now, you can try a head-to-head match against MyPlayer.java and MyPlayer2.java by typing
java OthelloCache MyPlayer(capitalization matters here at the dollar-sign prompt) which will play one game of MyPlayer (black) against MyPlayer2 (white). This will show you what happens during one game between the two -- take a look at the output to make sure it is working.
However, one game is not enough for a fair comparison, since there is a random element. Therefore, play 50 games of MyPlayer (black) against MyPlayer2 (white) by typing:
java OthelloCache scoreonly MyPlayerYou will notice that it takes a while to play all 50 of these games. Take this time to think about why this takes so long: for each game there are about 64 moves; for each move there are between 1 and 10 possible moves; for each possible move the computer must run your function to evaluate the move; this function may involve nested loops.
Also you can play one game of MyPlayer (black) against Edgar (white) -- this will play one game but will list out all the steps and a lot of other junk edgar uses.
java OthelloCache(Note that Edgar was trained on white so he can only be white.) And you can play 50 games of MyPlayer (black) against Edgar (white) -- This will play 50 games and show only the scores of each game, and then the average performance of the players over those 50 games.
java OthelloCache scoreonly
If one player doesn't appear to be absolutely slaughtering the other consistently, you may need even more than 50 games to get an accurate sense of their relative performance. Therefore, you can do a few tournaments to add up to 100 or 200 games.
This will be a simple yet challenging means to apply much of the theory you have learned this semester. And if you're possibly interested in pursuing a major in computer science, it will help you with that decision. If you enjoyed coming up with the algorithm and writing the code, then you may just be suited for the long and prosperous :) road ahead.
Acknowledgements for Part II: Thanks to Himani Naresh for helping write the first draft of this homework assignment, and to Himani Naresh again, as well as Eleazar Eskin and Astro Teller for creating the Java code to do Othello strategies on the web. Thanks to Astro Teller for use of the Edgar code.
email: evs at cs dot columbia dot edu