Minimalist UCI chess engine written by self learner from scratch

[maksimKorzh]

Hi all! It's the great honor for me that I was allowed to join this great community. I apologize if this is not the right place to post such a topic and hope the moderators kindly explain if I was wrong. So let's get to the point. I'd really appreciate any kind of feedback to my work - after for about a three years of researching how does particularly a chess engine works and numerous unsuccessful attempts to write my own I've finally managed to complete one. This is github repo https://github.com/maksimKorzh/Chenglite . I'm hobby programmer and self learner as well, so basically I've learned C via trying to write a chess engine, that's why your professional opinion about my engine is so important to me. There's only one source file so it won't take you long to have a quick look at the code to evaluate it and give me a brief feedback. Thanks for your attention.

With the deepest respect to the community, Maksim Korzh

[elcabesa]

First of all congratulation for your first attempt.

From a first look I think l have seen a lot of small error.
I'll write a small report later

[elcabesa]

Some errors
1) Quiescence search and nega max search. Take back should be placed before if (score >= beta) otherwise you return without having take back the move.
2) quiescence search. If you are in check you have to switch back to all move generation, not only capture.
3) quiescence. It looks like you are using a fail hard framework. When returning score you have to limit the range between alpha and beta.
4) quiescent search. Limiting depth to 4 is not very good, it's better to implement stand pat score. If alpha <score < beta and not in check.... return score.

[maksimKorzh]

Re: Minimalist UCI chess engine written by self learner from scratch
Post by elcabesa » Tue Sep 11, 2018 10:40 am

Some errors
1) Quiescence search and nega max search. Take back should be placed before if (score >= beta) otherwise you return without having take back the move.
2) quiescence search. If you are in check you have to switch back to all move generation, not only capture.
3) quiescence. It looks like you are using a fail hard framework. When returning score you have to limit the range between alpha and beta.
4) quiescent search. Limiting depth to 4 is not very good, it's better to implement stand pat score. If alpha <score < beta and not in check.... return score.

elcabesa, thank's a lot for pointing out those errors, you've helped me a lot!

[maksimKorzh]

Some errors
1) Quiescence search and nega max search. Take back should be placed before if (score >= beta) otherwise you return without having take back the move.
2) quiescence search. If you are in check you have to switch back to all move generation, not only capture.
3) quiescence. It looks like you are using a fail hard framework. When returning score you have to limit the range between alpha and beta.
4) quiescent search. Limiting depth to 4 is not very good, it's better to implement stand pat score. If alpha <score < beta and not in check.... return score.

Marco, I understand first two points - that's absolutely clear, so I've fixed TakeBack and got rid of checking out if in check for it slows down the performance too much (I have no move ordering for now).

The problem is in understanding point 3 and 4, I feel like a complete dumb... I've removed fixed depth 4 quiescence, here is the code

Code: Select all

static inline int QuiescenceSearch(int alpha, int beta, CHESSBOARD *board, SEARCH *info)
{
	int score = EvaluatePosition(board);
	
	// if there are no captures
	if(score > alpha)
		alpha = score;
	
	MOVELIST list[1];
	GenerateMoves(board, list);
	
	// if there are captures in position
	for(int moveNum = 0; moveNum < list->moveCount; ++moveNum)
	{
		CHESSBOARD boardStored[1];
		boardStored[0] = board[0];
		
		if(!MakeMove(board, list->moves[moveNum].move, captures))
			continue;
		
		//depth++;
		score = -QuiescenceSearch(-beta, -alpha, board, info);
		TakeBack(board, boardStored);

		if(score >= beta)
			return beta;
		
		if(score > alpha)
			alpha = score;
	}
	
	return alpha;
}

and now it seems to work perfectly well, but if the depth is say 3 - it starts to be slow as hell, but assume that is still because of the lack of move ordering. Could you please point out in more details where exactly the condition

Code: Select all

alpha < score < beta

must take place in quiescence? And what did you mean by saying

3) quiescence. It looks like you are using a fail hard framework. When returning score you have to limit the range between alpha and beta.

? Thanks in advance and also Thank you for your hospitality as well.

[hgm]

If you increase the score in QS to the static eval, you should check immediately if that score is now >= beta. Now you only do the test after moves are generated, and one move is searched, which would all be wasted affort in that case. A lot of wasted effort, because that move will lead to a new node where you also have to search at least one move, etc. Sou you will always have to follow one branch to the point where one player has exhausted all his captures, even when the static eval was above beta.

Move order is indeed important; with random ordering you will usually reach a point in the game where an unlimited-depth QS completely explodes. Thus usually happens because of 'plunder raids' by Queens, as Queens are very good at creating new capture possibilities when making a capture. So some of the branches search won't terminate before the board is almost completely empty. Giving priority to capturing the most-valuable piece, or even to the most-recently moved piece is usually enough to prevent that; then there suddenly isn't so much material anymore that Queens can capture without being immediately punished.

In my own minimalist engine micro-Max I search the best move of a one-ply-less-deep search first (and no sorting on the remaining moves), and at 0 ply (QS) the capture of the most-valuable victim. That turns out to work quite well, and can be seen as a minimum requirement.

I don't believe that point 3 was valid. It should never hurt to return the true score. It would not exactly be 'fail hard', but there is no reason why you should want to use fail hard, as it has absolutely no advantage to do so.

[maksimKorzh]

Wow, that's fantastic answer, making all the things completely clear to me now! Thank's a lot. H.G.Muller, I'm great fan of you and this is the great honor for me to get an answer from you, I've researched MicroMax as far as I could understand it... well, at least I've read a lot at your site describing how MicroMax works. Many, many thanks!

[elcabesa]

maybe I could be wrong somewhere but your search can be rewritten this way, take a look at it

Code: Select all

static inline int QuiescenceSearch(int alpha, int beta, CHESSBOARD *board, SEARCH *info/*, int depth*/)
{
	int eval = EvaluatePosition(board);
	int capScore = 0;
	
	// if in check do a negamax check at depth 1 to evade check
	if(InCheck(board, side)) 
		return NegaMaxSearch( alpha, beta, board, info, 1);
	
	info->nodes++;
	
	// stand pat ( if the result > alpha before capturing an enemy piece, don't move and return alpha, avoid search size explosion
	if( eval > alpha )
	{
		return eval;
	}

	//-------------------------------------------------
	// iterate on the movelist, here we cannot be in check
	//-----------------------------------------------------
	MOVELIST list[1];
	GenerateMoves(board, list);
	
	// if there are captures in position
	for(int moveNum = 0; moveNum < list->moveCount; ++moveNum)
	{
		CHESSBOARD boardStored[1];
		boardStored[0] = board[0];
		
		if(!MakeMove(board, list->moves[moveNum].move, captures))
			continue;
		
		capScore = -QuiescenceSearch(-beta, -alpha, board, info/*, depth - 1*/);
		TakeBack(board, boardStored);

		if(capScore >= beta)
			return beta;
		
		if(capScore > alpha)
			alpha = capScore;
			
		
	}
	return alpha;
}


static inline int NegaMaxSearch(int alpha, int beta, CHESSBOARD *board, SEARCH *info, int depth)
{
	int legalMoves = 0;
	int bestScore = -50000;
	int bestMove = 0;

	if(depth <= 0)
	{
		return QuiescenceSearch(alpha, beta, board, info, 4);
	}
	
	info->nodes++;
	
	MOVELIST list[1];
	GenerateMoves(board, list);
	
	for(int moveNum = 0; moveNum < list->moveCount; ++moveNum)
	{
		CHESSBOARD boardStored[1];
		boardStored[0] = board[0];
		
		if(!MakeMove(board, list->moves[moveNum].move, all))
			continue;
		
		legalMoves++;
		int score = -NegaMaxSearch(-beta, -alpha, board, info, depth - 1);
		TakeBack(board, boardStored);	
		
		if(score > bestScore)
		{
			bestScore = score;
			bestMove = list->moves[moveNum].move;
			
			info->bestScore = bestScore;
			info->bestMove = bestMove;
			
			if(score >= beta)
				return beta;
				
			if(score > alpha)
				alpha = score;	
		}
	}
	
	// checkmate/stalemate detection
	if(!legalMoves)
	{
		if(InCheck(board, side))
			return -100000; // on checkmate
			
		else
			return 0; // on stalemate
	}
	
	if(bestMove)
	{
		info->bestScore = bestScore;
		info->bestMove = bestMove;
	}
	
	return alpha;
}

[elcabesa]

I don't believe that point 3 was valid. It should never hurt to return the true score. It would not exactly be 'fail hard', but there is no reason why you should want to use fail hard, as it has absolutely no advantage to do so.

FailHard or failsoft are a choice, point 3 is valid if he want to implement a failhard framework.

I agree with you that failhard has no advantage over failsoft and my engine use failsoft, maybe failhard is a little easy to debug and understand for a novice.

now just the definition of failhard and failsoft :
Failhard: your program use a failhard framwork if all the search routines ( negamax and quiescence ) always return a value in the closed range [ alpha; beta ].
Failsoft, your search can return values outside the alpha or beta bound

Example : if your final score has a value of 500, and you are searching with a window [alpha = 100, beta = 200], in failhard you'll have to return 200, in failsoft you can return 500.

[elcabesa]

a good tutorial on how to write a chess engine is:

http://web.archive.org/web/201201121138 ... /index.htm

unfortunately the site doesn't exist anymore and the only reference is in this archive, some images are lost