Chess AI, Old School

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.

Filed under: software hacks