63

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


23

You're asking a pretty complex question, but it's good to go back to basics. There are a couple of concepts to consider: Evaluation If a (real) player is shown a position and asked "who is winning this game?", how do they go about deciding? Most likely, they will check a few basic things, such as: material differences, the degree to which pieces have ...


23

In a general way chess engines use a decision tree. The root of the tree is the current position and has a child node for each position that can be made by making a legal move. Each of these nodes in turn have a child node for the positions that can be reached by making a legal move from them. The engine pushes the tree out to a depth defined by its ...


19

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.


14

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

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


12

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


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

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


9

Here's a good starting point. Material comparison is key (and easy), then you can tune that to consider positional aspects like open ranks/files/diagonals, pawn structure, etc. https://www.chessprogramming.org/Evaluation


8

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


8

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


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

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


7

Is there a forced win for White?


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

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

I agree with the answers. I remember GM Roman Dzindzichashvili talking about it, in one of Roman's labs videos, i don't remember what video it was (if anyone knows the details please edit my answer). Roman said that the developer of Fritz engine is his friend. So Roman tested Fritz to see how good it was, and the developer told Roman that in order for ...


6

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


5

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


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


5

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


5

You can try finding the perfect Babson: compose a problem with four main lines. They consist of a defensive promotion of a black pawn to a queen, rook, bishop or knight, which forces White to promote to the same piece type in each case. Examples already exist, but they involve duals, which make them imperfect.


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

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


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

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