How do chess engines "think"?

Question

What I want to know is how engines are programmed to find moves. I'm sure they first calculate the most forcing lines such as captures and checks. But what about subtle, deep positional moves? They seem to find them very quickly as well (Generally speaking. Of course they miss such moves now and then). As in, how are they programmed to look for quiet moves/positional ideas? They can't just brute force every move, since that'd take too long, so there should be some clever way for them to arrive at the best moves really quickly. I'm interested in knowing this because I think it'd help players to think over the board in the real world as well.

Answer 1

In a general way chess engines use a decision tree. The root of the tree is the current position and has a child node for each position that can be made by making a legal move. Each of these nodes in turn have a child node for the positions that can be reached by making a legal move from them. The engine pushes the tree out to a depth defined by its capabilities and the time it is allowed to "think". Positions that can be reached in more than one way are simply cross referenced so that they will not have to be considered more than once. Once the tree is created the computer uses a set of weighted rules to analyze the final positions in the tree and starts to remove those that are undesirable or that the opponent can prevent it from reaching. The tree is cut down this way until only one move remains and the computer makes that move.

http://www.chess.com/blog/zaifrun has series or articles on creating a chess engine if you want a more in depth look at how they work.

Answer 2

You're asking a pretty complex question, but it's good to go back to basics. There are a couple of concepts to consider:

Evaluation

If a (real) player is shown a position and asked "who is winning this game?", how do they go about deciding? Most likely, they will check a few basic things, such as: material differences, the degree to which pieces have been developed or are positioned "well", doubled / isolated / connected / passed pawns, (controlled) open files, how far up the board the pawns are.

Now, if you had to, you could come up with a systematic way to calculate a position score based on the above. You could decide, for example, that a pawn is worth 1 point, and that a passed pawn is worth 0.3 points more. Isolated or doubled pawns might be worth a bit less, etc. If you add up everything, you get an estimate value for the immediate position at hand.

This is known as evaluation, and basically all chess programs have a way to evaluate positions (ignoring novelty AI chess engines which are typically very weak).

But what about subtle, deep positional moves?

Well, we've only barely scratched the surface of position evaluation. The actual implementation of an evaluation function could be simplistic, to allow for more positions to be evaluated per second (albeit in a rough fashion), or more complex, leading to less positions evaluated, but with a higher degree of confidence. It's not unusual for the evaluation function to take into account hundreds or even thousands of separate pieces of information.

Search

I've specifically left out something from the above, which most real players will immediately think about - is there any way to immediately win the game for either side? Any mates or "hanging" pieces visible? Although it's easy to trivialise this, it's anything but trivial.

What does it mean for a player to have full confidence in a combination? In the end, it boils down to having calculated all options. Real players typically won't do this (except for trivial or very forced mates), most of the time we will only consider a handful of options, and rule out others which seem to be "non-constructive" or obviously leading to a loss. We often make mistakes during this calculation, e.g. we may realise that a change in move orders makes threats evaporate, etc. The point is that to be completely sure of a combination, you actually need to calculate all the way to its conclusion, assuming each player will only make the best possible move available to them (this is referred to as "min/max").

Now, given that chess has a much larger search space (this is what "all possible moves in the future" is referred to) than what is feasible for a computer to calculate, compromises need to be made. Just like humans, computers can decide to disregard entire lines of thought based on certain criteria. This is known as heuristics. It's worthwhile noting that while you can only be really sure of a combination if you brute force it, a complex evaluation function can often detect the presence of threats (e.g. we could count forks, skewer opportunities, etc, to guide a search in that direction).

In the end, although computers are extremely fast, it's the heuristics which allow them to calculate so deep. That said, you may be surprised how deep modern engines calculate fully, typically it's beyond 3 moves, even in quick games.

Conclusion / combining it all

So, to summarise - evaluation functions have a lot of intelligence built into them (i.e. they take into consideration more things than your average human player), heuristics allow the computer to cull lines of thought it decides probably aren't going to end well, and computers are extremely, extremely fast. Add them up, and they're pretty difficult to beat.

Answer 3

It is just impossible for computers to look deep enough (25 ply and more) and check every possible move.

What makes is possible is the technique called Alpha-beta pruning which means that computers, similar to humans (but way better) follow only the promising continuations.

They evaluate the positions constantly (based on some precoded rules, valuing material, king safety, activity, pawn structures etc) and look into variations that seem to be leading them towards the best position.

It is still close to magic how they manage to do it efficiently enough to evaluate millions of these positions in a second.

So to summarise- you are correct, they can not look at all the moves if they play strategic chess, but they can very quickly look at decent moves. The problem is still with the very long term plans and horizon to which they can see, but this is being worked on (Rybka analyses much slower, but plays much more positional chess, while Houdini is romantic at it's 'mechanical heart' calculating more moves and playing more aggressively). Even computers have their own styles!

Answer 4

I agree with the answers.

I remember GM Roman Dzindzichashvili talking about it, in one of Roman's labs videos, i don't remember what video it was (if anyone knows the details please edit my answer).

Roman said that the developer of Fritz engine is his friend. So Roman tested Fritz to see how good it was, and the developer told Roman that in order for fritz to make complex decisions (sacrificing materials in exchange for positional advantage for example) they had to change the value of the pieces, like telling the program that a bad bishop is worth 1 point, a bishop on an open diagonal is worth 7 points, knights are worth 5 points in close positions...

I don't know the exact numbers for each piece but that's how it works, and now your engine won't have any problem sacrificing a bad bishop or whatever if you can tell him the value of each piece in each position.

EDIT

See also The Chess Programming Wiki.

Answer 5

Alpha-beta pruning simply means that if you find a line that turns out badly for you, you stop looking at that candidate move, and instead try others. It is a type of backward pruning meaning that you'll never miss a good move as a result. Forward pruning, by contrast, is based more on guesswork. Futility pruning, late move reductions and razoring are types of forward pruning, and all rely on the programmer's feeling for what type of moves should be considered. A program that does a lot of forward pruning may miss out on startling sacrifices that lead to mate, but on the other hand, it eliminates a lot of really bad moves, and so can go deeper in looking at the moves it does favour.

Most engines search the first few moves at full depth examining all the possibilities. If no move fails high (i.e. seems clearly worse than a move you've already considered), you extend the search just a bit more. In general, you continue exploring each line until you reach a quiescent position (with no checks, captures, mate threats, etc.), and then do your evaluation. Quiet moves may not be considered when they are deep in the search tree, but once you get to that actual position in the game, the engine looks at all moves, quiet and sharp alike. You can actually see this in the engine output sometimes, when an engine suddenly favours a move that it hadn't been considering a few moves back.

Engines calculate so quickly that it's not so important for them to consider which move to look at first, but for humans this is a key question. Jonathan Tisdall takes a stab at answering this in his book, Improve Your Chess Now. When you are on the attack, he suggests you look at the most violent moves first. When you are defending, you look at the most difficult lines first. He also cites positional rules of thumb (eg. centralization, coordination) when deciding which moves to look at first.

Other books that may be relevant are Emmanuel Neimann's Invisible Chess Moves and Charles Hertan's Forcing Chess Moves, both of whom argue for the importance of considering unlikely or surprising moves in sharp positions. Hertan even talks about developing 'computer eyes' for such tactics.