Computers are thought to calculate every possible move. However, for eg. there are about 20 possible first moves and 20 possible responses to that and so by this logic the no. of positions after for eg.'n' moves is 20 ^(2n). This can become a huge number very fast. So I suspect that the computer may actually be using a huge precomputed opening database which may include all possible moves and responses to a huge depth - maybe around 30 moves or so. Their programming may also include a mechanism to look up transpositions so that it can transition from an unfamiliar opening to a familiar one. If it is indeed using a huge precomputed opening database, can this not be considered as cheating? Its like a bringing a chess book to a tournament.
2
-
Interesting topic! Yet, I think you should edit your text so that it is clear what you are actually asking. Cheers.– user2001Commented Feb 7, 2014 at 13:41
-
I will bet win for the computer if you play with a book against it.– vinayanCommented Feb 7, 2014 at 14:11
Add a comment
|
3 Answers
Engines do use opening and endgame databases to help their play but that is only a small part of their strength. The strength of the engines come from what they do while they don't have a database move. The strength of engines come basically from two factors: evaluator and search.
The evaluator assigns a value to a position so that the search will know which positions to favor. Most engines nowadays evaluate on the order of 1 million positions in a second, so the evaluator needs to be fast. The evaluator may take into account for example material, pawn structure, king safety, mobility, just to name a few features. In state of the art engines, the parameters of evaluator function (i.e. how much a feature affects the total evaluation of the position) are tuned using thousands and thousands of CPU hours of testing.
As you mention, the number of possible variations grows very rapidly. The average number of moves in a position is around 35, so the number of positions already after 6 half-moves is more than one billion, which is clearly infeasible.
A simple improvement is using the alpha-beta search, which is based on the observation that, for example, if you have calculated that move 34.A wins a pawn, and you know that after move 34.B Black can reply 34...C after which White does not win a pawn, you don't have to check other responses to 34.B because clearly you already know that 34.A is better than 34.B. If you have a good heuristic such that best moves are always searched first, this reduces the number of positions required to search depth d to sqrt(35^d) instead of 35^d which is a huge improvement. Transition tables reduce the search tree even more.
But this is not even close to what top chess engines really can achieve! Using some smart and smarter tricks to decide which nodes (=positions encountered during the search) are important and which are not, they search some parts of the search tree deeper and cut some parts early, which allows them to reach depth d for important variations often in even less than 2^d nodes. A quite technical list of possible ideas for selectivity is given in the Chess programming wiki.
-
Very nice post, especially the links! Being a programmer myself find them very useful. Maybe if I get some spare time I will try to implement some of them. If only I could upvote this twice :( Best regards. Commented Feb 8, 2014 at 0:58
Why are computers so successful in chess?
First, they have opening database which means that you can not outplay them unless you invent a stunning opening novelty. High quality programs have databases that are immune to transpositions. So yes, it is like putting the opening encyclopaedia in front of you.
Second, they use endgame tablebases which means that their endgame technique is godlike, but this only works if they enter up to 6-men position. If they can not find the endgame on the board in their tablebase you have a chance to win by outplaying it.
Third, they calculate better. Why? Well look at the following simple example:
[fen "8/8/8/8/8/1P6/8/k1K5 w - - 0 1"]
This is a rough demonstration of how computer looks for the move:
He examines all the possible continuations, by "setting up" N boards-the N corresponds the number of available moves. Let us examine all lines for White here:
First candidate move:
[fen "8/8/8/8/8/1P6/8/k2K4 w - - 0 1"]
Second candidate move:
[fen "8/8/8/8/8/1P6/2K5/k7 w - - 0 1"]
Third candidate:
[fen "8/8/8/8/8/1P6/3K4/k7 w - - 0 1"]
Fourth candidate:
[fen "8/8/8/8/8/8/1P6/k1K5 w - - 0 1"]
Then, after "setting up" these positions in the memory he uses evaluation function to find the best move-in this case g7+.
After Black plays, the same process is repeated.
This method is very powerful because it allows them to find very effective zwishenzugs and they always find the winning tactics.
Quality of play depends on the quality of the evaluation function. Depth of variations also plays an important role here ( the number of moves computer can "foresee" ) but setting it high ensures again a godlike play. Although there is a theoretical chance to outperform it in calculation, in real life there is no chance to do it-not even grandmasters could have done it.
The only weak spot it has is for positional play since this part of chess is intuitive and can not be mechanized, so you would think you might have a chance there, but thanks to the progress of the opening theory you can always introduce dynamic play so there is no longer a chance to completely close the position and outmaneuver him like grandmasters did in the past.
If it is indeed using a huge precomputed opening database, can this not be considered as cheating? Its like a bringing a chess book to a tournament.
They do not cheat, they just have better "memory" and stronger processing power.
You have your brain to store opening moves, they have a hard drive.
You have your brain to visualize the board and analyze the moves, they have RAM and CPU to do that.
The problem with human brain is its failure to multitask. You just can not use your brain efficiently to remember opening moves, endgame or middle-game principles, visualize the board and calculate all the possibilities ( this is the hardest part! ) and so on.
The way I see it, they are better designed/organized for using processing and memorizing resources.
Best regards.
answered Feb 7, 2014 at 14:37
-
2I don't think the demonstration is very helpful, since it demonstrates searching depth of only one ply (which isn't a strength of engines), and leaves open the question why the evaluation function thinks g7+ is the best move.– JiKCommented Feb 7, 2014 at 14:51
-
The demonstration shows the strength engine has over a human-they can "visualize" all possible positions while many humans can not. Also, I have mentioned that engine uses evaluation function for every move, eventually evaluating
g7+as the strongest. There really is not enough space to explain exactly how evaluation function works-it is too complex. At this moment OP needs to know that computer is able to analyze all the possible positions with the help of the evaluation function. If you know the way for improving my post I will edit it and give you credit. Best regards. Commented Feb 7, 2014 at 15:07 -
well actually an engine is really a program in execution. the database is not a part of the engine but rather it is stored as a file on the hard disk. so when the engine accesses the database it is actually accessing an external resource. so my argument is that a human opponent should also have access to the same resource for a human - computer game to be considered fair. a similar argument can be made for the use of endgame tables which is also stored as a database.– guruCommented Feb 7, 2014 at 19:46
-
@AlwaysLearningNewStuff Oh, I missed the point. However, I think it would not take too much space to briefly explain what the search three is.– JiKCommented Feb 7, 2014 at 20:29
-
@guru: From your point of view, it could be treated as a cheat. However, giving a book to a human will change nothing, I fear. The main strength of the engine is its ability to "visualize" all the relevant positions and to calculate them with great speed and precision. The above diagrams just served to show the method. Imagine having to visualize every viable line in a complex tactically charged position, like in this game. How many humans can calculate all the relevant lines? We both know any computer can do it. Commented Feb 8, 2014 at 0:52
Chess engines aren't necessarily superior in strategy. In fact, the strategy is programmed in. But they can SEE MORE of the possibilities on a chess board (board vision). They can see all the forks and all the pins after this move, the next move, and so on. The human mind isn't that thorough and organized, and will miss opportunities and threats. So it isn't necessarily superior in strategic play, the chess software is superior in board vision.
