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 ...


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 ...


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 ...


18

The maximum number of moves in a chess game is not infinite, it's 11797 plies = 5898 moves and a half. This is due to the fifty-move rule. So no, the number of possible chess games is not infinite. The maximum number of legal moves in a position is 218. So a crude upper bound for the number of possible chess games is 218^11797 = 10^27586 Wait, actually ...


16

As far as I can see there is no fundamental difference between chess and xiangqi that would make xiangqi more difficult for a computer. The state space complexity of chess is somewhat higher, whereas the game tree complexity of xiangqi is higher. Also the branching factor of xiangqi is 38 compared to 35 for chess, not much of a difference. I suspect that ...


14

Whilst acknowledging the comment by @SmallChess that this is pointless, it is also relatively straightforward to do. I analysed 2,539,871 games from a ChessBase mega database counting the number of moves for the next player to move before each move was played. I did not include the number of moves available after the final move of the game had been played. ...


9

This answer is extended from my comment to Ross Milikan's answer to your question Numerical FEN writing. There is a website devoted to counting the number of legal positions up to equivalence with given number of pieces. Currently they have results for positions with 2 to 8 pieces. 2: 462 3: 368,079 4: 125,...


7

What you are looking for is called the branching factor, and I've always seen the number 35 mentioned, but I don't know what the original source is. I guess someone estimated it some 50 years ago by counting the number of moves in a number of random positions from games, and then it became "common knowledge". The number 35 is reasonable enough in practice, ...


7

The moment we knew that a variation would be winning for either White or Black, the other side would never go for that variation. E.g. after 1. g4 e5, White will never play 2. f3 because we know that variation is winning for Black. But there are some openings which have been analyzed to a draw by repetition of moves, even before the computer era, e.g. the ...


7

Many such positions were found thanks to endgame databases. Below is the record holder, which is 549 moves long. [FEN "1n1k4/6Q1/5KP1/8/7b/1r6/8/8 w - - 0 1"] However, probably more remarkable is this 19th century (!!) composition by Otto Blathy (he authored several other similar monstrous problems). White to move and mate in 292 moves. q5nn/1p2p3/...


7

Upper bounds on the number of allowable positions are discussed on the Shannon number Wikipedia page. There is an accepted upper bound of 5×10^52 by Vicor Allis, and a less verified upper bound of 2^155 (approx 10^46.7) by John Tromp. By comparison, the number of atoms on earth is about 10^50.


6

Q1: Yes. The total number of chess games can be considered infinite for all practical purposes. We don't have the technology to brute force over the first 13 moves from the initial position. Q2: The actual numbers all the way up to depth 13 is known. The exact number of possible positions for the 10th moves is 69,352,859,712,417. Read this Wikipedia article ...


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 ...


5

An interesting question with which I've done significant exploration. My program Symbolic can generate random games using the /dev/urandom pseudorandom generator to any length. For a recent run of ten million random game, the average length was 342.064 ply. [] rg 10000000 Checkmate 1527544 0.152754 FiftyMoves 2241451 0.224145 Insufficient 5358614 ...


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 ...


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: Generate a tree of all possible moves as far out as resources allow. For each final position ...


4

I reran the script from the answer GloriaVictis linked. For a twenty-five thousand games the average length was 357 ply.


4

The variability in number of legal moves is about the same for black & white... except for that odd little bump for white on move 7. This phenomenon demands further research!


4

Thanks to GloriaVictis's indications I have been able to find the answer to my question. In 1976 Walther Jorgersen, a Danish composer, published a mate in 200 in the magazine "Schwalbe". However, André Chéron extended the problem to 203 moves that same year by adding a small change. But unlike Blathy's mate (see GloriaVictis answer), this one is completely ...


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, ...


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....


3

Actually it is not really correct to say that "simply increasing the board size [...] comes at the cost of losing playability". The complexity of Go on a board of the same size as chess (i.e. 8×8) would be not high at all, in fact less than chess according to my intuition. But it is true that there is some reason why we humans have a vague feeling that ...


3

My move by move analysis see below. Comments appear below the board as you play through the game. Generally a blunder rich game. White seems to like pushing pawns a bit too much, while black played too passively in the beginning. Black should have attacked the strong white center right from the start with b6. Both players neglected the development of their ...


3

There are algorithms/chess engines that can heuristically evaluate a position and provide a score which can be proxied for who is winning. Completely analyzing an opening would require an engine to follow all paths or at least all reasonable paths (heuristically determined). This is computationally very time-intensive and we are very far from compute power ...


3

What follows is basically a partial answer that is heavy on explanation, plus a pointer for using it to obtain a fuller answer if so desired. Suppose we start with a blank 64-square chessboard and ask how many different positions we can make by placing down just 2 white knights. A quick answer is that it is 64*63 = 4032 positions, because we can place the ...


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 ...


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 ...


2

At some point you'll run out of combinations. So the answer is basically no.


2

Xiangqi has more theoretical complexity mainly due to larger board. So if you need to do exhaustive search, it has larger search space. Xiangqi is also more positional. For attacking each side has two rooks, 4 knight-strength pieces, and 5 pawns. So for a crude comparison with western chess, Q+3P are replaced with 4 purely defensive pieces. We know ...


2

Xiangqi is less "connected" than western chess. For instance, the five pawns cover only every other file; they're not side by side. There is no "queen" that unifies both lateral and diagonal movement. And the defensive pieces are either limited to the palace (advisors) or to patrolling the surround countryside (elephants); they cannot be used to help attack ...


Only top voted, non community-wiki answers of a minimum length are eligible