Author: Bas Hamstra
Date: 00:25:37 08/21/02
Go up one level in this thread
On August 21, 2002 at 02:14:52, Russell Reagan wrote:
>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
In my case I have a half/half approach, most of the 64 bit stuff, like the
update of the rotated bitboards (and I believe also the hashkeys) I push onto a
stack (which IS faster in my case). The rest I unmake().
Best regards,
Bas.
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.