[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: computer-go: Languages for programming go are?
I have limited understanding of go programming techniques but for what
it is worth, here is how I represent things:
The board is a one dimensional array, with a border around it for easy
edge detection. I store a "group number" on each intersection as well
as a white bit and a black bit. The group number is really a "string"
number. Separately, I have a structure that tells me things about any
given string (indexed by this group number) which I keep incrementally
updated. This is very simple and my program is primitive, so right
now all I keep is a liberty count, a count of stones in the group and
the location of a reference stone (it doesn't matter which stone) and
a hash key or signature number for the group.
It's not very sophisticated, but it's trivial to implement, and
incredibly fast. The move maker is very fast since I don't need to
maintain hooks and complicated logic for unmaking moves (which itself
is a FREE operation in my program.) Free is a relative term since one
can argue that I pay a price for this simplicity. I have noticed over
the years, with modern processors that state copy is incredibly cheap,
even a substantial amount of state, over anything that has much
conditional logic in it. Unmake routines have a lot of conditional
logic, as does makes (which is simpler for me.)
Don
Date: Fri, 29 Dec 2000 22:47:53 -0600
From: William Harold Newman <william.newman@xxxxxxxxxxxxxxxxx>
References: <001201c06e42$46a836e0$0200a8c0@porcupine> <NDBBKHJBACOMNGMLKGPGAEMCCFAA.anders@xxxxxxxxxxxxxxxxx>
Mime-Version: 1.0
X-Mailer: Mutt 1.0.1i
Sender: owner-computer-go@xxxxxxxxxxxxxxxxx
Precedence: bulk
Reply-To: computer-go@xxxxxxxxxxxxxxxxx
Content-Type: text/plain; charset=us-ascii
Content-Length: 6204
I'll reply to this since I think the question is interesting, but
remember to take my opinions with a big grain of salt, since Anders'
program can easily stomp my program.:-|
On Fri, Dec 29, 2000 at 03:48:51PM -0800, Anders Kierulf wrote:
> > 2) If one were to imagine a new language, invented solely for
> > the purpose of writing a great computer go system, what would
> > its characteristics likely be? (Or would there be multiple
> > new languages, for different parts of the problem?)
> > ...
> > Bob Myers
> > Intelligent Go Foundation
>
> In a sense, everybody developing a Go program is designing their own
> language for computer Go. The base code of a Go program provides types
> and functions that implement board management (such as blocks,
> liberties, playing and taking back a move), bitboards, pattern
> matching, hash tables, and more, and higher-level code (such as groups
> and tactical search) is based on those functions. Whether that base
> code is provided as a toolkit or as a language is not a crucial issue,
> as long as the desired higher-level Go concepts can be expressed in
> terms of the base code.
The topic sentence is sort of like the "library design is language
design, and vice versa" rule that I think Bjarne Stroustrup attributes
to Bell Labs culture. And I basically agree with the entire paragraph.
> SmartGo is written in C++, and while C++ is far from ideal, it lets
> us efficiently express the concepts we want to express. Our web site
> explains how C++ is used in SmartGo, see
> http://www.smartgo.com/t_use_of_cpp.htm. That web page also shows the
> method ForceApproachMove exactly as written in SmartGo. It would be
> very interesting to see how other Go programs express that algorithm,
> not in pseudo-code, but in real code that will actually work as
> written, and is efficient enough to generate moves during a tactical
> search that examines thousands of positions per second. Concrete
> examples like this is where the rubber hits the road. How would this
> look in Lisp? In GNU Go? In Many Faces of Go?
Low-level C++ code like the example on your web page looks very
similar in Lisp. The biggest difference is that the usual idiom is
often an iteration macro or a mapping function instead of an iterator
class, so e.g.
for (LibertyIterator iter(board, block); iter; ++iter) {
..
}
will often be something like
(do-block-libs (lib-iter board block)
..)
or
(map-on-block-libs (lambda (lib-iter) ..) board block)
instead of the more literal translation
(do ((iter (liberty-iter board block) (next iter)))
((null iter))
..)
There's seldom any great advantage to using Lisp at this level.
Lisp comes into its own in higher level code. Sometimes Lisp bigots
claim that the _Design Patterns_ book is mostly unnecessary in Lisp
because things like that are so much easier to write in Lisp. That's
an exaggeration, but it is true that concepts at that level are often
easier to express in Lisp than in C++.
Memoization/uniquification is a good example of a design theme which
is easy to express in Lisp and (AFAIK) more tedious to express in C++.
In my Go program, I have a single macro which memoizes a constructor
automatically if the class of objects is unique. It's moderately
complicated, a little more complicated than hand-crafting such a
memoization scheme for a single class in C++. But in Lisp I do it once
and can then use it for all classes afterwards without needing to
think about it again. The logic in the macro used in my program is
fairly hairy because of the way it deals with backtracking and
complicated argument lists and minimizing dynamic memory allocation
and a few other issues, and besides that Lisp macros are hard to read
for non-Lisp programmers, so I despite your suggestion that I show
real working code, I don't really want to use it as an example.
Instead, I'll show a textbook implementation of memoization, based on
the memoizing higher-order function from Figure 5.2 of Paul Graham's
_On Lisp_:
;;; Given an unmemoized function, return a memoized version.
(defun memoized (fn)
(let ((cache (make-hash-table :test 'equal)))
(lambda (&rest args)
(multiple-value-bind (val found?) (gethash args cache)
(if found?
val
(setf (gethash args cache)
(apply fn args)))))))
;;; Overwrite the bare function definition of FN-NAME with a
;;; memoized version.
(defun memoize! (fn-name)
(setf (symbol-function fn-name)
(memoized (symbol-function fn-name))))
This memoization utility can be used in a program like this:
;;; Define a bare constructor, which we don't want to call more
;;; than once with any set of arguments, because we'd like there
;;; to be only one "connection between G1 and G2" object in
;;; existence for any given pair of values G1 and G2.
(defun make-connection (g1 g2)
..)
;;; So we overwrite it with the memoized version.
(memoize! 'make-connection)
;;; Define some search function which is expensive to compute,
;;; enough so that we want to avoid calling it more than once
;;; with any given set of arguments.
(defun best-compound-connection (square-1 square-2 player)
..)
;;; So we overwrite it with the memoized version.
(memoize! 'best-compound-connection)
;;; etc.
..
The generic once-for-all-classes memoization logic in my program is
not as efficient as hand-crafted C++ class-specific versions could be.
But it's so much more concise (than any C++ version that I know how to
write) that I find it substantially easier to write and read and
debug. Also, when I'm writing C++ code, if I spent too much time
writing and debugging hand-crafted code, I might find that I don't
have time to implement memoization at all; and memoized Lisp code can
be a lot more efficient than C++ code which doesn't memoize!
So, IMHO it's worth considering using languages which use a higher
level of abstraction than C++, but the benefits may not be visible in
code at low levels of abstraction.
--
William Harold Newman <william.newman@xxxxxxxxxxxxxxxxx>
software consultant
PGP key fingerprint 85 CE 1C BA 79 8D 51 8C B9 25 FB EE E0 C3 E5 7C