From: mijokijo
Subject: Tic-Tac-Toe help
Date: 
Message-ID: <1169429879.635999.253430@v45g2000cwv.googlegroups.com>
Hey all, I am starting to make my first CL program, the game
tic-tac-toe. My intention is to learn CL, make games, and have fun all
at the same time. Eventually I hope to make a single-player RPG with
CL, but for now I must start with smaller things. So first I want to
make a simple game, tic-tac-toe, but I've run into some earlier issues.

I need to first define the board, so I figured I should be able to make
a simple 3x3 grid structure with ease. Wrong.

I suppose my programming inexperience is to blame, but I'm not sure how
to get this done easily.

I figured I could put the whole structure into a parameter.

I need a 3x3 grid, initial values set for each field (I figured I could
set it to #\_ for now, since I don't need it to be too fancy looking).

I'd like to be able to set the values of each field (when someone makes
a move) in a sane, readable manner (although I'm not sure I'll get that
wish).

The problem is in how I structure the grid. I've evaluated using
hash-tables, plists, and arrays, but I'm not really sure what is
appropriate for this task. I know that, depending on which one I pick,
the code determining if someone won will be different.

What I envision it looking like is as follows:

   ABC
1 _ _ _
2 _ _ _
3 _ _ _

Is this a good way to do so, or is there some other way I've looked
over?

Your help will be greatly appreciated.

From: wooks
Subject: Re: Tic-Tac-Toe help
Date: 
Message-ID: <1169438443.988574.28760@a75g2000cwd.googlegroups.com>
mijokijo wrote:

> Hey all, I am starting to make my first CL program, the game
> tic-tac-toe. My intention is to learn CL, make games, and have fun all
> at the same time. Eventually I hope to make a single-player RPG with
> CL, but for now I must start with smaller things. So first I want to
> make a simple game, tic-tac-toe, but I've run into some earlier issues.
>
> I need to first define the board, so I figured I should be able to make
> a simple 3x3 grid structure with ease. Wrong.
>
> I suppose my programming inexperience is to blame, but I'm not sure how
> to get this done easily.
>
> I figured I could put the whole structure into a parameter.
>
> I need a 3x3 grid, initial values set for each field (I figured I could
> set it to #\_ for now, since I don't need it to be too fancy looking).
>
> I'd like to be able to set the values of each field (when someone makes
> a move) in a sane, readable manner (although I'm not sure I'll get that
> wish).
>
> The problem is in how I structure the grid. I've evaluated using
> hash-tables, plists, and arrays, but I'm not really sure what is
> appropriate for this task. I know that, depending on which one I pick,
> the code determining if someone won will be different.
>
> What I envision it looking like is as follows:
>
>    ABC
> 1 _ _ _
> 2 _ _ _
> 3 _ _ _
>
> Is this a good way to do so, or is there some other way I've looked
> over?
>
> Your help will be greatly appreciated.

http://www.cs.berkeley.edu/~bh/v1ch6/ttt.html
From: Dan Bensen
Subject: Re: Tic-Tac-Toe help
Date: 
Message-ID: <ep2fuk$coj$1@wildfire.prairienet.org>
wooks wrote:
> http://www.cs.berkeley.edu/~bh/v1ch6/ttt.html
 > But in this new situation, the corner square
 > (the move we have to avoid) does block a fork,
 > while the edge square (the correct move)
 > doesn't block a fork!
??
Yes it does.

-- 
Dan
www.prairienet.org/~dsb
From: Ken Tilton
Subject: Re: Tic-Tac-Toe help
Date: 
Message-ID: <izWsh.73$Oh7.35@newsfe09.lga>
mijokijo wrote:
> Hey all, I am starting to make my first CL program, the game
> tic-tac-toe. My intention is to learn CL, make games, and have fun all
> at the same time....

...and get an "A" without even trying!!!


> Eventually I hope to make a single-player RPG with
> CL, 

"Form a diagonal or die trying"? Quake, move over!!

> ...but for now I must start with smaller things.

Like homework?

> So first I want to
> make a simple game, tic-tac-toe, but I've run into some earlier issues.

Thinking?

> 
> I need to first define the board, so I figured I should be able to make
> a simple 3x3 grid structure with ease. Wrong.

Wrong.

> 
> I suppose my programming inexperience is to blame, but I'm not sure how
> to get this done easily.

No, it is your teacher who is to blame. They forgot to tell you that for 
once in your life cheating would not work. Hopefully you are a babe with 
nerds lined up outside your door begging to help.

> 
> I figured I could put the whole structure into a parameter.
> 
> I need a 3x3 grid, initial values set for each field (I figured I could
> set it to #\_ for now, since I don't need it to be too fancy looking).

I believe Ruby has a GRID command. And I love #\_ ... says it all!

> 
> I'd like to be able to set the values of each field (when someone makes
> a move) in a sane, readable manner (although I'm not sure I'll get that
> wish).

No, SETF is a subset of RANDOMF, sometimes it does, sometimes it 
doesn't. (You cannot be sure you'll wish what you get.)

> 
> The problem is in how I structure the grid. I've evaluated using
> hash-tables, plists, and arrays, but I'm not really sure what is
> appropriate for this task

Nested lambdas! Hello?

> I know that, depending on which one I pick,
> the code determining if someone won will be different.

That's life. Riding high in April, shot down in May...

> 
> What I envision it looking like is as follows:
> 
>    ABC
> 1 _ _ _
> 2 _ _ _
> 3 _ _ _
> 
> Is this a good way to do so, or is there some other way I've looked
> over?

Brilliant! yes, encode the thing as a text file with nothing bot X,O, _, 
space, and newline. Setf of an element just rewrites the whole file, 27 
byte--nothing!

> 
> Your help will be greatly appreciated.
> 

Au contraire, you have helped me!! (break my habit of reading this 
moronic NG).

kt

-- 
The Dalai Lama gets the same crap all the time.
   -- Kenny Tilton on c.l.l when accused of immodesty
From: Frank Buss
Subject: Re: Tic-Tac-Toe help
Date: 
Message-ID: <1vn52gfq30a4u.1mzs95bsm3xyz.dlg@40tude.net>
mijokijo wrote:

> Hey all, I am starting to make my first CL program, the game
> tic-tac-toe. My intention is to learn CL, make games, and have fun all
> at the same time. Eventually I hope to make a single-player RPG with
> CL, but for now I must start with smaller things. So first I want to
> make a simple game, tic-tac-toe, but I've run into some earlier issues.

It's difficult to write games in Lisp, use Java:

http://www.frank-buss.de/java/tictactoe/index.html

You still want to use Lisp? Then you can use this as the base for your
tic-tac-toe:

http://www.frank-buss.de/lisp/aqueduct.html

Of course, it uses an array for the board.

-- 
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
From: ············@gmail.com
Subject: Re: Tic-Tac-Toe help
Date: 
Message-ID: <1169458372.339929.58980@v45g2000cwv.googlegroups.com>
Frank Buss ¼g¹D¡G

> mijokijo wrote:
> It's difficult to write games in Lisp, use Java:
   The reason is, I still think you need SDL to make a better game.
   And Lispwork is expensive, while it still builds executives more
4MB,
   which makes small game harder to deliver.
From: Frank Buss
Subject: Re: Tic-Tac-Toe help
Date: 
Message-ID: <1anf0smo0k7qa.1p683tl1ymnu$.dlg@40tude.net>
············@gmail.com wrote:

>    The reason is, I still think you need SDL to make a better game.
>    And Lispwork is expensive, while it still builds executives more
> 4MB,
>    which makes small game harder to deliver.

SDL is a good idea. Take a look at http://www.lispbuilder.org , which I
have initiated. In the last months Luke Crook and others have implemented
many interesting new things and cleaned up the API. Now it can be used for
2D development with SDL, 3D and even sound and music, both on Linux and
Windows (but still some problems on Mac).

I think 4 MB is not a problem for todays computers and internet
connections.

-- 
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
From: Pascal Bourguignon
Subject: Re: Tic-Tac-Toe help
Date: 
Message-ID: <87y7nvnoo5.fsf@thalassa.informatimago.com>
"mijokijo" <········@gmail.com> writes:
> Hey all, I am starting to make my first CL program, the game
> [...]
> I need a 3x3 grid, initial values set for each field (I figured I could
> set it to #\_ for now, since I don't need it to be too fancy looking).

Read some lisp tutorial.  If you don't know which, try one of:
http://www.cliki.net/Online%20Tutorial

(I'd advise: Common Lisp: A Gentle Introduction to Symbolic Computation 
http://www-cgi.cs.cmu.edu/afs/cs.cmu.edu/user/dst/www/LispBook/index.html
)


In lisp, we have a data type not found in other programming languages:
the symbol.  _ is a symbol named "_" (symbols are named by strings,
another datatype).  #\_ is the character underline (another data
type). 

Also, while we are famous for our lists,  we also have
multidimensional arrays.

Create your grid with: (MAKE-ARRAY '(3 3) :INITIAL-ELEMENT '_)
Have fun!


-- 
__Pascal Bourguignon__                     http://www.informatimago.com/

"Our users will know fear and cower before our software! Ship it!
Ship it and let them flee like the dogs they are!"
From: mijokijo
Subject: Re: Tic-Tac-Toe help
Date: 
Message-ID: <1169511195.304699.144220@11g2000cwr.googlegroups.com>
Wow, thanks for all the replies! You have been very helpful (at least
most of you '-_-').

Just so you know that I put for the effort to try it myself first, here
is the code I had for this particular problem up to this point.

(defparameter *grid*
  (list
   (list 'a (list 1 #\_)) (list 'a (list 2 #\_)) (list 'a (list 3 #\_))
   (list 'b (list 1 #\_)) (list 'b (list 2 #\_)) (list 'b (list 3 #\_))
   (list 'c (list 1 #\_)) (list 'c (list 2 #\_)) (list 'c (list 3
#\_))))

(defparameter *array* (make-array '(3 3 3) :initial-contents
				  '(((a a a) (1 2 3) (#\_ #\_ #\_))
				    ((b b b) (1 2 3) (#\_ #\_ #\_))
				    ((c c c) (1 2 3) (#\_ #\_ #\_)))))

(defparameter *plist* (list :a (list :1 #\_ :2 #\_ :3 #\_)
			    :b (list :1 #\_ :2 #\_ :3 #\_)
			    :c (list :1 #\_ :2 #\_ :3 #\_)))

(defparameter *hash* (make-hash-table))

Please don't laugh :(

The first part was an abomination that I regret ever typing down.
Certainly isn't what I would find in that sexy book, PCL.

*array* seemed like the way to go, but I guess I was both grappling
with the syntax and trying to understand a good way to represent each
space. The very helpful article posted by wooks showed me the error of
my ways!

*plist* seemed reasonable, but didn't work as expected :(

I didn't get far after *hash* before I needed to go to bed.

For the record, this is not a class project (I'm not even in school,
yet). However, I think it is a rather interesting coincidence that I
decided on tic-tac-toe as my entry program into Lisp.

I've been eyeing CL-SDL on cliki for making more complex and
interesting games in the future, but lispbuilder seems much more
enticing! Bookmarked for posterity.

Thank you Pascal for the link to that interesting tutorial, and thank
you Dan for the link to your website. I might need to steal some ideas
from you! :)
From: Pascal Bourguignon
Subject: Re: Tic-Tac-Toe help
Date: 
Message-ID: <87y7nupo2h.fsf@thalassa.informatimago.com>
"mijokijo" <········@gmail.com> writes:

> Wow, thanks for all the replies! You have been very helpful (at least
> most of you '-_-').
>
> Just so you know that I put for the effort to try it myself first, here
> is the code I had for this particular problem up to this point.
>
> (defparameter *grid*
>   (list
>    (list 'a (list 1 #\_)) (list 'a (list 2 #\_)) (list 'a (list 3 #\_))
>    (list 'b (list 1 #\_)) (list 'b (list 2 #\_)) (list 'b (list 3 #\_))
>    (list 'c (list 1 #\_)) (list 'c (list 2 #\_)) (list 'c (list 3
> #\_))))
>
> (defparameter *array* (make-array '(3 3 3) :initial-contents
> 				  '(((a a a) (1 2 3) (#\_ #\_ #\_))
> 				    ((b b b) (1 2 3) (#\_ #\_ #\_))
> 				    ((c c c) (1 2 3) (#\_ #\_ #\_)))))
>
> (defparameter *plist* (list :a (list :1 #\_ :2 #\_ :3 #\_)
> 			    :b (list :1 #\_ :2 #\_ :3 #\_)
> 			    :c (list :1 #\_ :2 #\_ :3 #\_)))
>
> (defparameter *hash* (make-hash-table))
>
> Please don't laugh :(

Ok.

There's at least one thing you've got the right idea about: the
details of the actual data structure used doesn't import much indeed.
It could be anything including list of lists, arrays, property lists,
or hash tables.

That's why you'd write something like:

    (defparameter *grid* (make-grid :rows 3 :columns 3 :empty-token '_))

Then you can write things like:

    (grid-ref     *grid* row col)
    (grid-empty-p *grid* row col)
    (setf (grid-ref *grid* 'a 1) 'x)



For the rest, first note that the meaning of :1 is not specified by
CLHS.  Some implementation may give you a keyword named "1", some may
do something entirely different.  You'd have to write :\1 or :|1|.

Then, it's rather unusual to keep the coordinates along inside the
data structure.  It's true that the keys are kept with plist, alist
and hash-table, but because these data structures are used as
dictionaries, for non-regular key ranges.  When you have regular
coordinates, we usually don't include them in the data, but use them
to index inside the data structure.  It's understandable that for the
users we name the rows with a sequence of letters instead of a
integer, but that doesn't prevent your program to keep internally
integers for both the row and the column, and use them to index in an
array or a list of list (or something else).


For example, you could write:

(defun coordinates-to-square-name (row col)
   (format nil "~36R~D" (+ 10 row) (1+ col)))

(defun coordinates-from-square-name (sqname)
   (values (- (parse-integer sqname :end 1 :radix 36) 10)
           (- (parse-integer sqname :start 1) 1)))



C/USER[16]> (coordinates-from-square-name "C3")
2 ;
2
C/USER[17]> (coordinates-from-square-name "B1")
1 ;
0
C/USER[18]> (coordinates-from-square-name "A2")
0 ;
1
C/USER[19]> (coordinates-to-square-name 2 2)
"C3"
C/USER[20]> (coordinates-to-square-name 1 0)
"B1"
C/USER[21]> (coordinates-to-square-name 0 1)
"A2"
C/USER[22]> 



Then you can implement the grid abstraction, for example with arrays:

(defstruct (grid (:constructor %make-grid))
   empty-token
   cells)

(defun make-grid (&key rows columns empty-token)
   (%make-grid :empty-token empty-token
               :cells (make-array (list rows columns)
                                  :initial-element empty-token)))

(defun grid-ref (grid row col)
   (aref (grid-cells grid) row col))

(defun (setf grid-ref) (new-cell grid row col)
   (setf (aref (grid-cells grid) row col) new-cell))

(defun grid-empty-cell-p (grid row col)
   (eql (grid-ref grid row col) (grid-empty-token grid)))



In your program, neve use directly a list, an array, or an hash table
function.  Go thru abstractions such as these grid functions. 

(defparameter *player-token* 'x)

(progn
 (format *query-io* "Enter the coordinates of your play (eg. B2): ")
 (let ((choice (string-trim " " (read-line *query-io*))))
  (if (= 2 (length choice))
   (multiple-value-bind (row col) (coordinates-from-square-name choice)
     (if (grid-empty-cell-p *grid* row col)
         (setf (grid-ref *grid* row col) *player-token*)
         (format *query-io* "This cell at ~A is already occupied.~%"
               (coordinates-to-square-name row col))))
   (format *query-io* "A coordinate must be a letter and a digit.~%"))))


Enter the coordinates of your play (eg. B2): a1
X
C/USER[46]> *grid*
#S(GRID :EMPTY-TOKEN _ :CELLS #2A((X _ _) (_ _ _) (_ _ _)))



-- 
__Pascal Bourguignon__                     http://www.informatimago.com/
You never feed me.
Perhaps I'll sleep on your face.
That will sure show you.
From: mijokijo
Subject: Re: Tic-Tac-Toe help
Date: 
Message-ID: <1169516415.824798.294110@m58g2000cwm.googlegroups.com>
Pascal Bourguignon wrote:
> "mijokijo" <········@gmail.com> writes:
>
> > Wow, thanks for all the replies! You have been very helpful (at least
> > most of you '-_-').
> >
> > Just so you know that I put for the effort to try it myself first, here
> > is the code I had for this particular problem up to this point.
> >
> > (defparameter *grid*
> >   (list
> >    (list 'a (list 1 #\_)) (list 'a (list 2 #\_)) (list 'a (list 3 #\_))
> >    (list 'b (list 1 #\_)) (list 'b (list 2 #\_)) (list 'b (list 3 #\_))
> >    (list 'c (list 1 #\_)) (list 'c (list 2 #\_)) (list 'c (list 3
> > #\_))))
> >
> > (defparameter *array* (make-array '(3 3 3) :initial-contents
> > 				  '(((a a a) (1 2 3) (#\_ #\_ #\_))
> > 				    ((b b b) (1 2 3) (#\_ #\_ #\_))
> > 				    ((c c c) (1 2 3) (#\_ #\_ #\_)))))
> >
> > (defparameter *plist* (list :a (list :1 #\_ :2 #\_ :3 #\_)
> > 			    :b (list :1 #\_ :2 #\_ :3 #\_)
> > 			    :c (list :1 #\_ :2 #\_ :3 #\_)))
> >
> > (defparameter *hash* (make-hash-table))
> >
> > Please don't laugh :(
>
> Ok.
>
> There's at least one thing you've got the right idea about: the
> details of the actual data structure used doesn't import much indeed.
> It could be anything including list of lists, arrays, property lists,
> or hash tables.
>
> That's why you'd write something like:
>
>     (defparameter *grid* (make-grid :rows 3 :columns 3 :empty-token '_))
>
> Then you can write things like:
>
>     (grid-ref     *grid* row col)
>     (grid-empty-p *grid* row col)
>     (setf (grid-ref *grid* 'a 1) 'x)
>
>
>
> For the rest, first note that the meaning of :1 is not specified by
> CLHS.  Some implementation may give you a keyword named "1", some may
> do something entirely different.  You'd have to write :\1 or :|1|.
>
> Then, it's rather unusual to keep the coordinates along inside the
> data structure.  It's true that the keys are kept with plist, alist
> and hash-table, but because these data structures are used as
> dictionaries, for non-regular key ranges.  When you have regular
> coordinates, we usually don't include them in the data, but use them
> to index inside the data structure.  It's understandable that for the
> users we name the rows with a sequence of letters instead of a
> integer, but that doesn't prevent your program to keep internally
> integers for both the row and the column, and use them to index in an
> array or a list of list (or something else).
>
>
> For example, you could write:
>
> (defun coordinates-to-square-name (row col)
>    (format nil "~36R~D" (+ 10 row) (1+ col)))
>
> (defun coordinates-from-square-name (sqname)
>    (values (- (parse-integer sqname :end 1 :radix 36) 10)
>            (- (parse-integer sqname :start 1) 1)))
>
>
>
> C/USER[16]> (coordinates-from-square-name "C3")
> 2 ;
> 2
> C/USER[17]> (coordinates-from-square-name "B1")
> 1 ;
> 0
> C/USER[18]> (coordinates-from-square-name "A2")
> 0 ;
> 1
> C/USER[19]> (coordinates-to-square-name 2 2)
> "C3"
> C/USER[20]> (coordinates-to-square-name 1 0)
> "B1"
> C/USER[21]> (coordinates-to-square-name 0 1)
> "A2"
> C/USER[22]>
>
>
>
> Then you can implement the grid abstraction, for example with arrays:
>
> (defstruct (grid (:constructor %make-grid))
>    empty-token
>    cells)
>
> (defun make-grid (&key rows columns empty-token)
>    (%make-grid :empty-token empty-token
>                :cells (make-array (list rows columns)
>                                   :initial-element empty-token)))
>
> (defun grid-ref (grid row col)
>    (aref (grid-cells grid) row col))
>
> (defun (setf grid-ref) (new-cell grid row col)
>    (setf (aref (grid-cells grid) row col) new-cell))
>
> (defun grid-empty-cell-p (grid row col)
>    (eql (grid-ref grid row col) (grid-empty-token grid)))
>
>
>
> In your program, neve use directly a list, an array, or an hash table
> function.  Go thru abstractions such as these grid functions.
>
> (defparameter *player-token* 'x)
>
> (progn
>  (format *query-io* "Enter the coordinates of your play (eg. B2): ")
>  (let ((choice (string-trim " " (read-line *query-io*))))
>   (if (= 2 (length choice))
>    (multiple-value-bind (row col) (coordinates-from-square-name choice)
>      (if (grid-empty-cell-p *grid* row col)
>          (setf (grid-ref *grid* row col) *player-token*)
>          (format *query-io* "This cell at ~A is already occupied.~%"
>                (coordinates-to-square-name row col))))
>    (format *query-io* "A coordinate must be a letter and a digit.~%"))))
>
>
> Enter the coordinates of your play (eg. B2): a1
> X
> C/USER[46]> *grid*
> #S(GRID :EMPTY-TOKEN _ :CELLS #2A((X _ _) (_ _ _) (_ _ _)))
>
>
>
> --
> __Pascal Bourguignon__                     http://www.informatimago.com/
> You never feed me.
> Perhaps I'll sleep on your face.
> That will sure show you.

D-D-Dang, never expected that! Now I need to study the code you're
giving me so that I understand it :) I'm especially interested in how
coordinates-to-square-name and coordinates-from-square-name work. I
will devote special attention to understanding that, tomorrow. 30
minutes to heroes...

Thanks again, you've have been far more helpful than I could have hoped.
From: mijokijo
Subject: Re: Tic-Tac-Toe help
Date: 
Message-ID: <1169607491.849407.102250@v45g2000cwv.googlegroups.com>
On Jan 22, 6:46 pm, Pascal Bourguignon <····@informatimago.com> wrote:
> "mijokijo" <········@gmail.com> writes:
> > Wow, thanks for all the replies! You have been very helpful (at least
> > most of you '-_-').
>
> > Just so you know that I put for the effort to try it myself first, here
> > is the code I had for this particular problem up to this point.
>
> > (defparameter *grid*
> >   (list
> >    (list 'a (list 1 #\_)) (list 'a (list 2 #\_)) (list 'a (list 3 #\_))
> >    (list 'b (list 1 #\_)) (list 'b (list 2 #\_)) (list 'b (list 3 #\_))
> >    (list 'c (list 1 #\_)) (list 'c (list 2 #\_)) (list 'c (list 3
> > #\_))))
>
> > (defparameter *array* (make-array '(3 3 3) :initial-contents
> >                              '(((a a a) (1 2 3) (#\_ #\_ #\_))
> >                                ((b b b) (1 2 3) (#\_ #\_ #\_))
> >                                ((c c c) (1 2 3) (#\_ #\_ #\_)))))
>
> > (defparameter *plist* (list :a (list :1 #\_ :2 #\_ :3 #\_)
> >                        :b (list :1 #\_ :2 #\_ :3 #\_)
> >                        :c (list :1 #\_ :2 #\_ :3 #\_)))
>
> > (defparameter *hash* (make-hash-table))
>
> > Please don't laugh :(Ok.
>
> There's at least one thing you've got the right idea about: the
> details of the actual data structure used doesn't import much indeed.
> It could be anything including list of lists, arrays, property lists,
> or hash tables.
>
> That's why you'd write something like:
>
>     (defparameter *grid* (make-grid :rows 3 :columns 3 :empty-token '_))
>
> Then you can write things like:
>
>     (grid-ref     *grid* row col)
>     (grid-empty-p *grid* row col)
>     (setf (grid-ref *grid* 'a 1) 'x)
>
> For the rest, first note that the meaning of :1 is not specified by
> CLHS.  Some implementation may give you a keyword named "1", some may
> do something entirely different.  You'd have to write :\1 or :|1|.
>
> Then, it's rather unusual to keep the coordinates along inside the
> data structure.  It's true that the keys are kept with plist, alist
> and hash-table, but because these data structures are used as
> dictionaries, for non-regular key ranges.  When you have regular
> coordinates, we usually don't include them in the data, but use them
> to index inside the data structure.  It's understandable that for the
> users we name the rows with a sequence of letters instead of a
> integer, but that doesn't prevent your program to keep internally
> integers for both the row and the column, and use them to index in an
> array or a list of list (or something else).
>
> For example, you could write:
>
> (defun coordinates-to-square-name (row col)
>    (format nil "~36R~D" (+ 10 row) (1+ col)))
>
> (defun coordinates-from-square-name (sqname)
>    (values (- (parse-integer sqname :end 1 :radix 36) 10)
>            (- (parse-integer sqname :start 1) 1)))
>
> C/USER[16]> (coordinates-from-square-name "C3")
> 2 ;
> 2
> C/USER[17]> (coordinates-from-square-name "B1")
> 1 ;
> 0
> C/USER[18]> (coordinates-from-square-name "A2")
> 0 ;
> 1
> C/USER[19]> (coordinates-to-square-name 2 2)
> "C3"
> C/USER[20]> (coordinates-to-square-name 1 0)
> "B1"
> C/USER[21]> (coordinates-to-square-name 0 1)
> "A2"
> C/USER[22]>
>
> Then you can implement the grid abstraction, for example with arrays:
>
> (defstruct (grid (:constructor %make-grid))
>    empty-token
>    cells)
>
> (defun make-grid (&key rows columns empty-token)
>    (%make-grid :empty-token empty-token
>                :cells (make-array (list rows columns)
>                                   :initial-element empty-token)))
>
> (defun grid-ref (grid row col)
>    (aref (grid-cells grid) row col))
>
> (defun (setf grid-ref) (new-cell grid row col)
>    (setf (aref (grid-cells grid) row col) new-cell))
>
> (defun grid-empty-cell-p (grid row col)
>    (eql (grid-ref grid row col) (grid-empty-token grid)))
>
> In your program, neve use directly a list, an array, or an hash table
> function.  Go thru abstractions such as these grid functions.
>
> (defparameter *player-token* 'x)
>
> (progn
>  (format *query-io* "Enter the coordinates of your play (eg. B2): ")
>  (let ((choice (string-trim " " (read-line *query-io*))))
>   (if (= 2 (length choice))
>    (multiple-value-bind (row col) (coordinates-from-square-name choice)
>      (if (grid-empty-cell-p *grid* row col)
>          (setf (grid-ref *grid* row col) *player-token*)
>          (format *query-io* "This cell at ~A is already occupied.~%"
>                (coordinates-to-square-name row col))))
>    (format *query-io* "A coordinate must be a letter and a digit.~%"))))
>
> Enter the coordinates of your play (eg. B2): a1
> X
> C/USER[46]> *grid*
> #S(GRID :EMPTY-TOKEN _ :CELLS #2A((X _ _) (_ _ _) (_ _ _)))
>
> --
> __Pascal Bourguignon__                    http://www.informatimago.com/
> You never feed me.
> Perhaps I'll sleep on your face.
> That will sure show you.

I've been looking at this code all day (although it short spurts).

I now understand that you're using a base 36 system for working the
coordinates. I had to look that, along with radixes, up to understand
coordinates-to-square-name and coordinates-from-square-name. Probably
not something I would have thought up myself, but now I understand a
bit more how that works. From the recent reply by Thomas where he
points how the coordinate system I am using is 1-based, and I think I
may understand now why you add 10 and 1 to the row and column in
coordinates-to-square-name, and the inverse for
coordinates-from-square-name. I'll have to be mindful of that.

I especially like your example of defstructs. I'm not sure if
defstructs are used in PCL (maybe in some of the chapters I haven't
read yet), but they are cool. Very powerful and concise. Sounds like
math :P

Macros are just plain awesome. PCL makes it plainly obvious, and the
expressiveness of it just the icing on the cake. Instead of saying,
"Set the value of this space in an array to this value", I can say,
"Set the value of this place on the board to this value." Crazy.

One question though. I've looked at the hyperspec for parse-integer,
but it doesn't really explain to me how :end and :start affect the
value parse-integer will return. I'm not sure how it works, so perhaps
you may be able to teach me that?
From: D Herring
Subject: Re: Tic-Tac-Toe help
Date: 
Message-ID: <b7mdna8HHe8rfCvYnZ2dnUVZ_oGlnZ2d@comcast.com>
mijokijo wrote:
> One question though. I've looked at the hyperspec for parse-integer,
> but it doesn't really explain to me how :end and :start affect the
> value parse-integer will return. I'm not sure how it works, so perhaps
> you may be able to teach me that?

"Start" and "end" are two common parameters in Lisp; for a given 
sequence, they tell the function to use subset of that sequence.  Start 
gives the 0-indexed position of the first entry to use; end gives the 
0-indexed position after the last entry to use.

So

(setq sum (parse-integer "12345" :start 1 :end 3))

is essentially the same as the following C code:

char *str="12345";
int start=1;
int end=3;
int i;
int sum=0;
for(i=start; i<end; i++)
{
   sum=10*sum + (str[i]-'0');
}

both should result in sum==23.

When :start or :end are not given, they default to the beginning and end 
of the sequence, respectively.  The CLHS entry for SUBSEQ may be helpful.

- Daniel
From: Pascal Bourguignon
Subject: Re: Tic-Tac-Toe help
Date: 
Message-ID: <87ejpkewmr.fsf@thalassa.informatimago.com>
"mijokijo" <········@gmail.com> writes:

> One question though. I've looked at the hyperspec for parse-integer,
> but it doesn't really explain to me how :end and :start affect the
> value parse-integer will return. I'm not sure how it works, so perhaps
> you may be able to teach me that?

:start and :end specify the range of the substring to be considered
by parse-integer.

    (parse-integer str :start start :end end) 

is equivalent to:

    (parse-integer (subseq str start end))

[but without the creation of a new string].


So in the case of coordinates-from-square-name, we parse an integer
first consisting only of the first character of the strirng, and next
consisting of all remaining characters but the first.




The first line of the description of parse-integer says:

     parse-integer parses an integer in the specified radix from the
     substring of string delimited by start and end.


-- 
__Pascal Bourguignon__                     http://www.informatimago.com/
I need a new toy.
Tail of black dog keeps good time.
Pounce! Good dog! Good dog!
From: mijokijo
Subject: Re: Tic-Tac-Toe help
Date: 
Message-ID: <1169695772.589063.309750@q2g2000cwa.googlegroups.com>
Thank you, both Pascal and D Herring, you've both been very helpful.
I'll stay diligent and keep you posted on my progress.
From: Thomas A. Russ
Subject: Re: Tic-Tac-Toe help
Date: 
Message-ID: <ymimz49cnca.fsf@sevak.isi.edu>
"mijokijo" <········@gmail.com> writes:

> (defparameter *array* (make-array '(3 3 3) :initial-contents
> 				  '(((a a a) (1 2 3) (#\_ #\_ #\_))
> 				    ((b b b) (1 2 3) (#\_ #\_ #\_))
> 				    ((c c c) (1 2 3) (#\_ #\_ #\_)))))

I'll concentrate on this one and give a simpler, but greatly less
instructive solution than Pascal's.

First comment:  The dimensions of an array specify the size.  If you
want a 3x3 grid, then you use the dimensions '(3 3).  In your example,
you have a 3-dimensional array, namely 3x3x3.  You probably don't really
want that, since you would really prefer to have your dimensions and
indices be implicit and thus outside the array data structure.  That
makes it a lot simpler as well.

Symbols might also be more Lisp-like than characters.  That's what
Pascal uses, and I will too.

As for the input coordinates, you have 1-based indexing.  The standard
arrays in Lisp and most other computer languages are zero-based -- for the
convenience of the compiler ;)  I'll go with your 1-based indexing,
although it means you have to write your own access code.  Fortunately
that won't be too hard, although it does mean I will introduce a macro.

OK, here we go:

(defparameter *board* (make-array '(3 3) :initial-contents '((_ _ _)
                                                             (_ _ _)
                                                             (_ _ _)))


;; Define constants for the column accessors.
;; I normally wouldn't do this, but it does make things cleaner for this
;; small example.

(defconstant a 1)
(defconstant b 1)
(defconstant c 1)


(defmacro cell (board row column)
  "Acccesor for row, column of a board.  Transforms index to 0-based."
  `(aref ,board (1- ,row) (1- ,column)))


Now you have the data structure and an accessor macro.  Using a macro
that expands into AREF is helpful since the built-in SETF operator knows
how to modify AREF expressions.  That means you can do the following:

;; Get a value:

(cell *board* 2 b)

;; Set a value:

(setf (cell *board* 2 b) 'x)

;; Display the board:

*board*





-- 
Thomas A. Russ,  USC/Information Sciences Institute
From: ·····@yahoo.com
Subject: Check multiple CLs Re: Tic-Tac-Toe help
Date: 
Message-ID: <1169578800.373714.288190@j27g2000cwj.googlegroups.com>
mijokijo wrote:
> Hey all, I am starting to make my first CL program, the game

Has CLisp been to lenient for lambda lists ?

(defun load-board ((board-file "sudokblank.lisp"))
  (with-open-file (board-stream board-file)
    (read board-stream)))

I needed to make default value bindings
&optional for ABCL & SBCL


The REPL made me think -
;      (print-board (eval-board (read-board)))


which made me wonder if Model-View-Controller was
;      (view (model (controller)))
but one diagram, showed 2 way messages between some parts
(I never found the 4th color SmallTalk book)


--- sudokblank.lisp
;;;;
;;;
;;
;

#2A(
(0 0 0  0 0 0  0 0 0)
(0 0 0  0 0 0  0 0 0)
(0 0 0  0 0 0  0 0 0)

(0 0 0  0 0 0  0 0 0)
(0 0 0  0 0 0  0 0 0)
(0 0 0  0 0 0  0 0 0)

(0 0 0  0 0 0  0 0 0)
(0 0 0  0 0 0  0 0 0)
(0 0 0  0 0 0  0 0 0)
)
---END
From: Pascal Bourguignon
Subject: Re: Check multiple CLs Re: Tic-Tac-Toe help
Date: 
Message-ID: <87r6tldixh.fsf@thalassa.informatimago.com>
·····@yahoo.com writes:

> mijokijo wrote:
>> Hey all, I am starting to make my first CL program, the game
>
> Has CLisp been to lenient for lambda lists ?
>
> (defun load-board ((board-file "sudokblank.lisp"))
>   (with-open-file (board-stream board-file)
>     (read board-stream)))
>
> I needed to make default value bindings
> &optional for ABCL & SBCL

In clisp (2.41) too, as specified by the standard:

C/USER[12]> (defun load-board ((board-file "sudokblank.lisp"))
  (with-open-file (board-stream board-file)
    (read board-stream)))

*** - FUNCTION: (BOARD-FILE "sudokblank.lisp") is not a symbol
The following restarts are available:
USE-VALUE      :R1      You may input a value to be used instead.
ABORT          :R2      ABORT
C/Break 1 USER[13]> 



-- 
__Pascal Bourguignon__                     http://www.informatimago.com/

NEW GRAND UNIFIED THEORY DISCLAIMER: The manufacturer may
technically be entitled to claim that this product is
ten-dimensional. However, the consumer is reminded that this
confers no legal rights above and beyond those applicable to
three-dimensional objects, since the seven new dimensions are
"rolled up" into such a small "area" that they cannot be
detected.
From: John Thingstad
Subject: Re: Tic-Tac-Toe help
Date: 
Message-ID: <op.tmmpsfn9pqzri1@pandora.upc.no>
On Mon, 22 Jan 2007 02:37:59 +0100, mijokijo <········@gmail.com> wrote:

> Hey all, I am starting to make my first CL program, the game
> tic-tac-toe. My intention is to learn CL, make games, and have fun all
> at the same time. Eventually I hope to make a single-player RPG with
> CL, but for now I must start with smaller things. So first I want to
> make a simple game, tic-tac-toe, but I've run into some earlier issues.
>
> I need to first define the board, so I figured I should be able to make
> a simple 3x3 grid structure with ease. Wrong.
>
> I suppose my programming inexperience is to blame, but I'm not sure how
> to get this done easily.
>
> I figured I could put the whole structure into a parameter.
>
> I need a 3x3 grid, initial values set for each field (I figured I could
> set it to #\_ for now, since I don't need it to be too fancy looking).
>
> I'd like to be able to set the values of each field (when someone makes
> a move) in a sane, readable manner (although I'm not sure I'll get that
> wish).
>
> The problem is in how I structure the grid. I've evaluated using
> hash-tables, plists, and arrays, but I'm not really sure what is
> appropriate for this task. I know that, depending on which one I pick,
> the code determining if someone won will be different.
>
> What I envision it looking like is as follows:
>
>    ABC
> 1 _ _ _
> 2 _ _ _
> 3 _ _ _
>
> Is this a good way to do so, or is there some other way I've looked
> over?
>
> Your help will be greatly appreciated.
>

Well I just wrote a tic-tac-toe program and will publish it on my website  
shortly.
I am really doing this to test CAPI but I thought I would export a all  
text version
so anyone can test it. Anyhow my website is:

home.chello.no/~jthing

-- 
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
From: John Thingstad
Subject: Re: Tic-Tac-Toe help
Date: 
Message-ID: <op.tmnqynzjpqzri1@pandora.upc.no>
On Tue, 23 Jan 2007 23:51:41 +0100, John Thingstad  
<··············@chello.no> wrote:

>
> Well I just wrote a tic-tac-toe program and will publish it on my  
> website shortly.
> I am really doing this to test CAPI but I thought I would export a all  
> text version
> so anyone can test it. Anyhow my website is:
>
> home.chello.no/~jthing
>

Well it's up now.
The stratergy is a bit lame.

line in this context is assumed to be vertical, horizonatal, diagonal or  
bidiagonal

1. If you have two on one line and the remaining square is blank the take  
the blank
2. If the oponent has two on a line and the remaining square is blank take  
it
3. if the center is available take it
4. if corners are available pick one
5. pick a arbitrary square

Noted a big problem.. Given a board

    1 2 3
A  - - -
B  - - -
C  - - -

I play

X--
---
---

computer always playes

X--
-O-
---

I play

X--
-O-
--X

Now I can't loose.

It takes a corner.
I take the other.

X-X
-O-
O-X

Now either which one it blocks I win..
Guess I should find a better stratergy for the computer...

But for now here goes.

-- 
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
From: John Thingstad
Subject: Re: Tic-Tac-Toe help
Date: 
Message-ID: <op.tmn0mdb3pqzri1@pandora.upc.no>
On Wed, 24 Jan 2007 13:14:37 +0100, John Thingstad  
<··············@chello.no> wrote:

Help me!
I am thouroughly miserable with this code.
The algorithm is wrong.
Many of the optimations don't turn out as planned.
The structure got perverted by adding detail.
I'd like to have a decent program for once. To look back on.
Use as a example. But this ain't it.
Before i ditch it.. Does anyone see what I missed.

-- 
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
From: ·········@gmail.com
Subject: Re: Tic-Tac-Toe help
Date: 
Message-ID: <1169656922.159967.30800@v45g2000cwv.googlegroups.com>
Just a small preamble.

I wrote a tic tac toe program in lisp over a couple of days during
Christmas break.   It was both an act of learning (I'm still relatively
new to lisp) and an act of self-defence.  I have a nephew who's at that
age where he always wants to play tic tac toe, and he doesn't realize
that it's a draw all of the time.  I figured if I wrote the program, he
could play it constantly instead of me :).

> Before i ditch it.. Does anyone see what I missed.

I didn't look at your code too closely, but I wanted to suggest that
you use a Minimax strategy in figuring out the best move for the
computer, rather than some heuristic approach (which is what I think
you're currently doing).  The game tree for tic tac toe is small, and
can be easily searched in real-time.  The Minimax algorithm will
automatically find the right move -- assuming you code it corectly --
in the "problem" scenario you describe in a previous post.

If you don't have an AI text book, take a look at the Wikipedia
description.

L8r.
--
Belfabius
From: John Thingstad
Subject: Re: Tic-Tac-Toe help
Date: 
Message-ID: <op.tmph20wupqzri1@pandora.upc.no>
On Wed, 24 Jan 2007 16:43:15 +0100, John Thingstad  
<··············@chello.no> wrote:

> On Wed, 24 Jan 2007 13:14:37 +0100, John Thingstad  
> <··············@chello.no> wrote:
>
> Help me!
> I am thouroughly miserable with this code.
> The algorithm is wrong.
> Many of the optimations don't turn out as planned.
> The structure got perverted by adding detail.
> I'd like to have a decent program for once. To look back on.
> Use as a example. But this ain't it.
> Before i ditch it.. Does anyone see what I missed.
>

Ok added quick fix.
rule 2.5
If it's your first move and the other guy has a corner then
take the oposing corner.

This is probaly not as good as minimax which is guaranteed to at win
or draw. But I don't think there are any other ways that you can make
the computer loose every time at least.

-- 
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
From: Nils M Holm
Subject: Re: Tic-Tac-Toe help
Date: 
Message-ID: <epa6m8$8ki$1@online.de>
John Thingstad <··············@chello.no> wrote:
> This is probaly not as good as minimax which is guaranteed to at win
> or draw. But I don't think there are any other ways that you can make
> the computer loose every time at least.

I think that minimax is overkill for ttt. I have once written a
ttt program that uses very few simple rules and I have not heard
that anybody ever beat it. It beats me from time to time, though. ;-)

Here are the rules (lefthand side is a pattern, righthand side is
the move to make, each rule is applied to each horizontal, vertical
and diagonal):

'(((_ o o)  (o o o)) 
  ((o _ o)  (o o o)) 
  ((o o _)  (o o o)) 
  ((_ x x)  (o x x)) 
  ((x _ x)  (x o x)) 
  ((x x _)  (x x o)) 
  ((_ x _)  (o x _)) 
  ((_ _ x)  (_ o x)) 
  ((x _ _)  (x o _)) 
  ((_ x o)  (o x o)) 
  ((_ o x)  (o o x)) 
  ((x _ o)  (x o o)) 
  ((x o _)  (x o o)) 
  ((o _ x)  (o o x)) 
  ((o x _)  (o x o)) 
  ((_ _ o)  (o _ o)) 
  ((_ o _)  (o o _)) 
  ((o _ _)  (o _ o)) 
  ((_ _ _)  (_ o _))))

The full source code is here: http://www.t3x.org/pstk/ttt.scm

-- 
Nils M Holm <n m h @ t 3 x . o r g> -- http://t3x.org/nmh/
From: John Thingstad
Subject: Re: Tic-Tac-Toe help
Date: 
Message-ID: <op.tmpnhzt8pqzri1@pandora.upc.no>
On Thu, 25 Jan 2007 13:09:44 +0100, Nils M Holm  
<·················@online.de> wrote:

> John Thingstad <··············@chello.no> wrote:
>> This is probaly not as good as minimax which is guaranteed to at win
>> or draw. But I don't think there are any other ways that you can make
>> the computer loose every time at least.
>
> I think that minimax is overkill for ttt. I have once written a
> ttt program that uses very few simple rules and I have not heard
> that anybody ever beat it. It beats me from time to time, though. ;-)
>
> Here are the rules (lefthand side is a pattern, righthand side is
> the move to make, each rule is applied to each horizontal, vertical
> and diagonal):
>
> '(((_ o o)  (o o o))
>   ((o _ o)  (o o o))
>   ((o o _)  (o o o))
>   ((_ x x)  (o x x))
>   ((x _ x)  (x o x))
>   ((x x _)  (x x o))
>   ((_ x _)  (o x _))
>   ((_ _ x)  (_ o x))
>   ((x _ _)  (x o _))
>   ((_ x o)  (o x o))
>   ((_ o x)  (o o x))
>   ((x _ o)  (x o o))
>   ((x o _)  (x o o))
>   ((o _ x)  (o o x))
>   ((o x _)  (o x o))
>   ((_ _ o)  (o _ o))
>   ((_ o _)  (o o _))
>   ((o _ _)  (o _ o))
>   ((_ _ _)  (_ o _))))
>
> The full source code is here: http://www.t3x.org/pstk/ttt.scm
>

Thanks! But I think I will let it stay the way it is for now.
By the look of it it covers most of the cases you stated anyhow.
If you look at my website you might note that there is a sort of
order to the madness.

http://home.chello.no/~jthing

Russian roulette is usually the first program I write when trying to learn
a new language. It teaches me decision, looping, variable declaration,
input from user, output to screen and random decision.
All I need to start and in a compact form.

There is a word game - hangman.
A simulation - Star-Trek

The three remaining programs use search for solving.

Mastermind - exhaustive search
Tic Tac Toe - Heuristic search (debatable)
Othello - Minimax search with alpha beta cutoff

I guess I should add a text based adventure someday :)

Beyond that I recommend studying Hex..
There is a great and original algorithm out there first
implementing using analog circuits by Claude Shannon.

Might be usable for Go etc. which are not solved well by search.
(To many opening moves makes a to broad tree.)

-- 
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/