Trying to build a smarter legal move generator

[Mike Sherwin]

I not only want it to make a list of legal moves I want it to score each move using simple precomputed piece square tables, pawn evaluation and mobility. I'm not sure how to include mobility in the evaluation. Here is what I have so far.

Code: Select all

static s32 Qsearch(Thread* t, s32 alpha, s32 beta) {
	sMove m[40];
	s32 legal, score, eval;
	eval = Evaluate(t);
	if (eval > alpha) {
		if (eval >= beta) return beta;
		alpha = eval;
	}
	legal = GenCaptures(t, m);
	if (!legal) return -ILLEGAL;
	for (s32 i = 0; m[i].ft != ES; i++) {
		NextMove(m, i);
		MakeMove(t, &m[i]);
		nodes++;
		score = -Qsearch(t, -beta, -alpha);
		TakeBack(t, &m[i]);
		if (score > alpha) {
			if (score >= beta) return beta;
			alpha = score;
		}
	}
	return alpha;
}

static s32 LMG(Thread* t, sMove* list) {
	sMove m[200];
	s32 l = 0;

	s32 n = GenAllMoves(t, m);

	for (s32 i = 0; m[i].ft != ES; i++) {
		MakeMove(t, &m[i]);
		m[i].sc = -Qsearch(t, -INF, INF);
		TakeBack(t, &m[i]);
		if (m[i].sc != ILLEGAL) {
			list[l] = m[i];
			l++;
		}
	}
	list[l].ft = ES;
	return n;
}

It is assumed that LMG (Legal Move Generator) is only called from legal positions. GenAllMoves is a pseudo legal move generator that returns pseudo mobility, n. Before any attempt at optimization -Qsearch is called with an open window to get an accurate score. ILLEGAL is -10;000. if != Illegal the move is added to the list of legal moves. I don't see a way to use mobility (n)? Do I just store mobility for each ply of the search and access it in the Evaluate function? The scores of the LMG list are used for move ordering, LMR and at the leafs for the actual scores that are backed up in the Search().

Any insights and/or advice is welcome. Thanks in advance!

[hgm]

If you call QS on every move (even those that are going to be skipped due to a beta cutoff), why bother with legal generation? QS will trivially find whether it can capture the King, and cause the move leading to it to get the 'illegal' score.

It sounds very expensive, though. Not so much in all-nodes, where you would search all moves anyway, but in cut-nodes, where you would search all moves but one in vain, in 90% of the cases, because the first one you try already gives the cutoff.

I suppose you would only do this at d=1, as for larger depth a previous iteration would already have done it at d=1, and the result would already be known as the hash move. And in any case, if d>=3 the node would have already been searched at d=2, and what it found as cut-move there should be more reliable than now starting to find a new one from schratch at d=1.