[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: computer-go: unmake move?
Don Dailey wrote:
>
>> 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?
Thanks. I will be waiting for it.
>
>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.
>
Very fast indeed. I never thought that copying works so well.
>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
>
>
>
Nobuhiro Yoshimura
Konami Computer Entertainment Tokyo The opinions expressed
Office: yosimura@xxxxxxxxxxxxxxxxx here are mine and not
Home: yoshimura@xxxxxxxxxxxxxxxxx necessarily those of Konami.