This doesn't seem to work in sbcl:
(let ((grid1 (make-array '(3 3)
:element-type 'standard-char
:initial-element #\space)))
(write grid1)
(let ((grid2 (make-array '(3 3)
:element-type 'standard-char
:initial-contents grid1)))
(write grid2)))
-------------------------------------------------------------------
Output:
malformed :INITIAL-CONTENTS: #2A((#\ #\ #\ )
(#\ #\ #\ )
(#\ #\
#\ )) is not a sequence, but 2 more
layers needed.
-------------------------------------------------------------------
That's a strange line break in the middle of the bottom row.
Can this work somehow, or do you have to iterate through the arrays
explicitly?
--
My name is dsb, and I'm at prairienet, which is an O-R-G.
In article <············@wildfire.prairienet.org>,
Dan Bensen <···········@cyberspace.net> wrote:
> This doesn't seem to work in sbcl:
>
> (let ((grid1 (make-array '(3 3)
> :element-type 'standard-char
> :initial-element #\space)))
> (write grid1)
> (let ((grid2 (make-array '(3 3)
> :element-type 'standard-char
> :initial-contents grid1)))
> (write grid2)))
> -------------------------------------------------------------------
>
> Output:
>
> malformed :INITIAL-CONTENTS: #2A((#\ #\ #\ )
> (#\ #\ #\ )
> (#\ #\
> #\ )) is not a sequence, but 2 more
> layers needed.
> -------------------------------------------------------------------
>
> That's a strange line break in the middle of the bottom row.
>
> Can this work somehow, or do you have to iterate through the arrays
> explicitly?
You could use displaced arrays:
(let* ((grid1 (make-array '(3 3) ...))
(grid1-vector (make-array 9 ... :displaced-to grid1))
(grid2-vector (make-array 9 ... :initial-contents grid1-vector))
(grid2 (make-array '(3 3) ... :displaced-to grid2-vector)))
(write grid2))
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***
Barry Margolin wrote:
> You could use displaced arrays:
>
Completely at a tangent, but displaced arrays probably have exciting
performance implications because of aliasing &c. Though it may
actually be that there isn't an issue because you can always tell early
enough whether or not two arrays share storage that you can raise it
out of any loop (in fact that must be the case I think). I guess
serious compilers would then have to be willing to generate different
code paths for the two cases though.
--tim
On 2006-08-30 00:06:34 -0400, Dan Bensen <···········@cyberspace.net> said:
> Can this work somehow, or do you have to iterate through the arrays explicitly?
You can use copy-array from cl-utilities:
<http://common-lisp.net/cgi-bin/viewcvs.cgi/cl-utilities/copy-array.lisp?root=cl-utilities&view=markup>
The
whole cl-utilities project is at:
<http://common-lisp.net/project/cl-utilities/>
Raffael Cavallaro wrote:
> You can use copy-array from cl-utilities:
Thanks.
Barry Margolin wrote:
> You could use displaced arrays:
The point is to change grid2 without affecting grid1.
Also, grid1 is passed to a function that needs grid2. Can you pass
grid1 as a read-only arg to create grid2 inside the function? Is there
a way to protect grid1 from code inside the function without creating
grid2 outside?
--
My name is dsb, and I'm at prairienet, which is an O-R-G.
Dan Bensen wrote:
> Also, grid1 is passed to a function that needs grid2.
Wait, scratch that. grid2 is passed after it's created and modified
outside the func. Sorry.
--
My name is dsb, and I'm at prairienet, which is an O-R-G.
In article <············@wildfire.prairienet.org>,
Dan Bensen <··········@cyberspace.net> wrote:
> Barry Margolin wrote:
> > You could use displaced arrays:
>
> The point is to change grid2 without affecting grid1.
My solution doesn't affect grid1.
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***
Barry Margolin wrote:
> In article <············@wildfire.prairienet.org>,
> Dan Bensen <··········@cyberspace.net> wrote:
>> Barry Margolin wrote:
>> > You could use displaced arrays:
>> The point is to change grid2 without affecting grid1.
> My solution doesn't affect grid1.
So how does this work? CLtL2 assumes you already know, and I didn't
find much on Google. Does it do nothing until you modify the displaced
array (grid2), then create an individual object for each new cell value?
So if I change most of grid2, I'll have lots of little cell boogers
floating around, and the program will have to track down all those
boogers to iterate through grid2?
--
My name is dsb, and I'm at prairienet, which is an O-R-G.
Dan Bensen wrote:
> Barry Margolin wrote:
> > In article <············@wildfire.prairienet.org>,
> > Dan Bensen <··········@cyberspace.net> wrote:
> >> Barry Margolin wrote:
> >> > You could use displaced arrays:
> >> The point is to change grid2 without affecting grid1.
> > My solution doesn't affect grid1.
>
> So how does this work? CLtL2 assumes you already know, and I didn't
> find much on Google. Does it do nothing until you modify the displaced
> array (grid2), then create an individual object for each new cell value?
> So if I change most of grid2, I'll have lots of little cell boogers
> floating around, and the program will have to track down all those
> boogers to iterate through grid2?
Barry Margolin's code:
(let* ((grid1 (make-array '(3 3) ...))
(grid1-vector (make-array 9 ... :displaced-to grid1))
;; v--Look Here---v
(grid2-vector (make-array 9 ... :initial-contents grid1-vector))
(grid2 (make-array '(3 3) ... :displaced-to grid2-vector)))
(write grid2))
---
Geoff
>>>> Barry Margolin wrote:
>>>> > You could use displaced arrays:
> Dan Bensen wrote:
>> So how does this work? CLtL2 assumes you already know, and I didn't
>> find much on Google. Does it do nothing until you modify the displaced
>> array (grid2), then create an individual object for each new cell value?
>> So if I change most of grid2, I'll have lots of little cell boogers
>> floating around, and the program will have to track down all those
>> boogers to iterate through grid2?
(This appears to be wrong (see below))
Geoffrey Summerhayes wrote:
> Barry Margolin's code:
>
> (let* ((grid1 (make-array '(3 3) ...))
> (grid1-vector (make-array 9 ... :displaced-to grid1))
> ;; v--Look Here---v
> (grid2-vector (make-array 9 ... :initial-contents grid1-vector))
>
> (grid2 (make-array '(3 3) ... :displaced-to grid2-vector)))
> (write grid2))
Thank you.
That's what I originally thought, a displaced array is just a different
view of the same data. When I change grid2, the change is reflected in
grid2-vector. So this is just a hack to provide :initial-contents with
a 1D array.
Good enough! :)
--
My name is dsb, and I'm at prairienet, which is an O-R-G.
On 2006-08-30 10:26:15 -0400, Dan Bensen <··········@cyberspace.net> said:
> So how does this work?
broadly speaking (where items in parens are optional):
:displaced-to = "give me an alias to (part of) the original array"
so if you modify the original, the new array is modified as well.
:initial-contents = "give me a new array whose elements are this
(nested) sequence"
so if you modify the original array the new array is unchanged.
The function copy-array from cl-utilities can do both. If you don't
want a mere alias to the original, just pass it the :undisplace t
keyword argument:
CL-USER 3 > (defvar my-first-array (make-array '(3 3) :initial-contents
'((1 2 3) (4 5 6) (7 8 9))))
MY-FIRST-ARRAY
CL-USER 4 > (defvar my-second-array (copy-array my-first-array :undisplace t))
MY-SECOND-ARRAY ;; the copied array which does not share storage
because we're not using displaced arrays
CL-USER 5 > my-first-array
#2A((1 2 3) (4 5 6) (7 8 9))
CL-USER 6 > my-second-array
#2A((1 2 3) (4 5 6) (7 8 9)) ;; yep, the copy matches the original
CL-USER 7 > (setf (aref my-first-array 1 1) 42)
42 ;; we modify the original array
CL-USER 8 > my-first-array
#2A((1 2 3) (4 42 6) (7 8 9)) ;; see the modification to the original
CL-USER 9 > my-second-array
#2A((1 2 3) (4 5 6) (7 8 9)) ;; but the copy is unchanged by the
modification to the original
Raffael Cavallaro wrote:
> :initial-contents = "give me a new array whose elements are this
> (nested) sequence"
Except this seems to break down in the case of a multidimensional array
variable.
> The function copy-array from cl-utilities can do both.
That's fine. I'm just trying to prod CL to see where the feature
envelope is. Also, I'm concerned about performance issues, because the
grids have to be passed and modified throughout a minimax tree for my
little tic-tac-toe program. (hence the 3x3 dims :)
--
My name is dsb, and I'm at prairienet, which is an O-R-G.
Dan Bensen wrote:
> Also, I'm concerned about performance issues, because the
> grids have to be passed and modified throughout a minimax tree for my
> little tic-tac-toe program. (hence the 3x3 dims :)
Usually you don't really need several nodes of the minimax tree at
once. Hence you don't need to copy your grid; just play and takeback
the moves as you traverse the tree.
Kim Minh.
http://www.kim-minh.com/
Kim Minh Kaplan wrote:
> Usually you don't really need several nodes of the minimax tree at
> once. Hence you don't need to copy your grid; just play and takeback
> the moves as you traverse the tree.
Yes, I'm doing that. Iterating through the moves explicitly. But what
do "play" and "takeback" mean? I'm creating a new grid for each node,
otherwise how else do you pass all the previous moves to a child node?
--
My name is dsb, and I'm at prairienet, which is an O-R-G.
Dan Bensen wrote:
> Kim Minh Kaplan wrote:
>
> > Usually you don't really need several nodes of the minimax tree at
> > once. Hence you don't need to copy your grid; just play and takeback
> > the moves as you traverse the tree.
>
> Yes, I'm doing that. Iterating through the moves explicitly. But what
> do "play" and "takeback" mean? I'm creating a new grid for each node,
> otherwise how else do you pass all the previous moves to a child node?
First, the *child* node does not need the previous moves to do its job,
so do not pass it. It is the *parent* node that wants to know the
result of the minimax algorithm i.e. the outcome of the game: the list
of moves that will be played and the corresponding score¹. That
really means that minimax takes as input the only board and returns the
predicted list of moves and score.
As for the question of passing (really returning as I explained) a list
of moves you could choose whatever mean you want to represent a move
and a list of move but it seems that a Common Lisp list of (integer 1
9) fit the bill perfectly.
¹ Strictly speaking it does not need the score as it could be
calculated from the list of moves but as it has already been calculated
it is really better to return it.
--
Kim Minh.
http://www.kim-minh.com/
Kim Minh Kaplan wrote:
> First, the *child* node does not need the previous moves to do its job,
I don't understand. The effect of a move depends on the parent grid
just before that move, not the original grid several plies earlier. And
the score is determined from the entire child grid after adding the
latest move, isn't it? How can you compute the score without knowing
the entire, completely updated grid? How do you pass the current state
of the game to deeper plies without creating new grids?
--
My name is dsb, and I'm at prairienet, which is an O-R-G.
Dan Bensen wrote:
> Kim Minh Kaplan wrote:
> > First, the *child* node does not need the previous moves to do its job,
>
> I don't understand. The effect of a move depends on the parent grid
> just before that move, not the original grid several plies earlier. And
> the score is determined from the entire child grid after adding the
> latest move, isn't it? How can you compute the score without knowing
> the entire, completely updated grid? How do you pass the current state
> of the game to deeper plies without creating new grids?
;; pseudocode
(loop for x in (available-moves grid)
do (progn
(setf (aref grid x) player-token)
(do-alpha-beta grid (1+ ply) (next-player player-token))
(setf (aref grid x) #\Space)))
--
Geoff
Geoffrey Summerhayes wrote:
> Dan Bensen wrote:
>> How do you pass the current state
>> of the game to deeper plies without creating new grids?
>
> (setf (aref grid x) player-token)
> (do-alpha-beta grid (1+ ply) (next-player player-token))
> (setf (aref grid x) #\Space)))
I see. This even works for Go. What about chess and checkers?
--
My name is dsb, and I'm at prairienet, which is an O-R-G.
Dan Bensen wrote:
> Geoffrey Summerhayes wrote:
> > Dan Bensen wrote:
> >> How do you pass the current state
> >> of the game to deeper plies without creating new grids?
> >
> > (setf (aref grid x) player-token)
> > (do-alpha-beta grid (1+ ply) (next-player player-token))
> > (setf (aref grid x) #\Space)))
>
> I see. This even works for Go. What about chess and checkers?
Essentially the same, checkers requires keeping the state of the
moved piece to 'unking' when necessary, go needs to restore captured
pieces, and chess has additional state information that isn't contained
in the board position that needs to be kept track of.
If you can find a copy, there is a book about Sargon, an 'old' chess
program,
that contains the entire Z-80 source code. 'Sargon: a computer program'
was the title, IIRC. I believer it used a 12x12 array for the board and
kept
the move list in a stack.
---
Geoff
Kim Minh Kaplan wrote:
> you don't need to copy your grid; just play and takeback
> the moves as you traverse the tree.
Geoffrey Summerhayes wrote:
> checkers requires keeping the state of the
> moved piece to 'unking' when necessary, go needs to restore captured
> pieces, and chess has additional state information that isn't contained
> in the board position that needs to be kept track of.
Thanks for the help. Just as I'm starting to learn functional
programming, this grid seems to be a good counterexample in support of
mutable state. I've been trying to avoid assignments as much as
possible, but it looks like you can pay a heavy price for that in
performance.
--
My name is dsb, and I'm at prairienet, which is an O-R-G.
Dan Bensen wrote:
> Thanks for the help. Just as I'm starting to learn functional
> programming, this grid seems to be a good counterexample in support of
> mutable state. I've been trying to avoid assignments as much as
> possible, but it looks like you can pay a heavy price for that in
> performance.
To do anything interesting with arrays you *need* assignment. Even in
the case where you copied your grid, you need an assignment expression
to play a move in the grid [something like (setf (aref grid move)
player)].
The tic tac toe problem can easily be solved in a purely functionnal
style: just represent the board as the list of moves that lead to it.
But for more interesting things I doubt this is a good idea.
Kim Minh.
http://www.kim-minh.com/
On 2006-08-30 13:58:41 -0400, Dan Bensen <··········@cyberspace.net> said:
> Raffael Cavallaro wrote:
>> :initial-contents = "give me a new array whose elements are this
>> (nested) sequence"
>
> Except this seems to break down in the case of a multidimensional array
> variable.
Not really - read what I wrote carefully:
"... whose elements are this (nested) *sequence*" (emphasis added)
Multidimensional arrays are *not* sequences, so you can't use them as
arguments to :initial-contents. This is why the cl-utilities function
copy-array was written in part - so that you can initialize a new array
with the contents of an existing *multi-dimensional array*, not just a
nested sequence.
CL-USER 11 > (defvar multi-array (make-array '(3 3) :initial-contents
'((1 2 3) (4 5 6) (7 8 9))))
MULTI-ARRAY
CL-USER 12 > (defvar uni-array (make-array 9 :initial-contents '(1 2 3
4 5 6 7 8 9)))
UNI-ARRAY
CL-USER 13 > (typep uni-array 'sequence)
T ;; i.e., unidimensional arrays, aka vectors, *are* sequences.
CL-USER 14 > (typep multi-array 'sequence)
NIL ;; i.e., multidimensional arrays are *not* sequences
CL-USER 15 > (defvar this-works (make-array 9 :initial-contents uni-array))
THIS-WORKS
CL-USER 16 > (defvar this-wont (make-array '(3 3) :initial-contents
multi-array))
Error: #2A((1 2 3) (4 5 6) (7 8 9)) is not of type SEQUENCE.
1 (abort) Return to level 0.
2 Return to top loop level 0.
Type :b for backtrace, :c <option number> to proceed, or :? for other options
CL-USER 17 : 1 > :top
CL-USER 18 > (defvar this-works-too (copy-array multi-array :undisplace t))
THIS-WORKS-TOO
In article <························@m73g2000cwd.googlegroups.com>,
"Kim Minh Kaplan" <········@gmail.com> wrote:
> You seem to be looking for COPY-SEQ.
No he isn't. COPY-SEQ only works for one-dimensional arrays, he's
trying to copy a multi-dimensional array.
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***
Barry Margolin wrote:
>
> Kim Minh Kaplan wrote:
>
> > You seem to be looking for COPY-SEQ.
>
> No he isn't. COPY-SEQ only works for one-dimensional arrays, he's
> trying to copy a multi-dimensional array.
Ah yes, I did not pay enough attention. Now close your eyes here comes
some hugly code:
(with-input-from-string
(s (with-output-to-string (s) (write grid1 :stream s)))
(read s))
--
Kim Minh.
http://www.kim-minh.com/
Barry Margolin wrote:
> No he isn't. COPY-SEQ only works for one-dimensional arrays, he's
> trying to copy a multi-dimensional array.
Well, if you insist on using copy-seq somewhere, perhaps
you could get away in many cases with a minimalist:
(defun min-copy-array (a)
(make-array (array-dimensions a)
:displaced-to (copy-seq
(make-array (array-total-size a)
:displaced-to a))))