67 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 ...
Mark's user avatar
  • 711
31 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 ...
A. Rex's user avatar
  • 780
26 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 &...
itub's user avatar
  • 10.5k
26 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 ...
RemcoGerlich's user avatar
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 ...
vsz's user avatar
  • 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 ...
Glorfindel's user avatar
  • 24.8k
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....
SmallChess's user avatar
  • 22.5k
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 ...
user1583209's user avatar
  • 20.7k
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 ...
chessprogrammer's user avatar
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 ...
Remellion's user avatar
  • 5,030
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 ...
Hauke Reddmann's user avatar
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 ...
Remellion's user avatar
  • 5,030
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 ...
SmallChess's user avatar
  • 22.5k
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 ...
Maxwell86's user avatar
  • 5,536
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? ...
SmallChess's user avatar
  • 22.5k
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 ...
Brian Towers's user avatar
  • 97.2k
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 (...
monk's user avatar
  • 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 ...
zamfofex's user avatar
  • 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 ...
user21820's user avatar
  • 2,809
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 ...
RemcoGerlich's user avatar
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 ...
koedem's user avatar
  • 3,441
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 ...
Cort Ammon's user avatar
  • 1,152
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 ...
Chromatix's user avatar
  • 1,679
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 ...
gareth's user avatar
  • 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 ...
D M's user avatar
  • 19.3k
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 ...
user17740's user avatar
  • 147
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 ...
Polytropos's user avatar
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. ...
koedem's user avatar
  • 3,441

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