[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: computer-go: unmake move?
> Can you tell me the size of "POSITION" ?
Yes, it's 4872 bytes on a 19x19 board. I could shrink it
significantly by making type STONE and COUNTER 16 bits (see the
structure below.) But I have tried this and there is a small
reduction in the search speed. I'm guessing it's because 16 bit
variables are less processor friendly that 32 bit variables.
Here is what my actual state looks like so you can see what kind of
data I move around:
typedef struct ptag
{
int ctm; /* number of ply's (color to move is bit 0) */
U64 signature; /* hash key of position */
STONE bd[BOARD_SIZE]; /* the actual board */
COUNTER in_hand[2]; /* enemy stones captured */
COUNTER next_unit; /* always incrmented unit number */
COUNTER move; /* move that created this state */
struct ptag *his; /* pointer to last position */
unit_type unit[MAX_UNITS]; /* list of all units */
COUNTER adjust; /* evaluation term */
} position;
The units of unit_type look like this:
typedef struct
{
COUNTER stone_count; /* how many stones in this unit? */
COUNTER lib_count; /* how many liberties for this unit? */
STONE headstone; /* a representative stone from the unit */
} unit_type;
The contents of the board (bd[]) are coded with a color bit and a unit
number which indexes a unit_type record. BOARD_SIZE is N+2 or 21 in
the case of the 19x19 game for edge detection.
I'm guessing my implementation is naive compared to any good program,
and the only thing I really keep track of is information about "units"
which in my terminolgy is a whole set of connected stones of the same
color. I always know how many stones in any unit and how many
liberties, which of course is easy to maintain incrementally.
I have never seen the code for any other go program or even a low
level description of how the board and state is represented, so I
don't really have a clue about how things SHOULD be done. But I can
imagine that a good program might carry a whole lot more data around
that mine does. In that case, its possible that this method is not
very close to optimal. But I would argue that if you carry more data
around, not only do you probably spend more time keeping it all up to
date, but you probably have to save a lot of state ANYWAY in order to
gracefully un-make a move. So it isn't as if going all the trouble of
undoing moves stops you from pushing state around. So I just choose
to push the whole thing in one simple and fast operation!
Based on my experience with chess, which admittedly requires much less
state, I would guess that this is probably at least reasonably close
to optimal. It's certainly FAR simpler and makes me more inclined to
experiment, knowing I didn't have to always provide for undoing any
new gizmo I add to the search.
You brought up the issue of memory bandwidth. There is always the
possiblity that this technique could blow out the cache. I don't
really know the answer, most of my experience is with Chess programs,
I am a beginner at go as a player AND a programmer and I have never
written a go program that un-makes moves so I don't have anything to
compare against. But I have written MANY chess programs using both
the position passing and the unmaker. I just know in chess it's hard
to demonstrate that one technique is faster than the other, so I go
with the one that leads to simpler code, that has less bugs and is
tailor made for parallel programming.
This probably goes without saying, but the more work your program does
making and unmaking moves, the more attractive this idea becomes. If
you push a huge amount of state around, maybe it's not so clear.
What I should probably do is to profile my code and measure the time
spent making a move and how much of this time is spent copying the
state. Whether this turns out good for me or not though, it would be
no guarantee that others would get the same results. If I do this, I
will post the results, ok?
By the way, for what it's worth, my program looks at slightly under
300,000 nodes per second on a 600 MHZ Athlon. This probably has
little meaning without knowing exactly how a given program works, but
at least you probably have a sense of what I do to keep the state up
to date when a move is made. I don't know if this is fast or slow
given what the program does. An unmake routine might slow this down,
or speed it up, but my guess is that it wouldn't make a big difference
either way.
I have this idea that many programmers may be prejudiced against this
idea, I certainly was when I first tried it in my chess program. It
just seemed silly to me to push whole positions around in the search
tree when you can just update in place. But then I realized I was
keeping some data in a stack anyway to help me unmake a move, and that
the un-make routine had plenty of logic of its own, a lot more than
you would imagine for simply moving a piece from one square to
another! So why not just do the ultra simple and high speed copy? As
I said, modern processors do this well. The real bottlneck is code
with decision making logic in it, like un-make!
Well, all I can say is don't be afraid to give this a try. I don't
really know if it would pay off or not in a typical go program, I just
know it's a whole lot simpler, the code is a lot cleaner, and I have a
strong sense that it's not a lot slower, and maybe it's not slower at
all. If unmaking a move is really complicated, it might very well be
faster.
Don
From: Nobuhiro Yoshimura <yosimura@xxxxxxxxxxxxxxxxx>
Date: Thu, 08 Jun 2000 10:08:49 +0900
MIME-Version: 1.0
X-Mailer: AL-Mail32 Version 1.01
Sender: owner-computer-go@xxxxxxxxxxxxxxxxx
Precedence: bulk
Reply-To: computer-go@xxxxxxxxxxxxxxxxx
Content-Type: text/plain; charset=us-ascii
Content-Length: 1053
Don Dailey wrote:
>
>Note that modern processors are extremely fast at copying data that is
>layed out consecutively in memory, believe me, you can have a very
>fast program that uses this technique.
Can you aply this rule to PCs ? I thought that memory bandwidth
is very narrow for PC.
Can you tell me the size of "POSITION" ?
>
>
>/* nega-max search */
>/* --------------- */
>
>int search( position *state, int depth, int alpha, int beta )
>{
> POSITION new_state; /* allocate state */
>
>
> foreach move in (0 .. number_of_moves)
> {
> make_move( state, &new_state, move );
> score = -search( &new_state, depth-1, -alpha, -beta );
>
> /* No need to unmake!!! */
>
> if (score > best_found_so_far)
> {
> ...
>
> }
>
> }
>
> return( best_found_so_far );
>
>}
>
Nobuhiro Yoshimura
Konami Computer Entertainment Tokyo The opinions expressed
Office: yosimura@xxxxxxxxxxxxxxxxx here are mine and not
Home: yoshimura@xxxxxxxxxxxxxxxxx necessarily those of Konami.