how to continue

[tcusr]

hello everyone, i have a question regarding the development of my first chess engine.
at the moment i have bug-free pseudo-legal move generator and make/unmake functions for my board representation class.
(i tested my perft results with this data https://github.com/AndyGrant/Ethereal/b ... andard.epd, i hope it is enough for me to say it is bug-free).
with these parts of the engine done, in what order should i implement the next things?
this is my second attempt at writing an engine so i was able to reach this point on my own but now i going to do things i've never done, i would like to hear the opinion of more experienced chess engine writers

[lithander]

The step I did after that was to implement a UCI compatible engine that used the move generator to play random but always legal moves.

After that I implemented a min max algorithm searching all combinations of moves to depth four and returning the best move leading to the most favorable position for the side to move based on counting the material on the board.

Then I replaced the min max with an alpha beta search that, if implemented correctly, returns the same result as min max but much faster.

You got a weak chess engine at that point that responds to threats and avoids moves that have mediate refutations but has no idea where to put pieces. Plays like a child who just knows the basic rules. But it's a start!

[algerbrex]

hello everyone, i have a question regarding the development of my first chess engine.
at the moment i have bug-free pseudo-legal move generator and make/unmake functions for my board representation class.
(i tested my perft results with this data https://github.com/AndyGrant/Ethereal/b ... andard.epd, i hope it is enough for me to say it is bug-free).
with these parts of the engine done, in what order should i implement the next things?
this is my second attempt at writing an engine so i was able to reach this point on my own but now i going to do things i've never done, i would like to hear the opinion of more experienced chess engine writers

Hi Pier, congrats on getting to this stage! What you'll need to focus on next are the search and evaluation parts of your engine. The evaluation is what lets the engine look at a given position and judge how good it is for white or black. And the search is what allows the engine to find the best move in a given position. As you can probably tell, both parts work together pretty closely, and both are important to the improvement of an engine's strength.

With that said, here's what I recommend focusing on implementing:

Search:

• Negamax (https://www.chessprogramming.org/Negamax)
• Alpha-beta pruning (https://www.chessprogramming.org/Alpha-Beta)
• MVV_LVA move ordering (https://www.chessprogramming.org/MVV-LVA)
• Quiescence search (https://www.chessprogramming.org/Quiescence_Search)
• Iterative deepening (https://stackoverflow.com/questions/417 ... ta-pruning) and time-control logic (https://www.chessprogramming.org/Time_Management). These two features let your engine play games with set time limits, which is particularly useful once you starting testing your engine more extensively.

Evaluation:

• Material count (https://rustic-chess.org/evaluation/material.html)
• Piece-square tables (https://www.chessprogramming.org/Piece-Square_Tables)

From my experience, the above basics should land your engine anywhere between 1500-1700 Elo, depending on your engine's overall speed, and the quality of the piece-square tables.

For starting off, I recommend simply using the piece-square tables from a more mature engine and crediting the author. Sunfish's piece-square tables are good ones to try: https://github.com/thomasahle/sunfish/b ... sunfish.py. You can always come back in the future and craft your own, either hand rolling them or automatically tuning them.

Once you have the above in place, it's time to do some testing with your engine. This is a pretty nice thread that explains how to get into the process of testing your engine: . Let me know if you have any questions.

Testing will often seem tedious, but as I've found through personal experience, and as others on here can attest to, good testing is important for improving your engine and catching bugs. After I started going beyond the basic features listed above in my own chess engine, testing was crucial and making steady progress.

If you're still confused about the exact implementation of some of the points I listed above, there are a lot of online open-source engines whose code would be helpful to look at. Look around on GitHub, or on this forum, or feel free to check out the search and evaluation code my own engine to an idea of what to write: https://github.com/algerbrex/blunder/tree/main/engine.

Goodluck!

[tcusr]

thank you for your answers guys!
i just want to say that im not a complete a beginner, i am familiar with most of the things you guys said and i implemented them (in a crappy way) in my previous engine that i am rewriting.
so my idea now is to write a simple evaluation function (just counting the material, i can improve it later with PSQT) and then write a negamax function with the alphabeta pruning implementation described here https://web.archive.org/web/20080216030 ... habeta.htm
and last i will implement the UCI protocol, is this a good plan?

i have a few other questions
1) how do i know what's the move with the best score that i get from the search functions implemented by the link above? is using PV the only way?
2) my move generator first generates promotions, pawn captures (also en passant) then knight, bishop/queen/ rook/queen king captures and finally the rest of quiet moves, do i still need to order them with MVV/LVA? i use 2 different generators (noisy and quiet) because i now that i will have to run a quiescence search at depth of A/B
3) my pseudo-legal generator executes perft 6 from the initial position in 5.1 seconds (compiled with -O3) and perft 5 from kiwipete in 8.4 seconds, is this fast enough to not cause problems in the futures? will generating fewer moves improve this (with for example a special move generator if the king is in check? i am a bit worried because in my make move function i only the play the move and that's it
thank you again

[Mergi]

1) how do i know what's the move with the best score that i get from the search functions implemented by the link above? is using PV the only way?

What i like to do is have a special function for the root node alpha-beta search. This root alpha-beta is also inside the iterative deepening framework, making it extra convenient to actually be in a separate function, and also because you often have to perform lots of special actions in the root node. You simply keep looping through the root moves, keeping track of the best returned score from the main AB-search and the move associated with it.

2) my move generator first generates promotions, pawn captures (also en passant) then knight, bishop/queen/ rook/queen king captures and finally the rest of quiet moves, do i still need to order them with MVV/LVA? i use 2 different generators (noisy and quiet) because i now that i will have to run a quiescence search at depth of A/B

While this is a good start, MVVLVA sorting should still be very much more efficient for cutting down the search tree. Especially since there might be many pawn captures that you might have to go through before getting to the possibly best capture of for example a rook capturing a queen. You should also consider positional scoring using the piece-square tables when you sort your moves (moving to a high value square, capturing on a high value square etc.), all this helps tremendously. Generally, move sorting reigns supreme when optimizing your engine and it's where most gains can be achieved.

3) my pseudo-legal generator executes perft 6 from the initial position in 5.1 seconds (compiled with -O3) and perft 5 from kiwipete in 8.4 seconds, is this fast enough to not cause problems in the futures? will generating fewer moves improve this (with for example a special move generator if the king is in check? i am a bit worried because in my make move function i only the play the move and that's it

Your move generator is most definitely fast enough for now and should probably be the last of your concerns until you hit like 3000+ ELO. That is, unless you enjoy making fast perft - I personally had a great fun making my move gen run fast, probably even more so than working on the rest of the engine


After implementing the basic alpha-beta search and evaluation, i recommend getting the UCI (or winboard if your prefer) protocol up and running as soon as possible, to make testing through GUI possible.

Also, I just want to reiterate what others have said already - definitely don't underestimate proper testing and good programming practices, especially if you are not totally confident with all the algorithms yet! As i've been improving the strength of my own engine, going through the CCRL list and picking opponents to play against, i was surprised by just how many engines on there are straight up full of bugs and quite honestly, barely functioning (btw, big props to the people testing the engines and making ELO lists - makes it so much easier for developers to pick an opponent to play tests against!). There's so many ways to create bugs that will be invisible most of the time, never crashing your engine, or not even displaying obviously wrong moves, but instead making it play worse than it could/should be.

[Chan Rasjid]

What i like to do is have a special function for the root node alpha-beta search. This root alpha-beta is also inside the iterative deepening framework, making it extra convenient to actually be in a separate function, and also because you often have to perform lots of special actions in the root node. You simply keep looping through the root moves, keeping track of the best returned score from the main AB-search and the move associated with it.
...

Do not implement a special rootsearch() function! I did and found it was wrong. If your nps is 1 Mnps and your depth reached in 1 sec is 10, rootsearch() is called only 10 times, search() is called a million times! I think almost all programs just use an infinite loop:

Code: Select all

while(1){
	if (followpv){
		/*ply == 0 means at root; rootlist precomputed and 
		validated; use a memcpy() to initialize the
		 root move list */
		search_pv();		
	}else{
		search_nonpv();		
	}
}

[Mergi]

If your nps is 1 Mnps and your depth reached in 1 sec is 10, rootsearch() is called only 10 times, search() is called a million times!

I'm not sure i follow. Why would it be wrong to search the root moves 10 times each after reaching a depth of 10? Wouldn't the exactly same thing happen no matter if you have specialized function or not? I know some other engines don't have a specialized function for it, but unless your search function grows into gigantic proportions and becomes too hard to maintain separately, i find it way more convenient like this, especially if your engine has only minimal functionality.

Code: Select all

// iterative deepening
for(depth = 1; depth < max_depth; depth++) {

// do some root position stuff like sorting moves, sending info to GUI, etc.

	for(move in root_moves) {
		make_move();
		ABsearch(depth - 1, alpha, beta);
		unmake_move();
	}

// do some more root position stuff 
}

[Chan Rasjid]

If your nps is 1 Mnps and your depth reached in 1 sec is 10, rootsearch() is called only 10 times, search() is called a million times!

I'm not sure i follow. Why would it be wrong to search the root moves 10 times each after reaching a depth of 10? Wouldn't the exactly same thing happen no matter if you have specialized function or not? I know some other engines don't have a specialized function for it, but unless your search function grows into gigantic proportions and becomes too hard to maintain separately, i find it way more convenient like this, especially if your engine has only minimal functionality.

Code: Select all

// iterative deepening
for(depth = 1; depth < max_depth; depth++) {

// do some root position stuff like sorting moves, sending info to GUI, etc.

	for(move in root_moves) {
		make_move();
		ABsearch(depth - 1, alpha, beta);
		unmake_move();
	}

// do some more root position stuff 
}

I think I'm wrong. It is the same.

In your case, you do iterative deepening within your rootsearch() after gen-move, sorting, etc. So your root move list is always ready. Then you do iterative deepening.

The codes should be:

Code: Select all

	
rootsearch(){
  gen_root_move();
  /* sort, etc*/	
  for (depth = 1; depth < MAX; ++depth){
    while (move){
      /* may be good to have searchpv() and search(); */			
      search();		
    }
}

[tcusr]

If your nps is 1 Mnps and your depth reached in 1 sec is 10, rootsearch() is called only 10 times, search() is called a million times!

I'm not sure i follow. Why would it be wrong to search the root moves 10 times each after reaching a depth of 10? Wouldn't the exactly same thing happen no matter if you have specialized function or not? I know some other engines don't have a specialized function for it, but unless your search function grows into gigantic proportions and becomes too hard to maintain separately, i find it way more convenient like this, especially if your engine has only minimal functionality.

Code: Select all

// iterative deepening
for(depth = 1; depth < max_depth; depth++) {

// do some root position stuff like sorting moves, sending info to GUI, etc.

	for(move in root_moves) {
		make_move();
		ABsearch(depth - 1, alpha, beta);
		unmake_move();
	}

// do some more root position stuff 
}

i thought i was supposed to always sort the moves, not only at the root?
also, with this method, how do i get the line the engine searched? is this why PV is used?

[Mergi]

i thought i was supposed to always sort the moves, not only at the root?

Sorting moves at the root node is different. During the search itself, you sort moves by kinda just guessing how good they are in the most basic way, usually just by MVVLVA. However that is just a very rough guess, you don't want to spend too much time on trying to figure out precisely how good a move somewhere down in the search tree is. However in the iterative deepening framework, we can do much better than that for the root moves. Those can be sorted much more precisely based on how well they performed during the previous iterations. This can be done in multitude of different ways. First, you would search the best move that was found during the previous iteration, as for the rest of the moves, I like to keep track of their current score (there's a little caveat to that), previous iteration score and how many nodes were explored for that particular root move (more nodes explored means that the move was harder to refute, meaning it's probably a decent move) and sort them based on these 3 statistics.

also, with this method, how do i get the line the engine searched? is this why PV is used?

There are many different ways of collecting the PV. The chess programming wiki presents several of them as well, depending on the features that you have implemented in your engine some might perform better than others. For example, the Transposition Table makes it trivial to some extent, however you run the risk of not being able to display the full PV because of overwrites, and getting into infinite loops when extracting the moves. I used to use that approach combined with an additional special smaller hash table, that backed-up just the PV nodes in case they were overwritten in the main TT. Recently i got rid of that though, after implementing multithreading it just became too bothersome to try to preserve the PV nodes in this way.

What i do now is very similar to the "PV-list on the stack" solution on the chess programming wiki. You simply create a new PvLine struct in every node you search, and pass it down the tree, letting the nodes below fill it for you with the PV line they find. In c++, if you are lazy, you can use std::vector for this, as usually PV won't be changing too much, the costs of using higher abstractions are negligible. In root node you pass in an empty vector, and when the search is finished for that particular root move, you will have the PV line stored in the vector.

Slightly modified code from the wiki ...

Code: Select all

int AlphaBeta(int depth, int alpha, int beta, std::vector<Move> &parent_line) {

    if (depth == 0) {
        return Evaluate();
    }
    
    std::vector<Move> this_line;
    GenerateLegalMoves();
    while (MovesLeft()) {

        MakeNextMove();
        val = -AlphaBeta(depth - 1, -beta, -alpha, this_line);
        UnmakeMove();

        if (val >= beta) return beta;
        if (val > alpha) {
            alpha = val;
            parent_line = std::move(this_line); // copy the PV moves found deeper in the tree to our parent's PV line
            parent_line.insert(parent_line.begin(), ThisMove()); // insert our own PV move (the one that caused alpha to improve) at the beginning
        }
    }
    return alpha;
}