I know that a lot of the people reading this are quite brilliant. Before
you read further, let me say that you need not know any programming
languages to help me (although I'm sure a lot of you do). I'm just looking
for some general insights--or stragedies--that anyone can come up on how
they would go about playing the following game. If I can get enough
different perspectives, I can write something to defend against all of them,
and maybe use some of the better offensive suggestions. Thanks in advance
for any time and thought you put into this. With that said, here's the
deal:
I'm working on an assignment for my Introduction to Computer Programming (in
scheme) class. I have to write a progam that plays the game of "21". It's
not define as the card game though.. It's a new game to me and to everyone
else I've talked to, so I'm assuming it's a new game for everyone here as
well. Below are the rules of the game as given to me:
The game is played by 2 players, either or both of which can be
interactive (person) or computer (program) players. The game board
has 5 columns; each player begins with twelve coins: ten of these have
values 0 through 10, one has value -1, and one is a 'block' coin,
whose use is explained below. The players take alternate turns
placing coins into ANY of the 5 columns on the board as long as the
total value of the coins in each column is NOT greater than 21. The
object of the game is to win by creating a column of coins that adds
up to exactly 21, or by preventing the opposing player from having any
legal moves.
A column can be composed of coins placed by either player. Position
within a column does not matter, so each player simply selects a coin
and a column when taking a turn.
The following apply:
1. A player can only play his or her own coins.
2. Only 1 coin may be placed at a turn.
3. A player cannot move coins that are already played.
4. If a player plays their 'block' coin, then their opponent cannot make
their next move in the column containing the block coin. After this
next move either player can play in that column.
5. The -1 coin is similar to any of the coins with values 1 -- 10,
except, of course, its value is -1. There are no restrictions on
its use other than the general ones that apply to the other coins
as well.
6. A player wins if they play a coin that results in a column summing
to 21, or if their opponent (i) makes an illegal move (e.g., tries to
play a nonexistent coin), (ii) plays a coin that results in a column
summing to more than 21, or (iii) runs out of coins.
Example game board
The following is a game board after each player has taken three turns.
Player B (whose coins played are indicated by <>) is the winner in this
game. The total of 21 in Column "one" was obtained when Player B's
<4> coin was added to that column. Note that coins played later
appear higher in the columns.
<4> [-1]
[8] <2>
<9> [4] [3] <10>
one two three four five
What Your Computer Player is Given and What It Should Produce
You will need to write a single move procedure (that may contain its
own local state and several local procedures). This procedure must be
called 'next-move' and must accept two parameters, the current game
board and a list of pieces that the player has not yet used, and
produce as a return value a "move". The formats for the board and
move structures are outlined below. It is important that your player
strictly adheres to these data structures and that it generates legal
moves; otherwise it will not interface correctly with the game referee
and will forfeit the game.
* The "move" data structure: your program should return a pair,
with the first element being the coin played, and the second
being the column where it is played. For example, (10 . 2)
represents playing the 10 coin in the second column, (block . 1)
represents playing the block coin in the first column.
* The "board" data structure: when the referee code calls your
move procedure, it sends the game board as an argument.
The game board your computer player receives is a copy of the
actual game board. So any changes your computer player makes
to it will not affect the actual game board. The game board data
structure is a list of sublists, one for each column:
( col1-list col2-list col3-list col4-list col5-list )
The first element of each sublist is a symbol --- either 'ok
or 'blocked --- indicating whether the next move can be in that
column. The only way for the column to be blocked is if the opposing
player's last move was to put their block coin in this column.
The rest of the sublist contains past moves with each past move
being a pair (coin . player). For example, (3 . a) represents
a coin with value 3 played by player A, and (block . b)
indicates a block coin played by player B. More recent past moves
are at the start of the sublist. For example, if the sublist is
('ok (2 . a) (8 . a) (5 . b)) then the first move in the column
was coin 5 by player B, the second was coin 8 by player A,
and the third was coin 2 by player A.
* The "available-pieces" data structure: when the referee code calls your
move procedure, it sends the available pieces as an argument. This
is also a copy of an available piece list maintained by the referee
code. The list consists of all pieces that the player has not
yet played. The list is ordered, and is originally
(-1 1 2 3 4 5 6 7 8 9 10 block)
This list tells you what pieces are available for the next move.
Note you do not have a corresponding list of what pieces
your opponent has not yet played, although you can construct
such a list from the information in the game board.
Your procedure does not need to update the board or the available
pieces list. The referee code will do this when you return your move
to it.
Example:
Suppose you are player A, so you start first.
A starting (empty) game board and list of available pieces look like this:
( (ok) (ok) (ok) (ok) (ok) )
(-1 1 2 3 4 5 6 7 8 9 10 block)
A game board with only one piece played (a 6 coin from player A) in
column 4 will look like this:
( (ok) (ok) (ok) (ok (6 . a)) (ok) )
A game board with a second piece (a 4 played by player B) added in
column 4:
( (ok) (ok) (ok) (ok (4 . b) (6 . a)) (ok) )
For the next move, the list of pieces available to player A is
(-1 1 2 3 4 5 7 8 9 10 block)
If player A plays their 8 coin in column 2 the game board becomes
( (ok) (ok (8 . a)) (ok) (ok (4 . b) (6 . a)) (ok) )
and the list of available pieces becomes
(-1 1 2 3 4 5 7 9 10 block)
Suppose that player B next plays their block coin in column 2. The game
board becomes
( (ok) (blocked (block . b) (8 . a)) (ok) (ok (4 . b) (6 . a)) (ok) )
Note the difference in use here between the 'block and 'blocked symbols.
Now it will be an illegal move if player A tries to play their next coin
in column 2. Suppose they plan a -1 coin in column 3. The game board
and list of available pieces become
( (ok) (ok (block . b) (8 . a)) (ok (-1 . a)) (ok (4 . b) (6 . a))
(ok) )
(1 2 3 4 5 7 9 10 block)
Notice that column 2 is now available for further play --- the block coin
remains in that column, but it only prevents the move immediately
after it from occurring in that column.
Note also that a move in the game board list is different than a move
returned by your move procedure. A board move does not need to
contain the column because board moves are elements of the column list
for the appropriate board column. On the other hand, a piece on the
game board does contain the player code (either 'a or 'b).
;;;;;;;;;;;;;;;;;;;;;;;;;
;;END RULES.
If this game was played with four columns instead of five, for example, the
player that I'll be writing could just mimic it's opponent. (If it puts a 5
coin in column 1, I put a 5 coin in column 2. If it puts a 7 coin in column
3, I put a 7 coin in column 4).. One could do this until they have a coin
that is equal to the difference between the sum of the coins in a column,
and 21.. and thus win the game everytime they are player B (not the player
that starts the game though).
Below is the code given to me for the ref. If you have any suggestions for
(any advice at all--perhaps a stradegy that you believe is winning) please
email me at ········@umn.edu , or reply to this post. Thanks in advance.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; 21.scm
;
; REFEREE CODE FOR MODIFIED GAME OF 21.
; PLEASE SEE THE INSTRUCTIONS FILE FOR
; EXPLANATIONS OF ITS USE
;
; LAST MODIFIED: 11/12/01
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; Move procedures for testing
;
; random move
(define (move-random board pieces)
(cons (list-ref pieces (random (length pieces))) (+ 1 (random 5))))
; interactive move
(define (move-interactive board pieces)
(let ((coin '())
(column '()))
(display " Enter coin: ")
(set! coin (read))
(display " Enter desired column: ")
(set! column (read))
(cons coin column)))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; Referee code for modified 21 game used as final project in CSci 1901
F2001.
; Everything below this point is internal to 'game.'
; The parameter a-or-b indicates whether the student code is player a or b.
(define (game proc-a proc-b)
(let ((max-cols 5)
(board '((ok) (ok) (ok) (ok) (ok)))
(col-totals '(0 0 0 0 0))
(pieces-a '(-1 1 2 3 4 5 6 7 8 9 10 block))
(pieces-b '(-1 1 2 3 4 5 6 7 8 9 10 block))
(whose-move 'A)
(last-move '()))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; element-of-set? procedure similar to text p 152
(define (element-of-set? item set)
(cond ((null? set) '())
((eq? item (car set)) #t)
(else (element-of-set? item (cdr set)))))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; constructors and selectors for various data structures
(define (make-move coin column) (cons coin column))
(define (make-piece coin owner) (cons coin owner))
(define (make-column block-symbol piece old-column-piece-list)
(if (null? piece)
(cons block-symbol old-column-piece-list)
(append (list block-symbol) (list piece) old-column-piece-list)))
(define (get-move-coin move) (car move))
(define (get-move-column move) (cdr move))
(define (get-piece-value piece) (car piece))
(define (get-piece-owner piece) (cdr piece))
(define (get-board-column-list column) (list-ref board (- column 1)))
(define (get-column-blocked-symbol column-list) (car column-list))
(define (get-column-moves column-list) (cdr column-list))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; if player equals A, returns B, and vice versa
(define (opponent player)
(cond ((eq? player 'A) 'B)
((eq? player 'B) 'A)
(else (error "Bad player symbol in OPPONENT: " player))))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; update procedures
;
; general update procedure
(define (update!)
(begin
(set! board (update-board))
(if (eq? whose-move 'A)
(set! pieces-a (update-pieces pieces-a))
(set! pieces-b (update-pieces pieces-b)))
(set! col-totals (update-col-totals))
(set! whose-move (opponent whose-move))
'ok))
; Return a board containing the previous board
; with the last move included.
(define (update-board)
; will return appropriate block symbol ('blocked or 'ok)
(define (blocked-symbol current-column)
(if (and (= (get-move-column last-move) current-column)
(eq? (get-move-coin last-move) 'block))
'blocked
'ok))
(define (update-board-helper current-column)
(if (> current-column 5)
'()
(cons (make-column (blocked-symbol current-column)
(if (= (get-move-column last-move)
current-column)
(make-piece (get-move-coin last-move)
whose-move)
'())
(get-column-moves
(get-board-column-list current-column)))
(update-board-helper (+ 1 current-column)))))
; start execution of update board here
(update-board-helper 1))
; Given a list of remaining pieces, return an updated list
(define (update-pieces piece-list)
(cond ((null? piece-list)
(error "bad coin in UPDATE PIECES : "
(get-move-coin last-move)))
((eq? (get-move-coin last-move) (car piece-list)) (cdr piece-list))
(else (cons (car piece-list)
(update-pieces (cdr piece-list))))))
; Return an updated column totals list
(define (update-col-totals)
(define (helper current-column)
(if (> current-column 5)
'()
(cons (+ (if (and (= current-column (get-move-column last-move))
(not (eq? (get-move-coin last-move) 'block)))
(get-move-coin last-move)
0)
(list-ref col-totals (- current-column 1)))
(helper (+ 1 current-column)))))
(helper 1))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; check for loss or win procedures:
;
; checks if last move results in a loss or win. If the move prevents
; the opponent from having any valid moves, this will be discovered
; the next time this procedure is called
(define (result-of-move)
(cond ((null? last-move) 'no-move)
((invalid-move-pair) 'invalid-move)
((block-column?) 'blocked-column)
((any-column-greater-than-21?) 'gt21)
((any-column-equals-21?) 'eq21)
(else 'proceed)))
; check if attempt to move onto blocked column
(define (block-column?)
(eq? (get-column-blocked-symbol
(list-ref board (- (get-move-column last-move) 1))) 'blocked))
; check if lst move contains an illegal column number or the coin is not
; one of the available coins.
(define (invalid-move-pair)
(or (> (get-move-column last-move) max-cols)
(< (get-move-column last-move) 1)
(not (element-of-set? (get-move-coin last-move)
(if (eq? whose-move 'A)
pieces-a
pieces-b)))))
; checks if any column total is greater than 21
(define (any-column-greater-than-21?)
(define (helper current-column)
(if (> current-column max-cols)
'()
(or (< 21 (+ (if (and (= current-column (get-move-column
last-move))
(not (eq? (get-move-coin last-move)
'block)))
(get-move-coin last-move)
0)
(list-ref col-totals (- current-column 1))))
(helper (+ 1 current-column)))))
(helper 1))
; checks if any column total equals 21
(define (any-column-equals-21?)
(define (helper current-column)
(if (> current-column max-cols)
'()
(or (= 21 (+ (if (and (= current-column (get-move-column
last-move))
(not (eq? (get-move-coin last-move)
'block)))
(get-move-coin last-move)
0)
(list-ref col-totals (- current-column 1))))
(helper (+ 1 current-column)))))
(helper 1))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; print procedures
;; display the column number
(define (display-col col)
(cond ((= col 1) "one ")
((= col 2) "two ")
((= col 3) "three")
((= col 4) "four ")
((= col 5) "five ")
(else " bad column in DISPLAY-COL ")))
;; find tallest column in board
(define (get-max-board-height ncols)
(if (= ncols 0)
0
(max (length (get-column-moves (get-board-column-list ncols)))
(get-max-board-height (- ncols 1)))))
;; prints labels
(define (print-labels col)
(if (= col max-cols)
(newline)
(begin
(display (display-col (+ col 1)))
(display " ")
(print-labels (+ col 1)))))
;; print pieces in coin list
(define (coin-list-print who pieces)
(if (null? pieces)
'ok
(begin
(if (eq? who 'A)
(display "[")
(display "<"))
(display (car pieces))
(if (eq? who 'A)
(display "]")
(display ">"))
(display " ")
(coin-list-print who (cdr pieces)))))
;; print coin lists
(define (print-coin-lists)
(newline)
(display " Player [A] coins: ")
(coin-list-print 'A pieces-a)
(newline)
(display " Player <B> coins: ")
(coin-list-print 'B pieces-b)
(newline)
(newline))
;; print contents of a single board piece (owner and value)
(define (print-piece piece)
(if (eq? (get-piece-owner piece) 'A)
(begin
(display "[")
(display (get-piece-value piece))
(display "]")
)
(begin
(display "<")
(display (get-piece-value piece))
(display ">")))
(cond ((eq? (get-piece-value piece) 'block)
(display " "))
((or (> (get-piece-value piece) 9)
(< (get-piece-value piece) 0))
(display " "))
(else (display " "))))
;; prints out a single row of the game board
(define (print-row row)
(define (print-row-helper col)
(if (> col max-cols)
'ok
(begin
(let ((move-list (get-column-moves (get-board-column-list
col))))
(if (> row (length move-list))
(display " ")
(print-piece (list-ref move-list (- (length move-list)
row)))))
(print-row-helper (+ col 1)))))
(print-row-helper 1))
;; prints out all board rows recursively from "row" on
(define (printer row)
(if (= row 0)
'ok
(begin
(display " ")
(print-row row)
(newline)
(printer (- row 1)))))
;; displaying and formatting the game board
(define (print-board)
(newline)
(display " --- The Current Board ---")
(newline) (newline)
(printer (get-max-board-height max-cols))
(newline)
(display " ")
(print-labels 0)
(print-coin-lists))
;; displaying move information and user messages
(define (display-move)
(newline)
(display "Coin ")
(if (eq? 'A whose-move)
(display "[")
(display "<"))
(display (get-move-coin last-move))
(if (eq? 'A whose-move)
(display "]")
(display ">"))
(display " requested to be placed in Column ")
(display (display-col (get-move-column last-move)))
(newline)
(newline))
;;;;;;;;;;;;;;;;;;;;;;;;
; copy a list
(define (copy list1)
(cond ((null? list1) '())
((list? (car list1)) (cons (copy (car list1)) (copy (cdr list1))))
(else (cons (car list1) (copy (cdr list1))))))
;;;;;;;;;;;;;;;;;;;;;;;;;
; game end code
(define (game-end result)
(display "*********** GAME ENDS**************")(newline)
(newline)
(cond ((eq? result 'eq21)
(begin (display whose-move)
(display " WINS! ---Scores 21")(newline)))
((eq? result 'gt21)
(begin (display (opponent whose-move))
(display " WINS! --- Opponent move results in")
(display " a column > 21")(newline)))
((eq? result 'invalid-move)
(begin (display (opponent whose-move))
(display " WINS! --- Opponent move has")
(display " bad value or column: ")
(display last-move)(newline)))
((eq? result 'no-move)
(begin (display (opponent whose-move))
(display " WINS! --- Opponent out of coins")
(newline)))
((eq? result 'blocked-column)
(begin (display (opponent whose-move))
(display " WINS! --- Opponent plays on blocked")
(display " column") (newline)))
(else (error "Bad move result in game-end: " result)))
(newline)
(if (eq? result 'invalid-move)
(opponent whose-move)
(begin (update!)
(display "Final board state: ")(newline)
(print-board)
(if (eq? result 'eq21)
(opponent whose-move)
whose-move))))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; main part of code: helper procedure
(define (helper)
(print-board)
(set! last-move (if (eq? whose-move 'A)
(proc-a (copy board) (copy pieces-a))
(proc-b (copy board) (copy pieces-b))))
(display "------")(newline)
(display-move)
(let ((result (result-of-move)))
(if (eq? result 'proceed)
(begin (update!)
(helper))
(game-end result))))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; start execution of 'game' here
(newline) (display "** Welcome to the Game of 21 **") (newline)
(helper)))
In article <············@laurel.tc.umn.edu>, Andy Homan wrote:
>I know that a lot of the people reading this are quite brilliant. Before
>you read further, let me say that you need not know any programming
>languages to help me (although I'm sure a lot of you do).
If that is the case, you should not post your question to a forum where
the discussion is not only specific to programming languages, but in
fact to a particular one.
Since your question is about the algorithm for game play, maybe try asking
in these places:
comp.programming
comp.theory
comp.ai.games
By the way, your program is written in Scheme, not Lisp. There is a Scheme
newsgroup called---unsurprisingly---comp.lang.scheme.