28

It is estimated that the total number of legal positions in chess is somewhere between 10^40 and 10^50. This is of course an enormous number. Computers today with reasonably good chess software can sometimes look 20 moves ahead to find the best continuation.

But (most) humans are incapable of such calculations. After each move, it is practically impossible to compute all the ramifications and variations. Therefore a move made by a human being is expected to be a very poor move indeed.

But this is not the case: looking at GMs games, those people are able to find the ''best'' moves recommended by top engines such as Stockfish, even though they obviously are not calculating billions of combinations per minute.

So what makes humans good at chess, if they are unable to see into the vast space of future variations? When looking at what GMs do better than amateurs, what I usually find is better ''intuition'' or ''feeling for the position''. But these can't be quantified. And GMs are obviously not psychic. So how can they find the best move most of the time? Chess masters often insist that they are not following an internal ''algorithm''. So what on Earth are they following?

How can humans be so good at chess?

  • 16
    It should be noted that, when comparing humans and computers at chess, humans are not good at all. Even if grandmasters can make good moves—or even moves the computer agrees with—much of the time, this is still not all of the time. Indeed, it has been decades since humans were really competitive against computers. – imallett Apr 29 at 23:28
  • 5
    most humans aren't :) – Eevee Apr 30 at 3:55
  • 3
    People don't do much of a state space search. Reinforcement learning algoritms are more comparable to human thinking - what they do is to play the game many times, collect feedback and learn a predictive model which can say how good a certain move is just from current board and a proposed move - computer alternative for intuition. With a perfect predictive model (which we don't have), optimal action for a board is argmax(model_score(move)) over all possible moves, which is fast to compute. Algorithms like alphazero combine those two approaches - state search + learning predictive models – cuddlecheek Apr 30 at 7:15
  • 1
    "obviously are not calculating billions of combinations per minute" not entirely true, or at least not clear. Internal workings of the human brain are still a mistery, but every cell in the brain works as a multiple stateful logic gates (probably bilions) and the cells themselves are bilions. There is no (known) main clock frequency, but one can handwave something like 10kHz. A powerful computer, indeed. – fraxinus Apr 30 at 9:53
  • 4
    I'd assume 9.999999^50 of those moves are utterly stupid. – Mazura Apr 30 at 23:10

14 Answers 14

40

Herbert Simon touched on this question. He received the Turing Award in 1975 and the Nobel Prize in Economics in 1978. His primary research interest was decision-making and is best known for the theories of "bounded rationality" and "satisficing".

Satisficing is a decision-making strategy or cognitive heuristic that entails searching through the available alternatives until an acceptability threshold is met. Simon used satisficing to explain the behavior of decision makers under circumstances in which an optimal solution cannot be determined.

In his paper Theories of Bounded Rationality (1972), Simon used "the game of chess as a microcosm that mirrors interesting properties of decision-making situations in the real world." Here are some useful quotes.

On the average, at any given position in a game of chess, there are about 30 legal moves-in round numbers, for a move and its replies, an average of about 10^3 continuations. Forty moves would be a not unreasonable estimate of the average length of a game. Then there would be perhaps 10^120 possible games of chess. Obviously the exact number does not matter: a number like 10^40 would be less spectacular, but quite large enough to support the conclusions of the present argument.

Chess players do not consider all possible strategies and pick the best, but generate and examine a rather small number, making a choice as soon as they discover one that they regard as satisfactory.

The limits of rationality in chess.

(...) three limits on perfect rationality were listed: uncertainty about the consequences that would follow from each alternative, incomplete information about the set of alternatives, and complexity preventing the necessary computations from being carried out. Chess illustrates how, in real world problem-solving situations, these three categories tend to merge.

Satisficing and optimizing.

The terms satisficing and optimizing (...) are labels for two broad approaches to rational behavior in situations where complexity and uncertainty make global rationality impossible. In these situations, optimization becomes approximate optimization - the description of the real-world situation is radically simplified until reduced to a degree of complication that the decision maker can handle. Satisficing approaches seek this simplification in a somewhat different direction, retaining more of the detail of the real-world situation, but settling for a satisfactory, rather than an approximate-best, decision. One cannot predict in general which approach will lead to the better decisions as measured by their real-world consequences. In chess at least, good players have clearly found satisficing more useful than approximating-and optimizing

| improve this answer | |
  • 2
    Very interesting read and it deserves a thumb up from me (contradicting what i say in the following), but it doesn't really answer the OP question. Just being a little pedantic ;) – user3658510 May 1 at 4:56
  • 1
    @user3658510 thanks! Your comment gives me the opportunity to add that it answers the question in the sense that humans can't optimize ("humans are incapable of such calculations") but they are "good" because they use another cognitive heuristic: satisfying! – Kortchnoi May 1 at 6:50
  • 1
    Nice. You could add that to the answer, as it would make it more complete. But here is also a good place. Anyone who is really interested would at least read the first few comments. – user3658510 May 1 at 7:23
29

Let's take a conversation. The number of sentences that could be said are infinite. The number of grammatically correct is still infinte, as is the number of logically/conversationally correct would be. The humans pare down what they say in any situation by intuition/experience. As chess players study what should be played, their task is much easier than you holding a simple conversation.

| improve this answer | |
25

Humans try to understand a game like this, to formulate rules, try to recognize patterns of what worked in one position and apply them in positions they consider similar.

And it turns out that that is possible, otherwise there wouldn't be humans of different playing strengths, everybody would just be guessing.

Then we used that knowledge to create engines like Stockfish; in the end they can't calculate all the way to checkmate either in most positions, and they have an evaluation function based on what we consider good. It's the same principle.

Only since completely new engines like AlphaZero, that start with zero knowledge about the game and have to work their way up themselves has that changed. It's interesting that the best of them are more or less on equal footing with Stockfish right now.

But the important thing is to turn this phenomenon around -- if it weren't possible for us to learn rules about the game of chess that work, then the game would have been very uninteresting and it would never have become popular.

E.g. imagine a game where you have to guess a whole number between 1 and 10^80. You get no hints when you get one wrong, you lose after a million wrong tries. Nothing can be learned, and nobody would play it.

If a game can be learned perfectly (like tic-tac-toe or Nim) then it probably won't become very popular either.

Chess is apparently in some sort of sweet spot.

| improve this answer | |
  • 1
    According to: chess.com/news/view/… it seems AlphaZero has overtaken Stockfish around a year ago? – Falco Apr 30 at 9:33
  • 2
    @Falco: an old version of Stockfish. But LeelaZero beat the current one. Anyway, hence "more or less" -- they're close-ish. – RemcoGerlich Apr 30 at 20:03
6

Interesting Chess

Given a board configuration, many expert chess players are able to reproduce the moves which produce that configuration. However, of the 10^40+ board positions, grandmasters would be hard-pressed to reproduce the vast majority of board states. Why is that? Well, that's because most of them involve obviously bad moves, like developing your king by itself to the center of the board, or sacrificing all your pieces willy-nilly. The games which produce these board states are not interesting. A much more difficult question is: "How many board states are likely?" What if that number is just 10^10 or so?

Learning

Computer science has one powerful optimization trick. When performing an expensive computation which always has the same result for a particular input, the programmer can instruct the program to simply remember the answer. This technique is called "memoization". Then, the next time the computation is requested, the program "cheats" by returning the memoized value instead of wasting a bunch of effort computing something exactly the same way it did before.

Humans also have one powerful optimization trick, called the Hebbian Learning Rule, often summarized as: "Neurons which fire together, wire together." It is overly simple to say that this explains all human learning, because it doesn't. But it is, in a sense, the computationally simplest and most abstract way to capture what the memoization technique does: if a pattern of neural firing consistently produces the same result, let's take a shortcut and not do all the work we did the first time.

Stockfish

Now, let's compare those tricks to what Stockfish does: brute force search of the game tree. Obviously, Stockfish is smarter than that. It can use an opening book, and endgame database, and it can prune branches of the game tree that are trivially silly. But there's one thing that Stockfish cannot do: it cannot say: "Wait a second! I've been here before. What did I do the last time I was here?" Stockfish has no memory (across games). Of course, this makes it useful for evaluating positions, because Stockfish's answer does not depend on which games it has already played. It will give you the same answer every time you evaluate the position, even if it plays a game in which it discovers that its evaluation was inaccurate.

AlphaZero

So now we begin to see why AlphaZero can evaluate 1000x fewer positions, and still wipe the floor clean with Stockfish: AlphaZero does the simplest thing an intelligent system can do--it remembers the past. You cannot ask what the AlphaZero evaluation of a position is, because that is a meaningless question. Each instance of AlphaZero is unique, shaped by its history of games played. Instead of saying: "I'm going to pretend like I've never seen this board state before, and blindly search the game tree" it says: "Well, I've seen this board state 237 times, and I already know that 3 moves are significantly better than all the others I evaluated" (it doesn't actually know how many times it's seen the board state, except implicitly).

Incidentally, this one simple trick is also why humans are able to evaluate tens of thousands of moves fewer than computers, and still play a respectable game. A grandmaster is not a human who can evaluate 60,000 positions per second. A grandmaster is a human who can remember 60,000 board positions and strong lines of attack and defense from the most important ones.

AlphaZero plays more human chess than any program before it, because it actually learns chess. In a way, it probably understands chess better than any entity in the universe. Its primary shortcoming is a lack of communication ability. If it had language, and could describe its reasoning, we would likely be awed by its analyses. And yet, we would quite possibly be surprised how human-like those analyses turn out to be, while noting that there is still an element of alien sensibility borne from the ability to evaluate tens of thousands of moves per second.

The fact that AlphaZero runs on transistors which can switch a billion times per second, compared to the measly 3-5 times per second for the typical human interneuron suggests that in a sense, AlphaZero is much like a hyper-accelerated human. But to get back to your original question: human grandmasters can look into the vast space of future moves. They do so by remembering which of those moves are better than others, rather than computing them fresh every time. Of course, play is a combination of memory and tree search, so humans, like AlphaZero are also exploring new lines of play every time. But they have to be more economical in their search, and it shows.

| improve this answer | |
5

"Intuition" is basically just pattern matching. We use our experience from past situations/chess positions that are familiar, in order to gain a "feel" of a current position. With this intuition, we can make up for calculating a relatively small amount by:

1) Being able to evaluate resulting positions in our calculations well.

2) Knowing what lines to prune in our mental calculation tree.

That being said, even the top humans are far below current Stockfish. And even though Stockfish is probably the best/second best in the world (with Leela), there's no telling how good objectively it really is. If it played against some agent that always made literally perfect moves, there's a good chance it wouldn't do that well.

There's also a kind of anthropic principle going on here. Humans wouldn't invent a game in which everyone who played it was guaranteed to do horribly. Imagine the number of theoretical games whose complexity exceeded chess (and any other game we play) by x orders of magnitude.

Finally, coming back to intuition/pattern matching, in a sense it can be quantified. Theoretically you could measure how good someone's memory is, how well/quickly they can detect when one event is similar to another, etc.

| improve this answer | |
  • But complex games evolve over time (on a time scale of centuries or millennia). The standard Go board is 19x19, but beginners are still taught using a 13x13 board, and historically 15x15 and 17x17 have both been used. As of now, 21x21 would probably be a step too far in complexity for humans to deal with. – alephzero Apr 30 at 17:10
  • I just wanted to write this. – m4n0 May 1 at 20:13
5

At one level, the answer is that we don't know how the human brain works. But something a bit more helpful:

The algorithm used by Stockfish (and other chess engines before the rise of deep neural nets) is called Minimax. The basic idea goes something like this:

  1. Generate a tree of all possible moves as far out as resources allow.
  2. For each final position in the tree, assign a score of how good that position is for you
  3. Work backwards towards the present position, deciding at alternating levels either
    1. Whether I should make this move (it leads to a final position that is good for me)
    2. Whether my opponent would make this move (it leads to a final position that is bad for me)

And then there are ways to optimize these evaluations so you don't have to process the entire tree.

What the computer is very good at is step 1: coming up with a tree of all possible moves. What the computer is not very good at is step 2: figuring out how good a position is for you. Chess engines benefit from looking far ahead not only because that's closer to a checkmate, but also because it's easier to score an endgame position with less material.

Humans, it turns out, are better at step 2. We can somehow look at a midgame position and decide "this attack looks strong" or "my king-side looks weak" even though we haven't worked out an actual line of play that would exploit said strength or weakness. This is where people bring in pattern recognition and experience as somewhat fuzzy explanations of what human brains are doing.

So what the human player is doing is more "top down" than the computer's "bottom up". Instead of thinking about millions of possible outcomes and then starting to discard worse ones to prune the tree, we throw away branches as we build the tree when we decide that position doesn't look promising.

| improve this answer | |
  • Regarding computers sucking at step 2, that's because that's what we've found works best in chess engines. Chess engines that try to emulate more abstract reasoning can be made, to some extent, but they're usually poor. Without going so extreme as human-like reasoning, we can still come up with more powerful evaluation functions than the ones we currently use. The downside to these is that they're slower and the slower they are, the less depth an engine can search; and the less depth an engine can search, the worse it typically does against engines that do search more deeply. – Mateen Ulhaq May 2 at 13:28
4

Good question, I've been curious about that myself. Humans have an extra plane to their reasoning. The first evaluation is that of strategical themes applicable to the position, and the next one is a tactical one of the paths selected above. Those who can perform the first step successfully can drastically narrow down the search space for the second step, where they can repeat the approach (strategy/tactics) to narrow it down even further. For those with top skills at both, the path to finding the best move will consist of just a handful evaluations as the search space can be reduced by orders of magnitude with each iteration.

| improve this answer | |
4

Making plans

(Pattern matching has been mentioned. Humans are good at it)

In addition we make plans.

For example, looking at a position we see that the opponent's king and queen is in a good position for a fork by our knight. However, the relevant square is currently guarded by an opponent piece.

So, we look for ways to make that opponent piece go away. Or maybe we can pin it.

Of course, if we just move a piece to pin it, it will be the opponents turn and they might do something devastating like moving their king out of harms way.

So, we need a move that is both a threat the opponent must reply to and sets up the fork we want.

And so on and so forth.

The point is that while making a plan like this we are only looking at small number of moves and positions.

It does not matter that we have other moves, we can ignore those. And part of the plan is to reduce the possible moves by the opponent.

The hard part comes next, checking if the plan holds water. Ideally the opponent's moves should be forced, but usually they have a few alternatives on each step. Are we really really sure all combinations of these alternatives are harmless?

Of course, looking at a position and seeing the possible weak spots we can plan to attack is just pattern matching again. This is why we can't have computers players make plans, they would waste time trying to set up utterly hopeless attacks. They would discard these plans are not working, but by the time they have discarded plan number several billion, they would have lost on time.

| improve this answer | |
3

I am a very bad amateur chess player, but one thing I notice is that people are able to prove (in the mathematical sense) many things about a position, and grandmaster has a much more developed intuition (also on mathematical sense) and a much larger repertoire of thoerems to help prove (or extract) information out of a position than an average player. Due to proving a large number of things, a grandmaster is able to prune many branches of the search tree.

A trivial example about a theorem: after I captured the bishop of a beginner opponent, he said "oh, I thought it was protected by the other bishop", immediately me and a spectator said: "it is impossible, a bishop can never protect the other bishop". That is a very basic theorem a chess player learns very soon.

As the player advances, he learns much more intricate theorems and learn to intuitively spot patterns to use the theorems extract information. One theorem explicitly stated by a better chess player than me: a knight can never fork two pieces if they are on different color squares.

I still get confused, in endgame, if my king will be able to catch the pawn before promotion, or if I can promote my pawn before the opponent, but I imagine such things are immediately obvious to higher level players, due to more developed intuition and bigger repertoire of theorems.

I think this is the kind of information a deep neural network, like AlphaZero, is able to learn after playing too many games. And I disagree with Lawnmowner Man that it simply "remembers" the positions, and that all AlphaZero instances are fundamentally different. They are different because of the stochastic nature of a neural network training, but after too many games, they are able to extract higher level abstractions than simply remembering positions, and get to more or less the same set of most useful theorems and intuitions. A repertoire that is also shared by grandmasters.

| improve this answer | |
3

Spotting more complex or different types of patterns

Computers don't have a particularly easy time identifying the same patterns that humans can easily spot.

This is especially noticeable in something like Computer Vision. Computers have made a lot of progress in terms of recognising objects, but they are still probably worse than a young child at recognising even one or two different types of objects.

While any given board state in chess may not have as many parameters as a large image and it's can be solved in a more systematic way, a similar argument applies.

Computers and human brains just don't work in the same way.

Humans manage to spot some complex patterns in terms of which pieces or parts of the board are threats or weaknesses. Computers need to throw a ton of processing power to spot those same patterns, and even then they may still not be able to see the exact same patterns. They may go a different route and just try a bunch of different moves and play each of those out to determine the best one or doing something else.

Humans do sometimes also consider different moves and mentally play those out, but at any given point there are different mechanisms at work to determine whether a board state is good or bad or whether a move is worth considering.

Intuition and your subconscious

I show you a picture of a cat and you identify it as a cat. If I then ask you to explain to me exact why you think it's a cat, you may not have an easy time doing that (especially if you can't look at the cat while doing so). You may start to identify things like the whiskers or cat-like ears, but if I dig a little deeper you may not be able to explain exactly what "cat-like ears" means. I may also be able to show you an image of what is clearly a cat (even of the same breed) without those features, or a picture of something which is clearly not a cat with those features.

Your subconscious is probably doing most of the work in identifying the features of a cat and it just tells you "that is a cat" without giving your conscious mind much more information.

To bring this back to chess, you can look at a move and your subconscious can spot some patterns based on the rules or your experience watching or playing past games. You can use this to identify the move as good or bad without necessarily being able to justify it.

Going any deeper into it would probably shift the discussion a bit too far into psychology, neuroscience and/or computer science.

| improve this answer | |
  • That's a great answer, thank you. – Klangen May 1 at 19:03
2

@Kortchnoi's answer is very insightful and worth a read.

It's also worth noting that a game between two perfect chess AI engines must always, in theory, end in a stalemate due to the min-maxing algorithm being mirrored on both sides.

On the other hand, two human chess players do not use the same "algorithm," and thus it could be argued that one player is simply better than the other. Moreover, humans make mistakes; a chess engine evaluates the possible game states and picks the "best" one, so it's not prone to human error in that sense.

One example from game theory that comes to mind is the pirate's dilemma, where the most reasonable choice is not always the one that a person ends up taking. Humans don't always think like AI—they base many of their decisions on fears, suspicions, and gut feelings, and chess is no exception.

| improve this answer | |
2

As far as chess is concerned many people before me have given brilliant answers. But, additionally I would like to point out that many chess players employ, apart from theorems they have learnt through practice, a different strategy based on opponents.

Games are simulated in practice and rough plans are made.

One such strategy I typically use is guard pieces until other player makes a mistake then pounce on them.

Often players try to fight without queens to reduce the mental strain if given a chance to do so.

In a game motivations are important, if I find a player is trying to achieve a certain objective to deliver the checkmate I only think along those decision tree to either guard or trap them. Both players have a mental image of what the other is trying to achieve.

The game is usually decided on whether the other person has the correct picture or not, and whether we have enough knowledge and practice to foil their plan.

| improve this answer | |
1

When talking about the strength of the human chess players, one normally forgets to mention that what they have is not only their own work. Most of it comes from many generations of others humans that have played and studied chess for many years and have added to the 'basic' modern knowledge of chess. Not that one doesn't have made many sacrifices to have such strength but it would be very different if one doesn't stand on the shoulders of giants :)

Stockfish is like an Godly Genius that has the mentality of a new born baby, the memory of an ant and the knowledge of chess player that just learned the rules (excluding the "artificial" extra opening books and end game library). Alpha zero is the same excluding that he has an excellent memory and, if given enough time, it can stand on its own shoulders.

Your question is similar to asking another one: Why has humans technology being so "low" for so many thousands of years and now it is accelerating like an explosion?

The science rules that gives us so much power, when we are so weak, are like the the knowledge in chess.

| improve this answer | |
1

There's not much I can add to the other answers, but I want to make clear that both the number of legal positions and the search depth are misleading or even irrelevant metrics. About legal positions: In the king & rook vs. king endgame there are over 200000 legal positions (when not considering symmetries), but mating with the rook is easy enough that you probably need to see it executed just once and can memorize the algorithm. For rules like "a bishop pair is worth more than 2 bishops", you don't need to compare the vast number of positions with a bishop pair to the ones without it. In fact, you don't even need to look at 1 position, because you probably learned it from a more experienced player without reference to any particular position. It can also be derived logically from the properties of a bishop. Looking beyond chess, the number of legal Go positions is known to be about 2*10^171 and the number of legal positions for Go on the smaller 9x9 board is about 1*10^38. Does that mean that Go is more complex than Chess and that 9x9 Go is less complex? Without additional information, that judgment can't be made. It would even be easy to design a game that has more legal positions than Go, but is trivial to play. All these examples should make clear that the number of legal positions does not really tell you anything about the game, even if you restrict the positions to some subset like "positions with a bishop pair".

About search depth: Stockfish searches 60 million positions per second on the hardware used by Deepmind to compare it to AlphaZero, whereas AlphaZero only searched about 60 thousand positions per second. Both are of similar strength. And you could easily write a chess engine that uses Stockfish's highly optimized move generation, but replaces its algorithms for pruning and evaluating with some crap that results in this new engine playing like an average player with the same resources that Stockfish itself would use to play on world champion level. And even without calculating ahead at all, a human player will sometimes choose a move that agrees with the strongest engines (e.g. when the opposing queen takes your queen, the intuition tells you to retake the opposing queen). In other words: The quality of your move choices matters as much or probably more than the search depth.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.