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
Minimalist UCI chess engine written by self learner from scratch
Moderators: hgm, Rebel, chrisw
-
- Posts: 771
- Joined: Sat Sep 08, 2018 5:37 pm
- Location: Ukraine
- Full name: Maksim Korzh
Minimalist UCI chess engine written by self learner from scratch
Didactic chess engines:
https://www.chessprogramming.org/Maksim_Korzh
Chess programming YouTube channel:
https://www.youtube.com/channel/UCB9-pr ... KKqDgXhsMQ
https://www.chessprogramming.org/Maksim_Korzh
Chess programming YouTube channel:
https://www.youtube.com/channel/UCB9-pr ... KKqDgXhsMQ
-
- Posts: 855
- Joined: Sun May 23, 2010 1:32 pm
Re: Minimalist UCI chess engine written by self learner from scratch
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
From a first look I think l have seen a lot of small error.
I'll write a small report later
-
- Posts: 855
- Joined: Sun May 23, 2010 1:32 pm
Re: Minimalist UCI chess engine written by self learner from scratch
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.
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.
-
- Posts: 771
- Joined: Sat Sep 08, 2018 5:37 pm
- Location: Ukraine
- Full name: Maksim Korzh
Re: Minimalist UCI chess engine written by self learner from scratch
elcabesa, thank's a lot for pointing out those errors, you've helped me a lot!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.
Didactic chess engines:
https://www.chessprogramming.org/Maksim_Korzh
Chess programming YouTube channel:
https://www.youtube.com/channel/UCB9-pr ... KKqDgXhsMQ
https://www.chessprogramming.org/Maksim_Korzh
Chess programming YouTube channel:
https://www.youtube.com/channel/UCB9-pr ... KKqDgXhsMQ
-
- Posts: 771
- Joined: Sat Sep 08, 2018 5:37 pm
- Location: Ukraine
- Full name: Maksim Korzh
Re: Minimalist UCI chess engine written by self learner from scratch
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).elcabesa wrote: ↑Tue Sep 11, 2018 12:40 pm 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.
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;
}
Code: Select all
alpha < score < beta
? Thanks in advance and also Thank you for your hospitality as well.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.
Didactic chess engines:
https://www.chessprogramming.org/Maksim_Korzh
Chess programming YouTube channel:
https://www.youtube.com/channel/UCB9-pr ... KKqDgXhsMQ
https://www.chessprogramming.org/Maksim_Korzh
Chess programming YouTube channel:
https://www.youtube.com/channel/UCB9-pr ... KKqDgXhsMQ
-
- Posts: 27822
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Minimalist UCI chess engine written by self learner from scratch
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.
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.
-
- Posts: 771
- Joined: Sat Sep 08, 2018 5:37 pm
- Location: Ukraine
- Full name: Maksim Korzh
Re: Minimalist UCI chess engine written by self learner from scratch
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!
Didactic chess engines:
https://www.chessprogramming.org/Maksim_Korzh
Chess programming YouTube channel:
https://www.youtube.com/channel/UCB9-pr ... KKqDgXhsMQ
https://www.chessprogramming.org/Maksim_Korzh
Chess programming YouTube channel:
https://www.youtube.com/channel/UCB9-pr ... KKqDgXhsMQ
-
- Posts: 855
- Joined: Sun May 23, 2010 1:32 pm
Re: Minimalist UCI chess engine written by self learner from scratch
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;
}
-
- Posts: 855
- Joined: Sun May 23, 2010 1:32 pm
Re: Minimalist UCI chess engine written by self learner from scratch
FailHard or failsoft are a choice, point 3 is valid if he want to implement a failhard framework.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.
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.
-
- Posts: 855
- Joined: Sun May 23, 2010 1:32 pm
Re: Minimalist UCI chess engine written by self learner from scratch
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
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