66 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 ...
user avatar
  • 702
30 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 ...
user avatar
  • 596
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 &...
user avatar
  • 10.2k
25 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 ...
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 ...
user avatar
  • 377
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 ...
user avatar
  • 23.9k
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....
user avatar
  • 21.4k
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 ...
user avatar
  • 20.4k
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 ...
user avatar
13 votes
Accepted

How does timeseal work?

I'm a chess player and programmer. There was actually a paper on this 10 years ago about the timestamp and other security on ICC. You should read it with the understanding that things may be different ...
user avatar
  • 1,133
13 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 ...
user avatar
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 ...
user avatar
  • 21.4k
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? ...
user avatar
  • 21.4k
10 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 ...
user avatar
  • 4,850
10 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 ...
user avatar
  • 4,850
9 votes

What is an accurate way to evaluate chess positions?

I have a feeling I'm a little late on this answer but - I'm also in the process of making an engine. The source code is in Python (which is fairly easy to read, even if you don't know it) and is ...
user avatar
9 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 ...
user avatar
  • 5,438
9 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 ...
user avatar
  • 75.7k
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 (...
user avatar
  • 171
7 votes
Accepted

How does Allie's search algorithm work?

Allie's search is a combination of MCTS and Minimax. The MCTS is very much like you would find in AlphaZero or LC0 as it was taken from the same papers. In addition to MCTS, Allie also does a minimax ...
user avatar
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 ...
user avatar
  • 2,323
6 votes

What is an accurate way to evaluate chess positions?

Adding up to the answer by @Eve Freeman, I would suggest looking up how does the best computer engine in the world, Stockfish, evaluate a given position. As the source code is open, you can do it for ...
user avatar
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 ...
user avatar
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 ...
user avatar
5 votes

Chess Statistics How to?

I'll leave others to point you a correct database for the games because I'll focus more on the statistical part. First, you need to ask yourself what you want to analyze. If you don't know, you ...
user avatar
  • 21.4k
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 ...
user avatar
  • 1,659
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 ...
user avatar
  • 15.2k
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 ...
user avatar
  • 149
5 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 ...
user avatar
  • 2,530
4 votes

What is an accurate way to evaluate chess positions?

I think chess programmers tend not to rely on the knowledge of strong chess players when designing their evaluation functions, but instead try out different elements, and then test them in games ...
user avatar
  • 1,267

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