Minds and Computers : An Introduction to the Philosophy of Artificial Intelligence
Figure 11.3 Breadth first search. Figure 11.4
Download 1.05 Mb. Pdf ko'rish
|
document (2)
Figure 11.3
Breadth first search. Figure 11.4 Depth first search. a tree, there is a danger in using it. If any of the branches of the tree go infinite – as they often will in interesting formal systems – and we use a depth first search, we run the risk of our search never terminat- ing. If there are no solution states on a branch which goes infinite, our depth first search will continue down the branch ad infinitum. A useful strategy can be to combine depth first and breadth first search. If we know, for instance, that some branches of the tree we are interested in will go infinite and we suspect that there will be numer- ous solution states distributed across nodes a long way down the tree, we might do a depth first search only to a certain level. If we exhaust the nodes down to that level without finding a solution state (which is tantamount to having conducted a breadth first search to that level) then we continue our depth first search to a deeper level. 11.3 HEURISTIC SEARCH Breadth first and depth first are both what we call blind searches – they are conducted without any consideration of the closeness to solution of the nodes being searched. Frequently, however, it will be the case that we have some e ffective procedure for determining, of a given node, the likelihood of there being solution states among the descendants of that node. A function which applies such an algorithm to nodes and assigns a value to them accordingly is a heuristic function. Determining good heuristics is very often the most di fficult element involved in solving complex problems in the symbolic artificial intel- ligence tradition. Consider, for instance, an exemplar classical artificial intelligence project: determining an algorithm for playing chess well. One heuris- tic for playing chess would be to simply construct the generation tree for chess, then for any given game state – represented by a node of the tree – assign a value in accordance with the number of descendant nodes which represent winning states. Playing the game is then just a matter of always moving to the position whose node has the best value of those available. Given a rule establishing an upper limit on the number of allow- able moves in a game (such as the fifty move rule), we can keep the tree finite, so this procedure seems feasible until we begin to quantify the sheer complexity of chess. The generation tree for chess su ffers from drastic combinatorial explosion. There are four hundred nodes at the second level alone. By the time we get to the tenth iteration – by which time each player has 117 made only five moves – there are around nine billion nodes. At the twentieth iteration there are something in the order of 10 30 nodes and that is a very big number. Even if we could generate one hundred trillion states per second, it would still take around ten billion years to produce the generation tree for only the first ten turns of chess. Clearly then, the naive heuristic we described is computationally untenable. Similarly, blind search techniques – while they have their uses – are often computationally untenable for formal systems of su fficient complexity to be of interest to artificial intelligence researchers. Investigating the generation trees of exponentially complex formal systems is only possible with the aid of clever heuris- tics which significantly reduce the computational load. Determining heuristic functions to guide chess play su fficiently well so as to challenge the best human players turns out to be extra- ordinarily di fficult and computing these functions demands substan- tial computational resources. We will discuss this further in the following chapter when we contrast automated methods of game play with human methods. Given a heuristic function, we still need to decide how to be guided by heuristic values in conducting a search. One such heuristic search procedure is hill climbing. A hill climbing search involves evaluating, at each node, the heuris- tic value of its immediate descendant nodes and then moving to the node with the best heuristic value. If we reach a terminal node without finding a solution state, we backtrack to the next best possibility. The letters in Figure 11.5 represent the order in which we would search the depicted generation tree if our heuristic assigned values to nodes as shown, where 0 represents a solution state. Download 1.05 Mb. Do'stlaringiz bilan baham: |
Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling
ma'muriyatiga murojaat qiling