How Computers Think in Chess

How Computers "Think" in Chess

Over time, a number of people have raised interesting questions about computer (artificial) intelligence and chess, what chess engines really do and how, and how far that technology could reach in comparison to human intelligence. 

I'd like to offer some thoughts and pointers for those of you who are interested in exploring this topic deeper or even just knowing how engines "think".  I have graduate degrees in computer science, and I've explored AI (artificial intelligence) in particular at some depth, hence my knowledge of the topic. 

So sit back and relax for a quick crash course on chess engines and how far artificial intelligence reaches today:

- Chess engines recognize a number of patterns (typical chess positions); the more patterns and the more refined those patterns are, the higher the quality of the engine.  Some of those are endgame patterns (e.g., akin to the Nalimov tablebase), while others are middlegame patterns (e.g., good moves to play against isolated pawns, etc.).  They also have vast opening databases, so they "know" what has been played by strong players before, and how those games have continued and ended.

- Chess engines evaluate a position in part based on the material balance (where each piece has a preset value, which may change based on how developed and active each piece is in the specific game, which is itself a positional characteristic) and in part based on positional characteristics (which come from those patterns I talked about).  The base material unit is 1 pawn, which is approximately equal to 1.00, so if you see an engine give an evaluation of +1.00, that means it deems the position of white as equivalent to one where that side has 1 extra pawn (even though all of that advantage may come from positional characteristics, not material ones).  Typically, an advantage of +1.00 (or more) is sufficient for that side to win the game, if played correctly, while an advantage below that threshold indicates a likelihood for a draw.  (If black has an advantage, the evaluation would be expressed in negative numbers but with the same magnitude, e.g., -0.58.)  Naturally, there is no hard line between one and the other, but that's a reasonable rule of thumb to keep in mind.

- Each move has two parts -- white's move and black's move.  Each of those two is a called half-move.  In slightly more technical terms, this "half-move" term is useful in chess engines (as you will find out if you study Artificial Intelligence) when the engine does what is called "alpha-beta search and pruning".  The latter is a fancy term for building a tree of possibilities and then evaluating it one step at a time as it traverses that tree from bottom (leaves) to top (root).  (In computer science trees are not like those in nature.)  So, each half-move corresponds to one level of depth of your tree.  At a given level, the engine attempts to maximize the evaluation function (which corresponds to picking a move that is as strong as possible for you, to increase the evaluation function the most), while at the next level it attempts to minimize that function (which corresponds to picking the opponent's best move, which from your perspective is the worst you can possibly expect to confront -- that's why it's minimizing the function there).

- Modern engines are not primitive, so they cut out some variations early and do not waste time (or memory) to explore them in depth.  (This is the "alpha-beta pruning" of the tree of possible moves.)  Sometimes this pruning may result in a perfectly valid sacrifice being ignored (which is why engines tend to not be very good at sac'ing lines), but most of the time that saves a huge amount of time, which can be better spent on evaluating other potentially useful moves.  The memory issue is not as severe in fact, since once the engine throws away a given possibility, it clears up and reuses that memory, while retaining only an encoding of the potentially fruitful continuations.

- Engines use heuristics (in human parlance these are rules of thumb -- principles that may or may not be true, but most of the time are true), and the more these heuristics they know about (e.g., difference between rook pawns and other pawns, difference between passed pawns and backward pawns, some strategic and positional considerations, etc.) the stronger the engines can be.  This also includes knowledge of typical patterns, which is why computers are good at solving typical chess puzzles -- because puzzles are a distilled form of patterns.

- On the topic of whether engines can get better over time, the answer is "Absolutely yes."  Both in terms of how deep they are able to think, as well as how truly intellingent they can become (i.e., ability to see and recognize more patterns beyond raw calculation).  If you read books on the functioning of the human brain, you'll realize that people in that branch of science believe that even we, humans, learn and act based purely on pattern matching: recognizing patterns in our environment and acting on them, based on subconscious and conscious actions that are programmed in our psyche.
The depth of exploration of a chess engine (unless limited by a human using a specific parameter) depends on the processing speed of your computer (a combination of clock speed, memory size, bus transfer speed, disk seek speed, etc.): a more powerful computer is able to compute more in a given chunk of time.  I used to be able to beat some engines at level 5 years ago; now I struggle at level 2 -- that's how far they've come (I assume I am no worse than I used to be).

- As far as whether chess engines will ever be able to express in human terms why they do something and not other, that's one of the Holy Grails of artificial intelligence.  While with the use of expert systems one can gain some traction in the area, the difficulty comes from the need to reverse engineer their raw calculation into something resembling a thought process (in the end, engines do raw calculation more than anything else and are exceedingly good at it).  Humans are for the time being only able to balance somewhat the strength of chess engines based on better intuition and knowledge of patterns (what to look for, what not to look for, etc.) -- but that has its limits which aren't advancing nearly as fast as machines' calculating power.
Those who are interested to explore more can look up the topic "Turing test" (http://en.wikipedia.org/wiki/Turing_test) -- this is a litmus test of intellingence: in laymen's language, it's about whether a computer could fool a human into being unable to distinguish between human-generated answers and computer-generated answers to a set of questions that the human poses.  Clearly, we're not quite there yet, but it's getting closer with time.

- As to whether it's good or not to use chess engines:
GMs get a strong buddy for little or no money when they use an engine.  It's not easy to find someone at your level when you're a very strong player and want to train, say, in the middle of the night, or prepare a novelty for tomorrow's tournament game even while you're asleep!  Engines can do that sort of thing quite well if you give them enough time.  Also, they can be very good at hinting possible hidden resources, which to a master-level player is sufficient (they can figure out the meaning behind a move because of their vast experience, if you only give them a slight hint, with no need for an in-depth explanation). 
With casual players, however, this is often not the case, so a strong engine is much less helpful to someone who is still learning the basics of the game, because they need a real coach instead, someone who can train them to see and phrase the ideas and strategies in human-understandable language.

- To understand the similarities and differences between human chess players and modern computer engines, one can assume (which is a fair assumption, close to reality) that a modern chess computer/engine resembles a human chess player who has all of the following characteristics:

• highly disciplined (i.e., reliably consistent in the decisions it makes);
• completely unemotional (i.e., a loss and a win are simply two states, neither of affects the machine's ability to play more games equally strongly and consistently; also while computers' strength of play depends on various parameters, none of them have to do with who the opponent is in the sense of any hierarchies/cults);
• extremely knowledgeable (i.e., has full and unclouded knowledge of openings, endgame positions, middle game strategic heuristics, and other patterns that have been programmed into it);
• very strong (i.e., capable of beating even GMs, for the most advanced engines);
• makes almost no calculation errors, except those due to the limited window of how many moves ahead it's programmed (or allowed by practical time constraints) to look;
• reliant solely on logical inferences based on pre-existing heuristics and memory (of positions, openings, patterns), but has no substitute for human intuition ("gut feeling");
• (generally) unable to learn from his/her own mistakes by itself, or to derive new knowledge without explicit new programming by humans.

These last couple of aspects are the humans' greatest enduring advantage over computers chess programs.  They are the fundamental reasons allowing the strongest GMs to still beat computers occasionally (though humans are increasingly wary of trying, for fear of what might happen to their image if they failed).

Note:  A lot of additional content has been added in the Q&A section below, as people kept asking me specific questions, to which I have provided answers there.  Be sure to look through that section for more interesting aspects of the ins and outs of computer engines.

I hope this article has been useful.  Please ask further questions in the comments and I'll be glad to offer my perspective, based on what I know on the topic.