People have been interested in chess-playing computers before there were any chess-playing computers. In a 1950 paper, [Claude Shannon] defined two major chess-playing strategies. Apparently, practical chess programs still use the techniques he outlined. If you’ve ever wondered how to make a computer play chess [FreeCodeCamp] has an interesting post that walks you through building a chess engine step-by-step.
The code is in JavaScript, but the approach struck us as old school. However, it is interesting to watch the evolution of code as you go from random moves, to slightly smarter strategy, to deeper searching. Because it is in JavaScript, you can follow along in your browser and find out when the program gets smart enough to beat you. The final version is even on GitHub.
The algorithm is a classic one. First, for each piece, you evaluate the possible moves and rate them. Then you generate all the possible opponent moves and rate them. You keep going as deep as you can, but the search space becomes very large, quickly. To make it simpler to think about, consider a 4×4 checkerboard with four red checkers on one side and four black checkers on the other. For the first move, there are four possible moves. Then there are four possible responses for each of those four, for a total of 20 (4 + 16). It just gets worse from there as the checkers get captured or blocked. And that’s just a small board with pieces that can’t move very much. An exhaustive search of the moves is very expensive.
Assuming you have the moves, though, the algorithm will assume its moves will be the ones that raise the rating of its positions and that the opponent will move in such a way as to minimize the rating. In addition, certain heuristics and other algorithms will dead-end the search early, allowing the computer to evaluate promising moves in more depth for a given amount of time.
Of course, this only works as well as your heuristic for how “good” or “bad” a particular position is. If you follow along with the post, you’ll have a framework where you can try your own ideas. We’ve looked at some hardware chess players before, including ones that use the standard interface to chess engines. Of course, the latest craze is deep learning for chess, but there are still a lot of programs that use the old school techniques. If you want to know even more, check out the MIT video from [Patrick Winston], below.
I became interested in chess programming a few years ago.
The old 80’s chess computers are realy interesting. Mainly with a 8bit micro controller and little memory.
I’ve still haven’t programmed my own chess computer but I will some day.
Here are some more resources:
https://chessprogramming.wikispaces.com/ Chess programming information.
http://home.hccnet.nl/h.g.muller/max-src2.html Tiny chess computer with source, it has already been ported to a AVR micro.
Interesting post. But what struck me the most was the part about deep learning. With all the flare about it, I wonder how much better is it than more conventional adaptive decision making methods. How would one rate them anyway?
A friend of mine get the Min/Max for the AVR and Included Threefold repetition rule using Compact Chess Representation of history boards (C.C.R.), as well as Fifty-move rule check. I’ve added a display, keys and a UI and it all became a chess computer codenamed Lily (https://hackaday.io/project/8705-chess-mate)
Borland had a chess game in Turbo Pascal with the source included. I learned a fair bit from that. However, once I understood the algorithm, I could beat the computer (occasionally, I was never a great player) by playing to the algorithm’s weaknesses. That made the game less interesting.
I wonder if its possible to use reverse engineering to find the chess algorithm given a chess programs moves…
Now THAT would be really interesting! However I suspect that this would only be possible in only a handful of engines since most of them (especially the ones offering difficulty levels) make extensive use of weird non-deterministic routines and random number decision making. Sure it’s pseudo-random… but good luck reversing that.
“Because it is in JavaScript, you can follow along in your browser and find out when the program gets smart enough to beat you.”
You mean when it can play chess?
I wonder if its possible to use reverse engineering to find the chess algorithm given a chess programs moves…
Here are some more resources:
<a href="https://chessprogramming.