It seems to me that one of the most critical steps in writing a chess engive program is how you define good vs bad - good vs bad in chess terms to a computer that only knows binary code and program languages.
Is that the big step?
How does a chess engine work?
Sort:
Oldest
Dec 23, 2014
0
#4
I am not a programmer, but I have written programs before. Let me say a few things and then the computer smart people can correct the 95% that I get wrong. 
To write a program to show a chess board with pieces and teach the program all the legal moves is not too complicated. That is 1970's technology.
An engine works by evaluating all the possible legal moves and then deciding which ones are best based on which ones lead to a better result. The computer does a tree, the possible moves and all the possible moves from the resulting positions and the possible moves from those positions. As you can see the possibilities can reach into the millions after only a few movces. The trick is to teach the computer what position is good and what position is bad. That requires...........
Ok, my part ends there.
Dec 23, 2014
0
#5
I can add a few more things to what I said earlier.
As in all programs there are limits. When a program is looking at positions two things govern that process - how long will it study and how fast can it process.
The first part, how long it will study a position is strictly written into the program. The second part, how fast it processes the analysis, is governed by the actual computer - the processing speed and, probably, the amount of random access memory, RAM.
Assuming the engine doesn't find a mate or tablebase position, here are some of the things used in evaluation: material, king safety, piece-square tables (e.g. a knight is better in the center than the corner), pawn structure, mobility, center control, and trapped pieces.
Another important function relating to the engine's strength is search: ideally avoid searching useless branches while still searching useful branches. The main algorithm used is alpha-beta, where the engine stops evaluating a branch if it is evaluated as below alpha or above beta (either player makes too bad of a move). There are various other methods to reduce or extend various branches.
There are two key parts to how a chess engine works. Search, and Evaluation. Evaluation is teaching it how to evaluate how good or bad a position is. Search is telling the engine WHICH moves to consider. Considering every move is often too processor intensive. For example, a3 as whites first move should not be considered by most engines. In most positions only certain moves should be accounted for. How you determine these moves is the hard part, along with evaluating.
One aspect of the program is a "static evaluation" method that can look at a position and check how good it is for White (the score for Black is (0 - the number for White), so if it is good for White it is bad for Black. This is the same pattern for scores generated in other ways! 0.0 is a draw, for example a bare king vs. a bare king in any legal position.) A static evaluation method can consider various factors like: Material count; Pawns that are on an advanced rank; How much space is available for pieces to move on one side or another; King safety (a good variety of squares near the king free too move to, protection by pawns etc ... I don't know how this part is really done.)
Another important measurement of a position is "quiescence". A position is quiet if it doesn't have a lot of captures or checks etc.
The static evaluation is defined so it can be computed without doing any lookahead. If the position is quiet, then the search can stop in the quiet position. If the position is not quiet, then additional lookahead should be done by the process to determine the true value of the position.
A basic process used to look through the game tree is a "minimax" procedure. White wants to make the move that maximizes the minimum value that Black can attain (and Black minimizes the maximum value that White can attain ....) . If White can choose between moves A and B, and Black has two answers to move B which are C and D, and C is better for Black, then neither side will to worry about what would happen with move D because he isn't going to choose that one (unless Black is human).
Also there is something called alpha-beta pruning. These things can be found in Wikipedia I bet.
I said that all because I didn't know TBently said it because I foolishly assumed the newer posts were at the top, not at the bottom of the page. (It would be easier if I would hold the computer upside-down)
I read a funny-sounding statement in a featured article just now. It said one GM won a game because his moves were better than the other GM's, even though he was behind. But there isn't any solid basis for saying move A in position 1 is better than move B in position 2 unless you use some measure like "number of pawns according to computer evaluation", but that's an estimate, a heuristic. Or if the writer were omniscient and could determine the exact perfect outcome of the game in each of those positions(0=drawn n>0 for forced mate in n by white, or n less than zero for mate in n by black. Also the number of different ways to achieve a win for either side could be estimated. Also, 'better' doesn't win in general, if behind - moves would have to be "better enough". So it was an imprecise statement, for interesting reasons. While writing that I also noticed that the computer estimate of goodness in static evaluation can sometimes be mistaken, and the search process can sometimes stop at the wrong place, because the computer isn't omniscient about the future of the game.
I ran a recent endgame through Stockfish and in the final position both the kings have to sit in front of connected passers forever. If anyone moves away they will lose. It's as drawn as drawn can be; but Stockfish gives an 0.2 advantage to one side.
What this drove home to me is that the engine isn't playing for the same goals a human player is. The human understands that the goal is to give mate, and if you can never do that, evaluation =0. The engine understands that the goal is to maximize its evaluation score, and if it has, say, a useless extra pawn it is happy to claim an advantage.
When GMs manage to draw Stockfish I think they're often exploiting this: Stockfish will get a position which makes it happy (positive evaluation) but where it has no plan for doing anything with that advantage, and will sit around forever.
Aug 3, 2015
0
#16
I think I am safe in saying that a chess engine is much better at openings and middlegame than endgame.
Engines that use an endgame tablebase (whatever that is) do pretty good, but most engines don't do that.
Tablebases are pretty easy to explain:
For a given set of pieces (let's say, KQB v KRR) you first enumerate all the positions that are checkmate for one side or the other. Then, you find all the positions that are exactly one move away from one of those: those are positions with evaluations of "one move from mate." Next, all the positions one move away from *those*: positions with evaluations of "two moves from mate." Continue until you have used up all possible positions with KQB vs. KRR. Many of them will be marked as "n moves from mate" with various values of n. (A big shocker of the tablebases was that n can be HUGE. Mate in 500, anyone?) The remainder are all draws as there is no way to reach mate from them with perfect play.
(I suppressed one detail here: you also have to handle positions where the number of pieces is reduced by a capture. You'd actually start by assessing positions with K+K+one piece first and work your way up. Then after each capture you've just reduced to a smaller tablebase which you already know.)
Right now tablebases are available up through 7 units. The number of possible positions with 8 units is too large for current technology. Tablebases for 6 units ("Nalimov") are freely available; 7 units ("Lomonosov") seems to require payment.
Tablebases are freaky. Regular chess engines do calculations that a human could, in principle, try to do, and use evaluation functions that are more or less the same ones we use (king safety, pawn structure, material balance, etc.) Tablebases have no evaluation and no strategy: all they know is the shortest path to mate. It turns out this often involves profoundly meaningless looking moves, especially for the longer mates.
To appreciate this, you can try playing through the position at:
http://tb7.chessok.com/probe/3/61
which is mate in 549 with best play--where "best play" is the ravings of a complete lunatic.
Tablebases give a 100% guaranteed answer to "is this a win or a draw with best play?" except that you have to consider the 50-move rule, which the tablebase itself does not. There is a very clever article by Dana Mackenzie on how a human might learn something from a tablebase:
We have some smart people here. We have chess players here. We even have programmers here.
How about if somebody explains to the rest of us how a chess eninge works?