alphabeta issue

[Sven]

When not using minimax any longer you also don't need to know the color of the moving side at the root node at arbitrary nodes in the tree. You should choose a name that reflects the semantics, also to avoid introducing new bugs.

Well, it can be a matter of convenience. E.g. to be able to do a simple compare so that I can either use the "regular shannon" (for the opponent moves) and my own "enhanced shannon" (for the moves my engine performs).

One more point: what exactly is the purpose of your "validateMoves()" method? In the snippet above you use it right after making a move. Does it validate (I guess: check legality of) ONE move, or ALL moves?

It validates all of them. So I do a move, then automatically all possible moves are calculated and then that validate command sees which are determined.

Could you please explain the meaning of "moves are calculated" and of "sees which are determined"?

Code: Select all

Scene::Move(Move move) {
     return new Scene(move);
}

// constructor
Scene::Scene(Move move) {
     // execute move
     // calculate moves that white and black can do
}

Scene::validateMoves(PlayerColor color) {
     // validate the moves for player 'color'
}

A second question: why does that "validateMoves()" call appear at that point in the search instead of appearing above the move loop (possibly implying few other changes)?

Oh that is an historical thing. I could move it in to the top of alphabeta but it would not give a direct gain. Maybe easier to read for outsiders but the program is not ready for opensourcing anyway.

Sorry, now I'm lost. I don't understand your alphaBeta search any longer. It is too unusual for my eyes and my brain.

When making a move M1 (you do it by copying the current position - "Scene" - and then modifying the copy, which is o.k. for me), why do you immediately calculate which moves are possible "for white and black" from the new position? Only one side can make moves in the new position. And furthermore, instead of generating moves immediately, the first thing you have to do is check whether the previous move that led to the current position was actually legal (unless you follow the "king capture" legality checking strategy, where you have to do something different). If it wasn't legal then don't bother with generating moves or even searching them, but skip the current move M1 and continue with the next move M2 of your move loop.

Sven

[flok]

When making a move M1 (you do it by copying the current position - "Scene" - and then modifying the copy, which is o.k. for me), why do you immediately calculate which moves are possible "for white and black" from the new position? Only one side can make moves in the new position.

I thought it was required for doing the evaluation. I read at http://chessprogramming.wikispaces.com/Evaluation this:
+ 0.1(M-M') where M is: M = Mobility (the number of legal moves)
Also it is required for me to see if my king is check.

And furthermore, instead of generating moves immediately, the first thing you have to do is check whether the previous move that led to the current position was actually legal (unless you follow the "king capture" legality checking strategy, where you have to do something different). If it wasn't legal then don't bother with generating moves or even searching them, but skip the current move M1 and continue with the next move M2 of your move loop.

That's why I do the validateMoves fist: first I see which moves I can do validly, and then I go through them for evaluation of alphaBeta() calling.

[lucasart]

Hi,

I implemented alphabeta in my chess-engine.
That seems to work until it encounters a checkmate happening before it reaches the end of the search-tree: it then tries to continue the search without a king.
My move generator then aborts (throws an exception) as it cannot do its thing without a king.
So to solve that, I either need to hack the movegenerator to just continue without the king but I don't like that as it is hackery.
So my question is: what is the regular way of aborting the search?

thanks

Quite simple, at every node of the search, you test to see whether the current position is mate (or stalemate) and stop the search if it (returning either a "mate in X ply" score or zero for a stalemate)
Perhaps your move generator assumes the current position is not check. Generating legal moves when the current position is in check is typically done by a separate function, as it behaves very differently.
And in the quiescent search, when the position is check, you generate all legal evasions, instead of captures only. If no moves were generated and the position was check, then it's mate or stalemate and you exit. Also beware not to leave the choice in the qsearch to accept the static eval when in check!

Here's my code to generate legal moves when in check. It's in C, but with the comments you should be able to figure out what it does and rewrite it in your own JAVA code

Code: Select all

move_t *gen_evasion(const Board *B, move_t *mlist)
/* Generates evasions, when the board is in check. These are of 2 kinds: the king moves, or a piece
 * covers the check. Note that cover means covering the ]ksq,checker_sq], so it includes capturing
 * the checking piece. */
{
	assert(board_is_check(B));
	const int us = B->turn, kpos = B->king_pos[us];
	const uint64_t checkers = B->st->checkers;
	const int csq = first_bit(checkers),	// checker square
		cpiece = B->piece_on[csq];			// checker piece
	uint64_t tss;

	// normal king escapes
	tss = KAttacks[kpos] & ~B->all[us] & ~B->st->attacks;

	// The king must also get out of all sliding checkers' firing lines
	uint64_t _checkers = checkers;
	while (_checkers) {
		const int _csq = next_bit(&_checkers),
		    _cpiece = B->piece_on[_csq];
		if (is_slider(_cpiece))
			tss &= ~Direction[_csq][kpos];
	}

	// generate King escapes
	while (tss) {
		int tsq = next_bit(&tss);
		mlist = serialize_moves(B, kpos, tsq, mlist);
	}

	if (!board_is_double_check(B)) {
		// piece moves (only if we're not in double check)
		tss = is_slider(cpiece)
			? Between[kpos][csq]	// cover the check (inc capture the sliding checker)
			: checkers;				// capture the checker

		/* if checked by a Pawn and epsq is available, then the check must result from a pawn double
		 * push, and we also need to consider capturing it en passant to solve the check */
		uint64_t ep_tss = cpiece == Pawn ? get_epsq_bb(B) : 0ULL;

		mlist = gen_piece_moves(B, tss, mlist, 0);
		mlist = gen_pawn_moves(B, tss | ep_tss, mlist);
	}

	return mlist;
}

[lucasart]

When making a move M1 (you do it by copying the current position - "Scene" - and then modifying the copy, which is o.k. for me), why do you immediately calculate which moves are possible "for white and black" from the new position? Only one side can make moves in the new position.

I thought it was required for doing the evaluation. I read at http://chessprogramming.wikispaces.com/Evaluation this:
+ 0.1(M-M') where M is: M = Mobility (the number of legal moves)
Also it is required for me to see if my king is check.

And furthermore, instead of generating moves immediately, the first thing you have to do is check whether the previous move that led to the current position was actually legal (unless you follow the "king capture" legality checking strategy, where you have to do something different). If it wasn't legal then don't bother with generating moves or even searching them, but skip the current move M1 and continue with the next move M2 of your move loop.

That's why I do the validateMoves fist: first I see which moves I can do validly, and then I go through them for evaluation of alphaBeta() calling.

I think you should forget about evaluation for the moment. Just material (plus piece on square table if you want). And before you write code, run it and say, I don't understand it plays stupid moves and captures the king, you should spend sometime with pencil and paper and understand how alpha beta minmax actually works.

Here's some pseudo code to help you understand what the most minimalistic search should do:

Code: Select all

search(depth, ply, alpha, beta)
{
	if (depth <= 0)
		return quiescent_search(depth, ply, alpha, beta)

	best_score = -infinity
	
	if (in_check)
		legal_moves = generate_evasions()
	else
		legal_moves = generate_moves()

	for (move in legal_moves)
	{
		play(move)
		score = -search(depth-1, ply+1, -beta, -alpha)
		undo(move)
		
		best_score = max(best_score, score)
		if (best_score >= beta)
			return best_score	// beta cutoff
	}
	
	if (legal_moves is empty) {
		if (in_check)
			return mated_in(ply)
		else
			return 0	// stalemate
	}
	
	return best_score
}

Now try to write a quiescent search in this kind of pseudo code, and imagine running it mentally on chess positions.
Of course I'll give you the "solution", but only if you make your own attempt. It's only by trying and failing that I understood these things.

[lucasart]

Here's my code to generate legal moves when in check.

The simple solution to generate check evasions would be:
* generate all moves using the normal move generator
* play and undo each move, and removes from the list any move that results in self-check
Of course, it's slow, but I suggest you start like this and later on come back to it and write an efficient evasion generator

[flok]

When making a move M1 (you do it by copying the current position - "Scene" - and then modifying the copy, which is o.k. for me), why do you immediately calculate which moves are possible "for white and black" from the new position? Only one side can make moves in the new position.

I thought it was required for doing the evaluation. I read at http://chessprogramming.wikispaces.com/Evaluation this:
+ 0.1(M-M') where M is: M = Mobility (the number of legal moves)
Also it is required for me to see if my king is check.

I now create a list moves only when required. E.g. when some code uses it.

[Sven]

Here's some pseudo code to help you understand what the most minimalistic search should do:

Fully agreed, only one element is missing in that pseudo code, the updating of alpha, as shown below:

Code: Select all

		best_score = max(best_score, score)
		if (best_score >= beta)
			return best_score	// beta cutoff
		if (best_score > alpha)
			alpha = best_score	// raise alpha

Sven

[lucasart]

Here's some pseudo code to help you understand what the most minimalistic search should do:

Fully agreed, only one element is missing in that pseudo code, the updating of alpha, as shown below:

Code: Select all

		best_score = max(best_score, score)
		if (best_score >= beta)
			return best_score	// beta cutoff
		if (best_score > alpha)
			alpha = best_score	// raise alpha

Sven

oh yes, I forget to raise alpha

[flok]

Here's some pseudo code to help you understand what the most minimalistic search should do:

Fully agreed, only one element is missing in that pseudo code, the updating of alpha, as shown below:

Code: Select all

		best_score = max(best_score, score)
		if (best_score >= beta)
			return best_score	// beta cutoff
		if (best_score > alpha)
			alpha = best_score	// raise alpha

Sven

According to http://chessprogramming.wikispaces.com/Alpha-Beta that is incorrect: if best_score >= beta, one should return beta, not best_score.

[lucasart]

Here's some pseudo code to help you understand what the most minimalistic search should do:

Fully agreed, only one element is missing in that pseudo code, the updating of alpha, as shown below:

Code: Select all

		best_score = max(best_score, score)
		if (best_score >= beta)
			return best_score	// beta cutoff
		if (best_score > alpha)
			alpha = best_score	// raise alpha

Sven

According to http://chessprogramming.wikispaces.com/Alpha-Beta that is incorrect: if best_score >= beta, one should return beta, not best_score.

it's not wrong or right. there are two ways of doing alpha beta, one is called fail hard (what you describe) and the other is called fail soft.
fail soft is what all good engines do nowadays, but you can try with fail hard if you like. or try both and compare the node counts... and introduce a hash table in there. food for thoughts

Actually the link you give also describes fail soft.