Generating moves gradually

See Mediocre v0.3

To start off I can say that this is one way of doing this, I am sure there are plenty of other ways that might be better (or worse). All I know is this made Mediocre a whole lot faster and if you do not have something similar it might well be worth implementing it.

Older versions of Mediocre had one big move move generation method called generatePseudoMoves(). This method generated all possible moves on the board and these were then 'filtered' with the method filterMoves(). The filterMoves method filtered out the moves that left the own king in check which resulted in all the legal moves.

For quiescent search moves the same was done except only captures were verified for legality (and the rest discarded).

A quicker apporach

To save time it makes sense to only generate the kind of move we want, capture or non-capture.

This is done by separating the generatePseudoMoves() into two methods, gen_caps() and gen_noncaps(). We simply do not store any move that is not a capture in the gen_caps, and do not store captures in the gen_noncaps.

Already by doing this we are saving some time in the quiescent search, but the ordinary search needs to use both the methods to get all the legal moves obviously.

However this is only part of what we can do with this.

Gradually finding all moves

In Mediocre v0.241b I introduced a way to avoid generating moves before we searched the hash move. If the hash move caused a cut-off we saved the time it would cost to generate the moves.

However if the hash move did not cause a cutoff all moves were generated, ordered and searched in one go.

Elaborating on this approach we can split up all the move generation in a similar fashion. In pseudo code it looks something like this (see the source code for Mediocre 0.3 for the full code):

while(generationState < GEN_END)
{
switch(generationState)
{
case GEN_HASH:
selectHashMove();
break;
case GEN_CAPS:
gen_caps();
sortCapsWithSee();
selectNonLosingCaps();
break;
case GEN_KILLERS: // See below
case GEN_NONCAPS:
gen_noncaps();
sortWithHistoryHeuristicAndKiller();
selectSortedNonCaps();
break;
case GEN_LOSINGCAPS:
selectLosingCapsFromCaps();
break;

for(int i = startIndex; i < endIndex; i++)
{
pickMoveFromList();
verifyTheMoveForLegality();
searchMove();
}
generationState++;
}

As you can see we start with selecting the hash move (if it exists, which it should after the internal iterative deepening), and searching it.

After we have searched the hash move and it did not cause a cut-off we move on to generating captures and ordering them with SEE (explained later), making sure we do not research the hash move (this goes for all the proceeding steps, if we run into the hash move again we simply discard it since it has already been searched).

When the captures are ordered we will have two parts, one with good/equal captures, and one with losing captures (captures that seem to lose material). We start with searching the good/equal captures one by one, leaving the losing captures for later.

Here is the next big time saver, instead of verifying all moves up front, that is checking wether it leaves the king in check, we save that check for when we actually search the move. If we get a cut-off somewhere we saved all the time verifying the rest of the moves.

So we take the first move in the good/equal captures list, verify it for legality and then play it on the board and search it.

Next comes the killer moves, for now they are handled in the non-captures part (more below).

So we generate the non-captures, sort the killers first and then by their history heuristic values. Verify each move and search it.

And last we get to the losing captures which rarely are any good (queen capturing a protected pawn for example) and do the same with them. We can not simply discard the losing captures here since they might lead to a winning combination that the SEE does not spot (however in the quiescent search the losing captures are indeed discarded, more about that later).

Extending the idea; killer moves

The killer moves are always sorted first in the non-capture phase as I explained above. However we already have the killer moves available without generating anything at all.

The problem is the killer moves are moves that are generally good at the certain ply, but we can not know if the move actually exist in the position we are at.

For example capturing a rook with a bishop might usually be good at a certain depth, but if we moved that bishop earlier in the search that move probably does not exist at this particular position.

To solve this we could write a verifying method that takes the killer move and checks if it actually exists on the board, if it does we could just play it without generating all the non-captures first.

I have not done this for Mediocre yet but it seems like a good idea since the killer moves often cause cut-offs, saving the time it would take to generate the non-captures.

Extending the idea; check evasions

When the own king is in check there is a very limited amount of moves that can be made to avoid the check. So instead of generating all possible moves with gen_caps and gen_noncaps we could make a third method called gen_evasions that only generates moves that takes us out of check. With the given condition that we know our king is in check this could be done quite fast by searching for the checking piece and generating moves that intervenes it.

This way we would save some time by not generating a bunch of moves that would be instantly be discarded by the inCheck lookup anyway.

I have not done this yet for Mediocre, but probably will quite soon.

In conclusion

This saved a whole bunch of time for Mediocre, mainly because the old move-sorting scheme was very crude and did a whole lot of unnescessary work.

Saving work until it actually has to be done is generally a good idea.

Moving on to SEE.