The Pattern On the Stone by W. Daniel Hillis

Author:W. Daniel Hillis [Hillis, W. Daniel]
Language: eng
Format: epub
ISBN: 9780465066872
Publisher: Basic Books

SETTLING FOR ALMOST ALWAYS

As hard as the traveling salesman problem is, it is not one of the most difficult problems to solve on a computer. Some problems are known to require even more than exponential time to solve. As discussed in the previous chapter, there are noncomputable problems that we know no algorithm can solve. Even when algorithms exist for certain problems, they are not necessarily the best approach. An algorithm, by definition, is guaranteed to get the job accomplished, but this guarantee of success often comes at too high a price. In many cases, it is more practical to use a procedure that only almost always gets the right answer. Often, “almost always” is good enough. A rule that tends to give the right answer, but is not guaranteed to, is called a heuristic. It is often more practical to use a heuristic than an algorithm: for instance, there are many effective heuristics for the traveling salesman problem—procedures that will provide an almost optimal route very quickly. In fact these heuristics usually do find the best route, although they are not absolutely guaranteed to do so. A real-life traveling salesman would presumably be happier with a good, fast heuristic than with a slow algorithm.

A simple example of the use of heuristics is the game of chess. A talented programmer who is only an average chess player can write a chess-playing program that will consistently beat the programmer. Such a program is not an algorithm, because it is not guaranteed to win. Heuristics make educated guesses; good heuristics usually make the right guess. Some of the most impressive behaviors of computers are the result of heuristics rather than of algorithms. (Philosophers have written a great deal of nonsense about “the limitations of computers” when what they are really talking about are the limitations of algorithms.)

A good chess-playing program can be written based on the following heuristics:

1.Estimate the relative strength of each player’s position by counting the number of pieces of each type remaining on the board.

2.Move so as to put yourself in the strongest possible position a few moves in the future.

3.Expect your opponent to adopt a strategy similar to your own.

Each of these rules is only an approximation of the ideal strategy, and it is possible to imagine situations in which each is actually wrong. The relative strength of a player’s position, for example, depends not just on the number of pieces but also on their position. A good position can often be more advantageous than an extra piece. Regardless, the first heuristic is generally correct; in most cases, having more pieces is better. Even before computers, chess players developed a simple method of numerically scoring the relative strengths of two players’ positions by assigning one point for a pawn, three for a bishop, five for a rook, and so on, and using the total score of each player’s remaining pieces as a measure of strength.

Based on these heuristics, you can write a chess-playing program that will trace out all plausible lines of play for the next few moves.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.