[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [computer-go] Data structures for Go
Hi Don,
Could you say us what is a 'old' processor and a 'modern'
one? Seems to me this a very fast varying concept :-)
Memory bandwith is always increasing, but processor speed is also
increasing at the same time. And the point is that if you perform only state
copying, the 'computing' units of your processor are idle at the same time.
On the other hand if you perform only computation, you could very well
perform state copy at the same time for free (provided your computation
uses only data within registers).
The best performances are probably achieved with a well balanced
strategy that makes sure the processor has no unit idle at any time
(which is very difficult, and which is why Intel introduced hyper-threading
technology).
The only way to do it is to run benchmarks, and I don't think we can
state that such or such strategy is better for "modern" hardware. It will
mainly depend on the ratio between memory bandwith and clock
speed (but processor's intrinsic parallelism should be taken into account
also).
To answer your last question, I use undo.
Regards,
Antoine
----- Original Message -----
From: "Don Dailey" <drd@xxxxxxxxxxxxxxxxx>
To: <computer-go@xxxxxxxxxxxxxxxxx>
Cc: <computer-go@xxxxxxxxxxxxxxxxx>
Sent: Wednesday, October 08, 2003 9:23 PM
Subject: Re: [computer-go] Data structures for Go
>
> Hi Peter,
>
> I have some thoughts on "undo" that you may want to consider. Whether
> it works for you will depend a lot on your implementation, but it
> works great for me and is a huge simplification.
>
> In my program, I never explicitly "undo" a move, I simply keep a new
> separate game state copy for each node visited during the search.
>
> In the past, a few have been critical of this idea, claiming it is way
> too slow to copy thousands of bytes just to make small state changes,
> like placing a stone on an intersection. I think this was true in the
> past, but processors have changed a lot in a short time. The code I
> write now would not work very well on old processors.
>
> If you a programming in C, you would probably store the complete game
> state in a structure. So to make a move, you simply copy the current
> game state structure to a new structure and then apply the new move to
> the new game state structure. There is no need to explicitly undo a
> move as you will see from the psuedo C code I am including.
>
> It turns out that modern processors are extremely fast when copying
> memory to memory. If undo routines (depending on how complicated your
> data structure is) have much logic in them, the slowdown can quickly
> defeat any advantage of updating in place.
>
>
> The advantages are numerous. Let me mention some of them:
>
> 1. No "undo" routine. Undo is free.
> 2. No undo program bugs.
> 3. Code is much simpler.
> 4. Code is cleaner, not depending on ugly update of global variables.
> 5. No "undo" stacks or other bookeeping data structures needed.
> 6. Data structure experimentation and development cycle much faster.
>
>
> There are 2 possible disadvantages:
>
> 7. Your program MIGHT run slower.
> 8. Memory (data) footprint will probably be larger.
>
>
> I should mention that your program might run FASTER too, but more
> likely it will be just a slight slowdown. Don't forget that you you
> are saving some time by not having to execute an undo routine. And it
> doesn't take very much undo logic to slow your program down enough to
> offset the very fast state copy. Unless your state is very large, you
> may not notice a big difference either way.
>
> The memory footprint will not increase much unless your position state
> is pretty huge. But your code will be smaller (even the code to make
> a move will be smaller and simpler because you won't have to provide
> all the undo hooks.)
>
> If you experiment a lot and the experimentation involves the way your
> board state is represented, then to me it seems crazy to even consider
> anything involving "undo."
>
> You may find that you will make different choices if you decide that
> undo is evil in the general case. Since you won't have to provide
> undo hooks, you may be able to benefit from other simplifications.
> This might translate to more sophisticated data representations since
> you are not faced with the daunting task of dealing with undo.
>
> In older processors, there was not a good argument for rejecting undo.
> Undo was a lot faster. I'm not sure what has changed, but modern
> processors seem to be a lot better at doing dumb things faster, like
> simply copying big chunks of memory. I have heard that modern
> processors are optimized for memory to memory copies although I'm not
> expert enough to confirm or deny!
>
>
> I think the biggest factor by far is how BIG your position state is,
> and how complicated your move logic and data structures are for
> representing a Go position. Very large states would argue in favor of
> undo, but complicated data structures involving slow make and undo
> routines would argue the other way.
>
> I will also point out that it's probably very easy to test whether the
> idea is workable for you. If your board representation is well
> contained and not scattered around in many global variables, you can
> probably implement and test the idea in a day.
>
> Another way is to estimate the cost of doing this to determine if it's
> worth it. Add a gratutious (dummy) state copy inside your make move
> routine and see how much it slows down your program. Subtract the
> time of your unmake routine if it's significant and see whether it's
> worth it to game cleaner simpler code. It may or may not be depending
> a lot on how your program works.
>
> I am curious, how many others out there avoid undo by passing state?
>
>
>
>
> Here is pseudo code of how my program search routine works.
> I'm leaving out almost all unnecceary details:
>
> ----------------------[ snip ]--------------------------
>
>
> typedef struct ptag // I'm making up things that might be included
> {
> int color_to_move;
> bd_t board[ SIZE_OF_BOARD ];
> u64 zobrist_signature;
> int stones_in_hand[2];
> int string_count;
> int reference_stone[MAX_STRINGS];
> int liberty_count[MAX_STRINGS];
>
> struct
> ptag *history; // points to previous position
>
> stuff other_great_stuff;
>
> } position;
>
>
>
> int make( position *old_pos, position *new_pos, mv_type move )
> {
>
> ... simple tests to see if move is clearly illegal
>
> *new_pos = *old_pos; // state copy
>
> new_pos->color_to_move += 1; // update color to move (lsb)
>
> ... other move make stuff
> ... etc
> }
>
>
>
> int search( position *p, alpha, beta, depth )
> {
> position next_position;
>
> ...
> ...
>
> foreach move
> {
> make_move( p, &next_position, move);
>
> // nega_max search
> score = -search( &next_position, -beta, -alpha, depth-1 );
>
>
> break if score >= beta
> ...
> }
>
> return(score);
> }
>
>
>
>
>
>
>
>
>
> Date: Wed, 8 Oct 2003 10:04:18 -0700
> Content-Type: text/plain; charset=US-ASCII; format=flowed
> From: Peter Drake <drake@xxxxxxxxxxxxxxxxx>
> X-BeenThere: computer-go@xxxxxxxxxxxxxxxxx
> X-Mailman-Version: 2.1.2
> Precedence: list
> Reply-To: computer-go <computer-go@xxxxxxxxxxxxxxxxx>
> List-Id: computer-go <computer-go.computer-go.org>
> List-Unsubscribe:
<http://computer-go.org/mailman/listinfo/computer-go>,
> <mailto:computer-go-request@xxxxxxxxxxxxxxxxx?subject=unsubscribe>
> List-Archive: <http://computer-go.org/pipermail/computer-go>
> List-Post: <mailto:computer-go@xxxxxxxxxxxxxxxxx>
> List-Help: <mailto:computer-go-request@xxxxxxxxxxxxxxxxx?subject=help>
> List-Subscribe: <http://computer-go.org/mailman/listinfo/computer-go>,
> <mailto:computer-go-request@xxxxxxxxxxxxxxxxx?subject=subscribe>
> Sender: computer-go-bounces@xxxxxxxxxxxxxxxxx
>
> We're contemplating doing some research on data structures for computer
> Go. It is not obvious to us how to store chains, groups, eyes,
> connections, and so on in an incrementally-updatable way that supports
> undo (which is necessary for any kind of search). The problem is
> further complicated by the fact that the objects being represented are
> fluid (growing, splitting, and merging) and sometimes ill-defined.
>
> To give one specific example, I don't know of an incremental version
> Benson's unconditional life algorithm. We have code to look at the
> entire board and tell what's unconditionally alive, but the whole thing
> currently has to be run from scratch for every new board.
>
> Is this something the computer Go community would find useful, or is it
> considered a minor implementation detail?
>
> Peter Drake
> Assistant Professor of Computer Science
> Lewis & Clark College
> http://www.lclark.edu/~drake/
>
> _______________________________________________
> computer-go mailing list
> computer-go@xxxxxxxxxxxxxxxxx
> http://computer-go.org/mailman/listinfo/computer-go
>
> _______________________________________________
> computer-go mailing list
> computer-go@xxxxxxxxxxxxxxxxx
> http://computer-go.org/mailman/listinfo/computer-go
>
_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://computer-go.org/mailman/listinfo/computer-go