Author: Russell Reagan
Date: 23:14:52 08/20/02
My question stems from two sources. The first was the code snippet from
Aristarch (http://www.zipproth.com/chess/For_programmers/for_programmers.html),
and the second came in the master's thesis recently posted here.
In the master's thesis (http://brick.bitpit.net/~blik/), he says that in his
program he didn't have a matching UndoMove() function, but instead made the move
on a copy of the position, and then taking back a move becomes trivial, just
decrement an array index. It seems to me that copying the entire position would
cost more than an UndoMove() function. Perhaps I am misunderstanding what he
said. Here is the text (page 41):
"Data moving
With so many move makers and data structures around we are faced with the task
of implementing their inverse functions as well. Not not only is this
error-prone, but it also increases the memory footprint again. So instead of
that we decided to perform the move makers on copies of the data that we must
keep invariant. If we do that, undo move is a trivial function. Copying an
attack table is, on average, about as expensive or faster than updating it. We
keep the side-dependent data, such as the piece lists, within the same block
that holds the attack table for that side. This brings us to and the second
advantage for copying: we now can exchange the friendly and enemy blocks during
make move(). Most operations in the move generators is and evaluator do no
operate on `white' or `black' data, but on `friend' and `enemy' data. Swapping
these blocks with each move again eliminates a lot of conditional code in these
modules."
I'm confused, because he talks about copying attack tables, but I fail to see
how performing the move on a copy of an attack table solves the problem of
having to write the UndoMove() function, so I assume he's talking about keeping
an array of positions, then to undo a move he just decrements a ply variable. To
me this would seem slower than running an UndoMove() function, having to copy
the entire position structure. Am I wrong about that?
I always assumed it was slower to copy over the entire position, but I read
this, and then I remembered seeing this code snippet from Aristarch:
int search_quiesence(int alpha, int beta) {
int result=eval(alpha,beta);
if (result>=beta) return result;
if (result>alpha) alpha=result;
pos[g].gen_captures();
if (select_moves(alpha)) return beta; //king cap.
for (int i=0; i<pos[g].n; i++) {
make_move(pos[g].move[i]);
result=-search_quiesence(-beta,-alpha);
undo_move();
if (result>alpha && (alpha=result) >= beta)
break; // move refuted opponent’s last one
}
return alpha;
}
It seems as though he is keeping an array of positions, and the undo_move()
function would just be a decrement of g, but again I think I am not
understanding exactly what he is doing.
I also see something that looks similar in Crafty with the TREE stuff, but I
quickly get lost in Crafty, and the UndoMove() function in Crafty appears to be
the inverse of the MakeMove() function, so I don't think Bob is using this
position array approach to making/unmaking moves.
Basically I'm curious if this is a good idea or not. I like the idea of having
an array of past positions, because then undoing a move is simple, and you don't
have to worry about saving and restoring values of the previous position
(captured piece, previous ep square/castling rights/50 move rule counter). It
sounds like this is the approach taken in Rookie, but I fear that I am
misunderstanding something. I would appreciate if someone could clarify what he
is talking about, and also provide some advice as to whether using a history of
positions and popping the current position is comparable to undoing the move
normally.
Thanks for your advice and help,
Russell
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.