Algorithm for chess program10/29/2022 ![]()
You may want to refer to the file endgame.cpp while reading the following discussion. Algorithm for chess program generator#I will focus on the generator algorithm in this article. Resistance is futile!Īlthough this browser-based demo is implemented in HTML, CSS, and TypeScript, the program that generates the database is written in C++. Play two or three rounds to convince yourself that it really works. In this demo, you play Black’s king, and the computer uses an endgame database to force a checkmate in the minimum possible number of moves. (In case this embedded demo isn’t working in your browser, you can run it in another browser tab: ). Before we dive into the algorithms and sample code, here is a live demo that shows it in action. To make the ideas easier to explain, I created a simplified endgame database generator just for this article. How does it work? Let’s find out! Live Demo Algorithm for chess program series#In any of the supported endgame situations, Chenard is a terrifying monster that forces checkmate in an optimal series of razor-sharp moves. I decided to create my own endgame databases. For each arrangement, the database tells what move the winning side should make to force a checkmate in the shortest possible time, no matter how the losing side responds. ![]() For example, there is a database that contains every possible arrangement of a king and rook versus an opponent king. I knew that most world-class chess programs solve this problem using pre-calculated databases of ideal moves for certain endgame configurations. But in an endgame, even with positional motivation to force the opponent’s lone king toward the edge of the board, the checkmate itself was often too far in the future to be seen. This kind of algorithm works well in a middle-game position where the AI can incrementally exploit the opponent’s mistakes and accumulate an ever-increasing advantage. After a configured amount of time elapses, the computer stops exploring and makes the move that appears best within its limited view of the future. The number of hypothetical board positions increases exponentially as the computer looks farther into the future. Like Doctor Strange versus Thanos, a minimax search recursively explores millions of possible future positions to decide which move leads toward the best outcome. Known as a minimax search, the algorithm involves generating a list of all legal moves the computer can make, trying each one, generating a list of all legal moves the human opponent can make in response, and so on. The problem was due to the nature of the search algorithm Chenard uses. Yet Chenard would keep making pointless moves and never get any closer to victory. As a reasonably skilled human player, forcing a checkmate in Chenard’s place would be easy for me. For example, I might have a lone king and Chenard might have a king and a rook. Algorithm for chess program how to#Sometimes Chenard ended up with a winning advantage in an endgame position, but it would not know how to force checkmate. However, there was one frustrating problem. Chenard’s advantage would snowball and I would end up in a hopeless situation. ![]() Chenard would exploit the error and force a decisive material advantage. Typically I would make some small tactical error in a complex middle-game position. After that, I mostly left its AI alone.īy 2005, computers had become so much faster that Chenard could defeat me almost every time I played it. Over the next couple of years, I tuned and tweaked the algorithm and improved it significantly. ![]() It wasn’t the strongest chess AI in the world, but I was excited to see it do some clever and unpredictable things. Eight months later, having learned from my mistakes, the first working version of Chenard was up and running. ![]() My first two efforts were frustrating but educational failures. It's this sort of position which seems perfectly tailored to exploit Stockfish's materialistic nature.Back in April 1993, I began my third attempt at writing a computer program to play chess. You're far more likely to see them sacrifice material for a long-term positional advantage, like a great human player would.įrom my experience looking at Alpha Zero and LCZero wins against Stockfish, one of the more common patterns I see is a sacrifice by the AI which gives such a dominant position that one or more of Stockfish's pieces become uselessly trapped behind their own pawns. The traditional engine tends to be extremely conservative and materialistic, only playing a sacrifice when it has calculated a line which recovers the material with interest (or forces checkmate). If you ask any of the top players who have spent time reviewing games by chess engines, I think you'll find a consensus around the belief that Alpha Zero and LCZero play far more human-like moves than do engines like Stockfish. On the other hand, they happen to be great judges of human- vs engine- style of play. For one, because chess players are hardly judges of what is and what isn't AI. ![]()
0 Comments
Leave a Reply.AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |