CS 2360 Assignment 5: Due Midnight Feb 27
Connect 4 (Part 1)
For this part of the assignment you need to write up the
infrastructure necessary to play connect 4. If you are
not familiar with the game, please see me. Also, see
the newsgroup, as I am going to be providing a sample implementation
of assignment for you to experiment with. You will actually
be implementing your connect 4 playing program (in terms
of the state-space search) next time (assignment 6).
For this assignment you need to:
- Build all the necessary ADTs for an implementation of
connect 4 to be built. Your source code should clearly
document how your ADTs work. This includes not only
explanations of the functions on the ADTs but also the
underlying representation, as well as a couple of
examples of each ADT in the abstract and how it is
actually implemented.
- You should implement a scoring function which
can take any legitimate board position and produce an
integer which is its score. This need not be terribly
complex in this part of the project, but certainly
should include detection of wins, simple blocks, and
three tokens in a row. This function should be named
c4-score-board and should take
parameters of the board, the size of the board, and
a color (in that order). (This function needs to
know which color it is scoring for!)
- You should implement a printing function which
can print a nicely formatted version of the board
on the terminal. This function should be called
c4-print-board and should take a
board and the size of the board as its arguments.
- You should implement a function c4-legal-columns
which takes parameters of a board and the size of the
board. It should return a list of legal columns that
can be played in. (This makes sure there is no overflow.)
- You should implement a function which can "slide"
a piece into a given column. (Note: You need to
make sure that it "falls" all the way to the bottom.)
This function must be called c4-slide-in-column
and it should take a board, the size of the board, a
column, and a color. It should return the new board
with the piece added to the appropriate column.
- You should have a function called c4-win-p
which takes a board, the size of the board, and a
color as parameters. It should return true if that
color has won. (The scoring function may be useful
here...)
- You should have a function test0 which takes
an integer as a paramter. This function should
generate an empty board of the specified size and
pass it to the board evaluation function (c4-score-board).
- You should have a function called "test1" which
takes the following board position (in your representation)
and produces a score for it:
+========================+
| _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ |
| _ _ _ _ B _ _ _ |
| _ _ R R R _ _ _ |
| _ _ B R B _ B _ |
| R R B B R _ B _ |
+========================+
You should produce a score for both red and black. This functin
does not take arguments. You will probably want to use
DEFCONST for your board here.
- You should implement another function called test2a
which takes the board position above (again, in your
representation) and sends it to c4-win-p. You
should test both colors for winning.
- You should implement a function called test2b
which takes the following board position and
passes it to the c4-win-p function.
+========================+
| _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ |
| _ _ _ _ B _ _ _ |
| _ _ _ R B _ _ _ |
| _ B R R R _ _ _ |
| _ R B R B _ B _ |
| R R B B R _ B _ |
+========================+
You should test both colors for winning. This function
takes no arguments. You will probably want to use
DEFCONST for your board here.
Assumptions you can and can not make:
- You may assume that the two colors for the connect
4 game are red and black, and that red always goes first.
- You can not assume the size of the board
is fixed at 8. Your code must understand any size board
(although you may assume we won't test this with values
less than 5 as these are not interesting). You may
assume the width and height of the board are the same.
You may find the following piece of code a useful starting
point in developing yourself a "driver" to test with. This
function (from my source) assumes the existance of some
functions not mentioned above, but they are clear enough
that without much work you can probably get this to go.
I issue no warranties either stated or implied about this
code...
;; This is a driver function which will allow you to play connect 4
;; using the computer to detect wins
(defun c4-simple-driver ()
(let ( current-board
current-column
user-input
user-color
(first-move t)
(turn 'R)
(lookahead 2) ;; this is how many tree levels to expand
;;bind this to a larger value if you want a bigger board
(board-size 8))
;; make a new board
(setq current-board (c4-gen-board board-size))
;; ask the user his preference...
(if (y-or-n-p "Do you want to be red and go first?")
(setq user-color 'R)
(setq user-color 'B))
;; loop until we find a winning board... note we check the PREVIOUS
;; color since we get to the top of this loop at a point when the
;; color has already changed
;; this trick with the setq sets the mrb (most recent board) to
;; the one used in this loop... very convenient for debugging
(loop until (or (c4-board-win-p (setq mrb current-board) board-size
(c4-invert-color turn))
;; this check is for stalemate
(null (c4-legal-columns current-board board-size)))
do
;; display the board
(c4-print-board current-board board-size)
;; is it the user 's turn?
(if (equal turn user-color)
(setq current-column
(loop
;; loop until we get a valid response
(if (equal turn 'R)
(format t "You are RED: ")
(format t "You are BLACK: "))
(format t
"Enter a column number to drop a piece into ")
(format t "(1 to ~S):~%" board-size)
(setq user-input (read))
;; make sure its in the right range a member of the valid
;; set of possible choices
(if (and (numberp user-input)
(> user-input 0)
;; modify this line if you play on a larger board
(<= user-input board-size)
(member (1- user-input)
(c4-legal-columns current-board
board-size)
:test #'equal))
(return (1- user-input)))))
(progn
;; this implements the searching for the computer's turn
(format t "%~%Thinking...~%")
;; if its the first time, just save time by not bothering...
(if first-move
(setq current-column (random board-size))
(setq current-column
(c4-choose-column current-board
board-size
lookahead
turn)))
(format t "~%~%Computer chooses: ~S ~%"
(1+ current-column))))
;; make sure we are not on the first turn anymore
;; until you get your searching code done, leave this line
;; commented out so you always pick randomly
;; (setq first-move nil)
;; slide the piece in
(setq current-board (c4-slide-in-column current-board
board-size
current-column
turn))
;; change turns
(if (equal turn 'R)
(setq turn 'B)
(setq turn 'R)))
;; see what result to print
(if (c4-legal-columns current-board board-size)
;; its not a stalemate
(if (equal (c4-invert-color turn) user-color)
(progn
(c4-print-board current-board board-size)
(format t "YOU WIN!~%"))
(progn
(c4-print-board current-board board-size)
(format t "YOU GOT BEAT!~%")))
;; it is a stalemate
(format t "This game is a tie!~%"))))
Back To The CS2360 Home
Page
Ian
Smith (iansmith@cc.gatech.edu)
Last Modified
19 Feb 95 by Ian Smith (iansmith@cc.gatech.edu)