Marty Hall wrote:
>
> ·······@netcom.com (Bill Newman) writes:
> > I have a program to play the game of Go.
>
> Are you willing to share it? I've never seen any that play above the
> beginner level, although I've never tried the commercial ones from
> Ishi Press.
>
They all play at the beginner level, depending on your
definition of beginner ;-).
> > Basically, I have a function which is a
> > crude approximation to the goodness of the position, and the
> > approximation gets better as I search deeper and minimax the
> > results.
>
> I'm probably speaking to an expert here, but just in case, you're
> using alpha-beta pruning, not a brute-force minimax, right? And given
> the humongous branching factor, I take it you aren't searching
> full-ply?
doh !
>
> > Instead, I modify the board in place and update only those score
> > terms which are changed.
> >
> > Now, if I do this when I am searching down various branches of the
> > tree, what do I do when I come back up the tree? In C++, I define the
> > variables which change in the search to be of class Remembered<FOO>,
> > e.g. Remembered<int>, and I overload the assignment operator so that
> > it remembers the old value whenever the object is modified, and puts
> > it into a stack of changes to be undone. When I come back up the
> > tree, I unwind the stack and undo the changes. This works cleanly and
> > reasonably efficiently even when the Remembered<FOO> objects are used
> > as data members of other classes.
My take on this is that you should be defining methods on your 'board'
objects
that perform these actions explicitly (my knowledge of clos syntax is a
bit vague,
so i won't try and give psuedo-code). So you'ld pass around the object
<Board>,
and as you added moves, you call the method <Board>.try(move), and as
you went
back up the tree, you call the method <Board>.undo().
Personally, i find the C++ technique of overloading operators to be
slick looking
in simple cases, but it often makes the code unreadable (what does '='
mean for these two
objects ? could be anything ...).
>
> I'm not positive I follow the problem. I'd imagine you'd do something
> like
>
> (Make-Move Board <args>)
> (setq Expected-Value (Alpha-Beta Board <more args>))
> (Unmake-Move Board <args>)
> (Do-Some-Pruning-With Expected-Value)
>
> You're saying that this presents difficulties?
Usually, yes. My guess is that he's saving and undoing more than
just the positions of the stones on the board, but he's also storing
some
higher level 'computed' information, like what groups are on the board,
and how
many liberties they have. These are relatively expensive to compute.
You certainly
don't want to copy them for every move you try.
> Another alternative is to simply create a resource pool of boards at
> the beginning, and copy onto that board but don't reallocate the
> space. Ie suppose that you generate the board positions on the fly and
> search to depth 4. Then you only need 4 boards. You still have to copy
> the previous board positions onto the "new" board at each level, but
> not allocate the new array. So you won't cons. If, however, you are
> searching deep enough to make it worthwhile to apply your static
> evaluation function at earlier levels (so you can order the moves to
> get an increased number of alpha-beta cutoffs), then you'll need a lot
> more boards in the resource pool. Ie if you search to depth 4 and you
> consider 40 moves at each level, you'll need 160 boards. But you can
> still allocate them in advance and then reuse them.
>
> I also didn't follow the details of your Square vs
> Square-with-Tactical-Analysis discussion, but CLOS *does* know the
> types of objects at runtime, if that was what you were asking.
I see what he's asking, but i don't know enough about clos to comment.
Lee.