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