I'm starting my college project to build my own chess engine. The problem is that I have no clue where to start or what to read. I found videos on YouTube but I don't want to be a copycat. I want to build it on my own. What should I read and how can I build it? Is there any chance that I can make it with my own ideas?
-
5Don't worry about copycatting to a certain extent. Plagiarism will get you in trouble, but just copying certain techniques and general ways of setting things up is standard practice in software development. If in doubt, ask the professor(s) where to draw the line. I say this as a software developer. Although, in this particular instance, I would advise you to go ahead and communicate with your professor(s) up front about using the same general techniques and setup, just to err on the side of caution.– PanzercrisisNov 9, 2021 at 15:33
-
3How ambitious a project is this intended to be?– RBarryYoungNov 9, 2021 at 18:28
-
2If you have to ask and it's just a project, don't. Most likely you'll spend a lot of time and have relatively little to show.– Bob JansenNov 9, 2021 at 21:42
-
1As I mention I want to take the advantage of this project to learn and build stuff from my own ideas.– Ahmed M.OsmanNov 10, 2021 at 15:48
-
Computer Chess II by David Welsh was quite influential for me, though since it came out in the mid-80's I'd guess it was pretty dated today (everything is pre-OO programming). On the other hand it was crucial for me in understanding alpha-beta pruning and it did have an description of the Negamax algorithm.– RBarryYoungNov 11, 2021 at 13:33
Add a comment
|
5 Answers
If your main goal is the engine, you can get the basic functionality following this kind of guide (i.e. https://andreasstckl.medium.com/writing-a-chess-program-in-one-day-30daff4610ec). With this, you can develop the basics (that guide is in python, but you can follow along with other languages): board painting, piece managing... (things that may be out of scope for your interests: the engine).
For creating a basic engine, you could start with this site: https://www.chessprogramming.org/Main_Page, in which you will have content to create your engine (you'll get the concepts, not the code itself), like the simplified evaluation: https://www.chessprogramming.org/Simplified_Evaluation_Function
With those concepts, you can enrich your engine as you go by.
Hope this helps!
The number 1 goal is to make an engine that makes a legal move. The immediate next goal is to make an engine that calculates all legal moves - you can choose one at random.
Next up is an evaluator - how good is a position? Again, we can start with a low goal - just consider checkmate to be the ultimate score, and count the pieces if the position is not checkmate. We can always improve the evaluation function, but you need one to get started.
-
9This shouldn't be sold short. Simply evaluating legality and validity (both for generating moves and for validating player moves) is a much more challenging task than it might seem at first glance and writing a valid chess board — not even engine — is a project I would expect to spend multiple days on. Nov 10, 2021 at 22:40
I think it has to be stated: you should start low.
First of all, as we are interested in a chess engine you should not spend effort creating a user interface (not even a crude one). You sbould make your engine speak either Chess Engine Communication Protocol or UCI. This way a number of existing graphical boards can be used with your engine, and lets you focus on the actual engine. This is exactly what is done by other engines such as Stockfish. And speaking the standard language for chess engines allows you run your program tests with other existing engines, to match against other programs, etc.
Second, your program will have to use some kind of internal representation of the game state. This will be basically the state of the board plus some additional flags (is castling allowed? An en-passant is possible?) Forsyth-Edwards Notation shows what you have to take into account. You could operate directly on FEN strings, but internally you may use any representation you want. You will need to translate between FEN and your internal structures.
Third, you will need to determine the moves you have available, as noted by MSalters. Initially make it pick a move at random.
At this point, you have a Minimum viable product. You have made your own chess engine. It plays quite badly, but you made an engine. From this point on, you could run out of time with your college project and still provide a working project.
Then the actual task is "just" making your engine play well, which is where things become really complex. You can build on existing algorithms, implement your own ideas and heuristics, etc.
Others have mentioned www.chessprogramming.org, but it does not seem to give a good explanation of negamax with alpha-beta pruning. You really need to understand this, as it is the key ingredient in getting an efficient chess engine. The static evaluation function is still important but much less than alpha-beta pruning and move-ordering heuristics and other pruning heuristics, as briefly mentioned in this related post. That is, if you replace the static evaluation function just by a checkmate checker plus a material balance evaluator, you would lose only a few moves of effective depth (i.e. you would need to search a few moves deeper to do as well as a better evaluation function that takes a small constant times as long to run). But if you remove alpha-beta pruning, your effective depth would be reduced by a significant fraction (possibly up to half)! And the move-ordering heuristics used with alpha-beta pruning as well as other pruning techniques would in general multiply the effective depth, hence improving them is very important!
-
1"you would lose only a few moves of effective depth": I disagree. If material balance is your only yardstick (except when mate is threatened), you will play a ridiculous game, choosing moves essentially at random (e.g. 1 Nc3 ... 2 Nb1). A reasonable static evaluation function is extremely important if you want to play well. I agree that it might be a good idea to implement a basic search before adding the evaluation function, but the program will play hopelessly badly.– TonyKNov 9, 2021 at 20:03
-
1@TonyK: Not that badly. Yes the opening will be weird, but once the opponent starts on a good opening the correct responses would be strongly favoured even with just material balance as the position evaluation function. If you think otherwise, and have the time to experiment, try taking SF and making the change, and let us know how high depth is needed to make it the same strength as the full SF at depth 14? Nov 9, 2021 at 20:37
-
2Well, we are both making unsubstantiated statements here. I am sure you are wrong, based on my extensive experience as a chess programmer in the distant past. But I am certainly not going to re-program SF to prove it to you.– TonyKNov 9, 2021 at 20:48
-
1@TonyK: Haha no problem. I also have extensive experience at designing AI for abstract games and combinatorial optimization problems. In the future when I have time, I will try to come back here and do the necessary experiments. =) Nov 9, 2021 at 20:51
I would recommend this video by Sebastian Lague. It will not give you all the answers, probably, but it summarizes a process of how he himself tried making an engine from scratch and what he learned along the way.
-
2Welcome to Chess! Whilst this may theoretically answer the question, it would be preferable to include the essential parts of the answer here, and provide the link for reference. Nov 8, 2021 at 23:01
-
1This. This is the correct answer. There's no way to summarise the video other than watch it yourself. it's exactly what OP's after a HowTo build an engine without much code to steal. Nov 11, 2021 at 14:25