HW#5: Tic-Tac-Toe Player Due Sunday 10/31

This assignment involves developing a scheme function that can play tic-tac-toe. Your function does not play a game of tic-tac-toe, it just makes a single move. Your function must be named username-player where username is your RCS id. For example, Dave's function would be called hollid2-player and could be called like this:

(hollid2-player board me)

Your function will be passed a representation of the game board and an integer (me) indicating what player you are (1 is X, 2 is O). Your function must produce a list of two integers in the range [0-2], for example your function could return '(1 2) or '(0 0).

Game board representation

The game board is represented by a three element list, the first element represents the first row, the second element represents the second row, ...

Each row is represented by a list of three integers in the range [0-2]. The first element represents the value of the leftmost column, and so on. The value of a cell is encoded as an integer according to the following:

• A 0 indicates an empty cell.

• A 1 indicates an X (player 1 has already picked this cell).

• A 2 indicates an O (player 2 has already picked this cell).

Here are some example boards:

'((0 0 0)
  (0 0 0)
  (0 0 0))

'((1 0 2)
  (0 1 0)
  (0 2 1))

'((2 1 2)
  (2 1 1)
  (0 0 1))

Below are some example ways that your function could be called:

;; test code
(hollid2-player '((0 0 0) (0 0 0) (0 0 0)) 1)
;;
(hollid2-player '((1 1 0) (2 0 0) (0 2 0)) 1)
;;

Return value

The return value indicates the row and column of the move your function is making. You don't return a modified game board, just the row and column of the move. Your moves must be valid (the cell specified by the row and column you return must be empty). For example, the function should produce something like this:

(hollid2-player '((1 1 0) (2 0 0) (0 2 0)) 1)
(list 0 2)

We have a tic-tac-toe game that will be used to pit your functions against other functions. This code will be run using something like this:

(play-game hollid2-player stupid-player)

You don't have access to this code ahead of time, so you need to develop your own test code.

Requirements

Your function must do the following:

• Must win when a win is possible

• Must block a win by the opponent (if you can't win on the same turn)

• Must make only valid moves (empty space)

• Must work as either player 1 (me=1) or player 2 (me=2).

• Must not take more than 10 seconds to run.

• Must not involve more than 2,000,000 lines of code.

Sample Player Code

Below are two sample player functions, one that always takes the first open slot it finds scanning each row in order (called stupid-player), and one that picks a random empty cell (called random-player).

;;
;; stupid-player takes a list (board) and a number, and returns
;;  a list of two integers (a move).
;;
;; stupid-player checks each row looking for an empty space.
;; picks the first empty space it finds.
;;
;;  me is an integer that indicates whether I am player 1 or 2
;;     stupid-player doesn't care...

(define (stupid-player board me)
  (local
  ;; sp-helper recurses on r and c
   ((define (sp-helper r c)
          (cond
	  ;; found an empty slot?
           [(= 0 (cell-value r c board)) (list r c)]
           [ else
                 (cond
		 ;; check everything in current row?
                  [(= c 2) (sp-helper (+ r 1) 0)]
                  [else
                   (sp-helper r (+ c 1))])])))
   (sp-helper 0 0)))
 
 
;;
;; random-player takes a list (board) and number and returns
;;  a list of two integers (a move).
;;  randomly picks a cell, takes it if the cell is empty,
;;  otherwise tries again. 
;;  
;;  me is an integer that indicates whether I am player 1 or 2
;;     random-player doesn't care...

(define (random-player board me)
  (local
   ((define r (random 3))
    (define c (random 3)))
   (cond
        [(= 0 (cell-value r c board)) (list r c)]
        [ else (random-player board me)])))
 

Notes

You do not need to worry about getting invalid boards (with no moves remaining) or anything other than 1 or 2 for me. In other words, you can assume your function will be called properly and does not need to do lots of error checking.

Submission

Submit your functions by 11:59 PM, Sunday, Oct 31st by submitting to the WebCT dropbox labeled "HW5". We will play some tic-tac-toe in clas on Nov 1st.