I'm playing with a Tic-Tac-Toe program what uses similar programming
patterns like the Othello game in
Norvig, Peter. Paradigms of artificial intelligence programming: case
studies in Common Lisp, pp. 596, Morgan Kaufmann Publishers, Inc., 1992.
Because I want to use different board sizes the board is represented as
(make-array (list n n) :initial-element 0)
The MOVES I will get from the playing engine are lists in the format
(ROW COLUMN), i.e. placing a piece on the board is
(defun place-piece (move player board)
"Place a piece to a board location."
(apply #'(lambda (row col) (setf (aref board row col) player)) move))
Is there there a better technique to decompose MOVE into ROW,COL besides
using a STRUCT?
--
Bernd
On 28 Jan., 10:31, Bernd Beuster <·············@lycos.de> wrote:
> (defun place-piece (move player board)
> "Place a piece to a board location."
> (apply #'(lambda (row col) (setf (aref board row col) player)) move))
>
> Is there there a better technique to decompose MOVE into ROW,COL besides
> using a STRUCT?
You could look at ARRAY-ROW-MAJOR-INDEX and ARRAY-ROW-MAJOR-AREF. This
should allow
you to store moves as fixnums.
You might also give your array an element-type appropriate to your
program so that the lisp-system can use specialized arrays.
ciao,
Jochen
On 28 Jan., 11:09, ·····@codeartist.org" <····@codeartist.org> wrote:
You could look at ARRAY-ROW-MAJOR-INDEX and ARRAY-ROW-MAJOR-AREF.
Sorry - I meant ROW-MAJOR-AREF of course.
ciao,
Jochen
··@codeartist.org schrieb:
>
> On 28 Jan., 11:09, ·····@codeartist.org" <····@codeartist.org> wrote:
> You could look at ARRAY-ROW-MAJOR-INDEX and ARRAY-ROW-MAJOR-AREF.
>
> Sorry - I meant ROW-MAJOR-AREF of course.
Thank you, this is much better:
(defconstant empty 0 "Empty field")
(defconstant cross 1 "Player X")
(defconstant circle 2 "Player O")
(defun initial-board (n)
"Return a board with empty fields of size NxN."
(make-array (list n n) :element-type `(integer ,empty ,circle)
:initial-element empty))
(defun place-piece (move player board)
"Place a piece to a board location."
(setf (row-major-aref board move) player))
(defun legal-p (move board)
"A legal move must be into an empty field."
(eq empty (row-major-aref board move)))
(defun legal-moves (board)
"Return list of legal moves."
(loop for move below (array-total-size board)
when (legal-p move board) collect move))
--
Bernd
* Bernd Beuster <············@online.de> :
| (defun place-piece (move player board)
| "Place a piece to a board location."
| (apply #'(lambda (row col) (setf (aref board row col) player)) move))
|
|
| Is there there a better technique to decompose MOVE into ROW,COL besides
| using a STRUCT?
I don't see any struct (introduced by defstruct) here. But it looks
like apply is just used to destrucure the list, which looks weird.
Isn't that just:
(defun place-piece (move player board)
(destructuring-bind (row col) move
(setf (aref board row col) player)))
;; or (let ((row (car move) ; or (first move)
;; (col (cadr move))) ; or (second move)
;; (setf (aref board row col) player)))
--
Madhu
From: robert maas, see http://tinyurl.com/uh3t
Subject: Re: Array access
Date:
Message-ID: <rem-2007jan29-005@yahoo.com>
(The Subject field seems to be unrelated to the actual topic!)
> From: Bernd Beuster <·············@lycos.de>
> Norvig, Peter. Paradigms of artificial intelligence programming: case
> studies in Common Lisp, pp. 596, Morgan Kaufmann Publishers, Inc., 1992.
I keep seeing that book mentionned and recommended. Would it, or
any other book like that, be of reasonable value to somebody who
already has more than 20 years experience programming, including
more than 15 years experience programming in lisp, who has no
interest in writing A.I. software, only data-processing
applications include somewhat expert systems (applications that
have a lot of problem-specific knowledge which is incorporated into
the code)?
> (defun place-piece (move player board)
> "Place a piece to a board location."
> (apply #'(lambda (row col) (setf (aref board row col) player)) move))
> Is there there a better technique to decompose MOVE into ROW,COL
> besides using a STRUCT?
It's your choice how much of the internal structure of a MOVE
object you wish to hide from the person writing the majority of
this program, i.e. yourself, anyone who later adds specific modules
to your program, such as modules to act as smart or intelligent
players of the game, perhaps in a tournament among such automated
players. If you don't want to hide anything, decide once and for
all the representation for a MOVE object will be a list of two
numbers, where the first number is the row and the second number is
a column, and all code will be dependent on this choice, then
somebody suggested destructuring bind and I agree that's best. I
really don't like like using APPLY in this manner. It's overkill,
fragile, and probably takes more CPU cycles because it has to be
general.
If you want to hide the access primitives but still not totally
obscure the internal representation, i.e. coders will *not* call
CAR and CADR explicitly, but *can* see the list of two elements any
time they want, then I suggest writing explicit accessor functions:
(defun build-move (row col) (list row col)) ;Or see later version using keywords
(defun move-get-row (move) (car move))
(defun move-get-col (move) (cadr move))
(defun move-change-row-ip (move newrow) (setf (car move) newrow) move)
(defun move-change-col-ip (move newcol) (setf (cadr move) newcol) move)
(defun move-change-row-copying (move newrow) (list newrow (cadr move)))
(defun move-change-col-copying (move newcol) (list (car move) newcol))
(defun move-copy (move) (copy-list move))
Note that for consistency (and to support generic OO version
discussed later below), both the -IP and the -COPYING versions of
the -CHANGE- functions return the [modified|newlyBuilt] MOVE object.
If you don't want programmers to have to remember that row comes
before col when calling build-move, you could use keywords instead:
(defun build-move (&key (row 0) (col 0)) (list row col))
If you want to hide the internal representation a bit more, you
could make it a struct. And if you want to totally hide the
internal representation, forbidding all additional operations (such
as appending extra elements to end of list, or truncating list, or
including row or col elements which aren't valid numbers in
appropriate range), then you want to make it an actual OO-object
whose methods have total control. You might even add a third
element to the list, a mutable/immutable flag, which is set at
build time, and can't be changed except by making a copy of the
object with a new value there. The -IP methods would then be
forbidden (throw exception) for MOVE objects that are immutable.
You might even have a default pair of -CHANGE- methods that do the
-IP version for mutable objects and the -COPYING version for
immutable objects.
It's your design decision. Consider all options.
If you're going to pack large arrays with such MOVE objects, you
might want to isolate the internal representation from the access
functions, but *not* have each MOVE object be a fullfledged OO
object, so that you can someday change the representation to be a
single INUM containing two byte fields packed in a single word of
memory instead of a linked list, and all code that uses the
explicit build/get/change functions will continue to work.
Whether those accessor functions actually work with a list of two
elements, or a struct, or a byte-packed INUM, is then invisible to
all programmers at all times except for one person when the
accessors are implemented or changed.
·······@yahoo.com (robert maas, see http://tinyurl.com/uh3t) writes:
> (The Subject field seems to be unrelated to the actual topic!)
> > From: Bernd Beuster <·············@lycos.de>
> > Norvig, Peter. Paradigms of artificial intelligence programming: case
> > studies in Common Lisp, pp. 596, Morgan Kaufmann Publishers, Inc., 1992.
>
> I keep seeing that book mentionned and recommended. Would it, or
> any other book like that, be of reasonable value to somebody who
> already has more than 20 years experience programming, including
> more than 15 years experience programming in lisp, who has no
> interest in writing A.I. software, only data-processing
> applications include somewhat expert systems (applications that
> have a lot of problem-specific knowledge which is incorporated into
> the code)?
Paradigms of AI Programming is excellent even if you have no interest
in AI. I think the value is summarized nicely by Norvig's 52 lessons
of PAIP at http://norvig.com/Lisp-retro.html. I'll quote them all
here:
1. Use anonymous functions. [p. 20]
2. Create new functions (closures) at run time. [p. 22]
3. Use the most natural notation available to solve a
problem. [p. 42]
4. Use the same data for several programs. [p. 43]
5. Be specific. Use abstractions. Be concise. Use the provided
tools. Don't be obscure. Be consistent. [p. 49]
6. Use macros (if really necessary). [p. 66]
7. There are 20 or 30 major data types; familiarize yourself with
them. [p. 81]
8. Whenever you develop a complex data structure, develop a
corresponding consistency checker. [p. 90]
9. To solve a problem, describe it, specify it in algorithmic
terms, implement it, test it, debug and analyze it. Expect this
to be an iterative process. [p. 110]
10. AI programming is largely exploratory programming; the aim is
often to discover more about the problem area. [p. 119]
11. A general problem solver should be able to solve different
problems. [p. 132]
12. We must resist the temptation to belive that all thinking
follows the computational model. [p. 147]
13. The main object of this book is to cause the reader to say to
him or herself "I could have written that". [p. 152]
14. If we left out the prompt, we could write a complete Lisp
interpreter using just four symbols. Consider what we would have
to do to write a Lisp (or Pascal, or Java) interpreter in Pascal
(or Java). [p. 176]
15. Design patterns can be used informally, or can be abstracted
into a formal function, macro, or data type (often involving
higher-order functions). [p. 177]
16. Use data-driven programming, where pattern/action pairs are
stored in a table. [p. 182]
17. Sometimes "more is less": its easier to produce more output than
just the right output. [p. 231]
18. Lisp is not inherently less efficient than other high-level
languages - Richard Fateman. [p. 265]
19. First develop a working program. Second, instrument it. Third,
replace the slow parts. [p. 265]
20. The expert Lisp programmer eventually develops a good
"efficiency model". [p. 268]
21. There are four general techniques for speeding up an algorithm:
caching, compiling, delaying computation, and indexing. [p. 269]
22. We can write a compiler as a set of macros. [p. 277]
23. Compilation and memoization can yield 100-fold
speed-ups. [p. 307]
24. Low-level efficiency concerns can yield 40-fold
speed-ups. [p. 315]
25. For efficiency, use declarations, avoid generic functions, avoid
complex argument lists, avoid unnecessary consing, use the right
data structure. [p. 316]
26. A language that doesn't affect the way you think about
programming is not worth knowing - Alan Perlis. [p. 348]
27. Prolog relies on three important ideas: a uniform data base,
logic variables, and automatic backtracking. [p. 349]
28. Prolog is similar to Lisp on the main points. [p. 381]
29. Object orientation = Objects + Classes + Inheritance - Peter
Wegner [p. 435]
30. Instead of prohibiting global state (as functional programming
does), object-oriented programming breaks up the unruly mass of
global state and encapsulates it into small, manageable pieces,
or objects. [p. 435]
31. Depending on your definition, CLOS is or is not
object-oriented. It doesn't support encapsulation. [p. 454]
32. Prolog may not provide exactly the logic you want [p. 465], nor
the efficiency you want [p. 472]. Other representation schemes
are possible.
33. Rule-based translation is a powerful idea, however sometimes you
need more efficiency, and need to give up the simplicity of a
rule-based system [p. 509].
34. Translating inputs to a canonical form is often a good strategy
[p. 510].
35. An "Expert System" goes beyond a simple logic programming
system: it provides reasoning with uncertainty, explanations,
and flexible flow of control [p. 531].
36. Certainty factors provide a simple way of dealing with
uncertainty, but there is general agreement that probabilities
provide a more solid foundation [p. 534].
37. The strategy you use to search for a sequence of good moves can
be important [p. 615].
38. You can compare two different strategies for a task by running
repeated trials of the two [p. 626].
39. It pays to precycle [p. 633].
40. Memoization can turn an inefficient program into an efficient
one [p. 662].
41. It is often easier to deal with preferences among competing
interpretations of inputs, rather than trying to strictly rule
one interpretation in or out [p 670].
42. Logic programs have a simple way to express grammars [p. 685].
43. Handling quantifiers in natural languiage can be tricky
[p. 696].
44. Handling long-distance dependencies in natural language can be
tricky [p. 702].
45. Understanding how a Scheme interpreter works can give you a
better appreciation of how Lisp works, and thus make you a
better programmer [p. 753].
46. The truly amazing, wonderful thing about call/cc is the ability
to return to a continuation point more than once. [p. 771].
47. The first Lisp interpreter was a result of a programmer ignoring
his boss's advice. [p. 777].
48. Abelson and Sussman (1985) is probably the best introduction to
computer science ever written [p. 777].
49. The simplest compiler need not be much more complex than an
interpreter [p. 784].
50. An extraordinary feature of ANSI Common Lisp is the facility for
handling errors [p. 837].
51. If you can understand how to write and when to use once-only,
then you truly understand macros [p. 853].
52. A word to the wise: don't get carried away with macros [p. 855].
Zach
robert maas, see http://tinyurl.com/uh3t schrieb:
> somebody suggested destructuring bind and I agree that's best. I
> really don't like like using APPLY in this manner. It's overkill,
> fragile, and probably takes more CPU cycles because it has to be
> general.
Is DESTRUCTURING-BIND build around LAMBDA or vice versa?
--
Bernd
Bernd Beuster <·············@lycos.de> writes:
> robert maas, see http://tinyurl.com/uh3t schrieb:
>> somebody suggested destructuring bind and I agree that's best. I
>> really don't like like using APPLY in this manner. It's overkill,
>> fragile, and probably takes more CPU cycles because it has to be
>> general.
> Is DESTRUCTURING-BIND build around LAMBDA or vice versa?
Function lambda-lists are not destructuring. It's macro lambda-lists that are.
But since you can implement everything with lambda and function calls,
the question stays rather meaningless.
--
__Pascal Bourguignon__ http://www.informatimago.com/
·······@yahoo.com (robert maas, see http://tinyurl.com/uh3t) writes:
> (The Subject field seems to be unrelated to the actual topic!)
> > From: Bernd Beuster <·············@lycos.de>
> > Norvig, Peter. Paradigms of artificial intelligence programming: case
> > studies in Common Lisp, pp. 596, Morgan Kaufmann Publishers, Inc., 1992.
>
> I keep seeing that book mentionned and recommended. Would it, or
> any other book like that, be of reasonable value to somebody who
> already has more than 20 years experience programming, including
> more than 15 years experience programming in lisp, who has no
> interest in writing A.I. software, only data-processing
> applications include somewhat expert systems (applications that
> have a lot of problem-specific knowledge which is incorporated into
> the code)?
Funny, I would have classified expert systems as A.I. software.
In any case, the book has a pretty nice description of how to write
interesting code in Common Lisp, with lots of examples. It is, however,
a bit hard to gauge whether you would find this useful or not. Perhaps
the best thing to do is for you to cruise on over to Peter Norvig's
website and look at the example code. If it piques your interest, then
you should get the book.
See http://www.norvig.com/paip.html
--
Thomas A. Russ, USC/Information Sciences Institute
Thomas A. Russ wrote:
> ·······@yahoo.com (robert maas, see http://tinyurl.com/uh3t) writes:
>
>
>>(The Subject field seems to be unrelated to the actual topic!)
>>
>>>From: Bernd Beuster <·············@lycos.de>
>>>Norvig, Peter. Paradigms of artificial intelligence programming: case
>>>studies in Common Lisp, pp. 596, Morgan Kaufmann Publishers, Inc., 1992.
>>
>>I keep seeing that book mentionned and recommended. Would it, or
>>any other book like that, be of reasonable value to somebody who
>>already has more than 20 years experience programming, including
>>more than 15 years experience programming in lisp, who has no
>>interest in writing A.I. software, only data-processing
>>applications include somewhat expert systems (applications that
>>have a lot of problem-specific knowledge which is incorporated into
>>the code)?
>
>
> Funny, I would have classified expert systems as A.I. software.
Nahh, expert systems are at least one order of magnitude less
interesting than AI. You are not wrong, tho. Expert systems are passed
off as AI to coverup AI's failure.
>
> In any case, the book has a pretty nice description of how to write
> interesting code in Common Lisp, with lots of examples. It is, however,
> a bit hard to gauge whether you would find this useful or not. Perhaps
> the best thing to do is for you to cruise on over to Peter Norvig's
> website and look at the example code. If it piques your interest, then
> you should get the book.
>
> See http://www.norvig.com/paip.html
>
I read two chapters and thought PAIP was a joke. And the guy thinks
Python is Lisp. How smart can he be?
kxo
--
Well, I've wrestled with reality for 35 years, Doctor, and
I'm happy to state I finally won out over it.
-- Elwood P. Dowd
In this world, you must be oh so smart or oh so pleasant.
-- Elwood's Mom
On 29 Jan., 19:34, ·······@yahoo.com (robert maas, see http://
tinyurl.com/uh3t) wrote:
> I keep seeing that book mentionned and recommended. Would it, or
> any other book like that, be of reasonable value to somebody who
> already has more than 20 years experience programming, including
> more than 15 years experience programming in lisp, who has no
> interest in writing A.I. software, only data-processing
> applications include somewhat expert systems (applications that
> have a lot of problem-specific knowledge which is incorporated into
> the code)?
It was the second CL book I read (directly after On Lisp by Paul
Graham). Compared to On Lisp it uses a "more realistic" use of macros
but falls somewhat short to make use of CLOS, conditions or the
package system. CLOS is used in only one of the examples - which is
the one in the chapter about (duh!) "Object-Oriented Programming". The
rest of the book either uses specific CL datastructures or sometimes
structures. The CLOS example is a bit small but actually quite good
since it shows CL style OOP by building a simple protocol and using
mixin-inheritance. AFAIR Peter Norvig did not use packages or
conditions in any of the examples in the book. There are (very short
and incomplete) description of this features in one chapter about
Common Lisp itself. So if you want to learn how to structure Common
Lisp code in a maintainable way or how to make use of the (incredible)
conditions and restarts - you will have to look for something else.
Were PAIP really shines is the chapter about efficiency issues. Peter
Norvig shows, by optimizing other examples of the book, how to write
optimized CL code which does not look like C in sexps afterwards. When
I read PAIP as a lisp freshman, I was really impressed by the examples
in the book. Writing a Prolog or Scheme compiler, Expert-Systems or a
natural language parser with complete working source printed in the
book? Woah! I still like the PAIP very much - but it may be not the
best book learn CL as a newby. On the other side - you mentioned you
have 15 years of experience in programming lisp - I'm not sure if the
book will show you many new tricks then ;-). Having just 7 years of CL
experience so far, I may conclude that the PAIP is definitely a good
read and emphasises a quite clean and good (maybe a bit dated) style.
ciao,
Jochen