70
votes
Accepted
If given infinite processing power, is there an algorithm that would play chess perfectly?
Does an algorithm exist? Yes. According to Zermelo's Theorem, there are three possibilities for a finite deterministic perfect-information two-player game such as chess: either the first player has ...
- 741
32
votes
Accepted
Given a legal chess position, is there an algorithm that generates a series of moves that lead to it?
The task you are considered is usually called a proof game, named such because the task is to prove that the position is legal. As a genre of puzzles, there are various aesthetic constraints, most ...
- 790
27
votes
If given infinite processing power, is there an algorithm that would play chess perfectly?
See https://en.wikipedia.org/wiki/Endgame_tablebase.
With infinite computer power, one could build such a table for the starting position and solve chess.
In practice, only positions with up to seven &...
- 10.6k
27
votes
Accepted
Why does a chess engine not get excited about a piece exchange at the end of its analysis depth?
Chess engines will always try to extend the search by a few moves, so a position is only evaluated if it is considered "quiet". This is called Quiescence Search, and the problem you describe ...
- 28.4k
20
votes
If given infinite processing power, is there an algorithm that would play chess perfectly?
If you really had infinite processing power, such an algorithm would be actually trivial to write. As chess has a finite number of possible states, you could in theory just iterate through them all ...
- 438
20
votes
Accepted
How do chess engines decide which best line to play when the game outcome is within their horizon?
If the engine can choose between getting mated in 2 or mated in 3, it'll choose the line where it is mated in 3 (even though the mate in 2 might be 'more difficult' to spot for humans).
It can't ...
- 25k
15
votes
Accepted
Is Deep Blue outdated?
IBM claimed the machine could search for 200 million moves per second, while Stockfish in the recent AlphaZero match could "only" search for 80 million per seconds on a modern multi-core machines. But....
- 22.6k
15
votes
Accepted
Average centipawn loss
Average centipawn loss is the difference of your move to the best computer move averaged over all moves.
Inaccuracies/Mistakes/blunders as defined per lichess are moves that are at least 0.5=50 ...
- 20.9k
13
votes
If given infinite processing power, is there an algorithm that would play chess perfectly?
To directly address the question: yes there is such an algorithm. It is called minimax. (The endgame tablebases are generated by using this algorithm (backwards!), but the plain old simple minimax ...
- 301
13
votes
Is the dead position problem solvable?
Computer detection of dead positions is much trickier than people think. It is unlikely that an algorithm exists that runs in reasonable time and is 100% accurate.
It is easy to check for a simple ...
- 5,040
12
votes
Which methods can be used to prove that a position is illegal?
Easy illegality is easy: not exactly 1 king on both sides, both kings in check, pawns on the final ranks. It's also fairly easy to tally promoted material and subtract the missing pawns. A quick ...
- 17.1k
11
votes
Accepted
When checkmate is impossible in a position
What you're asking goes by the name of "Dead Reckoning" in the domain of problems and retro problems.
(1) There isn't an algorithm I know of except the one mentioned by zaifrun: brute force. The ...
- 5,040
11
votes
Accepted
How do I learn Chess Programming?
https://www.chess.com/blog/zaifrun/creating-a-chess-engine-from-scratch-part-1
http://mediocrechess.blogspot.com (a blog that gives you some ideas how chess engine works)
How you would approach the ...
- 22.6k
10
votes
Accepted
How did the engines improve since Deep Blue?
Maybe you can take a look at TalkChess, a forum dedicated to computer chess. I found a recent thread that might be interesting for you: Progress in 30 years by four intervals of 7-8 years
A couple of ...
- 5,546
10
votes
Accepted
Lecture/Book on AlphaGo/AlphaZero
EDIT
@unutbu's link in the comment is a good introductory read.
Solid understanding for AlphaZero most likely require a quantitative degree (PhD?). Are you asking for a crash course in AlphaZero?
...
- 22.6k
10
votes
Given a legal chess position, is there an algorithm that generates a series of moves that lead to it?
If you are familiar with mathematical induction then it should be clear to you that the answer is trivially "Yes".
Just as for any position (legal or otherwise) it is possible to use the ...
- 100k
7
votes
Lecture/Book on AlphaGo/AlphaZero
I don't have enough reputation to comment, but AlphaGo Zero Explained In One Diagram is pretty good.
I also really like this tutorial.
Note that the first link doesn't describe when to create (...
- 171
7
votes
Is the dead position problem solvable?
Miguel Ambrona’s CHA solver “Chess Unwinnability Analyzer” (GitHub repo, white paper) is an efficient solution to this problem. It uses an incomplete algorithm to analyse positions and determine ...
- 171
7
votes
How do chess engines decide which best line to play when the game outcome is within their horizon?
The other answer is wrong; we can in fact program the chess engine to favour traps! As you already noted, when the engine thinks it is winning it should simply choose the best move. So the question is ...
- 2,835
6
votes
How can minimax chess engines do alpha-beta pruning without reaching the final positions?
You are confusing several concepts.
Alpha-beta pruning
Alpha-beta pruning is not "where they don't calculate positions that are obviously winning or obviously losing."
It's pruning branches where ...
- 28.4k
6
votes
Given a legal chess position, is there an algorithm that generates a series of moves that lead to it?
The natural approach to this problem is a tablebase-like approach like outlined by Brian. But doing something similar to that for just 7 pieces (namely, 7 men tablebases) with current algorithms ...
- 3,646
5
votes
Accepted
My chess AI makes the same repeated moves
Unfortunately, the only right answer to "How do I eliminate this scenario" is "fix your algorithm." Yes, you could implement the 3-fold repetition rule, but you should also figure out what it tells ...
- 1,182
5
votes
What is an accurate way to evaluate chess positions?
Surprisingly, it turns out that a Minimax engine will play reasonably well when the evaluation function is random; this is known as the Beale effect, and results from the principle that positions ...
- 1,689
5
votes
If given infinite processing power, is there an algorithm that would play chess perfectly?
Not only is there an algorithm to play perfect chess, it is possible to write a short program that will (given infinite resources) play any deterministic perfect-knowledge finite-duration two-player ...
- 51
5
votes
Average centipawn loss
I think the issue is that, when one side is winning by a large margin, the analysis will not always indicate an inaccuracy for a move which is not best but still clearly winning.
For example, after ...
- 19.9k
5
votes
Average centipawn loss
I have thought (maybe too much, lol) a lot about this.
"Average centipawn loss (cpl) is the difference of your move to the best computer move averaged over all moves." Yes.
Like all averages this ...
- 157
4
votes
Is the dead position problem solvable?
I would expect that it is a good bit easier to write a program that is good at detecting dead positions than to write a program that plays chess well.
A simple strategy may be to play out a large ...
- 872
4
votes
A different hashing algorithm for chess positions
Let me start out by elaborating on Hauke's comment:
Add friendly pieces/pawns to b5, c6, e6, f5, f3, e2. Then a Na1 is hashed the same as a Nd4. So as presented this function is not collision free.
...
- 3,646
Only top scored, non community-wiki answers of a minimum length are eligible