Othello code information

• (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.

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

  (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

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)

• 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

• 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

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)

  (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

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
; (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

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
; (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)