# Tag Info

65

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 a winning strategy, or the second player has a winning strategy, or either player can force a draw. We don't (yet) know which it is for chess. (Checkers, on ...

25

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 "men" (pawns and pieces, counting the kings) have been solved using current supercomputers, so we are very far from solving chess. The complexity of ...

25

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 that it is trying to prevent is called the "Horizon effect". So before evaluating a position, if there are captures, checks and so on in the position,...

25

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 commonly that the resulting game be unique. However, this is not necessary in general, and there is even a genre of counting the number of solutions. There are ...

20

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 until you find a path of perfect play. It would be horribly inefficient, but if you have infinite processing power, it wouldn't matter.

20

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 really set traps, because it doesn't know what things might be difficult to spot for a human (or other engine) opponent. It just evaluates the position, without ...

15

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... it was unclear how exactly IBM derived the number. There's no universe definition on how an engine calculates number of moves per second. How it's done is ...

13

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 now: How to Cheat at Chess: A Security Analysis of the Internet Chess Club But in general, you are correct. It is possible to manipulate the times reported ...

13

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 algorithm is all you need). This algorithm can play any two player zero sum game perfectly. Find pseudocode here: https://en.wikipedia.org/wiki/Minimax note that ...

11

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 centipawns / 1=100 centipawns / 3=300 centipawns worse than the suggested computer move. This rule is not strictly enforced in situations where you have a clear ...

10

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 problem: Check out chessprogramming.wikispaces.com. This'll be your reference site. Create an account at talkchess.com. All the best engine developers are there....

10

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? Please note unless you invest significant amount of your time, nothing I say will work. There is no book that can possibly cover everything. You will need to ...

9

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 matches between (former) top engines are played on the same hardware. The test suggests that in the recent years (2002-2017), the gain is mainly made by ...

9

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 reason is because you can find pretty amazing positions... (2) Check out many problems relying on Dead Reckoning at Andrew Buchanan's website. Also there are ...

9

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 condition like insufficient material (K+B v K, K+N v K). It is less easy to check for cases with blocked pawns, for instance: 2b1k3/8/8/1p1p1p1p/1P1P1P1P/8/8/...

8

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 how to aim for the sharpest lines for the opponent when it is losing. This is of course subjective, and depends on the kind of opponent we are pitting it ...

7

It is just impossible for computers to look deep enough (25 ply and more) and check every possible move. What makes is possible is the technique called Alpha-beta pruning which means that computers, similar to humans (but way better) follow only the promising continuations. They evaluate the positions constantly (based on some precoded rules, valuing ...

7

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 available here if you wish to read it. The list of currently active 'heuristics' (at the time of posting): Farther developed (closer to the opposite side) pieces ...

7

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 (expand) nodes. That part can be a little confusing. This link may help.

7

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 based backup of the tree whenever a new MCTS batch is evaluated by the NN. This minimax backup is then used to modify the Q values of the nodes in the tree that ...

6

There were attempts back in the 1980s to write chess engines with knowledge bases that would pick candidate moves like humans, but they were unsuccessful. The problem is that human pattern matching is difficult to put into words, so creating the rules for the knowledge base was extremely difficult. Training a neural network to pick candidate moves seems ...

6

This is essentially the question of what is the game complexity of chess. Note that by finiteness, we know that chess is determined, but we do not know if the starting position is a win for white, a win for black, or a draw. The game complexity of chess is roughly the minimum number of positions we need to check in the game tree to determine the state of ...

6

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 laws of chess to calculate all the legal moves in that position (this is what computer engines do) so given any position (legal or otherwise), P(n), other than the ...

5

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 free. I think the file with the evaluation function you are looking for is this one.

5

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 should really ask yourself what problem you want to address. Your question simply say "I want to do something, but I don't know what to do.". There're infinite ways ...

4

You might take a look at Giraffe which was recently in the news: https://thestack.com/iot/2015/09/14/neural-network-chess-computer-abandons-brute-force-for-selective-human-approach/ The hype is that in 3 days it taught itself the game and reached IM level. On the other hand the research is at http://arxiv.org/abs/1509.01549

4

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 which give you more options and your opponent fewer options are generally favourable. One reasonable way to generate random evaluations consistently and ...

4

This is a tricky question, and I'm sure there's no definitive solution. Lichess uses this definition (https://lichess.org/qa/102/how-are-the-mid-game-and-end-game-dividers-determined) Opening is obvious, starts on move 1. Mid-game is less obvious, and is still in testing. The long-and-short of the current heuristics are that the mid-game occurs when ...

4

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 you about your algorithm. This sort of repetition happens when there is an oscillating pattern that arises in your scoring. Think of it like rock paper ...

4

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 game perfectly. The game engine does not even need to know the rules of the game it is playing. All it needs is an opaque representation of a "game state" and ...

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