Sample code: Moves and variations

[Evert]

To be honest, building from scratch all the board representation and move generation code was so painful. I'm happy it's behind me, and I don't want to go in there again, unless I really have a good reason to.

I've done it five or six times and found it got a lot easier every time.
Of course, the last few times I was fairly happy with how things had turned out earlier and so I based the newer design on the old one. It'd take me longer if I had to do it all completely from scratch.

I would like to implement Chess960 for the next version. I haven't really thought about it though. Currently my castling moves are encoded as "e1g1" (if you see what I mean), so I was thinking of just coding castling moves as KxR whether in Chess960 or normal chess. I guess it would not be too hard to implement like this ? Is it how everyone else does this ? Are there nasty traps to watch out for ?

I have no idea hoe everyone else does it, but in Jazz I simply store a flag "castle move" in the move structure (it's only one bit afterall), and I then pull the rook move from a table based on the king's destination square. Jazz doesn't play Chess960, but I don't think I'd change anything if I wanted to support that (but I'm not really interested in doing that).
Sjaak does support Chess960, but it also generates castle moves rather differently from Jazz. It has a set of 2x2x3 bitmasks (for 2 colours, king and queen side castling, and three test-masks). The test masks inidcate which squares to king and rook are on, which squares should be empty and which squares should not be attacked. It also has the king's destination squares stored in a table.
Implementing castling for FRC (or any variant) just requires initialisation of the castle masks, which is done at the start of a new game (based on the starting position and the known rules, like "king goes to g1" for white kingside castling).
The only caveat I can think of is that castling in some FRC positions could be a null-move as far as the king or the rook is concerned; it's also possible that the destination square for the king isn't empty initially (it may contain the rook). Those could be things to look out for (it'd be for Jazz, although it wasn't for Sjaak).

As for other chess variants, I'm not that much interested and will probably never to do anything else than normal chess and chess 960.

In case you feel like giving it a try some time, it's a lot of fun.

[bob]

Transposition table move storage:

The code is not written yet for transposition table move storage, but the design is ready.

Code: Select all

ttmovetype =
  packed record
    frsq: sqtype; { six bits )
    tosq: sqtype; { six bits )
    msc:  msctype { three bits }
  end;

Since the program generates all moves and matches a transposition table move against the generated output, it is impossible to play an illegal move. This is true even in the extremely rare case of a false positive.

There's a significant speed advantage if you search the hash move before generating other moves. Quite often it will produce a cutoff and you get to avoid the move generation entirely... You do need a legality checker, but that is pretty simple code anyway. And I don't have to check for "in check" since my normal search does that for each move to exclude illegal moves.

[sje]

There's a significant speed advantage if you search the hash move before generating other moves. Quite often it will produce a cutoff and you get to avoid the move generation entirely... You do need a legality checker, but that is pretty simple code anyway. And I don't have to check for "in check" since my normal search does that for each move to exclude illegal moves.

Generating all the moves at once for each full width node has several benefits:

1) Generating all the moves at once is faster than generating the gainers and then generating the holders; this pays off at every ALL flavored node.

2) Generating all the moves gives immediate stalemate/checkmate detection with no extra work as the generator returns the move count.

3) Generating all the moves allows for easy implementation of extension schemes like "single response to check" as the move count is known before any move is searched.

4) Killer moves, like transposition moves, are matched from the full generation list, so none can ever be mismatched nor is any tricky post-match verification needed.

5) Profiling shows that most of the work is done in the move execute/retract routines, and the effort done there (e.g., maintaining the attack-to-square array and the pinned man bitboards) saves time in the legal-only generator.

6) Having all the moves present before searching any of them can make preliminary score assignment more accurate.

That being said, the savings or loss is still dependent upon the relative distribution of work between the generator and every thing else. So much depends on move representation and on what kind of data is kept in the database.

[bob]

There's a significant speed advantage if you search the hash move before generating other moves. Quite often it will produce a cutoff and you get to avoid the move generation entirely... You do need a legality checker, but that is pretty simple code anyway. And I don't have to check for "in check" since my normal search does that for each move to exclude illegal moves.

Generating all the moves at once for each full width node has several benefits:

1) Generating all the moves at once is faster than generating the gainers and then generating the holders; this pays off at every ALL flavored node.

2) Generating all the moves gives immediate stalemate/checkmate detection with no extra work as the generator returns the move count.

This would mean you generate legal rather than pseudo-legal moves??

3) Generating all the moves allows for easy implementation of extension schemes like "single response to check" as the move count is known before any move is searched.

Same question again. I do pseudo-legal unless I start off in check, then I generate only pseudo-legal. However, the single-response-to-check hurts more than it helps according to testing.

4) Killer moves, like transposition moves, are matched from the full generation list, so none can ever be mismatched nor is any tricky post-match verification needed.

5) Profiling shows that most of the work is done in the move execute/retract routines, and the effort done there (e.g., maintaining the attack-to-square array and the pinned man bitboards) saves time in the legal-only generator.

Would not argue there. Only advantage to my approach is that I simply avoid any move generation costs whatsoever on about 92% of the fail high (CUT) nodes, because that's the percentage of the time that the first move fails high, which almost never needs a move generation (one can get cute even on ALL nodes, and store the first move searched as the best move, even though it isn't. But ordering it first later does not hurt, because without the move in the hash entry, you would still try it first... you did the last time around...

6) Having all the moves present before searching any of them can make preliminary score assignment more accurate.

Don't follow that one. I don't use the number of pseudo-legal moves in my evaluation or ordering...

I try the hash move. If that doesn't fail high, I generate just captures and try the ones with SEE >= 0. If none of those fail high, I try the two killers. If neither of those fails high, I generate non-captures and continue searching.

That being said, the savings or loss is still dependent upon the relative distribution of work between the generator and every thing else. So much depends on move representation and on what kind of data is kept in the database.

[sje]

In the case of a transposition table hit, the retrieved score or bound may be enough to get a cut off, so no move generation would be needed. The generator needs to be called only if there's a need for further search. The same holds true for other terminator conditions like draw detection and tablebase probes.

Yes, only legal moves come out of the move generator regardless of check status. It's easy an the execute/retract routines do all the work with updating the attack-to array and the pinned/frozen bitboards.

With fractional depth, a single reply can get a half ply extension, two replies can get a quarter ply extension, and three replies can get an eighth ply extension.

With all the moves present, a clever move ordering routine can give priority to moves that de-hang hanging major pieces vs small gainer moves like grabbing a loose pawn. This would otherwise be impossible if all "good" captures were generated and tried first.