Quiescent Search (and Sorting MoveList)

[AndrewGrant]

So if you look at that code fragment I have two arrays, one to a list of moves, and one to a list of values. These arrays are matched up. Before searching any moves I will generate that list of values.

For TTHits and Killers, I add an additional weight onto those moves.

something of the form....

Code: Select all

for i = 0; i < numMoves; i++:
  if moves[i] == TTHit: values[i] = BIGNUMBER
  else if ISCAPTURE(moves[i]): values[i] = Value_Of_Capture

I am, however, not a fan of the way I currently do it. I would prefer to do move generation / searching in stages. Something like what is done in RodentII.

https://github.com/nescitus/Rodent_II/b ... c/next.cpp

[flok]

Very strange: every implementation I tried sofar eventually processes twice the number of nodes as the sorting version (and thus plays worse).

Code: Select all

// first I move some of the moves to the front of the movelist. softStartOffset points to the first move after that

// the ones moved to the start get infinite score so that they're always evaluated first
        short *mval = new short[nMoves];
        for(size_t idx=0; idx<sortStartOffset; idx++)
                mval[idx] = infinite;

// give the others their sort value
        for(size_t idx=sortStartOffset; idx<nMoves; idx++)
                mval[idx] = sortValue(moves -> atPointer(idx), b);

...
        for(size_t idx=0; idx<nMoves && !*stopFlag; idx++) {
                size_t best = 0;
                if (mval[best] < infinite) {
                        for(size_t i=1; i<nMoves - idx; i++) {
                                if (mval[i] > mval[best])
                                        best = i;
                        }
                }

                const Move m = moves -> at(best);

                moves -> set(best, moves -> at(nMoves - idx - 1));
                mval[best] = mval[nMoves - idx - 1];

Code: Select all

int sortValue(const Move *const restrict m, const Board *const restrict b)
{
	const ChessPiece *attacker = b -> getAt(m -> fx, m -> fy); // from
	const ChessPiece *victim   = b -> findVictim(*m); // to

	int attackerValue = attacker -> getType() + 1;
	int victimValue = victim ? victim -> getType() + 1 : 0;
	int promoteValue = m -> promoteTo == NONE ? 0 : m -> promoteTo + 1;

	return ((victimValue + promoteValue) << 3) | (7 - attackerValue);
}

Note that this sortValue is also used for the version that does sort.