What makes chess engines so good at chess?

What makes chess engines so good at chess?

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.

Solutions/Answers:

Answer 1:

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.

Answer 2:

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.

Answer 3:

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.

References

OSX implementation of WinBoard / XBoard?

OSX implementation of WinBoard / XBoard?

Is there a Mac OSX implementation (or equivalent) of WinBoard / XBoard?

Solutions/Answers:

Answer 1:

You can technically still use XBoard, but you will need to install X11 from MacPorts, since IIRC Apple no longer ships it.

Julien Marcel has a collection of well-compiled OS X chess engines (which do not require emulation).

As for not having a ChessBase client, HIARCS Chess Explorer does fine.

(FWIW, there is a port of XBoard to Cocoa – currently named OSXBoard – but it seems to have stalled.)

Matthew:out

Answer 2:

Jin seems like a good option.

Works well on OSX 10.8, and compatible with other platforms as well.

Answer 3:

Jin is the best, also on older macs there was another client “Fixation”. I would recommend using a virtualization application such as VMWare Fusion or VirtualBox with a Windows guest to run your preferred Windows chess software – as macs also suffer from not having a satisfactory ChessBase client to review games. Performance is not an issue as chess apps do not need be too powerful for these things.

Answer 4:

There is now a native quartz xboard.app through GTK2.
http://www.open-aurec.com/wbforum/viewtopic.php?f=19&t=52964

Answer 5:

xboard can be installed via macports

sudo port install xboard

if you run into trouble with your fonts see XBoard page on wiki.bitplan.com

References