# Othello code information

For this problem, you will create a computer-player for the game of Othello using an alpha-beta minimax search with an evaluation function and depth cutoff. The functions you should turn in are:
• (create-minimax-player eval-fn depth-cutoff)

This function should create a "strategy" (to be explained below) that will call your alpha-beta minimax search function, passing along the evaluation function, the depth cutoff, and any other information necessary.

• (eval-fn board max-player)

Given a board, returns a number to indicate max's potential of winning. max-player will be either 'X or 'O This function must be able to evaluate 8 by 8 Othello boards.

Also include any other functions that they require to run (except for the functions that I have provided to you in othello.scm, of course).

I have written all the functions to manipulate othello boards, get a list of valid moves, get child boards, etc. See the sections below for details.

### Getting started

First, try playing othello against a random strategy. Load the othello.scm code, and evaluate the following expressions:
```  (define board-size 6)

(play-othello human-player random-player)
```

The first expression redefines a global variable that controls the board size. Its default is 8, but I suggest using a smaller size here so that a game takes less time to play.

The second expression runs an Othello game. The play-othello function takes two arguments, both of which are "strategy functions". The first one is the player who will play first, and the first player always plays X.

In case you don't know, you can type C-c C-c in edwin/emacs to quit the game. If you're running it from a shell, type C-g.

### Strategy functions

A strategy function is a function that takes two arguments: a board and the player (i.e. whether it is playing 'X or 'O). It returns the move, specified as a list of two numbers specifying the x and y coordinate of the move.

The human-player strategy function prints out the board, tells you which player you are, asks for your move, and then returns it. Actually, the human-player function will check whether your move is valid and, if not, ask you again for your move.

The random-player strategy function gets a list of the valid moves, chooses one randomly, and returns it.

The function that you are to write:

```(create-minimax-strategy eval-fn depth-cutoff)
```
returns a strategy function. The reasons that I am having you do the assignment this way are:
• because the arguments to your alpha-beta minimax search function will depend on what information you choose to store at a node in your search tree and how you represent that information

• so I can control the depth of your search when testing your functions

There is a sample create-minimax-strategy function (commented out) at the bottom of the othello.scm file.

For each move, your returned strategy function will be called with the current board state. This state should correspond to the root node of the search you will do to determine the best move at this point in the game.

### Tips for writing an alpha-beta MINIMAX search

I highly recommend doing the written alpha-beta search problem before trying to write your implementation in scheme. You can implement alpha-beta search more or less right out of your textbook. However, bear in mind that the algorithms in the text return only the value of the tree, whereas your alpha-beta search algorithm must tell you strategy which move from the current board state (root node of the current search) results in the optimal play.
• Keep in mind the modification that I suggested in class: the line "if alpha >= beta then return alpha" for the max-player and "if beta <= alpha then return beta" for the min-player.
• For your convenience, I have written some functions to do max, min, >=, and <= with real numbers extended to plus and minus infinity. See the section on functions for your alpha-beta search.
• Think about what information you actually need to store at a node and what information your alpha-beta search needs.

### Tips for writing an evaluation function

I suggest you play a few games of Othello against the random strategy (or another person!) You will soon see that certain locations on the board, such as edges and corners, are more important than others.

NOTE: All the testing I will do with your code will be on 8 by 8 boards. However, if you write an evaluation function that also works on 6 by 6 boards, you may have an easier time developing/debugging your code as it takes less time to play a 6 by 6 game.

### Othello Scheme functions for writing your alpha-beta search

```;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
; (othello-end? board)
;
; Returns true if the board represents the end of the game --- when neither
; player has a valid move.  This is usually because the board is full, but
; it can occur earlier in the game.
;

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
; (othello-gc board player)
;
; returns a list of the possible boards that result from a move by the
; given player (the "child boards").  player is either 'X or 'O
;

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
; (othello-valid-moves board player)
;
; For a given board and player (either 'x or 'o), returns a list of valid
; moves available to that player.  The moves are represented by a list of
; two numbers, first the x and then the y coordinate of the move.
;

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
; (other-player p)
;
; Given 'X or 'O, it returns the symbol of the other player
;

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
;    (board-difference b1 b2)
;
;    given two boards which are assumed to differ in only one position (move),
;    return the (x y) coordinate of the move
;
```

The following functions extend the real numbers by adding the symbols 'pos-infinity and 'neg-infinity. I am providing the following functions.

```  (infty-max a b)
(infty-min a b)
(infty->= a b)
(infty-<= a b)
```
For example:
```  (infty-max 7 'pos-infinity)  ==>  'pos-infinity
(infty-<=  2 'neg-infinity)  ==>  #f
```

### Functions for writing an evaluation function

```;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
; Othello board representation and manipulation
;
; These functions deal with the internal representation of the board.
; Other funnctions should access the board using these functions.
;
; For writing an evaluation function for Othello, you should only need
; the following two functions:
;
;    (piece-at board loc)
;
;    Given a board and a location (represented as a list of two numbers,
;    the X and Y coordinates), returns either 'X, 'O, or 'blank
;
;    (tally-board board)
;
;    Returns a list of two numbers.  The first is the number of X pieces
;    on the board, the second is the number of O pieces.
;

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
;  (number-of-flips board loc player)
;
; how many pieces would the given move flip over
;
```

### Function for testing your code

```;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
; (print-board board)
;
; prints an ascii representation of the board to the screen
;
```

### Functions for creating and manipulating Othello boards

Note that all these functions return a new board. See the end of this section for an example.
```;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
; (new-board . input-board)
;
; create a new (blank board), but if a board as given as an optional second
; argument is given, creates a copy of that board instead
;

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
; (initial-board)
;
; creates a new board with the first four pieces in position
;

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
; (othello-make-move board loc player)
;
; makes the move (by "player" at "loc") on the board, returning a new board
; player must be the symbol 'X or 'O.  This function will flip all the
; pieces that need to be flipped.
;
; if the move is invalid, returns 'invalid-move
;
```

Suppose you want to test your evaluation function on some boards, but you need to create a few test boards. If you have a list of moves, you could do something like this:

```(define (make-moves move-list)
(define (mm-helper board move-list player)
(if (null? move-list)
board
(mm-helper (othello-make-move board (car move-list) player)
(cdr move-list)
(other-player player))))
(mm-helper (initial-board) move-list 'x))

(define moves '((4 2) (5 4) (4 5)))

(define board1 (make-moves moves))
```

### Advanced functions for creating and manipulating Othello boards

WARNING --- the functions below that end with an exclamation point (pronounced "bang") destructively modify an Othello board. See the end of this section for details.

```;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
; (play-piece! board loc p)
;
; Destructively modifies the given board by playing a piece of the
; given player ('X or 'O) at the given location.
;

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
; (init-board! board)
;
; place the first four pieces on the board, destructively modifying
; the given board
;
```

Here is a pitfall of destructively modifying boards:

```(define b1 (new-board))
(define b2 b1)
(init-board! b1)
(play-piece! b1 '(4 2) 'x)
```
Boards b1 and b2 are the same! In fact, they point to the same board representation in memory (hence the problem).