Can computers play chess?
After binging the new Netflix show The Queen’s Gambit in basically one sitting, I decided to become a grandmaster at chess. Unfortunately it is not that easy so I did what any programmer would do and see if I could write some code to help me. Turns out I was not the first person to do this. In fact I wasn’t even close. I’m of course joking I’ve heard awesome stories of IBM beating world champions and such but I’ve never thought about how. Turns out building a chess engine is hard so I wanted to explore the history of computers and chess.
Deep Blue was the IBM computer that beat Gary Kasparov who is one of the best chess players to ever live and was the reigning world champion at the time. This was the first time a computer was able to beat a world champion and even at that it was close. The computer beat him 3 to 2.5(there was a draw) and Kasparov accused IBM of cheating. At the time this was crazy but like most things in technology doesn’t compare to now. Most modern chess engines could beat Deep Blue 100 times over. So let’s see how this works. Chess requires thought, and great chess players must be able to predict moves, think ahead, understand rules and constraints, and then develop strategies that must be adaptable. Chess players even use psychology to play. Computers don’t have really the ability for any of that, not yet at least.
Chess engines basically use decision trees to play. A computer can run calculations millions of times faster than any human can so that’s what it does. Chess has about 10 to the 120th power possible moves in a single game. This number is not really conceivable and no computer can actually calculate for that. For perspective, it is estimated that there are 10⁷⁵ atoms in the universe… Enough said. So it’s not possible for a computer to look at all possible moves, so it only looks as many moves into the future as the hardware will allow. It uses the minimax algorithm to pick the best possible move for however many moves deep it can calculate. A function is written that calculates a score based upon each possible move. A simple one could be how many pieces you have minus the number of pieces you opponent has. The higher this number the better you are doing. Now that is not a great approach to chess but it can show how the computer can calculate. The engine will calculate that score for each possible move and It will pick the branch with the highest score based upon the latest move. If the computer plays as white, in the first move it picks the one with the highest score. This player is the maximizer. Now it assumes that the next move by the opponent is going to be the best move for them, being the worst move for white.This being the minimizer. Thus it assumes the move with the lowest score will be chosen and goes down that branch.
It starts with by making the move with the maximum score, then assumes the next move will have the minimum score and so forth. This algorithm is used to play a lot of games besides chess. Of course comparing the number of pieces is not the best way to determine a good move, so professional chess players consult to make the function much better. They has a grandmaster working with them on Deep Blue to look at things like position, opening and endgame theory, and a plethora of other factors that even humans consider when making a chess move. This method is what makes all modern chess engines work and now that computers hardware has more power, the algorithm is capable of searching more moves into the future. You can buy a more powerful engine for 20 bucks thats is much more powerful than the fruits of 8 years of work at IBM.
There is now a new challenger on the scene and it’s name is Artificial Intelligence. Every day AI makes advancements that is so crazy and cool that people don’t know what it will be able to do next. In 2017 however, we found that it was capable of becoming a chess master in 4 hours.
Google’s Alpha AI learned how to play chess and beat a modern chess engine all in 4 hours. Using neural networks (which is a way to process data inspired by biological processes) and a reinforcement learning algorithm, It started only knowing the rules of chess and and ended by beating the a modern chess engine in a 100 game test. Google’s computer won 28 and drew 72 meaning it didn’t lose a single match. AI learned what took people 1500 years of playing chess to learn in 4 hours. Even having the computer advantage the Google AI could look at around 80,000 chess positions per second. This seems like a lot but the engine it was playing can look at 70 million positions per second. The algorithm just learned what tended to be better moves, while the engine was looking at all possible moves and then comparing. That is crazy.
I don’t know what the future of chess or computing holds, but this was a fascinating research topic and I hope it creates interest in how these types of algorithms work. I didn’t really look into the specifics of how it makes good chess moves, so here is some resources if you want to look into anything I mentioned above.
https://www.geeksforgeeks.org/minimax-algorithm-in-game-theory-set-1-introduction/
