Questions about chess programming from a newbie

[Sven]

So worry about move ordering first. Searching the PV of the previous iteration first, and capture of the highest piece next should get you in business.

Agreed but MVV/LVA based ordering of captures is already present in Quokka and seems to work correctly, at least according to the source.

[Steve Maughan]

Matt,

Congrats on creating an original chess engine (and commiserations on getting hooked on this crack-like addiction called chess programming)!!

You may find it helpful to look through old blog posts on my website. These chronicle the early stages of my chess engine. See the link below.

My general advice is to not concentrate too much on speed optimization at this stage. Instead focus on bug free code. Create a perft routine to check move generation.

Once your engine is 2000 to 2200 ELO you may consider a rewrite using bitboards and correct "all" of the design errors you've discovered so far.

Also take a look at the source code of Fruit 1.0. IMHO it's beautiful. Notice the simplicity and emphasis on big free code.

- Steve

[Sven]

Hi Matt,

there is another important issue. Within generate_moves() you assign a high bonus to all checking moves to search them early. This has three major drawbacks:

1) Almost all checking moves are actually bad moves during a realistic chess tree search so they should better not be searched prior to captures.
2) Calling in_check() for each single move during generate_moves() is quite costly.
3) In your case you do this even in quiescence search, and even for all quiet moves which you filter out later on.

Therefore I suggest
a) to simply remove the in_check() detection in generate_moves() and the bonus assignment for checks (and so also the additional make/unmake!),
b) to also write a capture-only generator which generates captures and promotions only (for quiescence search even queen promotions are sufficient) without generating many quiet moves only to filter them out later.

[hgm]

b) to also write a capture-only generator which generates captures and promotions only (for quiescence search even queen promotions are sufficient) without generating many quiet moves only to filter them out later.

This is not entirely trivial for mailbox representations. The naive way for generating slider captures would automatically make you step through all non-captures along a ray before you hit upon the capture at the end.

One way to avoid this is to keep track for each square of how far the nearest occupied square is in each of the eight directions. You can then immediately look at the end of the ray, without scanning through all intermediate squares along the ray. (And you can also quickly calculate the mobility from it.) This information is reasonably easy to update incrementally, especially on captures (i.e. in QS, where the engine spends most of the time anyway).

[Sven]

b) to also write a capture-only generator which generates captures and promotions only (for quiescence search even queen promotions are sufficient) without generating many quiet moves only to filter them out later.

This is not entirely trivial for mailbox representations. The naive way for generating slider captures would automatically make you step through all non-captures along a ray before you hit upon the capture at the end.

One way to avoid this is to keep track for each square of how far the nearest occupied square is in each of the eight directions. You can then immediately look at the end of the ray, without scanning through all intermediate squares along the ray. (And you can also quickly calculate the mobility from it.) This information is reasonably easy to update incrementally, especially on captures (i.e. in QS, where the engine spends most of the time anyway).

In the beginning the task is not necessarily to write the fastest possible capture-only generator, just one that avoids storing a long move list where most moves are irrelevant is already sufficient. It was fairly easy for me (due to a clear programming style of the author!) to copy the generate_pseudo_legal_moves() function of Quokka to a new function generate_pseudo_legal_captures() and change it appropriately so that it does not generate castles or normal pawn moves, and simply scans the entire ray for sliding pieces. You proposal is good but I would call it an optimization. So the "naive" way of starting with the simple and working approach is my recommendation.

[hgm]

True, but having a separate capture generator that only differs from the general move generator by not storing the non-captures is also an optimalization. And one that saves far less time than the distance map, as the store unit of the CPU is usually idle anyway.

In a sense storing the moves in a list is already an optimalization. Micro-Max doesn't do that. It just remembers the best move, to play that first.

The point is that you don't want to start with a 'dead-end design', which makes it impossible to perform further optimalization when you would get to the stage they are called for, without discarding all the stuff that you painfully tested and validated before.

So I would not recommend designs without move list, even though they do not buy you much as long as you still have a fixed-depth search possibly with search bugs. You'd better take the extra complexity of managing the list from the start, as an investment, to make sure you can easily improve your move sorting when the time comes to do that.

In the same spirit it seems better to already think a little bit ahead of how you will eventually want to generate captures in a more efficient way (i.e. other than just generating all moves, and only keep the captures). This can have a drastic effect on how you loop over moves. E.g. will you be generating them victim by victim through 0x88 tests, in a staged way, or will you generate them all at once, sorting by MVV afterwards.

[Sven]

The capture generator as I proposed it has the main advantage that it can be implemented very easily and bug-free, it is kind of low hanging fruit. Your proposal is kind of sophisticated (keeping track of information that you currently don't have yet, so you need some initialization code, some updating code, and some code that uses the information). You may be right that it saves more runtime than "my" version of a capture generator but please consider also the stage of development of this engine. Just keep it simple in the beginning. It may be easy to implement for a genius like you, with decades of experience in chess programming, but I would not suggest going that way in case of a chess programming beginner. Furthermore, I have never heard of any engine that uses your approach, so I would stick to the well-known concepts in the first step.

[hgm]

But there is also a lot to be said for the approach: "do it right, or don't do it at all". A separate move generator for captures is not needed if you already have a move generator for all moves. That you have to debug anyway for generating all captures correctly. So I would say it is better to just use that one, rather than duplicate the effort for hardly any speed gain, and embarking on a path that will make it more difficult to do something really fast later.

If the low-hanging fruit is unripe, eating too much of it just gives you a belly ache!

For beginning programmers I would recommend starting with a single mail-box generator that does both captures and non-captures, and stores the captures and promotions at the start of the move list, and the non-captures at the end. Then in QS you can simply break from the move loop when you reach the non-capture section of the move list.

And when the time comes to make some speed optimalizations, switch to a capture generator based on victim-wise staged 0x88 attack tests for all pieces in the piece list of the side to move. From an educational POV that seems more attractive as well, as doing this teaches you some new and generally useful tricks.

[Henk]

And when the time comes to make some speed optimalizations, switch to a capture generator based on victim-wise staged 0x88 attack tests for all pieces in the piece list of the side to move. From an educational POV that seems more attractive as well, as doing this teaches you some new and generally useful tricks.

I collect all captures and promotions and sort them later. I can imagine that collecting them in MVVA order directly at least makes sorting unnecessary. Also then I only need to generate each move one at the time for a fail high ends move generation. Do you know if that will give a big speed gain. Drawback is that it looks difficult to implement.

[That means I first have to find a capture of the king, then capture of the queen by pawn, knight, bishop etc.]

[hgm]

It depends on how exactly you generate the attacks on a piece. In Spartacus I started using conventional 0x88 attack testing, running through the piece list of the side to move for each victim to detect alignment. Only for Pawn attacks it looks on the two board squares from which they could possibly come (which is faster than testing for 8 Pawns whether they attack). So that means that on a full board you have to do 8 alignment tests for each victim. One advantage of the method is that this speeds up as the board gets more empty, and the piece list gets shorter.

I was surprised how competitive this was. I guess that with normal move generation, you typically have more than 8 moves per piece. So doing 8 alignment tests is probably not more expensive than looking for all moves of an average piece whether it is a capture. And the gain then comes from the fact that you can stop after a cut move, and at d <= 1 when you reach futile victims.