# Tag Info

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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