make/unmake

[Robert Pope]

I've been thinking about doing a fresh rewrite of Beaches, and it seemed like one of the pieces that always gave me grief was properly restoring board flags in unmake: ep status, castle status, piece captured. Beaches held the changes in the "move" structure, and that never seemed very clean to me, possibly because I tried to be too compact about it.

How does everyone else store board info for an unmake?

Thanks,
Rob

[H.G.Muller]

For me things like moved piece, captured piece, hash key, and e.p. square are local variables of the search routine (possibly passed to it as an argument), so there is little to restore: the previous value automatically takes effect if the deeper stack frame is discarded on subroutine return. I do have to put the captured and moved piece back on the board, of course, but that seems unavoiable in any scheme that doesn't make copies of the entire board.

The castling status is hidden in the piece codings on the board: I set (or clear) a bit there when a piece is moved to a new location. Since during the unmake the piece that is put back is not taken from the board but from the local variable, this is also automatically undone as well.

[Alessandro Scotti]

Before entering the make/unmake loop I save all the required data into a PosUnmake structure. Then, I pass back this structure to unmake(), so that it can get the data it needs.

[H.G.Muller]

For my new engine I contemplate integrating the make/unmake code at the beginning/end of the search routine, respectively. Upto now I always put it in the loop over moves just before and after the recursive call, which seemed the logical place considering how you start the tree at the root. But as I am making more and more search calls from other places (where some selecteively generated moves are tried before full move generation, such as hash move, null move, recaptures, pin probes) it is a pain that I have to do the make/unmake in so many different places.

If I pass the move to be searched as a pointer to the entry on the move stack, that can also be used to pass back the move score and depth and best reply, passing the information is cheap. One of the advantages is that it can first update the hash key according to the move, and access the table to see if there is a useful hit. If there is, it never has to make the move. A (lazy) evaluation might also be possible in end leaves without making the move, and the search routine can be programmed to exploit these cases.

The downside is that the make/unmake should also be able to handle null move (most likely by conditionally skipping most of it).