Minds and Computers : An Introduction to the Philosophy of Artificial Intelligence
Figure 12.3 Minimax. Exercise 12.3
Download 1.05 Mb. Pdf ko'rish
|
document (2)
Figure 12.3
Minimax. Exercise 12.3 Assume that black wins the toss and – using the same values for horizon nodes depicted in Figure 12.3 – employ a minimax procedure to determine the value of the initial position. 12.3 PRUNING We now have the makings of a procedure for searching for strategies for playing a game as complex as chess. We search as far ahead as is computationally tenable, apply a heuristic function to the nodes at the search horizon, then use a minimax procedure to work back to the node we are searching from. This procedure, however, still su ffers from combinatorial explo- sion. Fortunately, there are further ways to maximise the e fficiency of our computational resources by cutting down the amount of search- ing we have to do, or pruning the search tree. One such method involves using what we have already discovered in a search to determine that we can disregard certain branches. The tree fragment depicted in Figure 12.5 shows a (greatly simplified) situ- ation in which this is possible. Given that black is a minimiser, we know that the value of node b will be 3. We also know that the value of node c will be at most 2. Consequently, we already know that the value of node a will be 3 (since white is a maximiser) regardless of the value of the node marked with a question mark. Certainly this is a trivial pruning in the example case. However, it should be clear that the principle will extend to significantly more 127 Figure 12.4 Winning strategy for white. complex cases and may allow us to disregard large parts of a search tree, based on what we have antecedently discovered. Another method for pruning is to find guiding principles which tell us to simply not bother considering certain moves. It is often the case with complex games that there will be certain legal moves available from a given state that no one playing well would actually make, or that no one would be at all likely to make. If we are informed with respect to the unlikelihood of these moves obtaining, we can disre- gard the branches of the search tree descending from those nodes. A further pruning method involves playing out certain sequences of moves from memory, without engaging in any search. In fact, this is precisely how computers typically play chess openings. They have access to a large database of standard openings and variations and play the initial moves from a predetermined sequence. The more we are able to prune the search tree, the more e ffectively our computational resources will be deployed. Consequently, in order to program a machine to play a complex game well, we will need to employ the best heuristics we can devise, in conjunction with various methods for simplifying the search task. 12.4 HUMANS VERSUS COMPUTERS We have now given some consideration to an activity which is gener- ally taken as constitutive of intelligence – the ability to (at least learn to) play well a complex game such as chess. We’ve seen – at least in broad strokes – how to employ symbol systems and search methods to automate the strategic play of such games. In the case of chess, this involves a large database of opening strategies, an optimised heuristic function for evaluating game states, various principles for disregarding unlikely moves, and the deploy- ment of significant computational resources to evaluate a very large number of states per second. As I write this, the machines which are 128 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