What are the best approaches to designing a chess engine? What classes/structures should it have? How are they connected to each other? I'm building a chess engine but I often find myself overwhelmed. I've learned from numerous resources (such as chess programming wiki) the algorithms for move generation, and have implemented them myself, but the design and structure of the whole thing is just generally a mess. If you've ever made a chess engine, how did you approach this?
I'm building a chess engine but I often find myself overwhelmed
I can identify quite a lot with how you're currently feeling. So before I address your questions, I'd like to give some encouragement if I may.
I started working on writing a chess engine back in February of this year, so about 10 months ago. I still have the code from that first attempt I ever made at writing an engine. It was a mess, and I had no clue what I was doing, even though at that point I had been programming for a couple of years.
But one thing I will always give my past self credit for is that I learned a lot from that first attempt, and the second attempt was better...and the third, and the fourth, and the fifth, and so on. If I remember correctly I actually started over about 10 times before I finally was able to create a solid codebase for the engine that I could start building from.
But every time I started over, my goal got a little closer, and I made sure I learned from my mistakes. So even if you're at the point where your code has just become too buggy or too messy to continue working from, that's alright. Learn from your mistakes this go-round, take some time to lick your wounds, create a new blank slate, and start again. If you keep persevering like this, I believe eventually you'll have something you can be very proud of.
With that out of the way, let me address the questions in your post:
What are the best approaches to designing a chess engine? What classes/structures should it have? How are they connected to each other?
Here's how to think about things conceptually. A chess engine has three basic parts:
- Move generation: this phase generates all of the moves for a given position
- Search: this phase uses the move generator to generate all of the possible moves for the root position, and for each of those nodes generate all of their moves, and so on recursively until a certain depth is reached, or a checkmate or draw occurs. If the position isn't a checkmate or draw, then the engine needs some way of figuring out if the position it stopped at is good or bad for it, so this is where the evaluation phase comes in.
- Evaluation: This is the phase that looks at a given chess position and tries to assign an integer value for how good the position is for black or white.
Hopefully, you can start to see the connection between these three phases. The search is the heartbeat of any engine, and it makes calls to the move generation phase and the evaluation phase to do its job correctly.
Now, that's the 30,000 ft overview. As you've discovered, however, the implementation specifics are the hard part. Here is how I recommend you start.
- Move generator: You said you've already been working on this so that's good. I would recommend using a mailbox design like here. You'll need some different functions to generate moves for the different pieces as well. If this still seems daunting, there's are a lot of places you can find some pseudo-code. The CPW has some, but also search up "mailbox chess engines github" in google and look through some of the code you find to get some ideas. Once you have legal or pseduo-legal move generator, test it throughly using PERFT, on multiple positions. If that last link's format is confusing, read a little about FEN strings too.
- Search: You don't have to start off fancy here. You can just have a single function, copying the code here: https://www.chessprogramming.org/Negamax. Try to read a little to understand it. Then add some code in to clean things up to your liking. If you need to see some actually, feel free to look at an earlier version of my engine's search code here.
- Evaluation: again, starting off, simpler is better. Just count material. Let pawns be worth say 100 points, bishops and knights worth 300, rooks worth 500, and queens worth 900. And then count how many of each piece each side has, and multiply that by the value of the piece. As I'm sure you can tell, this is quite crude, as chess is much more than just material. But it's an excellent place to start!
Once you have these three parts written, implement a little bit of the UCI protocol and a time-management scheme so you can use your engine in a nice GUI, like Cute Chess or Arena. Again, if you need to see my code, there are many open-source engines on GitHub and other places. And always feel free to look at any code from my engine as well.
At this point, you should have a working chess engine. Will it beat a grandmaster? Probably not. It probably won't even be beating you very well. But the more important point is that you'll have somewhere you can build from.
Once you have the above implemented, start slow, and start reading about some ways to improve things. The next step could be to improve your move ordering and add a quiescence search phase. And after that, you can look into using piece-square tables, to start teaching your engine what squares are good for each piece type. And eventually, you can move on to techniques used in modern beasts like Stockfish or Komodo like pruning, and reductions, and extensions.
But again, take things slow, and start off simple. You can always come back later and improve things. But if you start off trying to do every little thing, you'll likely end up with a very messy and buggy program that will be no fun to continue working on.
Hopefully, this helped to get you started down the right path. If you have any questions, feel free to fire away. I'd love to help out, and will try to answer when I have free time.
P.S: Make an account at talkchess.com. There are many smart people, many much smarter than myself, who can also give wonderful advice about how to begin the rewarding yet sometimes challenging process of writing a novel chess engine. I can't wait to see your engine rated on the CCRL soon! :-)
Edit: First, I realize I didn't make it clear, but if you wanted to look through the code, my engines code is posted here: https://github.com/algerbrex/blunder (hopefully this isn't marked as self-promotion.)
Second, I forgot to recommend some YouTube series that I highly recommend you watch if you need more help with a certain part of your engine:
- Programming a chess engine in C
- Toyfish series (A play on the name of the current strongest engine in the world, Stockfish)
- Bitboard engine in C
Both creators are great programmers and even better teachers. Hopefully, those help as well!